Modular multiplication method with precomputation using one known operand
View Patent ↗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^ for the product V·W being reduced modulo M is quickly estimated, q^=└V·P/X n+δ ┘, 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.
1. 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.
2. The method as in claim 1 , wherein the operands V and W and the modulus M are integers represented in computer hardware in binary form, and X is the integer 2, the pre-computed numerical value P, the estimated quotient q^ and the calculated remainder r′ also being integers.
3. The method as in claim 1 , wherein the operands V and W, the modulus M, the pre-computed numerical value P, the estimated quotient q^, and the calculated remainder r′ are polynomials over variable X.
4. The method as in claim 3 , wherein all computations upon the polynomials are performed in a finite field.
5. The method as in claim 3 , wherein all computations upon the polynomials are performed in GF(2 N ).
6. The method as in claim 1 , wherein q′=q^ is used.
7. The method as in claim 1 , wherein q′ is derived from the estimated q^ by applying a random numerical value E to the estimated quotient, such that q′=q^−E.
8. The method as in claim 7 , wherein pseudo-random number generating circuitry generates the random numerical value E.
9. The method as in claim 7 , wherein the random numerical value E is limited in size to at most one-half word.
10. The method as in claim 1 , wherein, for polynomials, V<X m+φ , and the constant δ is chosen so that δ≧φ−1, the estimated quotient q^ being equal to the actual quotient.
11. The method as in claim 1 , wherein, for polynomials, V<X n+φ , and the constant δ is chosen so that δ<φ−1, the estimated quotient q^ being an underestimation of the actual quotient Q within a maximum range determined by δ and φ, such that deg(Q−q^)≧φ−δ−2.
12. The method as in claim 1 , wherein, for integers, V<2 n+φ , and the constant δ is chosen so that δ<φ, the estimated quotient q^ being an underestimation of the actual quotient Q within a maximum range determined by δ and φ, such that Q−2 φ−δ ≦q^≦Q.
13. The method as in claim 1 , further executing a final reduction modulo M upon the remainder r′.
14. The method as in claim 1 , further comprising carrying at least one additional modular multiplication using the same first operand W and the same pre-computed numerical value P, but with another second operand V.
15. The method as in claim 1 , wherein the modular multiplication of operands V and W is part of a computer hardware-implemented cryptography program.
16. A computer hardware-implemented modular multiplication method, comprising:
loading a first integer 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 an integer P, where P=└(W·2 n+δ )/M┘ for the operand W and a modulus M, where n is an integer representing a bit size of the larger of W and M, and where δ is a selected constant greater than 1;
loading a second integer 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)/2 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.
17. The method as in claim 16 , wherein q′=q^ is used.
18. The method as in claim 16 , wherein q′ is derived from the estimated q^ by applying a random integer value E to the estimated quotient, such that q=q^−E.
19. The method as in claim 18 , wherein pseudo-random number generating circuitry generates the random integer value E.
20. The method as in claim 18 , wherein the random integer value E is limited in bit size to at most one-half word.
21. The method as in claim 16 , wherein V<2 n+φ , and the constant δ is chosen so that δ<φ, the estimated quotient q^ being an underestimation of the actual quotient Q within a maximum range determined by δ, and φ such that Q−2 φ−δ ≦q^≦Q.
22. The method as in claim 16 , further executing a final reduction modulo M upon the remainder r′as a series of subtractions r′:=r′−M until r′<M.
23. The method as in claim 16 , further comprising carrying at least one additional modular multiplication using the same first operand W and the same pre-computed numerical value P, but with another second operand V.
24. A computer hardware-implemented modular polynomial multiplication method in the binary finite field GF(2 N ), comprising:
loading a first polynomial operand w(x) into data storage accessible to a processor unit, wherein w(x) is a first operand to be multiplied by a second operand;
pre-computing, using the processor unit, and storing a polynomial p(x), where p(x)=└(w(x)x n+δ /m(x)┘ for the operand w(x) and a polynomial modulus m(x), where n is an integer representing the polynomial degree of the larger of w(x) and m(x), and where δ is a selected constant greater than 1;
loading a second polynomial operand v(x) into the data storage, wherein v(x) is the second operand to be multiplied by W where deg(v(x))<n+φ, and the constant δ is chosen so that δ≧φ−1;
computing, using the processor unit, an estimated polynomial quotient q^(x) for the product (v(x)w(x)) to be reduced modulo m(x), wherein the estimated quotient q^(x) └(v(x)·p(x))/x n+δ ┘, where q^(x) is equal to the actual quotient; and
calculating, using the processor unit, a polynomial remainder r′(x)=(v(x)·w(x))−(q′(x)·m(x)), where q′(x) is a polynomial quotient value derived from the estimated polynomial quotient q^(x), said remainder r′(x) being congruent to (v(x)·w(x))mod m(x).
25. The method as in claim 24 , wherein q′(x)=q^(x) is used.
26. The method as in claim 24 , wherein q′(x) is derived from the estimated q^(x) by applying a random polynomial value E(x) to the estimated polynomial quotient, such that q′(x)=q^(x)−E(x).
27. The method as in claim 26 , wherein pseudo-random number generating circuitry generates a random numerical value E which is interpreted as the polynomial E(x) in the binary finite field GF(2 N ), where each bit value in E represents a different polynomial degree of x.
28. The method as in claim 26 , wherein the random polynomial value E is limited in degree to at most one-half word.
29. The method as in claim 24 , wherein the estimated polynomial quotient q^(x) being an underestimation of the actual quotient Q with the difference (Q−q(x)) having a maximum degree determined by δ and φ, such that deg(Q−q^(x)≦φ−δ−2.
30. The method as in claim 24 , further executing a final reduction modulo x) upon the polynomial remainder r′(x).
31. The method as in claim 24 , further comprising carrying at least one additional modular multiplication using the same first polynomial operand w(x) and the same pre-computed polynomial value p(x), but with another second polynomial operand v(x).