Galois field structure

Galois field (update)

This article contains some additional information concerning the structural properties of a Galois field extension $E / F$, where $E = \operatorname{GF} ( q ^ { n } )$ and ${F} = \operatorname{GF} ( q )$; this is also of interest for computational applications. Usually $E$ is represented as an $n$-dimensional vector space over $F$, so that addition of elements of $E$ becomes trivial, given the arithmetics in $F$ (which, in applications, usually is a prime field $\operatorname { GF} ( p )$ represented as the residues modulo $p$). 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 $\{ 1 , \alpha , \alpha ^ { 2 } , \dots , \alpha ^ { n - 1 } \}$, where $\alpha$ is a root of an irreducible polynomial of degree $n$ over $F$ (so that $\alpha$ generates $E$ over $F$, cf. Galois field). In this context, one often prefers $\alpha$ to be a generator of the cyclic group $E ^ { * }$ (cf. Galois field); then $\alpha$ is usually called a primitive element or a primitive root for $E$, and the polynomial $f$ 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 and Primitive polynomial.

The standard alternative to using a polynomial basis is a normal basis, that is, a basis of the form $\{ \alpha , \alpha ^ { q } , \ldots , \alpha ^ { q ^ { n - 1 } } \}$, cf. Normal basis theorem. Hence such a basis consists of an orbit of maximal length $n$ under the Frobenius automorphism $x \mapsto x ^ { q }$. The element $\alpha$ is called a free element (or a normal element) in $E / F$. A stronger result is the existence of an element $\omega \in E$ that is simultaneously free in $E / K$ for every intermediate field $K$; 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 [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 $\omega \in E$ that is simultaneously free over $F$. This result is due to A.K. Lenstra and R.J. Schoof [a15], see also [a10]. In this context the concepts of trace and norm play an important role. For any Galois extension $E / F$ with Galois group $G$, one defines the trace and the norm (over $F$) of an element $z \in E$ as the sum and the product of all conjugates $z ^ { \sigma }$, $\sigma \in G$, respectively (each taken with the appropriate multiplicity). In the special case under consideration, there are explicit formulas:

\begin{equation} \tag{a1} \operatorname { Tr } _ { E / F } ( z ) = z + z ^ { q } + \ldots + z ^ { q ^ { n - 1 } } \end{equation}

and

\begin{equation} \tag{a2} N _ { E / F} ( z ) = z \cdot z ^ { q } \cdot \ldots \cdot z ^ { q ^ { n - 1 } }. \end{equation}

Now, let $f = x ^ { n } + a _ { n - 1 } x ^ { n - 1 } + \ldots + a _ { 1 } x + a _ { 0 }$ be an irreducible polynomial over $F$, and let $\alpha$ be a root of $f$ (generating $E$). Then

\begin{equation*} a _ { n - 1 } = - \operatorname { Tr } ( \alpha ) \text { and } a _ { 0 } = ( - 1 ) ^ { n } N ( \alpha ). \end{equation*}

There are many results on the existence of primitive and/or (completely) free elements $\alpha$ with prescribed trace and/or norm, or with other prescribed coefficients. The first of these is due to S.D. Cohen [a4]: Given $a \in F$, where $a \neq 0$ if either $n = 2$ or $( n , q ) = ( 3,4 )$, there exists a primitive element $\omega$ of $E$ with $\operatorname { Tr } _ { E / F } ( \omega ) = a$. For more results of this type, see [a10].

Given any ordered basis $B = ( \beta _ { 0 } , \dots , \beta _ { n - 1 } )$ of $E$, there exists a unique dual basis $B ^ { * } = ( \gamma _ { 0 } , \dots , \gamma _ { n - 1 } )$, defined by the property

\begin{equation*} \operatorname { Tr } _ { E / F } ( \beta _ { i } \gamma _ { j } ) = \delta _ { i j } \text { for } i , j = 0 , \dots , n - 1. \end{equation*}

One calls $B$ self-dual if $B = B ^ { * }$. A self-dual basis for $E / F$ exists if either $q$ is even or both $q$ and $n$ 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 $E / F$ exists if either $q$ is even and $n$ is not a multiple of $4$, or both $q$ and $n$ 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 $- 1$. Therefore the existence of such trinomials is an important (as of 2001 still open) question. These topics are discussed in detail in [a10] and [a12].

There is an alternative to using basis representations for finite fields: If one represents the non-zero elements of a Galois field ${F} = \operatorname{GF} ( q )$ as the powers of a primitive element $\omega$, multiplication is trivial, but addition then becomes difficult. For any element $\gamma \in F ^ { * }$, the discrete logarithm of $\gamma$ (to the base $\omega$) is the unique integer $c$ with $0 \leq c \leq q - 2$ satisfying $\omega ^ { c } = \gamma$; one writes $c = \operatorname { log } _ { \omega } \gamma$ and also puts $\operatorname { log } _ { \omega } 0 = \infty$. Identifying the elements of $F$ with their discrete logarithms, multiplying two elements reduces to adding the corresponding discrete logarithms:

\begin{equation*} \operatorname { log } _ { \omega } ( \gamma \delta ) = \operatorname { log } _ { \omega } \gamma + \operatorname { log } _ { \omega } \delta, \end{equation*}

where the addition is done modulo $q - 1$. In order to perform additions in this representation, one needs to determine the discrete logarithm of $\gamma + \delta$ for $\gamma , \delta \in F ^ { * }$. Since $\omega ^ { c } + \omega ^ { d } = \omega ^ { c } ( 1 + \omega ^ { d - c } )$, it suffices to determine the discrete logarithms for sums involving $1$. This motivates the definition of the so-called Zech logarithm $Z ( e ) = \operatorname { log } _ { \omega } ( 1 + \omega ^ { e } )$ (which is actually due to C.G.J. Jacobi); thus, $Z ( e )$ is determined from the equation $1 + \omega^e = \omega^{Z(e)}$. 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) 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); see, e.g., [a5], [a13], [a16], [a17].

As of 2001, the standard reference on Galois fields is [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, coding theory (cf. Coding and decoding), design theory (cf. Block design; Difference set; Symmetric design), cryptography (cf. Cryptography; Cryptology), and signal processing. These applications usually require the use of efficient arithmetics, often in very large Galois fields; e.g., both $\operatorname{GF} ( 2 ^ { 593 } )$ and $\operatorname{GF} ( 2 ^ { 155 } )$ 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 [a10] and [a12]; computational and algorithmic aspects are treated in [a20]. Some good references for actual applications of Galois fields in the areas mentioned above are [a1], [a2], [a3], [a5], [a6], [a10], [a9], [a8], [a11], [a13], [a21], [a18], [a16], [a17], [a19]. A good reference for computational aspects is [a22].

References

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