Arithmetic device

摘要

According to one embodiment, a first shift amount calculation unit counts the number of continuous zeros from a less significant bit toward a more significant bit of an intermediate result of a computation of Montgomery multiplication result z and calculates a first shift amount. A second shift amount calculation unit counts the number of continuous zeros from a less significant bit toward a more significant bit of redundant-binary-represented integer x and calculates a second shift amount. An addition/subtraction unit calculates the intermediate result by adding/subtracting, with respect to the 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. An output unit outputs, as the Montgomery multiplication result z, the intermediate result when the sum of the first shift amounts is equal to the number of bits of the integer p.

主权项

1. 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.