Abstract:
Improved multiplier construction methods facilitate efficient multiplication in finite fields. Implementations include digital logic circuits and user scaleable software. Lower logical circuit complexity is achieved by improved resource sharing with subfield multipliers. Split-optimal multipliers meet a lower bound measuring complexity. Multiplier construction methods are applied repeatedly to build efficient multipliers for large finite fields from small subfield components. 
     An improved finite field construction method constructs arbitrarily large finite fields using search results from a small starting field, building successively larger fields from the bottom up, without the need for successively larger searches. The improved method constructs arbitrarily large finite fields with limited construction effort using a polynomial constant equal to the product of a deterministic product term and a selectable small field scalar. The polynomials used in the improved method feature sparse constants facilitating low complexity multiplication.

Description:
FIELD OF THE INVENTION 
       [0001]    The invention relates generally to error correction and encryption coding of data in digital communications using finite fields, and particularly to a method and apparatus for efficient multiplication in finite fields and a method for construction of arbitrarily large finite fields. 
       BACKGROUND OF THE INVENTION 
       [0002]    A multiplier for complex numbers may be implemented by combining the outputs of smaller multipliers operating over the subfield of real numbers. A complex number, A, may be represented as a two-component vector {a 1 , a 0 } in a hypothetical computer, with the understanding that complex A may be regarded as a polynomial over the real numbers, 
         [0000]        A ( j )= a   1   j+a   0   =Im[A]j+Re[A]   
         [0000]    where a 0  and a 1  are real. Recall that the complex product C=AB is given by 
         [0000]        C ( j )= c   1   j+c   0   ={a   1   b   0   +a   0   b   1   }j+{a   0   b   0   −a   1   b   1 }. 
         [0000]    The relationship may be expressed as 
         [0000]        C ( j )= A ( j )  B ( j )modulo p ( j ), 
         [0000]    where p(x) is an irreducible polynomial of degree two over the real numbers, 
         [0000]        p ( x )= x   2 +1, 
         [0000]    and j is assumed to be a root of p(x). 
         [0003]    A first method of determining the complex product determines four real products {a 1 b 0 , a 0 b 1 , a 0 b 0 , and a 1 b 1 } and combines the products using a real addition and a real subtraction. In the hypothetical computer, m binary bits represent a real number, and the space-time complexity of a real m-bit multiplier is approximately m 2 , whereas the complexity of real addition, km, is relatively small. The space-time complexity of the complex 2m-bit multiplier by this first method is approximately 4 m 2  for larger in. 
         [0004]    Methods of determining a complex product using only three real multiplications have been known since the 1950s. A discussion is in  Fast Algorithms for Digital Signal Processing , Richard E. Blahut, pp. 1-19, ISBN 0-201-10155-6, Addison-Wesley, Reading Mass. (1985). A second method of determining the complex product computes two real additions, three real multiplications, and two real subtractions, s 0 =a 1 +a 0 , s 1 =b 1 +b 0 , m 1 =s 0  s 1 ,m 2 =a 1  b 1 , m 3 =a 0 b 0 , c 0 =m 3  m 2 , and c 1 =m 1  c 0 . The space-time complexity using this second method is approximately 3 m 2  for larger in. 
         [0005]    A similar algorithm may be used to reduce the complexity of multipliers for finite fields, which are also known as Galois fields, in honor of the mathematician Evariste Galois. Early references include  Sur la theorie des nombres, Bull Sci. Math. de M. Ferussac  13, 428-435 (1830),  J. Math. Pures Appl.  11, 398-407 (1846), and  Oeuvres math., pp.  15-23, Gauthier-Villars, Paris, 1987. 
         [0006]    A field with q elements is denoted GF(q); the smallest finite field is the field GF(2). The finite fields constructed here are extension fields of GF(2) with m-bit symbols, denoted GF(2 m ). These fields are known as fields of characteristic two, defined as a field where A+A=0 for any field symbol A. In these fields, addition is the same as subtraction. 
         [0007]    It turns out that a minimal complexity multiplier for a finite field with a small number of bits per symbol, i.e. in &lt;6, typically uses a standard field representation, sometimes referred to in the literature as an “alpha-basis” or “canonical” representation. In a canonical representation for GF(2 m ), a symbol B is represented by in bits, denoted b 0  to b m-1  here, and a distinguished element alpha (α) is defined with the understanding that 
         [0000]        B=b   0   +b   1   α+b   2 α 2   + . . . +b   m-1 α m-1 .
 
         [0000]    A small canonical multiplier for m-bit symbols requires (4m 2 −3) gate-area units as counted here. For example, a one-bit multiplier for GF(2) is implemented as a logical AND gate, whose complexity is counted as one gate-area unit here. A one-bit adder for GF(2) is assumed to have greater complexity; it is implemented as a logical exclusive-or (XOR) gate, 
         [0000]        a+b=a XOR b =( a AND b )NOR( a NOR b ), 
         [0000]    and counted as three gate-area equivalent units here. Prior art implementations for subfields with m=2, 3, 4 or 5 are detailed further below and their complexity is summarized in Table 1. 
         [0000]    
       
         
               
             
               
               
               
               
               
               
             
               
               
               
               
               
               
             
           
               
                 TABLE 1 
               
             
             
               
                   
               
               
                 Minimal complexity canonical multipliers for small fields 
               
             
          
           
               
                   
                 m 
                 Finite Field 
                 AND gates 
                 XOR gates 
                 Gate-area units 
               
               
                   
               
             
          
           
               
                   
                 1 
                 GF(2)  
                 1 
                 0 
                 1 
               
               
                   
                 2 
                 GF(4)  
                 4 
                 3 
                 13 
               
               
                   
                 3 
                 GF(8)  
                 9 
                 8 
                 33 
               
               
                   
                 4 
                 GF(16) 
                 16 
                 15 
                 61 
               
               
                   
                 5 
                 GF(32) 
                 25 
                 24 
                 97 
               
               
                   
               
             
          
         
       
     
         [0008]    A non-standard “split-field” multiplier may become a less complex alternative when the number of bits per symbol is even and at least six. A lower bound on the complexity of split-field multipliers is the combined complexity of three subfield multipliers and four subfield adders. If six bit symbols for GF(64) are split into two three-bit symbols over the subfield GF(8), for example, the lower bound using three GF(8) multipliers and four GF(8) adders is 135 gate-area units. A canonical multiplier for GF(64) is larger, using 141 gate-area units. In order to achieve the potential savings, an improved split-field multiplier whose complexity meets the lower bound is desired. 
         [0009]    A prior art split-field multiplier is used to develop the lower bound and compared with an improved multiplier below. The prior art multiplier is shown as FIG. 8c in U.S. Pat. No. 4,958,348,  Hypersystolic Reed - Solomon Decoder , Berlekamp et al. (1988), and discussed on pp. 4-5 of U.S. Pat. No. 5,689,452,  Method and apparatus for performing arithmetic in large Galois field  GF(2 n ), Cameron (1994). The multiplier uses a split-field representation, where an element (or “symbol”) in a finite field G with 2m-bit symbols has each symbol represented as a polynomial over a subfield F with m-bit symbols. It is known that if a quadratic polynomial 
         [0000]        p ( x )= p   2   x   2   +p   1   x+p   0    
         [0000]    is irreducible over the field F, i.e. it has no roots in F, an irreducible polynomial of the form 
         [0000]        q ( x )= x   2   +x+β   
         [0000]    may be derived from p(x), where β is an element of F. The prior art multiplier uses an irreducible polynomial of the q(x) form. According to the teaching of the &#39;452 patent, the limitation of form is not significant because an arbitrary primitive polynomial of degree two may be converted to the desired form through an algebraic transformation. 
         [0010]    Let ω be a root of q(x). Symbols A and B from G are represented as 
         [0000]        A (ω)= a   1   ω+a   0  
 
         [0000]        B (ω)= b   1   ω+b   0  
 
         [0000]    where a 1 , a 0 , b 1 , and b 0  are elements of F. The polynomial product 
         [0000]        A (ω) B (ω)= a   1   b   1 ω 2   +{a   1   b   0   +a   0   b   1   }ω+a   0   b   0  
 
         [0000]    is reduced modulo q(ω) to a polynomial of degree one or less. Because ω is a root of q(x), ω 2 +ω+β=0, and it follows that C(ω)=c 1 ω+c 0 , where 
         [0000]        c   1   =a   1   b   0   +a   0   b   1   +a   1   b   1 , and 
         [0000]        c   0   =a   0   b   0   +βa   1   b   1 . 
         [0011]    The desired product may be determined as follows: 
         [0000]        t   0   =a   1   +a   0 , 
         [0000]        t   1   =b   1   +b   0 , 
         [0000]        m   1   =t   0   t   1 , 
         [0000]        m   2   =a   1   b   1 , 
         [0000]        m   3   =a   0   b   0 , 
         [0000]        c   0   =m   3   +βm   2 , and 
         [0000]        c   1   =m   1   +m   3 . 
         [0000]    The multiplier for the field G using this prior art method has the complexity of three full multipliers and four adders for the field F plus the additional complexity, if any, of the constant multiplier used to multiply by β. 
         [0012]    Field construction is discussed in “ A New Architecture for a Parallel Finite Field Multiplier with Low Complexity Based on Composite Fields ,” C. Paar,  IEEE Trans. Computers , pp. 856-861, Vol. 45, No. 7, July 1996. Paar attributes the prior art method discussed above to V. Afanasyev, “ On the Complexity of Finite Field Arithmetic,” Proc. Fifth Joint Soviet - Swedish Int&#39;l. Workshop Information Theory , pp. 9-12, Moscow, USSR, January 1991. 
         [0013]    The prior art method may be applied repeatedly to produce large finite fields as discussed further below. As a simple example, consider an m-bit symbol field F which has been extended to a 2m-bit symbol field G using a first irreducible polynomial q(x) of degree two over F. A second, 4m-bit symbol extension field H is to be constructed using a second application of the method. Paar teaches that the field G is exhaustively searched to determine those primitive polynomials q(x) with a minimum complexity with respect to constant multiplication by β (see p. 859). 
         [0014]    Repeated application of the prior art method requires an ability to repeatedly search and identify a next member in a sequence of successive irreducible quadratic polynomials over larger and larger fields. To select the next sequence member, Paar further requires that all primitive polynomials in the set of possible irreducible quadratic polynomials be identified and that these polynomials are sorted for minimum multiplier complexity. He does not teach or suggest a method of repeatedly constructing extension fields without a plurality of searches for suitable polynomials. The search process becomes exponentially time consuming for large finite fields, limiting the size of finite fields which can be practically constructed using this prior art method. Instead, a general method to provide a sequence of extension polynomials facilitating minimal complexity multiplication without repeated searching is desired. 
       BRIEF SUMMARY OF THE INVENTION 
       [0015]    The invention incorporates an improved method of representing a finite field as an extension field, facilitating minimally complex multipliers for GF(2 2m ). The improved methods are implemented in improved integrated circuits with low gate-area and are suitable for efficient implementations in software on a general-purpose computer. A “spit-optimal” multiplier meets a lower bound on the gate-area complexity, constructed with the gate area of three full subfield multipliers and four subfield adders, and no additional gates. An improved method and apparatus for multiplying provide improved support for split-optimal multipliers and efficient multiplication. The method of multiplication facilitates efficient multiplicative inversion. 
         [0016]    A related method of repeatedly extending a small finite field to construct an arbitrarily large finite field is also disclosed. Split-optimal and nearly split-optimal solutions are disclosed for a wide variety of finite fields, in the range of four to 512 bits per symbol. The improved method facilitates construction of minimally complex multipliers for large finite fields by explicitly providing improved resource sharing to implement constant multipliers, and by utilizing particular polynomials with almost all-zero constants. The use of these constants facilitates efficient software implementations. Other desirable properties are incorporated in the constructed finite fields. 
     
    
     
       BRIEF DESCRIPTION OF THE SEVERAL VIEWS OF THE DRAWING 
         [0017]      FIG. 1  is an example schematic of hierarchical circuitry to multiply in an extension field, divided into three example levels of hierarchy. 
           [0018]    An example first (or bottom) level of hierarchy for a finite field multiplier is shown in  FIG. 1A . The circuit contains modifications to a canonical subfield multiplier that add one or more auxiliary outputs to explicitly provide resource sharing for a successive level of hierarchy. 
           [0019]    An example last (or top) level of hierarchy for a finite field multiplier is shown in  FIG. 1B . The multiplier circuit for an extension field includes three subfield multipliers and four subfield adders. An auxiliary output of a subfield multiplier provides a constant multiplication. 
           [0020]    An example middle level of hierarchy for a finite field multiplier containing three or more levels of hierarchy is shown in  FIG. 1C . An auxiliary output is added to the circuitry of  FIG. 1B  to explicitly provide resource sharing for a successive level of hierarchy. 
           [0021]      FIG. 2  is a flowchart representing a method of constructing arbitrarily large finite fields. 
       
    
    
     DETAILED DESCRIPTION OF THE INVENTION 
       [0022]    A.1. Improved Split-Field Multiplication 
         [0023]    Assume that finite field G has a split-field representation where each 2m-bit symbol is represented as a polynomial over a subfield F with m-bit symbols. In the field F, select an irreducible polynomial of the form 
         [0000]        r ( x )= x   2   +γx+y=x   2 +γ( x+ 1)
 
         [0000]    where γ is an element of F. Preferably, the polynomial r(x) is selected so that the coefficient γ facilitates low complexity constant multiplication, as shown further below. 
         [0024]    Let ω be a root of r(x). Symbols A and B from G are represented as 
         [0000]        A (ω)= a   1   ω+a   0  
 
         [0000]        B (ω)= b   1   ω+b   0  
 
         [0000]    where a 1 , a 0 , b 1 , and b 0  are elements of F. The polynomial product 
         [0000]        A (ω)  B (ω)= a   1   b   1 ω 2   +{a   1   b   0   +a   0   b   1   }ω+a   0   b   0 .
 
         [0000]    is reduced modulo r(ω) to obtain C(ω)=C 1 ω+c 0 , where 
         [0000]        c   1   =a   1   b   0   +a   0   b   1   +γa   1   b   1 , and 
         [0000]        c   0   =a   0   b   0   +γa   1   b   1 . 
         [0025]    The desired product may be determined as follows: 
         [0000]        m   1   =a   0   b   1 , 
         [0000]        t   0   =γb   1   +b   0 , 
         [0000]        t   1   =a   1   +a   0 , 
         [0000]    
       
      
       m 
       2 
       =a 
       1 
       t 
       0  
      
     
         [0000]    
       
      
       m 
       3 
       =b 
       0 
       t 
       1  
      
     
         [0000]        c   0   =m   3   +m   2 , and 
         [0000]        c   1   =m   1   +m   2 . 
         [0026]    These equations incorporate the complexity of three full subfield multipliers and four subfield adders plus the additional complexity, if any, of a constant multiplier for γ. All operations are performed over the subfield F. 
         [0027]      FIG. 1B  is a schematic of a multiplier circuit  200  for G to implement these equations without additional complexity for the constant multiplier. The circuit  200  multiplies a first input symbol A  201  by a second input symbol B  202  to produce a product symbol AB  203 . Symbols A, B and AB are elements of G, each symbol represented by 2m bits. The circuit  200  contains three m-bit subfield multipliers for the field F, a first multiplier  209  with output m 1    211 , a second multiplier  209  with output m 2    212 , and a third multiplier  209  with output m 3    213 . Circuit  200  also contains four adders  210  for the field F. A first adder  210  outputs t 0  and a second adder  210  outputs t 1 . The remaining two adders  210  output the two components of the product, c 0    215  and c 1    214 , which are combined in the 2m-bit output symbol AB  203 . 
         [0028]    In  FIG. 1B , the input symbol A  201  is partitioned into two m-bit symbols from F, a 0    204  and a 1    205 . Similarly, input symbol B  202  is partitioned into b 0    206  and b 1    207  from F. Various circuit interconnections within  FIG. 1B  are not shown to improve clarity; they are indicated by labeling of signal sources and sinks Symbol a 0    204 , for example, is sourced at the partitioning of bus  201  and connected to sinks at the U input of the first multiplier  209  and the second input of the second adder  210 . Similarly, a 1    205  is connected to the U input of the second multiplier  209  and the first input of the second adder  210 . 
         [0029]    Note that the first subfield multiplier  209  has an input operand, b 1    207 , and a first subfield adder  210  has the same input operand b 1    207 , but scaled by γ n−1  in signal  208 . Often, an auxiliary output  208  of the first subfield multiplier can be used as a source for the scaled operand with negligible additional cost, as demonstrated in the following sections. 
         [0030]    A.2. Resource Sharing with a Canonical Subfield 
         [0031]    Lets first consider a finite field G in a split-field representation where the subfield F is an m-bit subfield in a canonical representation, with m=2, 3, 4, or 5. Each symbol A in the field F is represented by m binary coefficients {a m-1 , . . . , a 1 , a 0 } and associated with a polynomial 
         [0000]        A (α)= a   0   +a   1 α+ . . . +a m-1 α m-1 ,
 
         [0000]    where α is a root of p(x), an irreducible polynomial of degree m over GF(2). Lists of suitable binary irreducible polynomials may be found in W. Wesley Peterson and E. J. Weldon, Jr.,  Error - Correcting Codes, Second Edition , Appendix C, pp. 472-492, ISBN 0-262-16-039-0, The MIT Press, Cambridge, Mass. (1980). 
         [0032]    Preferably, the polynomial p(x) has a minimum number of nonzero coefficients, resulting in simpler reduction modulo p(x). Preferred trinomials of the form 
         [0000]        p ( x )= x   m   +x+ 1 
         [0000]    are irreducible over GF(2) and result in minimal complexity multipliers with minimal delay for the field F when m=2, 3, or 4. When m=5, a preferred trinomial, p(x)=x 5 +x 3 +1, may be used instead. 
         [0033]    In some applications, it is preferred that the polynomial p(x) is a primitive polynomial, defined as follows. Let polynomial p(x) be an irreducible over a field F, and let ω be a root of p(x). The polynomial is used to generate a field G, each element of G representing an equivalence class of polynomials modulo p(ω) over F. Suppose that G has N distinct symbols. The polynomial p(x) is considered primitive over F if the powers of ω modulo p(ω), i.e. ω 1  modulo p(ω), ω 2  modulo p(ω), ω 3  modulo p(ω), and so on, are the N−1 distinct nonzero elements of the field G. In this case, the polynomial root, w, is known as a primitive element of the field G and can be used as a base for logarithm and antilog tables. Each of the example polynomials above, for m in the range of two to five, is primitive over the field GF(2). 
         [0034]    A minimal complexity subfield multiplier for a canonical subfield F is modified to be suitable for the purposes here in building larger fields. An example modified subfield multiplier  100  is shown in  FIG. 1A . If U and T are symbols of F with the understanding that a symbol such as U is regarded as a polynomial, 
         [0000]        U (α)= u   0   +αu   1 + . . . +α m-1   u   m-1 ,
 
         [0000]    then it follows that the product of U and T, 
         [0000]        U (α) T (α)modulo p (α)= u   0   T (α)
 
         [0000]      + u   1   {αT (α)modulo p (α)}
 
         [0000]      + . . . 
         [0000]      + u   m-1 {α m-1   T (α)modulo p (α)}.
 
         [0035]    The coefficients of the term [α k  T(α) modulo p(α)] may be determined from the coefficients of the previous term, [α k-1  T(α) modulo p(α)], by multiplying by α and reducing modulo p(α). For example, if the binary m-tuple 
         [0000]      { v   m-1   , . . . ,v   1   ,v   0 } 
         [0000]    represents an element V of F with m=2, 3, or 4, the element {αV modulo p(α)} is represented by 
         [0000]      { v   m-2   , . . . ,v   1   ,v   m-1   +v   0   ,v   m-1 } 
         [0000]    The scaled element can be implemented using one XOR gate and a rearrangement of bits. Each circled “α” represents an α-multiplier  103  in  FIG. 1A  and implements a multiplication by α and reduction modulo p(α) as described. A first α-multiplier  103  scales input T  102  by a to output a first auxiliary output symbol AUX 1    107 . When m&gt;2, a second α-multiplier  103  outputs a second auxiliary output symbol AUX 2    108 . When m is three or greater, the sequence of α-multipliers continues until the (m−1) th  α-multiplier  103  outputs an (m−1) th  auxiliary output symbol AUX m-1    109 . 
         [0036]    Each sub-product symbol, {u k α k T(α) modulo p(α)}, can then be implemented as a one-by-m product using m parallel AND gates with a common input u k  and an m-bit input {α k T(α) modulo p(α)}. In  FIG. 1A , input U  101  feeds bus separator  104 , providing the individual bits of U to produce a plurality of one-by-m sub-products in sub-circuits labeled “one-by-m”  105 . Finally, the various sub-products are summed using an array of XOR gates  106  to output the product UT  110 . 
         [0037]    For example,  FIG. 1A  illustrates a best prior art multiplier for GF(16) constructed using p(x)=x 4 +x+1, a primitive polynomial over GF(2). The two inputs to the subfield multiplier, U and T, are 4-bit symbols, depicted as thicker m-bit wide busses in  FIG. 1A . Three XOR gates and bit rearrangements provide a chain of three multiplications by α as described above. Sixteen AND gates implement four one-by-four multiplications, and twelve XOR gates are used to produce the sum of the four sub-products. 
         [0038]    When a canonical multiplier is used as a subfield multiplier in a larger field multiplier, the subfield multiplier is explicitly modified to support resource sharing in the larger multiplier by providing useful auxiliary outputs, such as those shown in  FIG. 1A . Preferably, scaling of one subfield multiplier input by γ is provided as an auxiliary output of a subfield multiplier. The modified subfield multiplier of  FIG. 1A , explicitly outputting the scaling of input T  102  by a plurality of low powers of α, provides one or more useful auxiliary outputs for those purposes here. When used as a subfield multiplier for GF(16), for example, it provides three possible constant multiplications in auxiliary outputs, AUX 1    107 , AUX 2    108 , and AUX 3    109 , at no additional gate-area cost. 
         [0039]    In various examples below, one or more auxiliary outputs may be left unused, or there may be additional auxiliary outputs referred to but not shown in  FIG. 1A , where the number of auxiliary outputs is m−1. For example, consider a GF(4) subfield multiplier with two-bit wide inputs, U  101  and T  102 . The two-bit input vector T may be denoted {t 1 , t 0 }. One scaled input, 
         [0000]      α T (α)modulo p (α),
 
         [0000]    —the vector {t 1 +t 0 , t 1 }—is an internally available scaled input that can be explicitly provided as a first auxiliary output, AUX 1 ={t 1 +t 0 , t 1 }. In addition, another low α-power scaling of the input T, 
         [0000]      α 2   T=α   2   T (α)modulo p (α)= t   0 α+( t   1   +t   0 ),
 
         [0000]    can be provided as a second auxiliary output, AUX 2 ={t 0 , t 1 +t 0 }, at negligible gate-area cost by reusing the output of the (t 1 +t 0 ) XOR gate and arranging output bits accordingly. 
         [0040]    To continue with this example, suppose that a GF(16) multiplier is then constructed using the split-field representation over GF(4). An irreducible polynomial r(x) over GF(4) of the form 
         [0000]        r ( x )= x   2   +γx+γ   
         [0000]    is chosen to generate G as an extension field of F, preferably with multiplication by γ facilitated by one or more auxiliary outputs of the subfield multiplier. Here, the selection of a polynomial r(x) with either {γ 0 =α} or {γ 0 =α 2 } provides a primitive polynomial for constructing G. By using a modified canonical subfield multiplier for GF(4)  100  with two corresponding auxiliary outputs as multiplier  209  in  FIG. 1B , the constant multiplication for either polynomial can be provided at no additional cost in multiplier  200 , providing a split-optimal multiplier for GF(16). In this case,  FIG. 1B  represents a GF(16) multiplier where the internal components of the multiplier operate over GF(4). 
         [0041]    Note that, as a first approximation of complexity, only additional gates are counted here. Additional complexity costs of buffering signals, of providing additional outputs, and of routing additional signals are mostly ignored here. 
         [0042]    This example split-optimal multiplier is considered the best design here for a split-field representation of GF(16), meeting the lower bound by using only three GF(4) multipliers and four GF(4) adders to implement the GF(16) multiplier. The complexity of the improved split-field design is 63 gate-area units. 
         [0043]    As a final complexity check, the best split-field design for GF(16) is compared to other multipliers for GF(16), such as a smaller canonical GF(16) multiplier using 61 gate-area units. When the gate area is equal or nearly equal, other issues may arise. In some applications, implementations using only primitive polynomials may be preferred or required. A circuit for a low complexity multiplicative inverter may be required as well. The suitability of the multiplier for G as a building block in a split-field multiplier for a larger field in a hierarchical design may also be considered. The hierarchical approach is explored further in the following section, and inversion is in the section after that. 
         [0044]    A.3. Resource Sharing with a Split-Field Subfield 
         [0045]    In the previous section, a first extension field G is constructed as a split-field representation over a canonical field F. In this section, lets denote the first field F as G 0 , and the first extension field, G, as G 1 . The approach advocated here provides optimal and near-optimal split-field multipliers for fields further extended from G 1 , providing a sequence of fields, G 2 , G 3 , and so on, each with a successive doubling of the field symbol size. In a multi-layer hierarchical design,  FIG. 1B  may be regarded as an Nth (or last or top) layer for multiplying in a largest successor field G N . In this section, a modified middle layer explicitly supports resource sharing in a hierarchical design with at least three layers. 
         [0046]    For example, G 1  may be constructed with a split-field multiplier as in the previous section with 4, 6, 8, or 10 bit symbols, as an extension field of G 0 , a canonical subfield F. In this case, a first extension polynomial r 0 (x)=x 2 +γ 0 x+γ 0  with root ω 0  is assumed to generate G 1 . The G 1  multiplier is modified to explicitly support a G 2  multiplier with 8, 12, 16, or 20 bit symbols. In this case, the G 2  hierarchical design would have three layers. 
         [0047]    The 2m-bit split-field multiplier of  FIG. 1B  for a field G, may be modified to explicitly support a 4m-bit multiplier for a successor split-field G n+1 . Each symbol A in the field G n  is represented by two m-bit coefficients {a 1 , a 0 } and associated with a polynomial 
         [0000]        A (ω n−1 )= a   0 +ω n−1   a   1 ,
 
         [0000]    where ω n−1  is a root of r n−1 (x)=x 2 +γ n−1 x+γ n−1 , an irreducible polynomial of degree two over a subfield G n−1 . 
         [0048]    A polynomial of the form 
         [0000]        r   n ( X )= x   2 +γ n   x+γ   n  
 
         [0000]    is irreducible over G n  and is used to generate G n+1 . Generally, the polynomial r n (x) is selected so that the constant multiplication by γ n  is easily implemented. 
         [0049]    In preferred embodiments, the constant γ n  has a minimum number of nonzero coefficients. The constant γ n  is an element of G n , with components {f 0 ,f 1 } and associated polynomial representation 
         [0000]      γ n (ω n−1 )= f   0 +ω n−1   f   1  
 
         [0000]    where f 0  and f 1  are symbols of G n−1 . A constant γ n  with f 0 =0 is preferably selected, simplifying multiplication. It turns out that a constant of this form is always available for the fields of interest here. 
         [0050]    For example, if n=1, a preferred γ 1  is of the form 
         [0000]      γ 1 (ω 0 )= s   1 ω 0  
 
         [0000]    where s 1  is a scalar in the field G 0 . To explicitly support a G 2  multiplier, the G 1  multiplier is augmented to provide an auxiliary output corresponding to γ 1 B, 
         [0000]    
       
         
           
             
               
                 
                   
                     
                       
                         γ 
                         1 
                       
                        
                       
                         ( 
                         
                           ω 
                           0 
                         
                         ) 
                       
                     
                      
                     
                       B 
                        
                       
                         ( 
                         
                           ω 
                           0 
                         
                         ) 
                       
                     
                   
                   = 
                     
                    
                   
                     
                       s 
                       1 
                     
                      
                     
                       
                         ω 
                         0 
                       
                        
                       
                         ( 
                         
                           
                             b 
                             0 
                           
                           + 
                           
                             
                               ω 
                               0 
                             
                              
                             
                               b 
                               1 
                             
                           
                         
                         ) 
                       
                     
                   
                 
               
             
             
               
                 
                   = 
                     
                    
                   
                     
                       s 
                       1 
                     
                      
                     
                       { 
                       
                         
                           
                             ω 
                             0 
                           
                            
                           
                             b 
                             0 
                           
                         
                         + 
                         
                           
                             ω 
                             0 
                             2 
                           
                            
                           
                             b 
                             1 
                           
                         
                       
                       } 
                     
                   
                 
               
             
             
               
                 
                   = 
                     
                    
                   
                     
                       s 
                       1 
                     
                      
                     
                       { 
                       
                         
                           
                             ω 
                             0 
                           
                            
                           
                             b 
                             0 
                           
                         
                         + 
                         
                           
                             ( 
                             
                               
                                 
                                   γ 
                                   0 
                                 
                                  
                                 
                                   ω 
                                   0 
                                 
                               
                               + 
                               
                                 γ 
                                 0 
                               
                             
                             ) 
                           
                            
                           
                             b 
                             1 
                           
                         
                       
                       } 
                     
                   
                 
               
             
             
               
                 
                   = 
                     
                    
                   
                     
                       s 
                       1 
                     
                      
                     
                       
                         { 
                         
                           
                             
                               ( 
                               
                                 
                                   
                                     γ 
                                     0 
                                   
                                    
                                   
                                     b 
                                     1 
                                   
                                 
                                 + 
                                 
                                   b 
                                   0 
                                 
                               
                               ) 
                             
                              
                             
                               ω 
                               0 
                             
                           
                           + 
                           
                             
                               γ 
                               0 
                             
                              
                             
                               b 
                               1 
                             
                           
                         
                         } 
                       
                       . 
                     
                   
                 
               
             
           
         
       
     
         [0000]    If an auxiliary output AUX is given by 
         [0000]      AUX(ω 0 )=aux 0 +ω 0 aux 1  
 
         [0000]    then the two components of AUX are 
         [0000]      aux 1   =s   1 (γ 0   b   1   +b   0 ), and
 
         [0000]      aux 0   =s   1 γ 0   b   1 .
 
         [0051]    These components are often available without adding gates to the G 1  multiplier, providing a split-optimal G 2  multiplier. As one example, let G 0  be a canonical representation of the five bit symbol field GF(32), generated by the polynomial 
         [0000]        p ( x )= x   5   +x   3 +1, 
         [0000]    a primitive polynomial over GF(2). Let α be a root of p(x). Let G 1  be a split-field representation of the 10-bit symbol field GF(1024), generated by the polynomial 
         [0000]        r   0 ( x )= x   2 +α 3   x+α   3 ,
 
         [0000]    a primitive polynomial over GF(32). A split-optimal multiplier for the field GF(1024) is constructed as shown in  FIG. 1B  using three GF(32) subfield multipliers, the subfield multiplier  209  that outputs m 1    211  providing a single auxiliary output  208  to scale b 1    207  by α 3 . Let ω 0  be a root of r 0 (x). A preferred choice for extension to 20-bit symbols is 
         [0000]        r   1 ( x )= x   2 +γ 1   x+γ   1  
 
         [0000]    where s 1 =1 and γ 1 =s 1 ω 0 =ω 0 . The polynomial 
         [0000]        r   1 ( x )= x   2 +ω 0   x+ω   0  
 
         [0000]    is primitive over the split-field GF(1024) and can be used to generate GF(2 20 ) with a doubly split-optimal multiplier. The first component 
         [0000]      aux 0 =γ 0   b   1  
 
         [0000]    is available at auxiliary output  208  of  FIG. 1B . The second component 
         [0000]      aux 1   =s   1 (γ 0   b   1   +b   0 )=γ 0   b   1   +b   0  
 
         [0000]    is available at the output t 0  of the first adder  210 , equal to the sum of auxiliary output  208  and b 0    206 . The two components in this case can be combined in an auxiliary output (not shown in  FIG. 1B ) without adding any gates to the G 1  multiplier. The middle layer for the G 2  multiplier, as shown in  FIG. 1B  with five bit G 0  components, is modified to provide the next auxiliary output for the top layer (not shown). The top layer for the G 2  multiplier is also constructed as shown in  FIG. 1B , but with 10-bit G 1  components. 
         [0052]    Another special case (not shown in  FIG. 1B ) for augmenting the G 1  multiplier occurs when s 1  is the multiplicative inverse of γ 0 . In this special case, 
         [0000]      aux 0   =s   1 γ 0   b   1   =b   1  
 
         [0000]    is available as signal  206 , one component of input B  202 . The other component 
         [0000]      aux 1   =s   1 (γ 0   b   1   +b   0 )
 
         [0000]    may be available as an auxiliary output of the second subfield multiplier  209  of  FIG. 1B  with output m 2    212 , which provides an auxiliary output equal to the product of a scalar and the T input, t 0 =γ 0 b 1 +b 0 , if s 1  is one of the available auxiliary output scaling values. 
         [0053]    A third split-optimal case (not shown in  FIG. 1B ) for G 2  occurs when both S 1  and s 1 γ 0  are available scaling values from auxiliary outputs in the subfield multipliers. In this special case, the component aux 0  is typically available as an auxiliary output of the first multiplier  209  with output m 1    211  while component aux 1  is available as an auxiliary output of the second multiplier  209  with output m 2    212 . 
         [0054]    In general, the split-field multiplier for G, provides resources for multiplication by the constant γ n  by supplying one or more auxiliary outputs. An augmented split-field multiplier circuit  300  is shown in  FIG. 1C . Most of the components and signals are the same as those shown in  FIG. 1B . 
         [0055]    In  FIG. 1C , each subfield multiplier  209  for the field for G n−1  is assumed to provide an auxiliary output providing scaling of the T input by 
         [0000]      γ n−1   =s   n−1 Π n−1  
 
         [0000]    where s n−1  is a scalar from G 0 , and the product symbol Π i  is defined by Π 0 =1 and 
         [0000]      Π i =ω i−1 Π i−1  
 
         [0000]    for i&gt;0. The multiplier for G n  is modified to provide an auxiliary output 
         [0000]    
       
         
           
             
               
                 
                   
                     
                       γ 
                       n 
                     
                      
                     B 
                   
                   = 
                     
                    
                   
                     
                       
                         γ 
                         n 
                       
                        
                       
                         ( 
                         
                           ω 
                           
                             n 
                             - 
                             1 
                           
                         
                         ) 
                       
                     
                      
                     
                       B 
                        
                       
                         ( 
                         
                           
                             ω 
                             n 
                           
                           - 
                           1 
                         
                         ) 
                       
                     
                   
                 
               
             
             
               
                 
                   = 
                     
                    
                   
                     
                       s 
                       n 
                     
                      
                     
                       
                         ∏ 
                         n 
                       
                        
                       
                         ( 
                         
                           
                             b 
                             0 
                           
                           + 
                           
                             
                               ω 
                               
                                 n 
                                 - 
                                 1 
                               
                             
                              
                             
                               b 
                               1 
                             
                           
                         
                         ) 
                       
                     
                   
                 
               
             
             
               
                 
                   = 
                     
                    
                   
                     
                       s 
                       n 
                     
                      
                     
                       
                         ∏ 
                         
                           n 
                           - 
                           1 
                         
                       
                        
                       
                         
                           ω 
                           
                             n 
                             - 
                             1 
                           
                         
                          
                         
                           ( 
                           
                             
                               b 
                               0 
                             
                             + 
                             
                               
                                 ω 
                                 
                                   n 
                                   - 
                                   1 
                                 
                               
                                
                               
                                 b 
                                 1 
                               
                             
                           
                           ) 
                         
                       
                     
                   
                 
               
             
             
               
                 
                   = 
                     
                    
                   
                     
                       s 
                       n 
                     
                      
                     
                       
                         ∏ 
                         
                           n 
                           - 
                           1 
                         
                       
                        
                       
                         { 
                         
                           
                             
                               ω 
                               
                                 n 
                                 - 
                                 1 
                               
                             
                              
                             
                               b 
                               0 
                             
                           
                           + 
                           
                             
                               ω 
                               
                                 n 
                                 - 
                                 1 
                               
                               2 
                             
                              
                             
                               b 
                               1 
                             
                           
                         
                         } 
                       
                     
                   
                 
               
             
             
               
                 
                   = 
                     
                    
                   
                     
                       s 
                       n 
                     
                      
                     
                       
                         ∏ 
                         
                           n 
                           - 
                           1 
                         
                       
                        
                       
                         { 
                         
                           
                             
                               ω 
                               
                                 n 
                                 - 
                                 1 
                               
                             
                              
                             
                               b 
                               0 
                             
                           
                           + 
                           
                             
                               ( 
                               
                                 
                                   
                                     γ 
                                     
                                       n 
                                       - 
                                       1 
                                     
                                   
                                    
                                   
                                     ω 
                                     
                                       n 
                                       - 
                                       1 
                                     
                                   
                                 
                                 + 
                                 
                                   γ 
                                   
                                     n 
                                     - 
                                     1 
                                   
                                 
                               
                               ) 
                             
                              
                             
                               b 
                               1 
                             
                           
                         
                         } 
                       
                     
                   
                 
               
             
             
               
                 
                   = 
                     
                    
                   
                     
                       s 
                       n 
                     
                      
                     
                       
                         ∏ 
                         
                           n 
                           - 
                           1 
                         
                       
                        
                       
                         
                           { 
                           
                             
                               
                                 ( 
                                 
                                   
                                     
                                       s 
                                       
                                         n 
                                         - 
                                         1 
                                       
                                     
                                      
                                     
                                       
                                         ∏ 
                                         
                                           n 
                                           - 
                                           1 
                                         
                                       
                                        
                                       
                                         b 
                                         1 
                                       
                                     
                                   
                                   + 
                                   
                                     b 
                                     0 
                                   
                                 
                                 ) 
                               
                                
                               
                                 ω 
                                 
                                   n 
                                   - 
                                   1 
                                 
                               
                             
                             + 
                             
                               
                                 s 
                                 
                                   n 
                                   - 
                                   1 
                                 
                               
                                
                               
                                 
                                   ∏ 
                                   
                                     n 
                                     - 
                                     1 
                                   
                                 
                                  
                                 
                                   b 
                                   1 
                                 
                               
                             
                           
                           } 
                         
                         . 
                       
                     
                   
                 
               
             
           
         
       
     
         [0056]    In a preferred embodiment, the two components of γ n B, 
         [0000]      aux 0   =s   n Π n−1   s   n−1 Π n−1   b   1  and
 
         [0000]      aux 1   =s   n Π n−1 {( s   n−1 Π n−1   b   1   +b   0 ),
 
         [0000]    are available without adding additional gates to the multiplier for G n , providing an auxiliary output to support a split-optimal multiplier for G n+1 . Alternatively, one or more auxiliary outputs of the multiplier G n  are modified or combined to facilitate easy multiplication by γ n  in the multiplier for G n+1 . 
         [0057]    When the field extension method is applied repeatedly, the potential gate area savings of providing multiple auxiliary outputs may be outweighed by the need to accommodate additional bus area and routing for each additional auxiliary output, and the assumption that additional auxiliary outputs can be added without additional cost becomes less valid. 
         [0058]      FIG. 1C  depicts an augmented split-field multiplier  300  demonstrating one method of providing a single useful auxiliary output  306 , an augmentation not shown in  FIG. 1B . The output AUX  306  has been added to provide resource sharing for further levels of hierarchy. In  FIG. 1C , it is assumed that all subfield multipliers  209  provide a single auxiliary output scaling by the same constant, γ n−1 . 
         [0059]    The auxiliary output  303  of multiplier  209  of  FIG. 1C  provides a scaling of the multiplier&#39;s T input, 
         [0000]      γ n−1   t   0   =s   n−1 Π n−1   t   0   =s   n−1 Π n−1 ( s   n−1 Π n−1   b   1   +b   0 )= s   n−1 aux 1   /s   n .
 
       Define 
       [0060]        v   n   =s   n   /s   n−1 . 
         [0000]    If v n  is not one, the component aux 1  can be obtained by re-scaling signal  303  by v n  in a constant multiplier. Similarly, auxiliary output  302  is a scaling of the T input of the third multiplier  209 , 
         [0000]      γ n−1   b   0   =s   n−1 Π n−1   b   0 .
 
         [0000]    The sum of auxiliary output  302  and auxiliary output  303  in a fifth adder  210  of  FIG. 1C  is 
         [0000]        s   n−1 aux 0   /s   n . 
         [0000]    The component aux 0  can be obtained by re-scaling the output of the fifth adder  210  by v n  in a constant multiplier. The two pre-scaled components of the auxiliary output are combined in bus  304 , re-scaled in constant multiplier  305 , and output on AUX  306 . 
         [0061]    As discussed above, a few first layers in a hierarchical design can be split-optimally crafted by appropriately selecting values for γ 1 , γ 2 , and so on to use available resources, and, if necessary, a plurality of auxiliary outputs may be added to explicitly provide resource sharing for one or more additional layers in a similar manner. However, as the number of hierarchical layers increases and the constructed field grows exponentially, so does the additional bus area for additional auxiliary output. For higher levels of hierarchy, using a relatively small number or extra gates to facilitate a chain of constant multiplications from a single auxiliary output, as in  FIG. 1C , may provide a better design tradeoff. 
         [0062]    A.4. Matching Inverter for a Split-Field Multiplier 
         [0063]    When G is in a split-field representation as described here, a low complexity inverter for the field G is available. Let A be a nonzero symbol in a G with 2m-bit split-field symbols, generated by an irreducible polynomial r(x)=x 2 +γx+γ over an m-bit subfield F. Let ω be a root of r(x), and let A be such that 
         [0000]        A (ω)= a   1   ω+a   0 .
 
         [0000]    Let B be the element associated with 
         [0000]        B (ω)= a   1 ω+( a   0   +γa   1 )
 
         [0000]    Note that d=AB is given by 
         [0000]    
       
         
           
             
               
                 
                   
                     
                       A 
                        
                       
                         ( 
                         ω 
                         ) 
                       
                     
                      
                     
                       B 
                        
                       
                         ( 
                         ω 
                         ) 
                       
                     
                   
                   = 
                     
                    
                   
                     
                       
                         a 
                         1 
                         2 
                       
                        
                       
                         ω 
                         2 
                       
                     
                     + 
                     
                       
                         { 
                         
                           
                             
                               a 
                               1 
                             
                              
                             
                               ( 
                               
                                 
                                   a 
                                   0 
                                 
                                 + 
                                 
                                   γ 
                                    
                                   
                                       
                                   
                                    
                                   
                                     a 
                                     1 
                                   
                                 
                               
                               ) 
                             
                           
                           + 
                           
                             
                               a 
                               1 
                             
                              
                             
                               a 
                               0 
                             
                           
                         
                         } 
                       
                        
                       ω 
                     
                     + 
                     
                       
                         a 
                         0 
                       
                        
                       
                         ( 
                         
                           
                             a 
                             0 
                           
                           + 
                           
                             γ 
                              
                             
                                 
                             
                              
                             
                               a 
                               1 
                             
                           
                         
                         ) 
                       
                     
                   
                 
               
             
             
               
                 
                   = 
                     
                    
                   
                     
                       
                         a 
                         1 
                         2 
                       
                        
                       
                         { 
                         
                           
                             γ 
                              
                             
                                 
                             
                              
                             ω 
                           
                           + 
                           γ 
                         
                         } 
                       
                     
                     + 
                     
                       γ 
                        
                       
                           
                       
                        
                       
                         a 
                         1 
                         2 
                       
                        
                       ω 
                     
                     + 
                     
                       
                         a 
                         0 
                       
                        
                       
                         ( 
                         
                           
                             a 
                             0 
                           
                           + 
                           
                             γ 
                              
                             
                                 
                             
                              
                             
                               a 
                               1 
                             
                           
                         
                         ) 
                       
                     
                   
                 
               
             
             
               
                 
                   = 
                     
                    
                   
                     
                       
                         a 
                         1 
                         2 
                       
                        
                       γ 
                     
                     + 
                     
                       
                         
                           a 
                           0 
                         
                          
                         
                           ( 
                           
                             
                               a 
                               0 
                             
                             + 
                             
                               γ 
                                
                               
                                   
                               
                                
                               
                                 a 
                                 1 
                               
                             
                           
                           ) 
                         
                       
                       . 
                     
                   
                 
               
             
           
         
       
     
         [0000]    If A is nonzero, then d is nonzero, and d is a member of the subfield F. Let e be the multiplicative inverse of d in the subfield F, 
         [0000]        e= 1 F   /d.    
         [0000]    It follows that C=eB is the multiplicative inverse of A in G. The following equations can be used to determine C(ω), the multiplicative inverse of A(ω): 
         [0000]        s=a   0   +γa   1 , 
         [0000]        d=a   0   s+γa   1   2 , 
         [0000]        e= 1 /d,    
         [0000]    
       
      
       c 
       0 
       =es,  
      
     
         [0000]        c   1   =ea   1 , 
         [0000]      where 
         [0000]        C (ω)= C   1   ω+c   0 .
 
         [0064]    In these equations, all operations are performed over the subfield F. In particular, the formulas express the inverse for field G in terms of the simpler inverse for subfield F. If G is GF(16) implemented as a split-filed over GF(4), for example, nonzero d is an element of GF(4), and d has two binary components {d 1 , d 0 }. The inverse of d has components 
         [0000]      { e   1   ,e   0   }={d   1   ,d   1   +d   0 }. 
         [0000]    In comparing the inverter for a split-field representation to the inverter for a canonical representation, the equations for a multiplicative inverse for the latter tend to contain a larger number of terms in a large finite field and are not easily simplified. 
         [0065]    B.1. Construction of Arbitrarily Large Finite Fields 
         [0066]    Consider the problem of constructing multipliers for a fairly large finite field G, such as one with 512 bit symbols. A problem with prior art methods is that the identification of one or more irreducible polynomials needed for construction of very large finite fields may be impractically difficult. For example, a prior art construction method for a field with 512 bit symbols as a canonical representation over GF(2) requires finding an irreducible polynomial of degree 512 over GF(2). Because tabulated polynomials are limited, the field constructor must typically conduct one or more polynomial searches. To check if an arbitrary binary polynomial of degree 512 is irreducible, a searcher determines if the arbitrary polynomial has any binary polynomial factors of degree 256 or less. A search of this magnitude is impractically time-consuming. 
         [0067]    An improved method for constructing arbitrarily large finite fields is as shown in a Field Construction flowchart of  FIG. 2 . To generate a sequence a finite fields, refer to the flow chart, beginning with step  400 . 
         [0068]    In step  401 , various initializations occur. The index i in G 1  is initialized to zero, the variable symbits is initialized to km, and an initial product Π 0  is initialized to 1. The fields constructed here are extension fields of a field F, represented as a canonical GF(2 m ), with m an integer greater than zero. An extension field of F is selected as an initial “search” field G 0 . Typically, a relatively small field, such as GF(16), is selected as the search field. The field G 0  may be the same as F, or may be constructed as an extension field of F by any known method, such as by selecting an irreducible polynomial of degree k over F to generate G 0 . The number of bits used to represent an element in the field G 0  is km, where k is an integer greater than zero. Thereafter, each successive field in the sequence of finite fields doubles the symbol size. 
         [0069]    The only search in the field construction method occurs once in step  402 . The field G 0  is searched to find a set of elements S. An element s of G 0  becomes a member of S if and only if the polynomial 
         [0000]        r ( x )= x   2   +s ( x+ 1) 
         [0000]    is irreducible over G 0 . The results of example searches are shown below. 
         [0070]    A sequence of extension fields is then constructed from G 0 , each successor subfield constructed using an irreducible polynomial of degree two, r i (x), over the predecessor subfield. Determination of a successor field begins in step  403 . In step  403 , a particular preferred irreducible polynomial is selected by choosing a particular value s i  in S. The coefficients of the preferred irreducible polynomial have a deterministic product term and a scaling by the chosen member of S. Preferred polynomials help to minimize multiplier complexity by having only one non-zero search field component. The constructed finite fields may incorporate other preferred characteristics, such as being generated solely from primitive polynomials. If so, the choice of a particular value s 1  may depend in whole or in part on the desired characteristics. For example, if only primitive polynomials are desired, each potential polynomial r i (x) corresponding to a choice for s i  in S may be tested to check if it is a primitive polynomial. 
         [0071]    When a suitable irreducible polynomial has been selected, successor field construction is completed in step  404 . The variable ω i  is an assumed root of the selected polynomial r i (x). An element C of G i+1  is represented as a two-component vector 
         [0000]        C=[c   0   ,c   1 ] 
         [0000]    where c 0  and c 1  are elements of G 1 . The element C is associated with the polynomial 
         [0000]        C (ω 1 )= c   0   +c   1 ω i .
 
         [0000]    Also in step  404 , the running product 
         [0000]      Π i+1 =ω i Π i  
 
         [0000]    is updated, the constructed field index i is incremented, and the variable symbits is doubled. 
         [0072]    Step  405  checks if the most recent successor field is sufficiently large for the purposes at hand. For example, the largest field generated may be used for error correction coding to protect data. In the case of error correction coding using Reed Solomon codes, the amount of data that may be protected by a given codeword is limited by the size of the constructed finite field, and step  405  may check to see if a sufficient amount of data can be protected. 
         [0073]    If the constructed field is sufficiently large, the field construction method is complete and step  405  proceeds to termination of the Field Construction method in step  406 . Otherwise, the method returns to step  403  to select a polynomial for a next successor field. Note that a successor polynomial is selected by choosing a value s i  in the previously found set S, without the need for a successive search. The flowchart loop of steps  403  to  405  continues until the constructed field present at step  405  is sufficiently large. 
         [0074]    The method is demonstrated with various examples. In the examples, two preferred forms of search fields F are a field GF(2 m ) represented with a canonical basis, or a field GF(2 m ) in a split-field representation. The examples demonstrate efficient multipliers with symbol sizes up to 512 bits, some generated exclusively from primitive polynomials. The examples were all found on my low horsepower home computer, demonstrating the practicality of the improved field generation method. 
         [0075]    B.2. Proof of the Validity of the Method 
         [0076]    Proposition: The Polynomial 
         [0000]        r   n ( x )= x   2 +γ n   x+γ   n  
 
         [0000]    is irreducible over G, and can therefore be used to extend field G n  to successor field G n+1 . 
         [0077]    Proof: The proof proceeds by induction on n. A first field, G 0 , is searched to find a subset of field elements, S, such that 
         [0000]        p ( x )= x   2   +sx+s    
         [0000]    is irreducible over G 0  if and only ifs is a member of S. An arbitrary first member of S, s 0 , is selected to generate an extension field G 1  using a first irreducible polynomial 
         [0000]        p   0 ( x )= x   2   +s   0   x+s   0 . 
         [0078]    Let ω 0  be a root of p 0 (x). The extension field G 1  is in a split-field representation, where an arbitrary element R of G 1  is represented as a two-component vector with 
         [0000]        R=r   1 ω 0   +r   0 .
 
         [0000]    where r 0  and r 1  are elements of G 0 . Consider a second polynomial 
         [0000]        p   1 ( x )= x   2   +s   1 ω O   x+s   1 ω 0   =x   2   +s   1 Π 1 ( x+ 1)
 
         [0000]    where s 1  is an element of G 0 . The polynomial p 1 (x) is irreducible over G 1  if and only if p 1 (x) has no root R in G. It may be observed that 
         [0000]    
       
         
           
             
               
                 
                   
                     
                       p 
                       1 
                     
                      
                     
                       ( 
                       R 
                       ) 
                     
                   
                   = 
                     
                    
                   
                     
                       R 
                       2 
                     
                     + 
                     
                       
                         s 
                         1 
                       
                        
                       
                         
                           ω 
                           0 
                         
                          
                         
                           ( 
                           
                             R 
                             + 
                             1 
                           
                           ) 
                         
                       
                     
                   
                 
               
             
             
               
                 
                   = 
                     
                    
                   
                     
                       
                         ( 
                         
                           
                             
                               r 
                               1 
                             
                              
                             
                               ω 
                               0 
                             
                           
                           + 
                           
                             r 
                             0 
                           
                         
                         ) 
                       
                       2 
                     
                     + 
                     
                       
                         s 
                         1 
                       
                        
                       
                         
                           ω 
                           0 
                         
                          
                         
                           ( 
                           
                             
                               
                                 r 
                                 1 
                               
                                
                               
                                 ω 
                                 0 
                               
                             
                             + 
                             
                               r 
                               0 
                             
                             + 
                             1 
                           
                           ) 
                         
                       
                     
                   
                 
               
             
             
               
                 
                   = 
                     
                    
                   
                     
                       
                         ( 
                         
                           
                             r 
                             1 
                             2 
                           
                           + 
                           
                             
                               s 
                               1 
                             
                              
                             
                               r 
                               1 
                             
                           
                         
                         ) 
                       
                        
                       
                         ω 
                         0 
                         2 
                       
                     
                     + 
                     
                       r 
                       0 
                       2 
                     
                     + 
                     
                       
                         s 
                         1 
                       
                        
                       
                         
                           ω 
                           0 
                         
                          
                         
                           ( 
                           
                             
                               r 
                               0 
                             
                             + 
                             1 
                           
                           ) 
                         
                       
                     
                   
                 
               
             
             
               
                 
                   = 
                     
                    
                   
                     
                       
                         ( 
                         
                           
                             r 
                             1 
                             2 
                           
                           + 
                           
                             
                               s 
                               1 
                             
                              
                             
                               r 
                               1 
                             
                           
                         
                         ) 
                       
                        
                       
                         
                           s 
                           0 
                         
                          
                         
                           ( 
                           
                             
                               ω 
                               0 
                             
                             + 
                             1 
                           
                           ) 
                         
                       
                     
                     + 
                     
                       r 
                       0 
                       2 
                     
                     + 
                     
                       
                         s 
                         1 
                       
                        
                       
                         
                           ω 
                           0 
                         
                          
                         
                           ( 
                           
                             
                               r 
                               0 
                             
                             + 
                             1 
                           
                           ) 
                         
                       
                     
                   
                 
               
             
             
               
                 
                   = 
                     
                    
                   
                     
                       
                         { 
                         
                           
                             
                               ( 
                               
                                 
                                   r 
                                   1 
                                   2 
                                 
                                 + 
                                 
                                   
                                     s 
                                     1 
                                   
                                    
                                   
                                     r 
                                     1 
                                   
                                 
                               
                               ) 
                             
                              
                             
                               s 
                               0 
                             
                           
                           + 
                           
                             
                               s 
                               1 
                             
                              
                             
                               ( 
                               
                                 
                                   r 
                                   0 
                                 
                                 + 
                                 1 
                               
                               ) 
                             
                           
                         
                         } 
                       
                        
                       
                         ω 
                         0 
                       
                     
                     + 
                     
                       
                         ( 
                         
                           
                             r 
                             1 
                             2 
                           
                           + 
                           
                             
                               s 
                               1 
                             
                              
                             
                               r 
                               1 
                             
                           
                         
                         ) 
                       
                        
                       
                         s 
                         0 
                       
                     
                     + 
                     
                       
                         r 
                         0 
                         2 
                       
                       . 
                     
                   
                 
               
             
           
         
       
     
         [0000]    It follows that p 1 (R)=0 if and only if the two components of p 1 (R) in G 0  are both zero. If the two components are zero, it follows that the sum of the components is zero, i.e. 
         [0000]        r   0   2   +s   1 ( r   0 +1)=0. 
         [0000]    This equation cannot be satisfied in the first field G 0  if s 1  is an element of S. Therefore, with s 1  an element of S, p 1 (x) has no roots and is irreducible. 
         [0079]    By inductive hypothesis, assume that an arbitrary sequence of members of S, 
         [0000]      { s   0   ,s   1   , . . . ,s   n−1 }, 
         [0000]    has been selected as scalars to produce a sequence of irreducible polynomials 
         [0000]      { p   0 ( x ), p   1 ( x ), . . . , p   n−1 ( x )}, 
         [0000]    where the polynomial 
         [0000]        p   k ( x )= x   2   +s   k Π k ( x+ 1)
 
         [0000]    is irreducible over the field G k  and is used to generate a split-field G k+1 . 
         [0080]    Let ω n−1  be a root of p n−1 (x). The extension field G n−1  is in a split-field representation, where an arbitrary element R of G n−1  is represented as a two-component vector with 
         [0000]        R=r   1 ω n−1   +r   0 .
 
         [0000]    where r 0  and r 1  are elements of G n−2 . Consider an n th  polynomial 
         [0000]        p   n ( x )= x   2   +s   n Π n ( x+ 1)
 
         [0000]    where s n  is an element of G 0 . The polynomial p n (x) is irreducible over G n−1  if and only if p n (x) has no root R in G n−1 . It may be observed that 
         [0000]    
       
         
           
             
               
                 
                   
                     
                       p 
                       n 
                     
                      
                     
                       ( 
                       R 
                       ) 
                     
                   
                   = 
                     
                    
                   
                     
                       R 
                       2 
                     
                     + 
                     
                       
                         s 
                         n 
                       
                        
                       
                         
                           ∏ 
                           n 
                         
                          
                         
                           ( 
                           
                             R 
                             + 
                             1 
                           
                           ) 
                         
                       
                     
                   
                 
               
             
             
               
                 
                   = 
                     
                    
                   
                     
                       
                         ( 
                         
                           
                             
                               r 
                               1 
                             
                              
                             
                               ω 
                               
                                 n 
                                 - 
                                 1 
                               
                             
                           
                           + 
                           
                             r 
                             0 
                           
                         
                         ) 
                       
                       2 
                     
                     + 
                     
                       
                         s 
                         n 
                       
                        
                       
                         
                           ∏ 
                           n 
                         
                          
                         
                           ( 
                           
                             
                               
                                 r 
                                 1 
                               
                                
                               
                                 ω 
                                 
                                   n 
                                   - 
                                   1 
                                 
                               
                             
                             + 
                             
                               r 
                               0 
                             
                             + 
                             1 
                           
                           ) 
                         
                       
                     
                   
                 
               
             
             
               
                 
                   = 
                     
                    
                   
                     
                       
                         r 
                         1 
                         2 
                       
                        
                       
                         ω 
                         
                           n 
                           - 
                           1 
                         
                         2 
                       
                     
                     + 
                     
                       r 
                       0 
                       2 
                     
                     + 
                     
                       
                         s 
                         n 
                       
                        
                       
                         
                           ∏ 
                           
                             n 
                             - 
                             1 
                           
                         
                          
                         
                           
                             ω 
                             
                               n 
                               - 
                               1 
                             
                           
                            
                           
                             ( 
                             
                               
                                 
                                   r 
                                   1 
                                 
                                  
                                 
                                   ω 
                                   
                                     n 
                                     - 
                                     1 
                                   
                                 
                               
                               + 
                               
                                 r 
                                 0 
                               
                               + 
                               1 
                             
                             ) 
                           
                         
                       
                     
                   
                 
               
             
             
               
                 
                   = 
                     
                    
                   
                     
                       
                         ( 
                         
                           
                             r 
                             1 
                             2 
                           
                           + 
                           
                             
                               s 
                               n 
                             
                              
                             
                               r 
                               1 
                             
                              
                             
                               ∏ 
                               
                                 n 
                                 - 
                                 1 
                               
                             
                           
                         
                         ) 
                       
                        
                       
                         ω 
                         
                           n 
                           - 
                           1 
                         
                         2 
                       
                     
                     + 
                     
                       r 
                       0 
                       2 
                     
                     + 
                     
                       
                         s 
                         n 
                       
                        
                       
                         
                           ∏ 
                           
                             n 
                             - 
                             1 
                           
                         
                          
                         
                           
                             ω 
                             
                               n 
                               - 
                               1 
                             
                           
                            
                           
                             ( 
                             
                               
                                 r 
                                 0 
                               
                               + 
                               1 
                             
                             ) 
                           
                         
                       
                     
                   
                 
               
             
             
               
                 
                     
                    
                   
                     
                       
                         ( 
                         
                           
                             r 
                             1 
                             2 
                           
                           + 
                           
                             
                               s 
                               n 
                             
                              
                             
                               r 
                               1 
                             
                              
                             
                               ∏ 
                               
                                 n 
                                 - 
                                 1 
                               
                             
                           
                         
                         ) 
                       
                        
                       
                         
                           s 
                           
                             n 
                             - 
                             1 
                           
                         
                          
                         
                           ( 
                           
                             
                               ω 
                               
                                 n 
                                 - 
                                 1 
                               
                             
                             + 
                             1 
                           
                           ) 
                         
                       
                     
                     + 
                     
                       r 
                       0 
                       2 
                     
                     + 
                     
                       
                         s 
                         n 
                       
                        
                       
                         
                           ∏ 
                           
                             n 
                             - 
                             1 
                           
                         
                          
                         
                           
                             ω 
                             
                               n 
                               - 
                               1 
                             
                           
                            
                           
                             ( 
                             
                               
                                 r 
                                 0 
                               
                               + 
                               1 
                             
                             ) 
                           
                         
                       
                     
                   
                 
               
             
             
               
                 
                   = 
                     
                    
                   
                     
                       
                         { 
                         
                           
                             
                               ( 
                               
                                 
                                   r 
                                   1 
                                   2 
                                 
                                 + 
                                 
                                   
                                     s 
                                     n 
                                   
                                    
                                   
                                     r 
                                     1 
                                   
                                    
                                   
                                     ∏ 
                                     
                                       n 
                                       - 
                                       1 
                                     
                                   
                                 
                               
                               ) 
                             
                              
                             
                               s 
                               
                                 n 
                                 - 
                                 1 
                               
                             
                           
                           + 
                           
                             
                               s 
                               n 
                             
                              
                             
                               
                                 ∏ 
                                 
                                   n 
                                   - 
                                   1 
                                 
                               
                                
                               
                                 ( 
                                 
                                   
                                     r 
                                     0 
                                   
                                   + 
                                   1 
                                 
                                 ) 
                               
                             
                           
                         
                         } 
                       
                        
                       
                         ω 
                         
                           n 
                           - 
                           1 
                         
                       
                     
                     + 
                   
                 
               
             
             
               
                 
                     
                    
                   
                     
                       
                         ( 
                         
                           
                             r 
                             1 
                             2 
                           
                           + 
                           
                             
                               s 
                               n 
                             
                              
                             
                               r 
                               1 
                             
                              
                             
                               ∏ 
                               
                                 n 
                                 - 
                                 1 
                               
                             
                           
                         
                         ) 
                       
                        
                       
                         s 
                         
                           n 
                           - 
                           1 
                         
                       
                     
                     + 
                     
                       
                         r 
                         0 
                         2 
                       
                       . 
                     
                   
                 
               
             
           
         
       
     
         [0000]    It follows that p n (R)=0 if and only if the two components of p n (R) in G n−2  are both zero. If both components are zero, the sum of the components is zero, i.e. 
         [0000]        r   0   2   +s   n Π n−1 ( r   0 +1)=0.
 
         [0000]    By inductive hypothesis, this equation cannot be satisfied in the field G n−2  if s n  is an element of S. Therefore, p n (x) has no roots and is irreducible. 
         [0081]    B.3. Examples of Application of the Method 
         [0082]    If the search field is GF(2), the set S={1}. By definition, the constants {s n } are all members of S, with s n =1 for all n. Extension fields of search field GF(2) are then constructed as shown in Table 2. 
         [0083]    The first line in Table 2 indicates that the first extension, with n=0, uses the polynomial r 0 (x)=x 2 +x+1 to generate G 1 =GF(4) as an extension field of G 0 =GF(2). Let ω 0  be a root of r 0 (x). The second line indicates that the polynomial 
         [0000]        r   1 ( x )= x   2 +10 2   x+ 10 2    
         [0000]    is irreducible over G 1  and is used to generate G 2 =GF(16). Here, the notation 10 2  is shorthand used to indicate that γ 1 , as a member of GF(4), is a two component vector, 
         [0000]      [ a   1   ,a   0 ]=[1,0] 
         [0000]    over GF(2), with the understanding that γ 1 =a 1 ω 0 +a 0 =ω 0 . The third line indicates that the polynomial 
         [0000]        r   1 ( x )= x   2 +1000 2   x+ 1000 2    
         [0000]    is irreducible over G 2  and is used to generate G 3 =GF(256). Here, the notation 1000 2  indicates that γ 2 , as a member of GF(16), is a two component vector, 
         [0000]      [ b   1   ,b   0 ]=[10 2 ,00 2 ] 
         [0000]    over GF(4), with the understanding that γ 2 =b 1 ω 1 +b 0 =ω 1 ω O . 
         [0000]    
       
         
               
             
               
               
               
               
             
           
               
                 TABLE 2 
               
             
             
               
                   
               
               
                 Beginning of construction of arbitrarily large fields from GF(2) 
               
             
          
           
               
                 n 
                 m 
                 γ n   
                 α n   
               
               
                   
               
               
                 0 
                  1 
                 1 
                   
               
               
                 1 
                  2 
                 ω 0  = 10 2   
                 ω 0  = 10 2   
               
               
                 2 
                  4 
                 ω 0 ω 1  = 1000 2   
                 ω 1  = 0100 2   
               
               
                 3 
                  8 
                 ω 0 ω 1 ω 2  = 10000000 2   
                 ω 0 ω 2  = 00100000 2   
               
               
                 4 
                  16 
                 ω 0 ω 1 ω 2 ω 3  = 1000000000000000 2   
                 ω 0 ω 3  = 0000001000000000 2   
               
               
                 5 
                  32 
                 ω 0  . . . ω 4   
                 ω 0 ω 4   
               
               
                 6 
                  64 
                 ω 0  . . . ω 5   
                 ω 0 ω 5   
               
               
                 7 
                 128 
                 ω 0  . . . ω 6   
                 ω 0 ω 6   
               
               
                 8 
                 256 
                 ω 0  . . . ω 7   
                 ω 0 ω 7   
               
               
                 9 
                 512 
                   
                 ω 0 ω 8   
               
               
                   
               
             
          
         
       
     
         [0084]    According to the proposition, an arbitrarily large finite field can be constructed by proceeding in a similar manner. Because each γ n  has only one nonzero component, multiplication by the coefficient γ n  is relatively easy, and scaling by the search field scalar, s n =1, is trivial. The schematics of  FIG. 1  simplify for this example because each subfield multiplier has only one auxiliary output corresponding to the sole choice for s n , advantageously simplifying higher order extensions. 
         [0085]    As discussed in the previous section, there are disadvantages for this construction over GF(2). The constructed multiplier for GF(16) with 63 gate-area units is 3% larger than a canonical multiplier for GF(16) with 61 gate-area units, and successor fields stem from the constructed GF(16) multiplier. On the other hand, successive multipliers may be made split-optimal with a minimal number of auxiliary outputs. 
         [0086]    Another potential disadvantage of this example is that the third extension polynomial and successive polynomials are not primitive polynomials. In the fourth column of Table 2, a preferred primitive element α n  for the field G n+1  is listed. When ω n  is the preferred primitive element of G n+1 , the polynomial r n (x) is primitive. In some applications, such as Reed Solomon coding over finite fields, a simple constant multiplier for a primitive element of the field is desired, implying a preference for primitive polynomials. 
         [0087]    If the polynomial is not primitive, a primitive element of the field must typically be found and provided as in column 4 of Table 2. If the goal is to exclusively provide primitive polynomials at each construction stage, the choice of GF(2) as the search field is too constraining 
         [0088]    As another example, let the search field F=GF(4), an extension field of GF(2) using the primitive polynomial p(x)=x 2 +x+1. Let a 0  be a root of p(x). The set S is the set of all suitable search field values for γ in GF(4), so that 
         [0000]        r ( x )= x   2   +γx+γ   
         [0000]    is irreducible if and only if γ is a member of S. Lets denote each of the four members of GF(4) as a duobinary digit, {0 4 =00 2 , 1 4 =01 2 , 2 4 =10 2 , 3 4 =11 2 }. In this notation, the set 
         [0000]        S={ 2 4 ,3 4 }={α 0 ,α 0   2 }.
 
         [0000]    It turns out that either of the two choices for γ 0  provides a primitive polynomial over GF(4). In Table 3, large fields are constructed using GF(4) as the search field. Each is constructed using only primitive polynomials. 
         [0089]    Note that, in the example of Table 3, an arbitrary member of s 0  of S may be selected as the value for γ 0 . Thereafter, a preference for primitive polynomials requires that the sequence of selected scalar values alternates between the two members of S. This may be expressed as s 0 =α 0   k  where k is one or two, and s i+1 =s i   2  for all i. 
         [0090]    The construction can continue in this manner to produce arbitrarily large finite fields. The constructed polynomials have been verified to be primitive with symbol sizes up to 512 bits. I conjecture that the alternating selection of scalar values in this example provides primitive polynomials for all values of n. 
         [0000]    
       
         
               
             
               
               
               
               
             
           
               
                 TABLE 3 
               
             
             
               
                   
               
               
                 Construction of fields from GF(4) using only primitive polynomials 
               
             
          
           
               
                 n 
                 m 
                 γ n   
                 α n   
               
               
                   
               
               
                 0 
                  2 
                 α 0   k  = 2 4  or 3 4   
                 2 4   
               
               
                 1 
                  4 
                 α 0   2k ω 0  = 30 4  or 20 4   
                 ω 0  = 10 4   
               
               
                 2 
                  8 
                 α 0   4k ω 1 ω 0  = 2000 4  or 3000 4   
                 ω 1  = 0100 4   
               
               
                 3 
                  16 
                 α 0   8k ω 2 ω 1 ω 0  = 30000000 4  or 20000000 4    
                 ω 2  = 00010000 4   
               
               
                 4 
                  32 
                 α 0   16k ω 0  . . . ω 3   
                 ω 3   
               
               
                 5 
                  64 
                 α 0   32k ω 0  . . . ω 4   
                 ω 4   
               
               
                 6 
                 128 
                 α 0   64k ω 0  . . . ω 5   
                 ω 5   
               
               
                 7 
                 256 
                 α 0   128k ω 0  . . . ω 6   
                 ω 6   
               
               
                 8 
                 512 
                   
                 ω 7   
               
               
                   
               
             
          
         
       
     
         [0091]    For more examples, let the search field F=GF(16), a canonical extension field of GF(2) using the primitive polynomial p(x)=x 4 +x+1. Let α be a root of p(x). Here, an element B of GF(16) is denoted as a 4-tuple {b 3 b 2 b 1 b 0 } 2  with the understanding that 
         [0000]        B (α)= b   3 α 3   +b   2 α 2   +b   1   α+b   0 .
 
         [0000]    Interpreting the 4-tuple as a hexadecimal digit, the powers of α in GF(16) are given by 
         [0000]      AntilogTable={1,2,4,8,3,6 ,C,B, 5 ,A, 7 ,E,F,D, 9,1}, 
         [0000]    where the i th  entry of AntilogTable is α i , starting with i=0. The field F is searched to find the set S, where 
         [0000]        S={ 2,3,4,5,8 ,A,C,F}   16 . 
         [0000]    Note that S provides eight choices at each construction stage for s. Several low powers of α, including α=2 16 , α 2 =4 16 , and α 3 =8 16 , are members of S and are available as auxiliary outputs of a modified canonical GF(16) multiplier. 
         [0092]    One method of constructing arbitrarily large fields is to select members of S to provide a minimal complexity constant multiplication at each construction stage. 
         [0093]    For example, one sequence of selections that simplifies implementation is to use a single constant as in Example 1 above, but with a sole value such as s i =α for all i in this example for the search field GF(16). A disadvantage of this sequence is that the second extension field, GF(65536), and subsequent extension fields use polynomials that are not primitive. 
         [0094]    In Table 4, two preferred sequences of selections are listed to provide examples with primitive polynomials at all construction stages. The first sequence of selections is listed as column s n  in Table 4, whereas an alternative second sequence of selections is listed as column t n . The sequences were found using a computer program implementing the flowchart of  FIG. 2 , using a preference for primitive polynomials where each s i  is a low power of α. Multipliers to implement the extension fields from this example are the least complex known for common computer symbol sizes in multiples of eight bits. 
         [0000]    
       
         
               
             
               
               
               
               
               
             
           
               
                 TABLE 4 
               
             
             
               
                   
               
               
                 Construction of fields from canonical GF(16)  
               
               
                 using only primitive polynomials 
               
             
          
           
               
                 n 
                 m 
                 s n   
                 t n   
                 α n   
               
               
                   
               
               
                 0 
                  4 
                 4 16   
                 2 16   
                 2 16   
               
               
                 1 
                  8 
                 2 16   
                 8 16   
                 ω 0  = 10 16   
               
               
                 2 
                  16 
                 4 16   
                 4 16   
                 ω 1  = 0100 16   
               
               
                 3 
                  32 
                 8 16   
                 8 16   
                 ω 2  = 00010000 16   
               
               
                 4 
                  64 
                 2 16   
                 4 16   
                 ω 3   
               
               
                 5 
                 128 
                 8 16   
                 2 16   
                 ω 4   
               
               
                 6 
                 256 
                 4 16   
                 4 16   
                 ω 5   
               
               
                 7 
                 512 
                   
                   
                 ω 6   
               
               
                   
               
             
          
         
       
     
         [0095]    B.4. The Improved Construction Method with Prior Art Polynomials 
         [0096]    As discussed in the introduction A.1, a prior art split-field construction method may be used to extend a finite field F to a field G using a quadratic irreducible polynomial of the form 
         [0000]        q ( x )= x   2   +x+β.    
         [0000]    A prior art finite field multiplier for the extension field G may be implemented using three full multipliers for the field F, four adders for the field F, and a constant multiplier, multiplying by the constant I. Given a plurality of possible choices for β, a polynomial q(x) that facilitates simple constant multiplication is preferably selected. To minimize complexity, the field F is typically searched for all suitable values for β, and a polynomial q 0 (x) with a particular value β 0  that minimizes complexity is selected. 
         [0097]    It is known in the art that this extension method may be applied repeatedly. If an extension field H doubling the symbol size of G is desired, the field G is searched for a new set of suitable values for β, and a polynomial q 1 (x) with a particular value β 1  that minimizes complexity is selected. A disadvantage of this approach is that it requires a new search at each stage of construction. 
         [0098]    Instead, a method of selecting a sequence of irreducible polynomials for extending the field G without additional searches, as in the previous section, is desired. The flowchart of  FIG. 2  may be modified to support the prior art&#39;s preferred quadratic polynomial as follows. Steps  400 ,  401 ,  402 ,  405 , and  406  remain as shown in  FIG. 2 . 
         [0099]    Step  403  is replaced by a new step  503  (not shown in  FIG. 2 ). The new step  503  is as follows: 
         [0100]    Step  503 : 
         [0101]    Select a scalar s i  in S. 
         [0102]    Let r i (x)=x 2 +x+Π i /s i    
         [0000]    Note that step  503  defines polynomial r i (x) differently than in step  403 . 
         [0103]    Step  404  is replaced by a new step  504  (not shown in  FIG. 2 ). The new step  504  is as follows: 
         [0104]    Step  504 : 
         [0105]    Let ω i  be a root of r i (x). 
         [0106]    Construct field G i+1  as a split-field using a {1, ω i } basis and r i (x). 
         [0107]    Let Π i+1 =(ω i +1) Π i . 
         [0108]    Increment i and double symbits. 
         [0000]    Note that step  504  also redefines the running product R. 
         [0109]    As a simple example, suppose that a multiplier for GF(65536) is to be constructed using the improved method with prior art polynomials over F=GF(16). The field F is in a canonical representation and is generated by the primitive binary polynomial, 
         [0000]        p ( x )= x   4   +x+ 1, 
         [0000]    as above. Let α be a root of p(x). The field F is searched to find the set S, where 
         [0000]        S={α,α   2 ,α 3 ,α 4 ,α 6 ,α 8 ,α 9 ,α 12 }={2,4,8,3 ,C, 5 ,A,F}   16 .
 
         [0000]    A first selection from S, s 0 =α 2 =4 16 , is used to form a primitive quadratic polynomial over F, 
         [0000]        q   0 ( x )= x   2   +x+s   0   −1   =x   2   +x+α   13   =x   2   +x+D   16 . 
         [0000]    A binary vector 
         [0000]      { b   3   ,b   2   ,b   1   ,b   0 } 2    
         [0000]    representing a symbol in a canonical GF(16) may be multiplied by the choice β O =D 16  using two XOR gates and a rearrangement to obtain 
         [0000]      { b   0   +b   1   ,b   0   ,b   3   ,b   0   +b   1   +b   2 } 2 . 
         [0000]    A multiplier for GF(256) using this selection is implemented using three GF(16) multipliers, four GF(16) adders, and a β-multiplier, with a total of 48 AND gates and 63 XOR gates. Let ω 0  be a root of q 0 (x). A second selection from S, S 1 =α, is used to form a primitive quadratic polynomial over GF(256), 
         [0000]        q   0 ( x )= x   2   +x+α   14 (ω 0 +1).
 
         [0000]    Multiplication by the choice β 1 =α 14 (ω 0 +1) in the sixteen-bit multiplier may be performed in two steps. Given that an eight-bit multiplier contains a constant multiplier providing α 13 b 1 , a split-field vector 
         [0000]        B=b   1 ω 0   +b   0  
 
         [0000]    may be multiplied by (ω 0 +1) to form 
         [0000]      (ω 0 +1) B=b   0 ω 0 +( b   0 +α 13   b   1 ),
 
         [0000]    using four XOR gates, and each of two components of this sub-product may be scaled by α 14  using a single XOR gate. These six XOR gates may be added to one of three eight-bit multipliers in a sixteen-bit multiplier to provide an auxiliary output multiplying one eight-bit input by β 1 . The total number of gates for a sixteen bit multiplier using these selections and resource sharing through an auxiliary output is 144 AND gates and 227 XOR gates, or 825 gate-area units. The doubly split-optimal multipliers for GF(65536) disclosed in the previous section are more efficient, using 144 AND gates and 215 XOR gates, or 789 gate-area units. 
         [0110]    By way of comparison, a prior art best example multiplier for GF(65536) is listed in Table 1 and shown in FIG. 1 of Paar, supra, p. 860. The prior art sixteen-bit multiplier uses 144 AND gates and 258 XOR gates, or 918 gate-area units. It is about 11% larger than the example above, and about 16% larger than the optimal multiplier for GF(65536). 
         [0111]    A second advantage of the method disclosed here is that it allows for scalable implementations in software. Suppose, for example, that the sixteen-bit multiplier described in this section is to be implemented in software using known techniques for multiplication involving log and antilog tables. With the new construction, a software implementer may elect to use one of the three following alternatives. The first alternative allocates a storage space of 32 four-bit entries for log and antilog tables over GF(16), providing that a GF(65536) multiplication may be accomplished using 27 GF(16) log table lookups and relatively simple operations. The second alternative allocates a storage space of 512 eight-bit entries for log and antilog tables over GF(256), so that a GF(65536) multiplication may be accomplished using nine GF(256) log table lookups and simple operations. This second alternative provides a good compromise between throughput performance and storage requirements. The third alternative uses a storage space of 131,072 sixteen-bit entries for log and antilog tables for GF(65536), providing that a GF(65536) multiplication may be accomplished using three log table lookups and simple operations. Throughput may be flexibly traded off against required storage space to accommodate various needs. With the prior art construction, a best multiplier for GF(65536) is constructed directly as an extension field of GF(16), without the same alternative of supporting operations implemented over GF(256) with intermediate sized tables. 
         [0112]    A further advantage of the improved construction method is that it provides for construction of a plurality of successor fields without requiring additional searches, using a preferred form of the constant β i  for each successor field. If extension polynomials using the form of q(x) are preferred, the modified construction method can be used to produce arbitrarily large fields using this preferred form without consuming the additional time and resources of additional polynomial searches. 
         [0113]    The embodiments shown and discussed here are for purposes of illumination and are not for purposes of limitation. As is well known in the art, various features of the methods discussed here may be implemented in other equivalent ways, and other combinations and permutations of the methods discussed herein may be utilized without departing from the true spirit of the invention, which is limited only by the claims.