Patent ID: 8024391

Claim:
A computer hardware-implemented modular multiplication method, comprising: loading a first numerical operand W into data storage accessible to a processor unit, wherein W is a first operand to be multiplied by a second operand; pre-computing, using the processor unit, and storing a numerical value P, where P=└(W·X n+δ )/M┘ for the operand W and a modulus M, where X is selected to represent either a numerical constant or a polynomial variable, n is an integer representing a size of the larger of W and M, and where δ is a selected constant greater than 1; loading a second numerical operand V into the data storage, wherein V is the second operand to be multiplied by W, where V<2 n+φ , and the constant δ is chosen so that δ≧φ; computing, using the processor unit, an estimated quotient q^ for the product (V·W) to be reduced modulo M, wherein the estimated quotient q^=└(V·P)/X n+δ ┘, where q^ is equal or lower by one to the actual quotient; and calculating, using the processor unit, a remainder r′=(V·W)−(q′·M), where q′ is a quotient value derived from the estimated quotient q^, said remainder r′ being congruent to (V·W) mod M.