High-performance booth-encoded montgomery module

A high-performance Booth-encoded Montgomery module for performing the computation of A*B*r−1 (mod N), where A, B and N are the (n-bit) multiplicator, (n-bit) multiplicand, and (n-bit) modular number, respectively, and r=2n, the module comprising:

• a Booth encoder for receiving two bits of A to perform a Booth encoding process, so as to produce a Booth code for output;
• a multiplicand selector for receiving B and the Booth code output from the Booth encoder so as to select a multiplicand based on the Booth code for output;
• a first carry propagate adder for adding the output of the multiplicand selector and a previous computation result to output;
• a multiplexer for receiving four inputs 0, N, 2N, and 3N from a lookup table and selecting one of the inputs to output;
• a second carry propagate adder for adding the outputs of the first carry propagate adder and the multiplexer to output;
• and
• a shifter for shifting the output from the second carry propagate adder to right by two bits, so as to produce a computation result.