View source for Galois field structure

''Galois field (update)''

This article contains some additional information concerning the structural properties of a [[Galois field|Galois field]] extension <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g130/g130010/g1300101.png" />, where <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g130/g130010/g1300102.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g130/g130010/g1300103.png" />; this is also of interest for computational applications. Usually <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g130/g130010/g1300104.png" /> is represented as an <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g130/g130010/g1300105.png" />-dimensional [[Vector space|vector space]] over <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g130/g130010/g1300106.png" />, so that addition of elements of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g130/g130010/g1300107.png" /> becomes trivial, given the arithmetics in <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g130/g130010/g1300108.png" /> (which, in applications, usually is a prime field <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g130/g130010/g1300109.png" /> represented as the residues modulo <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g130/g130010/g13001010.png" />). However, the choice of a basis is crucial for performing multiplication, inversion and exponentiation. Various types of bases have been studied extensively. The most obvious choice is that of a polynomial basis <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g130/g130010/g13001011.png" />, where <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g130/g130010/g13001012.png" /> is a root of an [[Irreducible polynomial|irreducible polynomial]] of degree <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g130/g130010/g13001013.png" /> over <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g130/g130010/g13001014.png" /> (so that <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g130/g130010/g13001015.png" /> generates <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g130/g130010/g13001016.png" /> over <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g130/g130010/g13001017.png" />, cf. [[Galois field|Galois field]]). In this context, one often prefers <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g130/g130010/g13001018.png" /> to be a generator of the [[Cyclic group|cyclic group]] <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g130/g130010/g13001019.png" /> (cf. [[Galois field|Galois field]]); then <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g130/g130010/g13001020.png" /> is usually called a primitive element or a primitive root for <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g130/g130010/g13001021.png" />, and the polynomial <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g130/g130010/g13001022.png" /> is called a primitive polynomial. Note that these terms carry a different meaning in the context of Galois fields than in algebra in general, see [[Galois theory|Galois theory]] and [[Primitive polynomial|Primitive polynomial]].

The standard alternative to using a polynomial basis is a normal basis, that is, a basis of the form <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g130/g130010/g13001023.png" />, cf. [[Normal basis theorem|Normal basis theorem]]. Hence such a basis consists of an orbit of maximal length <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g130/g130010/g13001024.png" /> under the [[Frobenius automorphism|Frobenius automorphism]] <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g130/g130010/g13001025.png" />. The element <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g130/g130010/g13001026.png" /> is called a free element (or a normal element) in <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g130/g130010/g13001027.png" />. A stronger result is the existence of an element <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g130/g130010/g13001028.png" /> that is simultaneously free in <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g130/g130010/g13001029.png" /> for every intermediate field <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g130/g130010/g13001030.png" />; such an element is called completely free (or completely normal). A constructive treatment of normal bases and completely free elements in Galois fields can be found in [[#References|[a7]]].

Much current research (as of 2001) concerns the construction of primitive and/or free elements with additional properties. The seminal result in this direction is the primitive normal basis theorem: There always exists a primitive element <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g130/g130010/g13001031.png" /> that is simultaneously free over <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g130/g130010/g13001032.png" />. This result is due to A.K. Lenstra and R.J. Schoof [[#References|[a15]]], see also [[#References|[a10]]]. In this context the concepts of trace and norm play an important role. For any [[Galois extension|Galois extension]] <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g130/g130010/g13001033.png" /> with Galois group <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g130/g130010/g13001034.png" />, one defines the trace and the norm (over <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g130/g130010/g13001035.png" />) of an element <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g130/g130010/g13001036.png" /> as the sum and the product of all conjugates <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g130/g130010/g13001037.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g130/g130010/g13001038.png" />, respectively (each taken with the appropriate multiplicity). In the special case under consideration, there are explicit formulas:

<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g130/g130010/g13001039.png" /></td> <td valign="top" style="width:5%;text-align:right;">(a1)</td></tr></table>

and

<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g130/g130010/g13001040.png" /></td> <td valign="top" style="width:5%;text-align:right;">(a2)</td></tr></table>

Now, let <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g130/g130010/g13001041.png" /> be an irreducible polynomial over <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g130/g130010/g13001042.png" />, and let <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g130/g130010/g13001043.png" /> be a root of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g130/g130010/g13001044.png" /> (generating <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g130/g130010/g13001045.png" />). Then

<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g130/g130010/g13001046.png" /></td> </tr></table>

There are many results on the existence of primitive and/or (completely) free elements <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g130/g130010/g13001047.png" /> with prescribed trace and/or norm, or with other prescribed coefficients. The first of these is due to S.D. Cohen [[#References|[a4]]]: Given <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g130/g130010/g13001048.png" />, where <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g130/g130010/g13001049.png" /> if either <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g130/g130010/g13001050.png" /> or <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g130/g130010/g13001051.png" />, there exists a primitive element <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g130/g130010/g13001052.png" /> of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g130/g130010/g13001053.png" /> with <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g130/g130010/g13001054.png" />. For more results of this type, see [[#References|[a10]]].

Given any ordered basis <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g130/g130010/g13001055.png" /> of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g130/g130010/g13001056.png" />, there exists a unique dual basis <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g130/g130010/g13001057.png" />, defined by the property

<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g130/g130010/g13001058.png" /></td> </tr></table>

One calls <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g130/g130010/g13001059.png" /> self-dual if <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g130/g130010/g13001060.png" />. A self-dual basis for <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g130/g130010/g13001061.png" /> exists if either <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g130/g130010/g13001062.png" /> is even or both <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g130/g130010/g13001063.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g130/g130010/g13001064.png" /> are odd. It is easily checked that the dual basis of a normal basis is likewise a normal basis; a self-dual normal basis for <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g130/g130010/g13001065.png" /> exists if either <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g130/g130010/g13001066.png" /> is even and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g130/g130010/g13001067.png" /> is not a multiple of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g130/g130010/g13001068.png" />, or both <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g130/g130010/g13001069.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g130/g130010/g13001070.png" /> are odd. The number of bases of these types has also been determined. For computational purposes (in particular, for hardware implementations), it would be desirable to have a self-dual polynomial basis; unfortunately, such bases do not exist. If one slightly weakens the requirements, a suitable substitute can be found in the so-called weakly self-dual polynomial bases; these belong to irreducible binomials and irreducible trinomials with constant term <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g130/g130010/g13001071.png" />. Therefore the existence of such trinomials is an important (as of 2001 still open) question. These topics are discussed in detail in [[#References|[a10]]] and [[#References|[a12]]].

There is an alternative to using basis representations for finite fields: If one represents the non-zero elements of a Galois field <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g130/g130010/g13001072.png" /> as the powers of a primitive element <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g130/g130010/g13001073.png" />, multiplication is trivial, but addition then becomes difficult. For any element <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g130/g130010/g13001074.png" />, the discrete logarithm of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g130/g130010/g13001075.png" /> (to the base <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g130/g130010/g13001076.png" />) is the unique integer <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g130/g130010/g13001077.png" /> with <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g130/g130010/g13001078.png" /> satisfying <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g130/g130010/g13001079.png" />; one writes <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g130/g130010/g13001080.png" /> and also puts <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g130/g130010/g13001081.png" />. Identifying the elements of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g130/g130010/g13001082.png" /> with their discrete logarithms, multiplying two elements reduces to adding the corresponding discrete logarithms:

<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g130/g130010/g13001083.png" /></td> </tr></table>

where the addition is done modulo <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g130/g130010/g13001084.png" />. In order to perform additions in this representation, one needs to determine the discrete logarithm of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g130/g130010/g13001085.png" /> for <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g130/g130010/g13001086.png" />. Since <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g130/g130010/g13001087.png" />, it suffices to determine the discrete logarithms for sums involving <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g130/g130010/g13001088.png" />. This motivates the definition of the so-called Zech logarithm <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g130/g130010/g13001089.png" /> (which is actually due to C.G.J. Jacobi); thus, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g130/g130010/g13001090.png" /> is determined from the equation <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g130/g130010/g13001091.png" />. Using discrete logarithms in conjunction with Zech logarithms is a useful representation in practical applications where repeated computations over a comparatively small finite field are required (with applications in coding theory being typical examples), since then the Zech logarithms can be pre-computed and, when needed for addition, retrieved by a simple table lookup. It is clear that a table lookup of Zech logarithms becomes impractical for large Galois fields. Thus the possibility of using this type of representation for large fields depends on the practicality of actually computing discrete logarithms, which is generally believed to be a very difficult problem. In fact, some systems in public-key cryptography (see [[Cryptography|Cryptography]]) are based on the intractability of computing discrete logarithms in sufficiently large Galois fields or, for state-of-the-art systems, in elliptic curves over Galois fields (cf. also [[Elliptic curve|Elliptic curve]]); see, e.g., [[#References|[a5]]], [[#References|[a13]]], [[#References|[a16]]], [[#References|[a17]]].

As of 2001, the standard reference on Galois fields is [[#References|[a14]]]. In recent years there has been a resurgence of research in finite fields due to the wide variety of applications of various theoretical aspects of finite fields, e.g. in [[Galois geometry|Galois geometry]], coding theory (cf. [[Coding and decoding|Coding and decoding]]), design theory (cf. [[Block design|Block design]]; [[Difference set|Difference set]]; [[Symmetric design|Symmetric design]]), cryptography (cf. [[Cryptography|Cryptography]]; [[Cryptology|Cryptology]]), and signal processing. These applications usually require the use of efficient arithmetics, often in very large Galois fields; e.g., both <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g130/g130010/g13001092.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g130/g130010/g13001093.png" /> have been used in commercial cryptographical devices. This has been one of the major motivations for studying the structural properties of proper Galois fields as sketched above in more detail. The interplay of structural and arithmetical properties is discussed in detail in [[#References|[a10]]] and [[#References|[a12]]]; computational and algorithmic aspects are treated in [[#References|[a20]]]. Some good references for actual applications of Galois fields in the areas mentioned above are [[#References|[a1]]], [[#References|[a2]]], [[#References|[a3]]], [[#References|[a5]]], [[#References|[a6]]], [[#References|[a10]]], [[#References|[a9]]], [[#References|[a8]]], [[#References|[a11]]], [[#References|[a13]]], [[#References|[a21]]], [[#References|[a18]]], [[#References|[a16]]], [[#References|[a17]]], [[#References|[a19]]]. A good reference for computational aspects is [[#References|[a22]]].

====References====
<table><TR><TD valign="top">[a1]</TD> <TD valign="top">  E.F. Assmus,   J.D. Key,   "Designs and their codes" , Cambridge Univ. Press  (1992)</TD></TR><TR><TD valign="top">[a2]</TD> <TD valign="top">  E.R. Berlekamp,   "Algebraic coding theory" , McGraw-Hill  (1968)</TD></TR><TR><TD valign="top">[a3]</TD> <TD valign="top">  T. Beth,   D. Jungnickel,   H. Lenz,   "Design theory" , Cambridge Univ. Press  (1999)  (Edition: Second)</TD></TR><TR><TD valign="top">[a4]</TD> <TD valign="top">  S.D. Cohen,   "Primitive elements and polynomials with arbitrary trace"  ''Discr. Math.'' , '''83'''  (1990)  pp. 1–7</TD></TR><TR><TD valign="top">[a5]</TD> <TD valign="top">  A. Enge,   "Elliptic curves and their applications to cryptography" , Kluwer Acad. Publ.  (1999)</TD></TR><TR><TD valign="top">[a6]</TD> <TD valign="top">  P. Fan,   M. Darnell,   "Sequence design for communication applications" , Wiley  (1996)</TD></TR><TR><TD valign="top">[a7]</TD> <TD valign="top">  D. Hachenberger,   "Finite fields: Normal bases and completely free elements" , Kluwer Acad. Publ.  (1997)</TD></TR><TR><TD valign="top">[a8]</TD> <TD valign="top">  J.W.P. Hirschfeld,   "Projective geometries over finite fields" , Oxford Univ. Press  (1998)  (Edition: Second)</TD></TR><TR><TD valign="top">[a9]</TD> <TD valign="top">  J.W.P. Hirschfeld,   "Finite projective spaces of three dimensions" , Oxford Univ. Press  (1985)</TD></TR><TR><TD valign="top">[a10]</TD> <TD valign="top">  D. Hachenberger,   D. Jungnickel,   "Topics in Galois fields" , Springer  (to appear)</TD></TR><TR><TD valign="top">[a11]</TD> <TD valign="top">  J.W.P. Hirschfeld,   J.A. Thas,   "General Galois geometries" , Oxford Univ. Press  (1991)</TD></TR><TR><TD valign="top">[a12]</TD> <TD valign="top">  D. Jungnickel,   "Finite fields: Structure and arithmetics" , Bibliographisches Inst. Mannheim  (1993)</TD></TR><TR><TD valign="top">[a13]</TD> <TD valign="top">  N. Koblitz,   "Algebraic aspects of cryptography" , Springer  (1998)</TD></TR><TR><TD valign="top">[a14]</TD> <TD valign="top">  R. Lidl,   H. Niederreiter,   "Finite fields" , Addison-Wesley  (1983)</TD></TR><TR><TD valign="top">[a15]</TD> <TD valign="top">  A.K. Lenstra,   R.J. Schoof,   "Primitive normal bases for finite fields"  ''Math. Comput.'' , '''48'''  (1987)  pp. 217–231</TD></TR><TR><TD valign="top">[a16]</TD> <TD valign="top">  "Applications of finite fields"  A.J. Menezes (ed.) , Kluwer Acad. Publ.  (1993)</TD></TR><TR><TD valign="top">[a17]</TD> <TD valign="top">  A.J. Menezes,   "Elliptic curve public key cryptosystems" , Kluwer Acad. Publ.  (1993)</TD></TR><TR><TD valign="top">[a18]</TD> <TD valign="top">  F.J. MacWilliams,   N.J.A. Sloane,   "The theory of error-correcting codes" , North-Holland  (1977)</TD></TR><TR><TD valign="top">[a19]</TD> <TD valign="top">  "Difference sets, sequences and their correlation properties"  A. Pott (ed.)  P.V. Kumar (ed.)  T. Helleseth (ed.)  D. Jungnickel (ed.) , Kluwer Acad. Publ.  (1999)</TD></TR><TR><TD valign="top">[a20]</TD> <TD valign="top">  I.E. Shparlinski,   "Computational and algorithmic problems in finite fields" , Kluwer Acad. Publ.  (1992)</TD></TR><TR><TD valign="top">[a21]</TD> <TD valign="top">  J.H. van Lint,   "Introduction to coding theory" , Springer  (1999)  (Edition: Third)</TD></TR><TR><TD valign="top">[a22]</TD> <TD valign="top">  J. von zur Gathen,   J. Gerhard,   "Modern computer algebra" , Cambridge Univ. Press  (1999)</TD></TR></table>