Method and apparatus for efficient modulo multiplication

摘要

A method of a hardware based Montgomery reduction contemplates preparing a table comprising a plurality of sets of values of 2^K+i (mod n), 2^K+i+1 (mod n) and (2^K+i+2^K+i+1)(mod n), where i=to M−2, n is a modulo number, K is an integer, and M is a number of significant bits in a binary Y; selecting one of the values within one of the plurality of sets of the table in dependence upon a value of two neighboring bits Y_i+1,i of the binary Y; adding two neighboring selected values and calculating the modulo value of the sum value with the modulo number n; repeatedly adding two neighboring calculated modulo values and calculating the modulo value of the intermediate sum of the two neighboring calculated modulo values until only a single calculated module value is obtained; and setting the single value as the Montgomery representation.