| 摘要 |
<p>The invention relates to a calculation A * B mod N in a RAM-restricted environment wherein A, B and N are L byte numbers. The following elements are required: a) a RAM buffer W of at leat 8*L+9 bits; b) computation means for reducing modulo N the 8*L+9 bit numbers stored in said buffer W; c) one byte shift-to-the-left means for buffer W wherein after the shift W(0) is reset to 0; d) backward multiplication means wherein a byte A(i) of A is multiplied by the whole number B and the result is added to the contents of W, wherein said index i is decremented from L-1 to 0 (both values included) between successive calls of this means; e) control means for sequencing the usage of said computation means, shift-to-the-left means and backward multiplication means. The following operations are executed by the control means: 1) reset buffer W to 0; 2) initialize an index i with the value L; 3) decrement i; 4) if i is negative, terminate the calculation; 5) perform a backwards multiplication as described in (d); 6) perform a small reduction operation as described in (b); 7) if index i is nonzero shift buffer W one position to the left; 8) go to step 3.</p> |
