| 摘要 |
A method and apparatus for calculating the product P of a first number X and a second number Y, modulo N, where Y is partitioned into j words each of length p bits, and has a length (m+n) bits, cyclically operates on successive ones of the j words of Y, carrying out intermediate modulo reductions of the intermediate products formed. A specially selected multiple, N', of N is used so that only a single reduction of the intermediate based on N' guarantees that the intermediate product P is never longer than (m+n) bits at the end of each cycle. N' is an integer multiple of N, and the value N' is selected such that the (m-1) most significant bits are equal to '1', and the least significant bit is '0'.
|
