Method and apparatus for implementing a look-ahead for low radix Montgomery multiplication

摘要

A method for performing Montgomery multiplication on n bit numbers includes computing look-ahead partial sum values to generate a Montgomery result after n/2+1 iterations of intermediate result computations. According to one embodiment of the present invention, Montgomery multiplication is performed to compute A*B mod M where A, B, and M are n-bit numbers.