Patent ID: 8407270

Claim:
A method of calculating a negative inverse of a modulus M 0 , the method comprising: setting a modulus M 0 ; defining P obtained by converting the modulus M 0 to a negative number, and defining S obtained by subtracting 1 from P; and calculating a negative inverse V 0 of the modulus M 0 by using P and S, wherein the calculating of the negative inverse comprises: dividing S by 2; assigning a value of a least significant bit (LSB) of S divided by 2 as a value of the LSB that is not determined among the bits forming the negative inverse V 0 of the modulus M 0 ; and replacing S by a value obtained by adding a value obtained by dividing S by 2 to a value obtained by multiplying P by the value of the LSB of the divided S, wherein the setting, defining, and calculating steps are performed by at least one processor.