Patent ID: 7792893

Claim:
A non-transitory recording media having a computer program encoded therein that when executed causes a computer to execute a method for computing a conversion parameter R 2 (mod n) of Montgomery modular multiplication wherein the effective word length of the residue modulo n is taken as m, the bit length per 1 word is taken as k, and 2 m×k =R, the executed method for computing a conversion parameter of Montgomery modular multiplication comprising: a first operation for calculating H 0 =2 v ×R (mod n), wherein v is an integer, v≧1, and (m×k)/v is an integer, comprising: an operation for initializing two registers REG 1 , REG 2 by REG 1 =n, REG 2 =2 (m−1)×k wherein REG 1 is a register composed of m words and REG 2 is a register composed of m or more words, and an operation for obtaining 2 v ×R (mod n) by repeating k+v times a modular squaring computation employing the value of REG 1 as a residue modulo with respect to REG 2 ; a second operation for calculating H p =2 v×2^p ×R (mod n) from H 0 =2 v ×R (mod n) by repeating H i =REDC(H i−1 , H i−1 ) n with respect to i=1, 2 . . . p, wherein (p represents an integer satisfying the condition 2 p ≧(m×k)/v>2 p−1 , REDC represents the Montgomery modular multiplication REDC(a, b) n =a×b×R −1 (mod n), and x^i represents exponential computation x i ; and a third operation for calculating H p =R 2 (mod n) by calculating H p =REDC(H p , g) n with respect to H p obtained in the second operation when 2 p >(m×k)/v and finally outputting H p as R 2 (mod n), wherein g=2 k×E(p,m,k) and E(p, m, k)=2×m−(v×2 p )/k.