| 摘要 |
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<n>-M and X=alphax2<n>+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<n+1>modN is set as b, AxB is set as X, XmodN is transferred to (X/2<n+1>xb+Xmod2<n+1>)modN and further transferred to (X.n/2<n+1>xb+X.nmod2<n+1>)modN, calculations of X.n/2<n+1>xb+X.nmod2<n+1 >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".
|
