Patent ID: 8417756

Claim:
A method of calculating a Montgomery representation, comprising: preparing, by processing circuitry, a table of a plurality of sets, each of the plurality of sets including a value of 2 K+i (mod n), a value of 2 K+i+1 (mod n) and a value of (2 K+i +2 K+i+1 )(mod n) corresponding to a value of two neighboring bits Y i+1,i of a binary Y, where i=0 to M−2, n is a modulo number, K is an integer, and M is a number of significant bits in the binary Y; selecting, by a multiplexer, one of the values within each of the plurality of sets of the table in dependence upon the value of the two neighboring bits Y i+1,i of the binary Y; respectively adding, by a first plurality of adders, each pair of two neighboring selected values and respectively calculating, by a first plurality of modulo calculators, the modulo value of the sum of the each pair of two neighboring selected values with the modulo number n; repeatedly adding, by a second plurality of adders, each pair of two neighboring calculated modulo values output from a previous calculation stage until only a single sum is obtained, and repeatedly calculating, by a second plurality of modulo value calculators, 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 calculated modulo value as the Montgomery representation.