| 摘要 |
PROBLEM TO BE SOLVED: To provide a method for computing an inverse element: m'=-m<SP>-1</SP>modb which is necessary in the Montgomery multiplication algorithm at high speed using a general-purpose computing unit, and a method for carrying out parallel computing of one xyR<SP>-1</SP>mod m operation and the succeeding xyR<SP>-1</SP>mod m operation when carrying out pipeline execution of the power remainder operation using the Montgomery multiplication algorithm. SOLUTION: When m=k-1, m(m+2)=k<SP>2</SP>-1 and further, m(m+2)äm(m+2)+2}=k<SP>4</SP>-1. By repeating the same operation, it can finally be set as m(m+2)äm(m+2)+2}...=k<SP>2^n</SP>-1. The inverse element is obtained by applying this principle. Also, the Montgomery multiplication algorithm is improved by applying the principle of non-restoring method that is general in division, and the result of mathematical operation is decided definitely without being based on the result in the middle of operation. COPYRIGHT: (C)2004,JPO&NCIPI
|
