Patent ID: 8085931

Claim:
A computation method for computing a value relating to a Montgomery conversion parameter, which is used in a Montgomery multiplication remainder operation and is a remainder value relating to a divisor n of a remainder, using a register, which has at least m words that have a bit length k per 1 word and an operation unit for executing a Montgomery multiplication remainder operation REDC (A, B) n , which is defined as 2 −m*k ×A×B (mod n), for values A and B and a divisor n of a remainder having a significant word length m, comprising storing a negative number of a divisor n of a remainder in the register; carrying out a shift process of performing one-bit shift of a value stored in the register in a carry direction; judging whether a most significant bit which overflows the register becomes 0 or 1; repeating the shift process until it is judged that the most significant bit becomes 0; repeating a process of executing a Montgomery multiplication remainder operation REDC (REG, REG) n for a value REG, which is stored in the register on which the shift process has been repeated until said judging finds the most significant bit becomes 0, by the operation unit and storing a result thereof in the register, p times which p is an integer that satisfies 2 p-1 <m×k≦2 p ; executing a Montgomery multiplication remainder operation REDC (REG, g) n for a value REG stored in the register by the operation unit and storing a result thereof in the register when 2 p >m×k (here, g=2 k*G(p,m,k) and G(p, m, k)=2×m−2 p /k); and outputting a value stored in the register as an equivalence which gives the same remainder value relating to a divisor n as a Montgomery conversion parameter.