Patent ID: 8085931
Filing Date: 2011-12-27
Classification: G06F

Abstract:
1. 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) executing a Montgomery multiplication remainder operation REDC (REG, g) 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.