Patent ID: 7801937
Filing Date: 2010-09-21
Classification: G06F

Abstract:
1. A Montgomery multiplier circuitry implemented on a semiconductor substrate to compute A*B mod M, the Montgomery multiplier including a partial sum calculator to compute partial sum values to generate a Montgomery result for n bit numbers after n/2+1 iterations of intermediate result computations wherein A, B, and M are n-bit numbers, the partial sum calculator comprises: a first partial quotient generator to generate partial quotient values; a second partial quotient generator to generate subsequent partial quotient values; and a partial sum generator to generate the Montgomery result after n/2+1 iterations of intermediate result by performing radix 2 multiplication computations from the first and second partial quotient generators, the partial sum generator including a first AND gate that performs an AND function on a subsequent partial quotient value generated by the second partial quotient generator and M, a second A gate that performs an AND function on a partial quotient value generated by the first partial quotient generator and M/2, a third AND gate that performs an AND function on 2 LSB bits from B and A, and a fourth AND gate that performs an AND function on a LSB bit from B and A/2.