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(2). Once operand W is loaded into a data storage location, a value P=└W·X/M┘ is pre-computed by the processing system. Then when a second operand V is loaded, the quotient q^ for the product V·W being reduced modulo M is quickly estimated, q^=└V·P/X┘, optionally randomized, q'=q^−E, and can be used to obtain the remainder r′=V·W−q′·M, which is congruent to (V·M) mod M. A final reduction can be carried out, and the later steps repeated with other second operands V.