Patent ID: 7603558

Claim:
A Montgomery transform device for obtaining a Montgomery transform result m′ (=mR mod p) of n-bit from an input m of 2n-bit on the basis of a multiplier R not less than n-bit and a modulus p of n-bit; comprising: a Montgomery reduction device configured to execute Montgomery reduction composed of multiplication, addition and a bit shift to the input m of 2n-bit on the basis of the modulus p and the multiplier R and obtain a Montgomery reduction result (mR −1 mod p) of n-bit; and a Montgomery multiplication device configured to execute Montgomery multiplication of the Montgomery reduction result (mR −1 mod p) by the cube of the multiplier R (R 3 mod p) on the basis of the multiplier R and the modulus p and output the obtained Montgomery multiplication result (mR mod p) of n-bit as the Montgomery transform result m′ (=mR mod p).