Optimization technique for modular multiplication algorithms

Abstract

Methods and apparatus for optimization techniques for modular multiplication algorithms. The optimization techniques may be applied to variants of modular multiplication algorithms, including variants of Montgomery multiplication algorithms and Barrett multiplication algorithms. The optimization techniques reduce the number of serial steps in Montgomery reduction and Barrett reduction. Modular multiplication operations involving products of integer inputs A and B may be performed in parallel to obtain a value C that is reduced to a residual RES. Modular multiplication and modular reduction operations may be performed in parallel. The number of serial steps in the modular reductions are reduced to L, where L serial steps, where w is a digit size in bits, and L is a number of digits of operands=[k/w].

What is claimed is: 
     
         1 . A method, comprising:
 performing modular multiplication for first and second integers A and B, including,
 employing a first operand for A and a second operand for B, the first and second operands having 2*k bits, 
 splitting A into k high bits AH and k low bits AL; 
 precomputing one of K M =B*2 −k  mod M or K B =B*2 k  mod M, where M is a 2*k-bit modulus; 
 multiplying one of AH*B or AL*B to obtain a first value; 
 multiplying one of AL*K M  or AH*K B  to obtain a second value; and 
 adding the first and second values to obtain C; and 
   performing a modular reduction on C.   
     
     
         2 . The method of  claim 1 , wherein the modular multiplication comprises a Montgomery Multiplication that uses AH*B to obtain the first value and the modular reduction comprises a Montgomery Reduction. 
     
     
         3 . The method of  claim 2 , further comprising:
 splitting C into upper 2*k bits CH and lower k bits CL; and   using CH and CL to perform the Montgomery Reduction to obtain a residual that is a function of mod M.   
     
     
         4 . The method of  claim 3 , further comprising:
 calculating R=2 2*L*w  mod M, where w is a digit size in bits and L is a number of digits of operands=[k/w]; and
 calculating a residual RES=A*B*R −1  mod M. 
   
     
     
         5 . The method of  claim 3 , wherein w is a digit size in bits, L is a number of digits of operands=[k/w], and wherein the Montgomery Reduction is performed in L serial steps. 
     
     
         6 . The method of  claim 1 , wherein the modular multiplication comprises a Barrett Multiplication that uses AH*L to obtain the first value and the modular reduction comprises a Barrett Reduction. 
     
     
         7 . The method of  claim 6 , further comprising:
 splitting C into upper k bits CH and lower 2*k bits CL; and   using CH and CL to perform the Barret Reduction to obtain a residual RES=A*B mod M.   
     
     
         8 . The method of  claim 7 , wherein w is a digit size in bits, L is a number of digits of operands=[k/w], and wherein the Barrett Reduction is performed in L serial steps. 
     
     
         9 . The method of  claim 1 , wherein multiplying AH*B or AL*B and multiplying AL*K M  or AH*K B  is done in parallel. 
     
     
         10 . The method of  claim 1 , wherein the modular multiplication operations are interleaved with modular reduction operations. 
     
     
         11 . A non-transitory machine-readable medium having instructions stored thereon to be executed on a processor or processor core of an apparatus to enable the apparatus to:
 perform modular multiplication for first and second integers A and B, including,
 employ a first operand for A and a second operand for B, the first and second operands having 2*k bits, 
 split A into k high bits AH and k low bits AL; 
 precompute K=B*2 −k  mod M, where M is a k-bit modulus; 
 multiply one of AH*B or AL*B to obtain a first value; 
 multiply one of AL*K M  or AH*K B  to obtain a second value; and 
 add the first and second values to obtain C; and 
   perform a modular reduction on C.   
     
     
         12 . The non-transitory machine-readable medium of  claim 11 , wherein the modular multiplication comprises a Montgomery Multiplication that uses AH*B to obtain the first value and the modular reduction comprises a Montgomery Reduction. 
     
     
         13 . The non-transitory machine-readable medium of  claim 11 , wherein w is a digit size in bits, L is a number of digits of operands=[k/w], and wherein the modular reduction is performed in L serial steps. 
     
     
         14 . The non-transitory machine-readable medium of  claim 11 , wherein the modular multiplication comprises a Barrett Multiplication that uses AL*B to obtain the first value and the modular reduction comprises a Barrett Reduction. 
     
     
         15 . The non-transitory machine-readable medium of  claim 14 , wherein execution of the instructions further enables the apparatus to:
 split C into upper k bits CH and lower 2*k bits CL; and   use CH and CL to perform the Barret Reduction to obtain a residual RES=A*B mod M.   
     
     
         16 . The non-transitory machine-readable medium of  claim 11 , wherein the modular multiplication operations are interleaved with modular reduction operations. 
     
     
         17 . An apparatus, comprising:
 a processor, having one or more processor cores;   memory, coupled to the processor;   a plurality of instructions, to be executed on at least one of the one or more processor cores to an enable the apparatus to:
 perform modular multiplication for first and second integers A and B, including,
 employ a first operand for A and a second operand for B, the first and second operands having 2*k bits, 
 split A into k high bits AH and k low bits AL; 
 precompute one of K M =B*2 −k  mod M or K B =B*2 k  mod M, where M is a 2*k-bit modulus; 
 multiply one of AH*B or AL*B to obtain a first value; 
 multiply one of AL*K M  or AH*K B  to obtain a second value; and 
 add the first and second values to obtain C; and 
 
 perform a modular reduction on C. 
   
     
     
         18 . The apparatus of  claim 17 , wherein the modular multiplication comprises a Montgomery Multiplication that uses AH*B to obtain the first value and the modular reduction comprises a Montgomery Reduction. 
     
     
         19 . The apparatus of  claim 17 , wherein the modular multiplication comprises a Barrett Multiplication that uses AL*B to obtain the first value and the modular reduction comprises a Barrett Reduction. 
     
     
         20 . The apparatus of  claim 17 , wherein the modular multiplication operations are interleaved with modular reduction operations.