Modular multiplication method with precomputation using one known operand

Abstract

A modular multiplication method implemented in an electronic digital processing system takes advantage of the case where one of the operands W is known in advance or used multiple times with different second operands V to speed calculation. The operands V and W and the modulus M may be integers or polynomials over a variable X. A possible choice for the type of polynomials can be polynomials of the binary finite field GF(2N). Once operand W is loaded into a data storage location, a value P=└W·Xn+δ/M┘ is pre-computed by the processing system. Then when a second operand V is loaded, the quotient q{circle around ( )} for the product V·W being reduced modulo M is quickly estimated, q{circle around ( )}=└V·P/Xn+δ┘, optionally randomized, q′=q{circle around ( )}−E, and can be used to obtain the remainder r′=V·W−q′·M, which is congruent to (V·W) mod M. A final reduction can be carried out, and the later steps repeated with other second operands V.

Dependencies are inferred from the claim text.