Namespaces
Variants
Actions

Difference between revisions of "Galois field structure"

From Encyclopedia of Mathematics
Jump to: navigation, search
(→‎References: Lidl & Niederreiter (1996))
m (→‎References: zbl link)
 
(5 intermediate revisions by 3 users not shown)
Line 1: Line 1:
 +
<!--This article has been texified automatically. Since there was no Nroff source code for this article,
 +
the semi-automatic procedure described at https://encyclopediaofmath.org/wiki/User:Maximilian_Janisch/latexlist
 +
was used.
 +
If the TeX and formula formatting is correct and if all png images have been replaced by TeX code, please remove this message and the {{TEX|semi-auto}} category.
 +
 +
Out of 93 formulas, 92 were replaced by TEX code.-->
 +
 +
{{TEX|done}}
 
''Galois field (update)''
 
''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]].
+
This article contains some additional information concerning the structural properties of a [[Galois field|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|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|irreducible polynomial]] of degree $n$ over $F$ (so that $\alpha$ generates $E$ over $F$, cf. [[Galois field|Galois field]]). In this context, one often prefers $\alpha$ to be a generator of the [[Cyclic group|cyclic group]] $E ^ { * }$ (cf. [[Galois field|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|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]]].
+
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|Normal basis theorem]]. Hence such a basis consists of an orbit of maximal length $n$ under the [[Frobenius automorphism|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 [[#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:
+
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 [[#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]] $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:
  
<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>
+
\begin{equation} \tag{a1} \operatorname { Tr } _ { E / F } ( z ) = z + z ^ { q } + \ldots + z ^ { q ^ { n - 1 } } \end{equation}
  
 
and
 
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>
+
\begin{equation} \tag{a2} N _ { E  / F} ( z ) = z \cdot z ^ { q } \cdot \ldots \cdot z ^ { q ^ { n - 1 } }. \end{equation}
  
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
+
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
  
<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>
+
\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 <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]]].
+
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 [[#References|[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 [[#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
+
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
  
<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>
+
\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 <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]]].
+
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 [[#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:
+
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:
  
<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>
+
\begin{equation*} \operatorname { log } _ { \omega } ( \gamma \delta ) = \operatorname { log } _ { \omega } \gamma + \operatorname { log } _ { \omega } \delta, \end{equation*}
  
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]]].
+
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|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., [[#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]]].
+
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 $\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 [[#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====
 
====References====
 
<table>
 
<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">[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">[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">[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">[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">[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">[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">[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">[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">[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">[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">[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">[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">[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); second edition Cambridge University Press (1996) Zbl 0866.11069</TD></TR>
+
<tr><td valign="top">[a14]</td> <td valign="top">  R. Lidl,  H. Niederreiter,  "Finite fields" , Addison-Wesley  (1983); second edition Cambridge University Press (1996) {{ZBL|0866.11069}}</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">[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">[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">[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">[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">[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">[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">[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>
+
<tr><td valign="top">[a22]</td> <td valign="top">  J. von zur Gathen,  J. Gerhard,  "Modern computer algebra" , Cambridge Univ. Press  (1999) {{ZBL|0936.11069}}</td></tr>
 
</table>
 
</table>
 +
 +
[[Category:Field theory and polynomials]]

Latest revision as of 14:35, 19 March 2023

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
How to Cite This Entry:
Galois field structure. Encyclopedia of Mathematics. URL: http://encyclopediaofmath.org/index.php?title=Galois_field_structure&oldid=33663
This article was adapted from an original article by Dieter Jungnickel (originator), which appeared in Encyclopedia of Mathematics - ISBN 1402006098. See original article