Method and apparatus for finite field multiplication

Abstract

A method of computing the product D of two finite field elements B and C modulo an irreducible polynomial f 1 (x), wherein the finite field elements B and C are represented in terms of an optimal normal basis (ONB) of Type 1 over a field F 2 n and the irreducible polynomial f 1 (x) being of degree n, which comprises the steps of representing the element B as a vector of binary digits b i , where b i is a co-efficient of an i th basis element of the ONB representation of element B, in polynomial order, representing the element C as a vector of binary digits c i , where c i is a co-efficient of an i th basis element of the ONB representation of element C, arranged in polynomial order, initializing a register A, selecting a digit c i of vector C, computing a partial product vector A of the i th digit c i of the element C and the vector B, adding the partial product to the register A, shifting the register A, reducing the partial product A by a multiple f 2 (x) of the irreducible polynomial f 1 (x) if bits in a position above n are set, storing the reduced partial product in the register A, repeating for each successive bit of the vector C and upon completion the register A containing a final product vector; and reducing the final product vector A by the irreducible polynomial f 1 (x) if an n th bit of the register is set. The reduction step by the multiple of the irreducible polynomial simply involves a shift operation performed on the partial products.

The embodiments of the invention in which an exclusive property or privilege is claimed are defined as follows:  
     
         1 . A computer system for determining the product of two finite field elements B and C modulo an irreducible polynomial f 1 (x), wherein the finite field elements B and C are represented in terms of an optimal normal basis (ONB) of Type 1 over a field F 2     n    and said irreducible polynomial f 1 (x) being of degree n, comprising: 
 (a) a memory containing a first vector of binary digits b i , where b i  is a co-efficient of the i th  basis element of said ONB representation of element B, arranged in polynomial order;     a second vector of binary digits c i , where c i  is a co-efficient the i th  basis element of said ONB representation of element C, arranged in polynomial order;     a computer program having functions for invocation, said functions for computing a partial product of a multiplier with a multiplicand and for reducing said partial product by a multiple of said irreducible polynomials f 1 (x);    (b) a control program for invoking said functions; and    (c) a processor for running said computer program.    
     
     
         2 . A method of determining the product of two finite field elements B and C modulo an irreducible polynomial f 1 (x) in a computer system having a computer program with functions for invocation and a control program for invoking said functions, said finite field elements B and C being represented in terms of an optimal normal basis of Type 1 over a field F 2     n    and said irreducible polynomial f 1 (x) being of degree n, and said field elements B and C being represented as a vector of binary digits, each digit being the co-efficient of the elements arranged in polynomial order, said method comprising: 
 (a) invoking a function to compute the partial product of said element B with a selected digit of said element C;    (b) monitoring an overflow bit of said partial products;    (c) invoking a function for reducing said partial products by a multiple f 2 (x) of the irreducible f 1 (x) when said overflow occurs and deriving a reduced partial product therefrom;    (d) adding said reduced partial product to said successive partial product;    (e) continuing said steps (c) and (d) for successive digits of said element C to derive a final product;    (f) reducing said final product by said irreducible f 1 (x) if said n th  bit is set.    
     
     
         3 . A method of computing the product D of two finite field elements B and C modulo an irreducible polynomial f 1 (x), wherein the finite field elements B and C are represented in terms of an optimal normal basis (ONB) of Type 1 over a field F 2     n    and said irreducible polynomial f 1 (x) being of degree n, said method comprising the steps of: 
 (a) representing the element B as a vector of binary digits b i , where b i  is a co-efficient of an i th  basis element of said ONB representation of element B, in polynomial order;    (b) representing said element C as a vector of binary digits c i , where c i  is a co-efficient of an i th  basis element of said ONB representation of element C, arranged in polynomial order;    (c) initializing a register A;    (d) selecting a digit c i  of said vector C;    (e) computing a partial product vector A of said i th  digit c i  of said element C and the vector B;    (f) adding said partial product to said register A;    (g) shifting said register A    (h) reducing said partial product A by a multiple f 2 (x) of the irreducible polynomial f 1 (x) if bits in a position above n are set;    (i) storing said reduced partial product in said register A;    (j) repeating said steps (e) to (h) for each of said successive bit of said vector C and upon completion said register A containing a final product vector; and    (k) reducing said final product vector A by said irreducible polynomial f 1 (x) if an n th  bit of said register is set.    
     
     
         4 . A method as defined in    claim 3   , said reducing said partial product A includes shifting said bits greater than n to said lower most bit positions and adding said bits thereto.  
     
     
         5 . A method as defined in    claim 4   , said shifting being performed on a word length of bits.  
     
     
         6 . A method as defined in    claim 5   , said adding being an XORing.  
     
     
         7 . A method as defined in    claim 3   , said reducing said partial product A includes testing said (n+1)th bit and shifting said bit said lower most bit positions and adding said bit thereto.  
     
     
         8 . A method as defined in    claim 3   , including storing said vector B in a register.  
     
     
         9 . A method as defined in    claim 3   , said multiple f 2 (x) being represented by f 2 (x)=(x+1)f 1 (x).  
     
     
         10 . A method as defined in    claim 3   , said reducing said final partial product A comprises complementing said component bits to thereby reduce said result to degree (n−1).  
     
     
         11 . A method as defined in    claim 3   , including the step of adding said irreducible f 1 (x) to said vector B if the number of ones (1) bits of said vector is greater than n/2.  
     
     
         12 . A method as defined in    claim 11   , said step comprising complementing said bits upto said component of degree n.  
     
     
         13 . A method as defined in    claim 3   , said bits c i  being selected in decreasing significance.  
     
     
         14 . A method as defined in    claim 3   , said I th  basis element having a form a 2′ .  
     
     
         15 . A finite field multiplier for computing the product D of two finite field elements B and C modulo an irreducible polynomial f 1 (x), wherein the finite field elements B and C are represented in terms of an optimal normal basis (ONB) of Type 1 over a field F 2     n    and said irreducible polynomial f 1 (x) being of degree n, comprising: 
 a) a register B for holding the digits b i  of a vector of binary digits b i , where b i  is a co-efficient of an i th  basis element of said ONB representation of said element B, arranged in polynomial order;    b) an shift register A for holding a result of said computation and of size at least greater than the degree n of the finite field and for shifting its contents in response to a shift control signal;    c) means for sequentially selecting digits c i  of a vector of binary digits c i , where c i  is a co-efficient of an i th  basis element of said ONB representation of said element C, arranged in polynomial order, and for generating an add control signal in response to said digit c i  being set; and    d) an arithmetic logic unit (ALU) having a finite field adder circuit responsive to said add control signal, for adding said register B and said register A received as vectors of binary digit inputs and outputting a result of said addition to said shift register A thereby computing a partial product vector A of said i th  digit c i  of said element C and the vector B while adding said result to a previous partial product in said register A and whereby said successive partial products may be reduced by a multiple f 2 (x) of the irreducible polynomial f 1 (x) if bits (n+1) or greater are set by shifting said upper (n+1) bits to a lowermost (n+1) bits of said register A; said reduced partial products being computed for successive components of said vector C and upon completion said register A containing a final product vector and said final product vector A being reduced by said irreducible polynomial f 1 (x) if an n th  bit of said register is set by applying said complement signal such that said register A represents said product of said two finite field elements B and C modulo f 1 (x).    
     
     
         16 . A method of squaring a finite element B modulo an irreducible polynomial f 1 (x), wherein the finite field elements B is represented in terms of an optimal normal basis (ONB) of Type 1 over a field F 2     n    and said irreducible polynomial f 1 (x) being of degree n, said method comprising the steps of: 
 a) representing the element B as a vector of binary digits b i , where b i  is a co-efficient the i th  basis element of said ONB representation of element B, arranged in polynomial order;    b) interleaving the binary digits of the representation of element B with zero digits to derive a square thereof;    c) storing in successive cells of a 2n cell shift register the binary digits of the interleaved representation of the element B;    d) reducing said square by a multiple f 2 (x) of the irreducible polynomial f 1 (x).    
     
     
         17 . A method as defined in    claim 16   , said reduction is a cyclic shift of an upper n bits to the lower n bits.  
     
     
         18 . A method of squaring a finite element B modulo an irreducible polynomial f 1 (x), wherein the finite field elements B is represented in terms of an optimal normal basis (ONB) of Type 1 over a field F 2     n    and said irreducible polynomial f 1 (x) being of degree n, said method comprising the steps of: 
 a) representing the element B as a vector of n binary digits b i , where b i  is a co-efficient the i th  basis element of said ONB representation of element B, arranged in decreasing polynomial order;    b) selecting successive word length sets of said representation;    c) interleaving the binary digits of each said words with zero digits;    d) storing an xor of alternate sets of interleaved words in a register for all such sets; and    e) permuting said stored words to derive a square of said element B therefrom.