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 N ). Once operand W is loaded into a data storage location, a value P=└W·X n+δ /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/X n+δ ┘, 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.

1 . A system comprising:
 a multiplier to perform multiplication operations;   a storage device coupled to the multiplier to store multiple operands, V, and a known operand W to be multiplied, a modulus M, and intermediate results, including a value P pre-computed as a function of W and M and a maximum possible size of V;   a controller to control the multiplier to perform multiple modular multiplication operations for multiple different values of v using the pre-computed value P where W is constant.   
     
     
         2 . The system of  claim 1  wherein 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. 
     
     
         3 . The system of  claim 2  where V<2 n+φ , and the constant δ is chosen so that δ≧φ. 
     
     
         4 . The system of  claim 3  wherein the multiplier is controlled to compute an estimated quotient, q{circle around ( )}, and a congruent remainder for modular operation (V·W) mod M for multiple values of V. 
     
     
         5 . The system of  claim 4  wherein the estimated quotient q{circle around ( )}=└(V·P)/X n+δ ┘. 
     
     
         6 . The system of  claim 4  and further comprising a random number generator to generate a random numerical value E to apply to the estimated quotient. 
     
     
         7 . The system of  claim 1  wherein the operands, V and w, are integers. 
     
     
         8 . The system of  claim 1  wherein the operands, V and W, are polynomials. 
     
     
         9 . A system comprising:
 a multiplier to perform multiplication operations;   a storage device coupled to the multiplier to store multiple operands, V, and a known operand W to be multiplied, a modulus M, and intermediate results, including a value P pre-computed as a function of W and M and a maximum possible size of V;   a controller to control the multiplier to perform multiple modular multiplication operations for multiple different values of V using the pre-computed value P where V is constant.   
     
     
         10 . The system of  claim 9  wherein 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. 
     
     
         11 . The system of  claim 10  where V<2 n+φ , and the constant δ is chosen so that δ≧φ. 
     
     
         12 . The system of  claim 11  wherein the multiplier is controlled to compute an estimated quotient, q{circle around ( )}, and a congruent, remainder for modular operation (V·W) mod M for multiple values of V. 
     
     
         13 . The system of  claim 12  wherein the estimated quotient q{circle around ( )}=└(V·P)/X n+δ ┘. 
     
     
         14 . The system of  claim 12  and further comprising a random number generator to generate a random numerical value E to apply to the estimated quotient. 
     
     
         15 . The system of  claim 9  wherein the operands, V and W, are integers. 
     
     
         16 . The system, of  claim 9  wherein the operands, V and W, are polynomials. 
     
     
         17 . A method comprising:
 loading a first 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 value P, where   
       P is a function of the operand w and a modulus M;
 loading a second operand V into the data storage, wherein V is a second operand to be multiplied by W; 
 computing, using the processor unit, an estimated quotient q{circle around ( )} for the product (V·W) to be reduced modulo M using P and V; 
 calculating a remainder r′ such that it is congruent to (V·W) mod M; and 
 repeating the loading of operand V, computing, and calculating for multiple values of V. 
 
     
     
         18 . The method of  claim 17  wherein 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, where δ is a selected constant greater than 1, and where V<2 n+φ , and the constant δ is chosen so that δ≧φ. 
     
     
         19 . The method of  claim 18  wherein the estimated quotient q{circle around ( )}=└(V·P)/X n+δ ┘. 
     
     
         20 . The method of  claim 17  and further comprising generating a random numerical value E to apply to the estimated quotient q{circle around ( )}.