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.