Patent ID: 8352529

Claim:
A Montgomery method-use modular multiplication calculation apparatus for calculating a result Y by performing both a multiplication of certain values A and B and a residue calculation with a modulo N, the Montgomery method-use modular multiplication calculation apparatus comprising: a first product-sum calculation unit configured to multiply the value of certain one digit of the value A and the value of certain one digit of the value B by using three values as inputs, which are the value of the certain one digit of the value A, the value of the certain one digit of the value B and a first carry value, and configured to output a first result from adding the multiplication result to the first carry value by dividing the first result into two values, which are a higher-order digit as new first carry values of the first product-sum calculation unit and a lower digit unit; a second product-sum calculation unit configured to multiply the value of certain one digit of the modulo N and a certain one digit value m by using three values as inputs, which are the value of the certain one digit of the modulo N, the certain one digit value m and a second carry value, and configured to output a second result from adding the multiplication result to the second carry value by dividing the second result into two values, which are a higher-order digit as new second carry values of the second product-sum calculation unit and a lower digit; and an addition unit configured to add the lower digit of the output of the first product-sum calculation unit, the lower digit of the output of the second product-sum calculation unit and a third carry value, configured to output the addition result by dividing it the addition result into two values, which are a higher-order digit as a new third carry value of the addition unit and a lower digit, and configured to store the lower digit in certain one digit of a variable Y.