Patent ID: 8909689

Claim:
An arithmetic device that computes a Montgomery multiplication result z of the product of integers x and y modulo an integer p by a repeated arithmetic multiplication providing a plurality of intermediate results, said device comprising: a conversion unit that converts the integer x to a redundant binary representation; a first shift amount calculation unit that counts a first counted number that is the number of continuous zeros from a less significant bit toward a more significant bit of a first intermediate result of the plurality of intermediate results and calculates a first shift amount based on the first counted number; a second shift amount calculation unit that counts a second counted number that is the number of continuous zeroes from a less significant bit toward a more significant bit of the integer x of the redundant binary representation and calculates a second shift amount based on the second counted number; an addition/subtraction unit that calculates a second intermediate result of the plurality of intermediate results by adding/subtracting, with respect to the first intermediate result which has been bit-shifted by the first shift amount, the integer p, and the integer y which has been bit-shifted by the second shift amount, and sends the second intermediate result to the first shift amount calculation unit; and an output unit that outputs, as the Montgomery multiplication result z, a final intermediate result when the sum of the first shift amounts is equal to the number of bits of the integer p.