Patent Publication Number: US-2023163944-A1

Title: Reduced complexity modular polynomial multiplication for r-lwe cryptosystems

Description:
BACKGROUND 
     The ring-learning with errors (R-LWR) problem is utilized to build many ciphers resisting quantum-computing attacks and fully homomorphic encryption that allows computations to be carried out on encrypted data. Modular multiplication of long polynomials with large coefficients is the most critical operation in these schemes. The polynomial multiplication complexity can be reduced by the Karatsuba scheme. 
     The discussion above is merely provided for general background information and is not intended to be used as an aid in determining the scope of the claimed subject matter. The claimed subject matter is not limited to implementations that solve any or all disadvantages noted in the background. 
     SUMMARY 
     A device-implemented method includes receiving a first polynomial and a second polynomial, both of order n−1 and forming d polynomial segments from both the first polynomial and the second polynomial such that each polynomial segment is of order (n/d)−1. The d polynomial segments of the first polynomial and the d polynomial segments of the second polynomial are used to form segment products. Each segment product is divided into a first polynomial substructure of order n/d and a second polynomial substructure of order (n/d)−1. A first polynomial substructure containing the first n/d coefficients of a product of the first polynomial and the second polynomial is summed with a second polynomial substructure to form a sum substructure. The sum substructure is used multiple times to determine coefficients of a polynomial representing the modulo x n +1 of the product of the first polynomial and the second polynomial. 
     In accordance with a further embodiment, a device-implemented method includes receiving a first polynomial and a second polynomial, both of order n−1 and using a Karatsuba scheme on the first polynomial and second polynomial to form segment products. Each segment product is divided into a first polynomial substructure and a second polynomial substructure. A second polynomial substructure, containing the last (n/d)−1 coefficients of a product of the first polynomial and the second polynomial, is summed with a first polynomial substructure to form a sum substructure. The sum substructure is used multiple times to determine coefficients of a polynomial representing the modulo x n +1 of the product of the first polynomial and the second polynomial. 
     In accordance with a still further embodiment, a method includes performing a cryptographic operation based on modulo xn+1-&gt;x{circumflex over ( )}n+1 of a product of two polynomials each of order n−1. The modulo xn+1-&gt;x{circumflex over ( )}n+1 of the product of the two polynomials is determined using a Karatsuba scheme of forming the product of the two polynomials to form segment products. Each segment product is divided into polynomial substructures. A sum substructure is formed using a polynomial substructure containing coefficients of a polynomial representing the product of the two polynomials. The sum substructure is used multiple times to determine coefficients for a polynomial representing a modulo x n +1 of the product of the two polynomials. 
     This Summary is provided to introduce a selection of concepts in a simplified form that are further described below in the Detailed Description. This Summary is not intended to identify key features or essential features of the claimed subject matter, nor is it intended to be used as an aid in determining the scope of the claimed subject matter. 
    
    
     
       BRIEF DESCRIPTION OF THE DRAWINGS 
         FIG.  1 ( a )  is a graph showing the alignment of segment products that need to be added together in Karatsuba multiplication with 2-decomposition under the prior art. 
         FIG.  1 ( b )  is a graph showing the alignment of segment products that need to be added together in Karatsuba multiplication with 2-decomposition with integrated modular reduction by x n +1. 
         FIG.  2 ( a )  is a graph showing the alignment of segment products that need to be added together in Karatsuba multiplication with 3-decomposition under the prior art 
         FIG.  2 ( b )  is a graph showing the alignment of segment products that products need to be added together in Karatsuba multiplication with 3-decomposition with integrated modular reduction by x n +1. 
         FIG.  3 ( a )  is a graph showing the alignment of segment products that need to be added together in Karatsuba multiplication with 4-decomposition under the prior art 
         FIG.  3 ( b )  is a graph showing the alignment of segment products that products need to be added together in Karatsuba multiplication with 4-decomposition with integrated modular reduction by x n +1. 
         FIG.  4   . is a table of common terms contributing to 4-decomposed Karatsuba multiplication with integrated polynomial modular reduction. 
         FIG.  5    is a flow diagram of a method determining a product of two polynomials in accordance with one embodiment. 
         FIG.  6    is a block diagram of a dedicated circuit used to determine the product of two polynomials in accordance with one embodiment. 
     
    
    
     DETAILED DESCRIPTION 
     In the embodiments described below, a new method is proposed to integrate a modular reduction into the Karatsuba polynomial multiplication. Modular reduction is applied to intermediate segment products instead of the final product. As a result, additional substructure sharing is enabled and the number of coefficient additions needed for assembling the segment products to get the final result is substantially reduced. For polynomial multiplications with decomposition factors 2, 3, and 4, the proposed scheme reduces the number of additions by 13-17%. 
     1. Introduction 
     Lattice-based ciphers utilizing the ring-learning with errors (R-LWE) problem are among the most promising and feasible candidates to resist quantum-computing attacks. Additionally, fully homomorphic encryption (FHE) allows computations to be carried out on encrypted data. It is a key enabler for secure and private cloud or distributed computing. The most popular FHE schemes, such as the BGV and BFV, are also based on the R-LWE problem. 
     The computations involved in the R-LWE problem can be broken down into polynomial multiplications and additions over the ring Z q [x]/(x n +1). The multiplication between two polynomials is followed by modulo reduction by x n +1 and the calculations on the coefficients are done modulo q. Large n and q are needed to achieve sufficient security level in Lattice-based ciphers and reduce the frequency of the expensive bootstrapping in FHE. For example, to allow four levels of multiplications between each bootstrapping, q has 180 bits and n=4096. 
     The embodiments described herein reduce the modular polynomial multiplication complexity by integrating the modular reduction into the Karatsuba multiplication process. Instead of waiting until after the segment products are assembled to get the final polynomial product, the modular reduction is applied to individual segment products. Since the modulus is in the format of x n +1, the reduction is carried out effectively as shifting the segment products. Due to the shifting, additional substructure sharing is enabled when the segment products are added up to derive the final result. Accordingly, the number of required coefficient additions is substantially reduced. For Karatsuba polynomial multiplications with decomposition factors of 2, 3, and 4, the proposed method leads to 13-17% reduction on the number of coefficient additions needed to assemble the segment products. 
     2. Polynomial Multiplication Over Ring and Karatsuba Formula 
     Over the ring Z q [x]/(x n +1), each element is a polynomial with degree lower than n and the coefficients are non-negative integers less than q. The product of A(x)=a 0 +a 1 x+ . . . +a n−1 x n−1  and B(x)=b 0 +b 1 x+ . . . +b n−1 x n−1  (0≤a i ; b i &lt;q) is A(x)B(x) mod (x n +1) and the computations over the coefficients, a i ; b i , are carried out modulo q. 
     In the schoolbook multiplication of two polynomials of length n, n 2  multiplications on the coefficients are needed. The Karatsuba algorithm was originally proposed to reduce the complexity of large integer multiplications. The same formula can be also used to reduce the number of coefficient multiplications in polynomial multiplication at the cost of larger number of coefficient additions. Decompose A(x) of degree n−1 into A 0 (x)+A 1 (x)x n/2 , where A 0 (x)=a 0 +a 1 x+ . . . +a n/2−1 x n/2−1  and A 1 (x)=a n/2 +a n/2+1 x+ . . . +a n−1 x n2/2−1 . Decompose B(x) in a similar way. Then, using the Karatsuba formula, P(x)=A(x)B(x) can be computed as P 0 (x)+P 1 (x)x n/2 +P 2 (x)x n , where 
     
       
      
       P 
       0 
       =A 
       0 
       B 
       0  
      
     
         P   1 =( A   0   =A   1 )( B   0   +B   1 )− A   0   B   0   −A   1   B   1  
 
         P   2   =A   1   B   1   (1)
 
     For conciseness, ‘(x)’ is dropped from the notations if no ambiguity occurs as in the above equations. There are only three multiplications of polynomials of length n/2 in (1). Hence, the number of coefficient multiplications is reduced to 3(n/2) 2 =3n 2 /4. The degree of P(x) is 2(n−1). Rewrite P(x) as P 1 (x)+x n P h (x), where P 1 (x)=p 0 +p 1 x+ . . . +p n−1 x n−1  and P h (x)=p n +p n+1 x+ . . . +p 2n+2 X n−2 . Then 
     
       
         
           
             
               
                 
                   
                     
                       P 
                       ⁡ 
                       ( 
                       x 
                       ) 
                     
                     ⁢ 
                     
                       mod 
                       ⁡ 
                       ( 
                       
                         
                           x 
                           n 
                         
                         + 
                         1 
                       
                       ) 
                     
                   
                   = 
                     
                   
                     
                       ( 
                       
                         
                           
                             P 
                             l 
                           
                           ( 
                           x 
                           ) 
                         
                         + 
                         
                           
                             ( 
                             
                               
                                 x 
                                 n 
                               
                               + 
                               1 
                               - 
                               1 
                             
                             ) 
                           
                           ⁢ 
                           
                             
                               P 
                               h 
                             
                             ( 
                             x 
                             ) 
                           
                         
                       
                       ) 
                     
                     ⁢ 
                     
                       mod 
                       ⁡ 
                       ( 
                       
                         
                           x 
                           n 
                         
                         + 
                         1 
                       
                       ) 
                     
                   
                 
               
             
             
               
                 
                   = 
                     
                   
                     
                       
                         P 
                         l 
                       
                       ( 
                       x 
                       ) 
                     
                     - 
                     
                       
                         
                           P 
                           h 
                         
                         ( 
                         x 
                         ) 
                       
                       . 
                     
                   
                 
               
             
           
         
       
     
     The number of coefficient multiplications can be further reduced by using larger decomposition factors. If A(x) and B(x) are each decomposed into three segments of length n/3, the product P(x)=P 0 (x)+P 1 (x)x n/3 +P 2 (x)x 2n/3 +P 3 (x)x n +P 4 (x)x 4n/3  can be calculated as 
     
       
         
           
             
               
                 
                   
                     
                       
                         
                           
                             P 
                             0 
                           
                           = 
                             
                           
                             
                               A 
                               0 
                             
                             ⁢ 
                             
                               B 
                               0 
                             
                           
                         
                         ; 
                       
                     
                   
                   
                     
                       
                         
                           P 
                           1 
                         
                         = 
                           
                         
                           
                             
                               ( 
                               
                                 
                                   A 
                                   0 
                                 
                                 + 
                                 
                                   A 
                                   1 
                                 
                               
                               ) 
                             
                             ⁢ 
                             
                               ( 
                               
                                 
                                   B 
                                   0 
                                 
                                 + 
                                 
                                   B 
                                   1 
                                 
                               
                               ) 
                             
                           
                           - 
                           
                             
                               A 
                               1 
                             
                             ⁢ 
                             
                               B 
                               1 
                             
                           
                           - 
                           
                             
                               A 
                               0 
                             
                             ⁢ 
                             
                               B 
                               0 
                             
                             : 
                           
                         
                       
                     
                   
                   
                     
                       
                         
                           P 
                           2 
                         
                         = 
                           
                         
                           
                             ( 
                             
                               
                                 A 
                                 0 
                               
                               + 
                               
                                 A 
                                 1 
                               
                               + 
                               
                                 A 
                                 2 
                               
                             
                             ) 
                           
                           ⁢ 
                           
                             ( 
                             
                               
                                 B 
                                 0 
                               
                               + 
                               
                                 B 
                                 1 
                               
                               + 
                               
                                 B 
                                 2 
                               
                             
                             ) 
                           
                         
                       
                     
                   
                   
                     
                       
                           
                         
                           - 
                           
                             ( 
                             
                               
                                 
                                   ( 
                                   
                                     
                                       A 
                                       0 
                                     
                                     + 
                                     
                                       A 
                                       1 
                                     
                                   
                                   ) 
                                 
                                 ⁢ 
                                 
                                   ( 
                                   
                                     
                                       B 
                                       0 
                                     
                                     + 
                                     
                                       B 
                                       1 
                                     
                                   
                                   ) 
                                 
                               
                               - 
                               
                                 
                                   A 
                                   1 
                                 
                                 ⁢ 
                                 
                                   B 
                                   1 
                                 
                               
                             
                             ) 
                           
                         
                       
                     
                   
                   
                     
                       
                           
                         
                           
                             - 
                             
                               ( 
                               
                                 
                                   
                                     ( 
                                     
                                       
                                         A 
                                         1 
                                       
                                       + 
                                       
                                         A 
                                         2 
                                       
                                     
                                     ) 
                                   
                                   ⁢ 
                                   
                                     ( 
                                     
                                       
                                         B 
                                         1 
                                       
                                       + 
                                       
                                         B 
                                         2 
                                       
                                     
                                     ) 
                                   
                                 
                                 - 
                                 
                                   
                                     A 
                                     1 
                                   
                                   ⁢ 
                                   
                                     B 
                                     1 
                                   
                                 
                               
                               ) 
                             
                           
                           ; 
                         
                       
                     
                   
                   
                     
                       
                         
                           
                             P 
                             3 
                           
                           = 
                             
                           
                             
                               
                                 ( 
                                 
                                   
                                     A 
                                     1 
                                   
                                   + 
                                   
                                     A 
                                     2 
                                   
                                 
                                 ) 
                               
                               ⁢ 
                               
                                 ( 
                                 
                                   
                                     B 
                                     1 
                                   
                                   + 
                                   
                                     B 
                                     2 
                                   
                                 
                                 ) 
                               
                             
                             - 
                             
                               
                                 A 
                                 1 
                               
                               ⁢ 
                               
                                 B 
                                 1 
                               
                             
                             - 
                             
                               
                                 A 
                                 2 
                               
                               ⁢ 
                               
                                 B 
                                 2 
                               
                             
                           
                         
                         ; 
                       
                     
                   
                   
                     
                       
                         
                           
                             P 
                             4 
                           
                           = 
                             
                           
                             
                               A 
                               2 
                             
                             ⁢ 
                             
                               B 
                               2 
                             
                           
                         
                         ; 
                       
                     
                   
                 
               
               
                 
                   ( 
                   3 
                   ) 
                 
               
             
           
         
       
     
     In total, 6 multiplications between polynomials of length n/3 are needed and the total number of coefficient multiplications is reduced to 6(n/3) 2 =2n 2 /3. However, compared to (1) for 2-decomposition, the number of additions needed for assembling the segment products to get P(x) is increased a lot. For larger decomposition factors, the formulas in (1) and (3) can be applied in an iterative manner to further reduce the number of coefficient multiplications. 
     3. Karatsuba Polynomial Multiplication with Integrated Modular Reduction 
     Coefficient multipliers have larger silicon area than adders. Hence, the goal of the Karatsuba algorithm is to reduce the number of coefficient multiplications. More significant multiplication number reduction is achieved by using a larger decomposition factor. However, the number of additions needed to assemble the segment products increases fast with the decomposition factor as can be seen from (1) and (3). Since additions and subtractions have similar complexity, they are not differentiated in terms of complexity herein. Conventionally, the reduction by x n +1 is carried out after the final product is computed. As shown in (2), the modular reduction by such a polynomial can be implemented as negating and shifting the coefficients for the terms whose powers are at least x n . This paper proposes to carry out the modular reduction on the segment products in the Karatsuba multiplication before they are added up. This enables the sharing of many common terms in the segment product additions. As a result, the number of coefficient additions is substantially reduced without affecting the multiplication complexity. 
     In the discussion below, reference is made to “addition operations.” Such operations can implement adding two values together or subtracting one value from another. In order to subtract a value, the negative of the value is added to the other value in the addition operation. As such, the “sum” of an addition operation can either represent the sum of two values or the difference between two values. Thus, generic references to addition operations below should be read as including the determination of either a sum of two values or the difference between two values. The determination of whether an addition operation produces a sum or a difference of two values can be determined by examining the context in which the addition operation is implemented in the discussion below. 
     In 2-decomposed Karatsuba multiplication, let C 0 (x)=A 0 (x)B 0 (x), C 1 (x)=(A 0 (x)+A 1 (x))(B 0 (x)+B 1 (x)), and C 2 (x)=A 1 (x)B 1 (x). Each of these segment products has n−1 coefficients. In  FIG.  1 ( a ) , each product is represented by a bar of length n−1. The bars are aligned to the powers of x that the segment products are multiplied to get P(x)=P 0 (x)+P 1 (x)x n/2 +P 2 (x)x n . For example, C 0 (x)=P 0 (x) and C 0 (x) is also a part of P 1 (x), which is multiplied with X n/2 . Hence, there are two bars for C 0  starting from the columns of x 0  and X n/2 . The negative signs on the bars mean that the corresponding coefficients are to be subtracted. The coefficients in the same column need to be added/subtracted to derive each final coefficient of P(x). Add ‘l’ and ‘h’ to the subscript of a segment product to denote its lower n/2 and higher n/2−1 coefficients, respectively. From  FIG.  1 ( a ) , C 2,1 -C 0,h  can be shared in the computations of the coefficients in the range of x n/2  to X n−1  and x n  to x 3n/2−1 . After all coefficients of P(x) are derived, the highest n−1 coefficients are subtracted from the lowest n−1 coefficients to implement the modular reduction according to (2). 
     To reduce the number of additions, embodiments carry out the modular reduction by x n +1 on the segment products before they are added up. According to (2), any term p i x i  with i≥n becomes −p i x i-n  after the modular reduction. As a result, the segment products can be added up as shown in  FIG.  1 ( b ) . Then the coefficients for 1, x, . . . , x n/2−1  and those for x n/2 , x n/2+1 , . . . x n−1  in the final modular multiplication result can be computed as 
       ( C   0,h   −C   2,l )−( C   2,h   +C   0,l )+ C   1,l  
 
       ( C   0,h   −C   2,l )+( C   2,h   +C   0,l )− C   1,h .
 
     Two terms instead of one common term are shared in the above calculations and no further modular reduction is needed. In total, 2(n/2−1)+4n/2−1/3n−3 coefficient additions are needed. The additional common term that is shared includes the first coefficients (C 0,l ) and the last coefficients (C 2,h ) of the product of the two polynomials P(x), where the first coefficients are for powers of x 0  to x n/2−1  in the product and the last coefficients are for powers of X 3n/2  to x 2n−2  in the product. As shown in  FIG.  1 ( a ) , the Karatsuba multiplication followed by a modulo x n +1 operation does not allow the first coefficients and the last coefficients of the product to be formed into a common term that can be reused during the multiplication and modulo x n +1 operations. The present embodiments, on the other hand, allow these additional common terms to be formed thereby reducing the total number of operations that must be performed and significantly improving the operation of the device. For Karatsuba multiplication that decomposes operands into three segments, denote A 0 B 0 , A 1 B 1 , A 2 B 2  by C 0 , C 1 , and C 2 , respectively. Let D 0 , D 1 , and D 2  be (A 0 +A 1 )(B 0 +B 1 )−C 1 , (A 1 +A 2 )(B 1 +B 2 )−C 1 , and (A 0 +A 1 +A 2 )(B 0 +B 1 +B 2 ), respectively. From (3), these intermediate results should be added up according to  FIG.  2 ( a )  to derive P(x). Three common terms, C 2,l +D 1,h , D 0,h −D 1,l , and C 0,h +D 0,l , can be shared to save 3(n/3−1) additions. Besides, another n−1 coefficient subtractions are required afterwards to modulo reduce P(x) by x n +1. On the other hand, by carrying out the modular reduction on the intermediate results first, more common terms become shareable among the segment product additions as shown in  FIG.  2 ( b ) . The coefficients whose powers are in the ranges of 1 to x n/3−1 , x n/3  to x 2n/3−1,  and x 2n/3  to x n−1  in the final modular multiplication result can be computed as 
       ( D   0,h   −D   1,l )−( D   0,l   +C   0,h   +C   2,h )+ D   2,l  
 
       ( D   0,l   +C   0,h   +C   2,h )−( D   1,h   +C   0,l +( C   2,l )
 
       ( D   0,h   −D   1,l )+( D   1,h   +C   0,l   +C   2,l )− D   2,h  
 
     The shareable terms are enclosed in the parentheses above. Only (n/3−1)+2(n/3−1)+2(n/3−1)+1+5n/3−1=10n/3−5 coefficient additions are required. One of the common terms that is shared is (D 1,h  C 0,l +C 2,l ), which contains the first coefficients (C 0,l ) of the product of the two polynomials P(x), where the first coefficients are for powers of x 0  to X n/3−1  in the product. Another of the common terms that is shared is (D 0,l +C 0,h +C 2,h ), which contains the last coefficients (C 2,h ) of the product of the two polynomials P(x), where the last coefficients are for powers of X 5n/3  to X 2n−2  in the product. As shown in  FIG.  2 ( a ) , the Karatsuba multiplication followed by a modulo x n +1 operation does not allow the first coefficients and the last coefficients of the product to be formed into a common term that can be reused during the multiplication and modulo x n +1 operations. The present embodiments, on the other hand, allow these additional common terms to be formed thereby reducing the total number of operations that must be performed and significantly improving the operation of the device. 
     The multiplication with a larger decomposition factor can be carried out by iteratively applying the formulas for small decomposition factors. For example, 4-decomposed polynomial multiplication can be implemented by applying the formulas in (1) for 2-decomposition in two layers. Let A(x)=A 0 (x)+A I (x)x n/4 +A 2 (x)x n/2 +A 3 (x)x 3n/4 , where each A i (x) has n/4 coefficients. Define A 0 ′(x)=A 0 (x)+A 2 (x)X n/2  and A′ 1 (x)=A 1 (x)+A 3  (x)X n/2 . Decompose B(x) and define B 0 ′ and B 1 ′(x) in a similar way. By applying the formulas in (1), P(x)=(A 0 ′(x)+A 1 ′(x)x n/4 )(B 0 ′(x)+B 1 (x)x n/4 ) can be rewritten as 
     
       
         
           
             
               
                 
                   
                     
                       
                         
                           P 
                           ⁡ 
                           ( 
                           x 
                           ) 
                         
                         = 
                           
                         
                           
                             
                               A 
                               0 
                               ′ 
                             
                             ⁢ 
                             
                               B 
                               0 
                               ′ 
                             
                           
                           + 
                           
                             
                               ( 
                               
                                 
                                   
                                     ( 
                                     
                                       
                                         A 
                                         0 
                                         ′ 
                                       
                                       + 
                                       
                                         A 
                                         1 
                                         ′ 
                                       
                                     
                                     ) 
                                   
                                   ⁢ 
                                   
                                     ( 
                                     
                                       
                                         B 
                                         0 
                                         ′ 
                                       
                                       + 
                                       
                                         B 
                                         1 
                                         ′ 
                                       
                                     
                                     ) 
                                   
                                 
                                 - 
                                 
                                   
                                     A 
                                     0 
                                     ′ 
                                   
                                   ⁢ 
                                   
                                     B 
                                     0 
                                     ′ 
                                   
                                 
                                 - 
                                 
                                   
                                     A 
                                     1 
                                     ′ 
                                   
                                   ⁢ 
                                   
                                     B 
                                     1 
                                     ′ 
                                   
                                 
                               
                               ) 
                             
                             ⁢ 
                             
                               x 
                               
                                 n 
                                 / 
                                 4 
                               
                             
                           
                         
                       
                     
                   
                   
                     
                       
                         
                           + 
                             
                           
                             A 
                             1 
                             ′ 
                           
                         
                         ⁢ 
                         
                           B 
                           1 
                           ′ 
                         
                         ⁢ 
                         
                           
                             x 
                             
                               n 
                               / 
                               2 
                             
                           
                           . 
                         
                       
                     
                   
                 
               
               
                 
                   ( 
                   4 
                   ) 
                 
               
             
           
         
       
     
     Then the formulas in (1) can be applied again to each of the product term in (4). For example, A 0 ′(x)B 0 ′(x)=(A 0 (x)+A 2  (x)X n/2 )(B 0 (x)+B 2  (x)X n/2 ) can be computed as 
         A   0   B   0 ⇄(( A   0   +A   2 )( B   0   +B   2 )− A   0   B   0   −A   2   B   2 ) x   n/2   +A   2   B   2   x   n .  (5)
 
     Using this 2-layer approach, the segment products need to be added up for P(x) calculation as shown in  FIG.  3 ( a ) . There are nine segment products in total. C 00 =A 0 B 0 , C 01 =(A 0 +A 2 )(B 0 +B 2 ), and C 02 =A 2 B 2  are used to compute A 0 ′B 0 ′ according to (5). C 20 =A 1 B 1 , C 21 =(A 1 +A 3 )(B 1 +B 3 ), and C 22 =A 3 B 3  contribute to the calculation of A 1 ′B 1 ′ in a similar way. (A 0 ′+A 1 ′)(B 0 ′+B 1 ′) is derived by using C 10 =(A 0 +A 1 )(B 0 +B 1 ), C 01 =(A 0 +A 1 +A 2 +A 3 )(B 0 +B 1 +B 2 +B 3 ), and C 12 =(A 2 +A 3 )(B 2 +B 3 ). The coefficients in the same column are added up to compute each coefficient of P(x). Besides, n−1 coefficient additions are needed afterwards to carry out the modular reduction by x n+1 . 
     By applying the polynomial modular reduction on the segment products, the coefficients that need to be added up are aligned as shown in  FIG.  3 ( b ) . The intermediate results shareable among the additions can be more easily identified by using  FIG.  4   . In this figure, each term involved in  FIG.  3 ( b )  is listed. If a term contributes to a sum, then a +/− sign is put into the corresponding entry. The common patterns among the rows correspond to the shareable intermediate results and they are shade-coded in  FIG.  4   . X 0 =C 00,h −C 20,1 , X 1 =C 00,l −C 22,h , X 2 =C 02,h −C 22,l , and X 3 =C 02,l +C 20,h  can be shared among the computations for each of the four rows and C 01,h -C 22,l  is shareable between the first and last rows. Besides, X 0 -X 1  can be further shared among the computations for rows 1, 2, and 4, and (X 0 -X 1 )−C 10,l  is common between rows 2 and 4. X 2 -X 3  can be further shared among the calculations of the last three rows and (X 2 -X 3 )+C 12,l  are shareable between rows 2 and 4. Sharing these common terms saves (4×3+1+2+2+1+1)(n/4−1)+2+2+1+1=19(n/4−1)+6 coefficient additions. A similar method can be applied to find the common terms shareable in the additions of the segment products in  FIG.  3 ( a )  and it was found that only 15(n/4−1)+4 coefficient additions can be saved. 
     X 1  includes the first coefficients (C 00,l ) of the product of the two polynomials P(x), where the first coefficients are for powers of x 0  to x n/4−1  in the product and includes the last coefficients (C 22,h ) of the product of the two polynomials P(x), where the last coefficients are for powers of x 7n/4  to X 2n−2  in the product. As shown in  FIG.  3 ( a ) , the Karatsuba multiplication followed by a modulo x n +1 operation does not allow the first coefficients and the last coefficients of the product to be formed into a common term that can be reused during the multiplication and modulo x n +1 operations. The present embodiments, on the other hand, allow these additional common terms to be formed thereby reducing the total number of operations that must be performed and significantly improving the operation of the device. 
     In the Karatsuba formulas, the same segment products are multiplied with different powers of x to compute the coefficients of the overall product. Hence, the same segment products appear at different columns in  FIGS.  1 ( a ),  2 ( a ), and  3 ( a ) . Reducing the segment products by x n +1 effectively relocates those with higher powers of x to the right-side of the plane. Since there are a limited number of segment products and most of them appear multiple times, it becomes more likely that the same terms need to be added up in different columns and hence more intermediate results can be shared. For Karatsuba multiplications with even larger decomposition factors, similar approaches can be applied to reduce the number of coefficient additions needed for assembling the segment products. 
     4. Complexity Analyses and Comparisons 
     The number of segment products is minimized in Karatsuba multiplication. However, the number of coefficient additions needed for assembling the segment products to derive the modular multiplication result can be reduced by integrating the x n +1 reduction into the segment products as proposed in this paper. In this section, the number of coefficient additions needed for assembling the segment products in the proposed design is compared to that of the original Karatsuba multiplication for decomposition factors of 2, 3, and 4. 
     For 2-decomposition, considering that (n/2−1) additions are saved by sharing C 2,l -C 0,h , the number of coefficient additions needed for summing up the segment products in  FIG.  1 ( a )  and modulo reduction afterwards is 3(n/2−1)+3(n/2−1)+2−(n/2−1)+n−1=7n/2−4. Similarly, by counting the number of segment products to add from  FIG.  2 ( a )  and taking into account shareable terms and the following modular reduction, the number of coefficient additions required for the original 3-decomposed design is 2(n/3−1)+4(n/3−)+1+4(n/3−1)+2+2(n/3−1)+1−3(n/3−1)+(n−1)=4n−6. On the other hand, the proposed approach only needs 3n−3 and 10/3n−5 additions for 2 and 3-decomposed designs, respectively, as analyzed in the previous section. The numbers of additions needed to sum up the segment products following  FIG.  3 ( a )  and  FIG.  3 ( b )  in a straightforward manner are 42(n/4−1)+18 and 46(n/4−1)+21, respectively. Adopting substructure sharing, the original and the proposed designs require 42(n/4−1)+18−(15(n/4−1)+4)+(n−1)=31n/4−14 and (46n/4−1)+21−(19(n/4−1)+6)=27n/4−12 coefficient additions, respectively. These numbers are listed in Table 1. Ignoring the constant components in the formulas, the proposed design can achieve around 14%, 17%, and 13% reductions for decomposition factors 2, 3, and 4, respectively. 
     Thus, the number of addition operations (both adding and subtracting values) for polynomials decomposed into 2 segments is on the order of 3n operations; the number of addition operations (both adding and subtracting values) for polynomials decomposed into 3 segments is on the order of 10n/3 operations; and the number of addition operations (both adding and subtracting values) for polynomials decomposed into 4 segments is on the order of 27n/4 operations. 
     
       
         
           
               
             
               
                 TABLE 1 
               
             
            
               
                   
               
               
                 Number of additions needed for assembling segment products 
               
               
                 in modular multiplication using Karatsuba formula 
               
            
           
           
               
               
               
               
            
               
                   
                 2-decomp 
                 3-decomp 
                 4-decomp 
               
               
                   
                   
               
            
           
           
               
               
               
               
               
            
               
                   
                 mod. + mod. 
                 7n/2 − 4 
                 4n − 6 
                 31n/4 − 14 
               
               
                   
                 proposed 
                 3n − 3 
                 10n/3 − 5 
                 27n/4 − 12 
               
               
                   
                   
               
            
           
         
       
     
       FIG.  5    provides a flow diagram of a method of performing a modulo x n +1 polynomial multiplication of two polynomials of order n−1. In accordance with one embodiment, this method is performed as part of a cryptographic operation.  FIG.  6    provides a block diagram of a specialized hardware device consisting of multiplication and addition units dedicated to performing the method of  FIG.  5    by dividing the input polynomials into two segments. 
     In step  500  of  FIG.  5   , first and second polynomials such as polynomials A(x) and B(x) of  FIG.  6    are received at the dedicated hardware. In accordance with one embodiment, each polynomial is of an order of n−1 and receiving the polynomials comprises receiving the coefficients for the polynomials on a group of electrical conductors  600  for polynomial A(x) and a group of electrical conductors  605  for polynomial B(x). At step  502 , polynomial segments are formed from the received polynomials. In the embodiments described above, 2, 3, or 4 segments are formed depending on the particular embodiment. If the number of segments is d, each segment is of order (nld)−1. In the example embodiment of  FIG.  6   , d=2 so two segments are formed for polynomial A(x) by separating the group of electrical conductors  600  carrying the coefficients for polynomial A(x) into segment conductor group  601  carrying the coefficients for segment A 1  and segment conductor group  602  carrying the coefficients for segment A 0 . Two segments are formed for polynomial B(x) by separating the group of electrical conductors  605  carrying the coefficients for polynomial B(x) into segment conductor group  603  carrying the coefficients for segment B 1  and segment conductor group  604  carrying the coefficients for segment B 0 . 
     At step  504 , the segments are used to compute segment products, such as C 0 , C 1 , and C 2  in  FIG.  6   . Segment product C 0  is formed in  FIG.  6    by applying the electrical conductors in segment conductor group  602  for segment A 0  and the electrical conductors in segment conductor group  604  for segment B 0  to a dedicated multiplication circuit  606  that multiplies each coefficient carried by segment conductor group  602  by every coefficient carried by segment conductor group  604 . The output of dedicated multiplication circuit  606  is conductor group  622 , which carries n−1 coefficients. Similarly, segment product C 2  is formed by applying the electrical conductors of segment conductor group  601  representing the coefficients of segment A 1  and the electrical conductors of segment conductor group  603  representing the coefficients of segment B 1  to a dedicated multiplication circuit  608  that multiplies each coefficient carried by segment conductor group  601  by every coefficient carried by segment conductor group  603 . The output of dedicated multiplication circuit  608  is conductor group  624 , which carries n−1 coefficients. Segment product C 1  is formed by first applying the electrical conductors of segment conductor group  601  and the electrical conductors of segment conductor group  602  to a dedicated addition circuit  610  that adds each coefficient carried by the electrical conductors of segment conductor group  601  by a corresponding coefficient carried by segment conductor group  603 . In particular, for all values of a from 0 to n/2−1, the coefficient for x a  found in segment A 0  is added to the coefficient of x a  found in segment A 1 . Similarly, the electrical conductors of conductor group  603  and the electrical conductors of conductor group  604  are applied to a dedicated addition circuit  612  that adds each coefficient of segment B 1  to a corresponding coefficient of segment B 0 . Conductor groups  614  and  616 , which are output by addition circuit  610  and  612 , respectively, each carry the n/2 sums formed by their respective addition circuits. Conductor groups  614  and  616  are applied to a dedicated multiplication circuit  618  that multiples each sum carried by conductor group  614  by every sum carried by conductor group  616 . The output of dedicated multiplication circuit  618  is conductor group  622 , which carries n−1 coefficients. 
     Steps  502  and  504  implement portions of the Karatsuba scheme for polynomial multiplication. 
     At step  506 , each of segment products C 0 , C 1  and C 2  are divided into substructures by dividing conductor groups  620 ,  622  and  624  into conductor subgroups  626 ,  628 ,  630 ,  632 ,  634  and  636  at step  506 . Conductor subgroup  626  carries the C 1,l  coefficients and conductor subgroup  628  carries the C 1,h  coefficients of segment product C 1 . Conductor subgroup  630  carries the C 0,l  coefficient and conductor subgroup  632  carries the C 0,h  coefficients of product segment C 0 . Conductor subgroup  634  carries the C 2,l  coefficients and conductor subgroup  636  carries the C 2,h  coefficients of segment product C 2 . 
     At step  508 , common terms, also referred to as sum substructures, are formed from the substructures of the segment products. Each sum substructure is formed by adding each coefficient of a segment substructure to a corresponding coefficient of another segment substructure. At least one of the sum substructures is formed using a segment substructure that contains the first n/d coefficients (for powers of x 0  to x n/d−1 ) of the product of A(x) and B(x) and at least one of the sum substructures is formed using a segment substructure that contains the last (n/d)−1 coefficients (for powers X (2d−1)n/d  to x 2n−2 ) of the product of A(x) and B(x). 
     In  FIG.  6   , step  508  is implemented using dedicated addition and subtraction circuits  650  and  652 . Specifically, conductor subgroups  632  and  634  are input to dedicated subtraction circuit  650 , which subtracts each coefficient of C 2,l  from a corresponding coefficient of C 0,h  and provides the resulting differences on difference electrical conductors  677 , which represent a sub substructure. Conductor subgroups  626  and  630  are input to dedicated addition circuit  652 , which adds each coefficient of C 2,h  to a corresponding efficient of C 0,l . and provides the resulting sums on sum electrical conductors  670 , which represent a second sum substructure. 
     At step  510 , the sum substructures are used multiple times to determine coefficients of a polynomial representing the modulo x n+1  of the product of A(x) and B(x). In  FIG.  6   , this involves applying the sum substructure on different electrical conductors  677  and the sum substructure on sum electrical conductors  670  to both a dedicated addition circuit  654  and a dedicated subtraction circuit  656 . Dedicated addition circuit  654  adds each coefficient carried by sum electrical conductors  670  with a corresponding coefficient carried by difference electrical conductors  677 . Subtraction circuit  656  determines a difference between each coefficient carried by difference electrical conductors  672  a corresponding coefficient carried by sum electrical conductors  670 . The sums output by addition circuit  654  are carried by electrical conductors  674  and the differences output by subtraction circuit  656  are carried on electrical conductors  676 . Electrical conductors  674  are input to subtraction circuit  658  together with conductor subgroup  628 . Subtraction circuit  658  determines a difference between each sum carried by electrical conductors  674  and a corresponding coefficient carried by conductor subgroup  628  for C 1,h . The differences produced by subtraction circuit  658  are carried by electrical conductors  678  and represent the coefficients for the lower n/2 powers of x. Electrical conductors  676  are input to addition circuit  660  together with conductor subgroup  626 . Addition circuit  660  adds each coefficient carried by electrical conductors to a corresponding coefficient carried by conductor subgroup  626  for C 1,l . The sums produced by addition circuit  660  are carried by electrical conductors  680  and represent coefficients for powers of x between n/2 and n−1. Electrical conductors  680  and  678  are combined into a larger conductor group  682  representing the result consisting of n coefficients. 
     Dedicated subtraction circuit  650  and dedicate addition circuit  652  form a respective difference and sum that are used multiple times. In particular, the outputs of dedicated difference circuit  650  and dedicated addition circuit  652  are applied to both dedicated addition circuit  654  and dedicated difference circuit  656  and thus are determined once but are used twice. In addition the output of addition circuit  652  is used as part of implementing the modulo x n +1 operation. As shown in  FIG.  1 B , the modulo x n +1 operation involves subtracting C 2,h  to form the higher coefficients of the result and adding C 0,l  to form the lower coefficients of the result. In  FIG.  6   , C 0,l  and C 2,h  are provided as input to addition circuit  652  and the resulting sum of circuit  652  is used to perform the modulo x n +1 operation through its application to dedicated addition circuit  654  and dedicated subtraction circuit  656 . Thus, the first coefficients of the product and the last coefficients of the product are used to form a difference and sum that are each used multiple times. This reduces the number of additions that must be performed and thereby improves the device. 
     Although the embodiment of  FIG.  6    shows each addition being performed by a separate dedicated adder, in other embodiments a single adder is provided and is time-multiplexed to perform all of the addition operations described above. 
     Although an embodiment is described above that uses dedicated hardware to optimize performance, the embodiments described above may also be applied to a software implementation on a computer. In such embodiments, a processor executes instructions stored in a memory to implement the steps described in  FIG.  5   . The reduction in the number of additions performed to determine the modulo x n+1  of the product of two polynomials that is provided by the various embodiments, improves the operation of the computer by allowing the computer to obtain the result faster than it could without the embodiments described above. As such, the embodiments represent a technical solution to the technical problem of slow running computers. 
     Although elements have been shown or described as separate embodiments above, portions of each embodiment may be combined with all or part of other embodiments described above. 
     Although the subject matter has been described in language specific to structural features and/or methodological acts, it is to be understood that the subject matter defined in the appended claims is not necessarily limited to the specific features or acts described above. Rather, the specific features and acts described above are disclosed as example forms for implementing the claims.