摘要 |
A method for calculating a conversion parameter of the Montgomery modular multiplication to improve the efficiency of software installation, comprising a first step for calculating H 0 = 2 v × R (mod n) (where v is an integer, v ‰¥ 1, and (m × k)/v is an integer), a second step for calculating Hp = 2 v×2^p × R (mod n) from H 0 = 2 v À i = REDC(H i-1 , H i-1 ) n with respect to i = 1, 2, ..., p (where 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 step for calculating Hp = R 2 (mod n) by calculating Hp = REDC(H p , g) n with respect to Hp obtained in the second step when 2 P > (m × k)/v (where g = 2 k×E(p,m,k) , E(p, m, k) = 2 × m - (v × 2 P )/k) and finally outputting Hp as R 2 (mod n). |