| 摘要 |
PROBLEM TO BE SOLVED: To provide a remainder operation method for speeding up modular multiplication in a BMM (Bipartite Modular Multiplication) method. SOLUTION: In a PBMM (Pipelined Bipartite Modular Multiplication) method, modulus M which is an r-ary and n-digit integer, r-ary and n-digit multiplicand X, and multiplier Y are input in X*Y=X×Y×r<SP>-m</SP>mod M. In the step 1, each variable is initialized. Then, in the step 2-1, preprocessing is carried out so that a task T<SB>1b</SB>and a task T<SB>2b</SB>can be executed in parallel. In the step 2-2, the cycle k is increased one by one from 1 to n/2, and in each cycle k, the talk T<SB>1b</SB>and the task T<SB>2b</SB>are executed in parallel. In the step 2-3, when k=n/2, the remainder of the result of addition of C<SB>n/2</SB>and D<SB>n/2</SB>is taken in by the modulus M, and the result is set as D<SB>n/2+1</SB>. In the following step 3, the D<SB>n/2+1</SB>is output as Z, and the process ends. COPYRIGHT: (C)2007,JPO&INPIT
|
