Modular multiplication method and calculating device

摘要

To provide a modular multiplication method and a calculating device that do not rely on the Montgomery technique, wherein the number of times of multiply-add calculations is reduced to shorten a calculation time for calculation speed-up, there is no limitation in input value, and it is possible to execute a remainder calculation exceeding the calculable maximum bit length of a multiply-add unit that is used. Assuming that N=2ⁿ-M and X=alphax2ⁿ+beta, a relation of XmodN=(alphaxM+beta)modN is derived, which is utilized. n represents a maximum bit number where "1" is assigned in N, a solution of 2ⁿ⁺¹modN is set as b, AxB is set as X, XmodN is transferred to (X/2ⁿ⁺¹xb+Xmod2ⁿ⁺¹)modN and further transferred to (X.n/2ⁿ⁺¹xb+X.nmod2ⁿ⁺¹)modN, calculations of X.n/2ⁿ⁺¹xb+X.nmod2ⁿ⁺¹ are repeated until a bit length of X.n becomes n+1, X.n-N is derived and a derived result is set as a solution of "AxBmodN".