2. Finite Fields

In the present section, some elementary results are collected about finite fields, and some broad outlines of their proofs is given. A less cursive approach of these questions can be found in [Lidl, 9] or in [10].

2.1 Characteristic

Let $\mathrm{GF}\! \left( q \right)$ be a finite field of cardinal $q$ . Let $\gamma$ be the (unique) ring homomorphism from $\mathbb {Z}$ into $\mathrm{GF}\! \left( q \right)$ . Since $\mathrm{GF}\! \left( q \right)$ is finite, $\ker \gamma$ cannot be the $\left\{ 0\right\}$ ideal and, since $\mathbb {Z}\left/ \ker \gamma \right. =\gamma \left( \mathbb {Z}\right)$ is an integral domain, $\ker \gamma$ is a prime ideal. The (positive) generator of that ideal is the so-called characteristic of the given field, and it is to be noticed that any $\mathrm{GF}\! \left( q \right)$ contains some prime field $\mathrm{GF}\! \left( p \right) =\mathbb {Z}\! \left/ p\right.$ as subfield.

2.2 Order and degree of an element

Let $x$ be given in $\mathrm{GF}\! \left( q\right) ^{*}$ , and $\gamma$ denotes now, the mapping $\mathbb {Z}\hookrightarrow \mathrm{GF}\! \left( q\right) ^{*}$ defined as $\gamma \, n=x^{n}$ . Then again $\gamma$ is a group homomorphism, and since that mapping cannot be injective, the ideal $\ker \gamma$ is a $n\mathbb {Z}$ for some $n\geq 1$ . That $n$ is the so-called (multiplicative) order of $x$ , and will be denoted as $\mathrm{ord}x$ .

As a consequence, any $x\in \mathrm{GF}\! \left( q\right) ^{*}$ is a root of the polynomial: $X^{\mathrm{ord}x}-1$ , which obviously belongs to $\mathbb {Z}\! \left/ p\right. \left[ X\right]$ . Hence each and every element of $\mathrm{GF}\! \left( q \right)$ is algebraic over $\mathbb {Z}\! \left/ p\right.$ , and thus $\mathrm{GF}\! \left( q \right)$ is a subfield of the algebraic closure of $\mathbb {Z}\! \left/ p\right.$ . In short: $\mathbb {Z}\! \left/ p\right. \subset \mathrm{GF}\! \left( q \right) \subset \mathrm{Alg}\left( \mathbb {Z}\! \left/ p\right. \right)$ .

Let be given an $y\in \mathrm{GF}\! \left( q \right)$ . Since $\mathbb {Z}\! \left/ p\right. \left[ X\right]$ is principal, the set $\left\{ P\in \mathbb {Z}\! \left/ p\right. \left[ X\right] \, \left\vert \, P\left( y\right) =0\right. \right\}$ is an ideal generated by an unique monic polynomial. That polynomial is obviously irreducible and will be referred as the ``minimal polynomial for $y$ ''. We denote it by $P_{y}$ and put $\deg y=\deg P_{y}$ .

2.3 Primitive elements

Any $\mathrm{GF}\! \left( q\right) ^{*}$ is a cyclic group [3], i.e., it exists at least one primitive element $\xi$ such that $\mathrm{GF}\! \left( q\right) ^{*}=\xi ^{\mathbb {Z}}$ . A sketch of the proof is as follows :

2.4 Descriptions of a given finite field

Collecting all these results, we get that any finite field is algebraically generated over its prime field $\mathbb {Z}\! \left/ p\right.$ by some (proper) element $\alpha$ , and thus is isomorphic to some quotient field of $\mathbb {Z}\! \left/ p\right. \left[ X\right]$ . As a consequence, $\mathrm{GF}\! \left( q \right)$ is a vector space over $\mathbb {Z}\! \left/ p\right.$ , proving that $q$ is a power of a prime, i.e., $q=p^{m}$ . Moreover $\mathrm{GF}\! \left( q\right) ^{*}$ cyclic, and is thus multiplicatively generated by some (primitive) element $\xi$ . As a summary, we get:

$\displaystyle \mathrm{GF}\! \left( q \right)$	$\textstyle =$	$\displaystyle \left\{ x\in \mathrm{Alg}\left( \mathbb {Z}\! \left/ p\right. \right) \, \left\vert \, x^{q}=x\right. \right\}$
$\displaystyle \exists \alpha \, :\, \mathrm{GF}\! \left( q \right)$	$\textstyle \sim$	$\displaystyle \mathbb {Z}\! \left/ p\right. \left[ X\right] \, \left/ \, P_{\alpha }\left( X\right) \right.$	(1)
$\displaystyle \exists \xi \, :\, \mathrm{GF}\! \left( q \right)$	$\textstyle =$	$\displaystyle \left\{ 0\right\} \cup \left\{ \xi ^{k}\, \left\vert \, 0\leq k\leq q-2\right. \right\}$

2.5 Frobenius automorphism

The elementary binomial formula $\left( a+n\right) ^{n}=\sum _{0}^{n}{n \choose k}a^{k}b^{n-k}$ comes to a nice result when $n$ is taken equal to the characteristic of $\mathrm{GF}\! \left( q \right)$ . Since any prime $p$ as the property to divide any of the binomials ${p \choose k}$ except for the ending ones, the formula shortens to $\left( a+b\right) ^{p}=a^{p}+b^{p}$ . Thus the mapping $\psi \, :\, x\mapsto x^{p}$ is a morphism of $\mathrm{GF}\! \left( q \right)$ into itself. But $a^{p}-b^{p}=0$ implies $\left( a-b\right) ^{p}=\left( a-b\right) =0$ and $\psi$ is injective and therefore bijective.

The Frobenius mapping $\psi$ induces an automorphism over $\mathrm{GF}\! \left( q \right)$ .

Let $x$ be some element of $\mathrm{Alg}\left( \mathbb {Z}\! \left/ p\right. \right)$ , $P_{x}$ as minimal polynomial, and $n=\deg x$ . Since the coefficients of $P_{x}$ are in $\mathbb {Z}\! \left/ p\right.$ , they are $\psi$ -invariant, and we get $P_{x}\left( \psi \left( x\right) \right) =\left( \psi P_{x}\right) \left( \psi \left( x\right) \right) =\psi \left( P_{x}\left( x\right) \right) =0$ . Any $\psi ^{k}\left( x\right)$ is therefore a root of $P_{x}$ , and since $\deg P=n$ , there are at most $n$ different $\psi ^{k}\left( x\right)$ . On the other hand, $\psi ^{k}\left( x\right) =\psi ^{j}\left( x\right)$ leads to $\psi ^{m}\left( y\right) =y$ where $m=\left\vert k-j\right\vert$ and $y$ is a root of $P_{x}$ . But $\psi ^{m}\left( y\right) =y$ is $y^{p\: \widehat{\: }\, m}=y$ , implying $y\in \mathrm{GF}\! \left( p^{m} \right)$ and $\deg y\leq m$ . Therefore, $n$ divides $k-j$ : there are exactly $n$ different $\psi ^{k}\left( x\right)$ .

The elements of a $n$ -sized $\psi$ -orbit are the roots of an irreducible polynomial of degree $n$ over $\mathbb {Z}\! \left/ p\right.$ .

2.6 Subfields and subgroups

Therefore $\mathrm{GF}\! \left( p^{m} \right)$ is the subfield of $\mathrm{Alg}\left( \mathbb {Z}\! \left/ p\right. \right)$ that is fixed by $\psi ^{m}$ , leading to the following embedding result $\left[ \mathrm{GF}\! \left( p^{n} \right) \subset \mathrm{GF}\! \left( p^{m} \right) \right] \Leftrightarrow \left[ n\, \vert\, m\right]$ . That result can also be seen as resulting from the divisibility of one characteristic polynomial by the other.

Let us now consider all the multiplicative subgroups of a given $\mathrm{GF}\! \left( 2^{m} \right) ^{*}$ . Since that group is cyclic, it contains exactly one subgroup of cardinal $d$ for each $d$ that divides $q-1$ . Some of them are a field-group $\mathrm{GF}\! \left( 2^{n} \right) ^{*}$ where $n\vert m$ , but most of them are not. Therefore, in Fig. 1, the subfields lattice (boldfaced) is a sublattice of the multiplicative groups lattice.

**Figure:** Subgroups of $\mathrm{GF}\! \left( 256 \right) ^{*}\protect$ .
$\resizebox* {!}{0.25\textheight}{\includegraphics{struct.eps}}$

The proper elements of such a $d$ -sized subgroup are exactly the $\varphi \left( d\right)$ roots of $\Phi _{d}\left( X\right)$ , the cyclotomic polynomial relative to the $d$ exponent. As an example, when $q=256$ , we get $q-1=3\times 5\times 17$ and therefore the characteristic polynomial of $\mathrm{GF}\! \left( 256 \right)$ splits into $X^{256}-X=X\times \Phi _{1}\times \Phi _{3}\times \Phi _{5}\times \Phi _{15}\times \Phi _{17}\times \Phi _{51}\times \Phi _{85}\times \Phi _{255}$ .

Moreover, since $\Phi _{15}$ describes the primitive elements of $\mathrm{GF}\! \left( 2^{4} \right)$ , it splits into two polynomials of degree 4, and since $\Phi _{17},\, \Phi _{51},\, \Phi _{85},\, \Phi _{255}$ describe proper elements of $\mathrm{GF}\! \left( 2^{8} \right)$ , they split over $\mathbb {Z}\! \left/ p\right.$ into irreducible polynomials of degree 8.

2.7 Trace of an element

The so-called trace of an element in $\mathrm{GF}\! \left( q \right)$ is defined as $\mathrm{Tr}_{m}\left( x\right) =\sum _{0}^{m-1}\, \psi ^{k}\left( x\right)$ . Thus, for a proper element $x$ of $\mathrm{GF}\! \left( q \right)$ , $\mathrm{Tr}_{m}\left( x\right)$ is the sum of all the roots of the minimal polynomial of $x$ . For an $x$ of smaller degree, that sum is to be multiplied by the natural integer $m\, /\deg x$ and then reduced modulo $p$ . Elementarily, $\mathrm{Tr}_{m}\left( x+y\right) =\mathrm{Tr}_{m}\left( x\right) +\mathrm{Tr}_{m}\left( y\right)$ .

2.8 Discrete logarithm and Zech logarithm

Given a primitive element $\xi$ , there is a one to one correspondence between the $k\in \mathbb {Z}\left/ \, q-1\right.$ and the $\xi ^{k}\in \mathrm{GF}\! \left( q\right) ^{*}$ . With the convention $0=\xi ^{\infty }$ , we get a bijection $L_{\xi }$ from $\mathrm{GF}\! \left( q \right)$ towards $\mathbb {N}_{q}\doteq \mathbb {Z}\left/ \, q-1\right. \cup \left\{ \infty \right\}$ (since $\mathbb {Z}\left/ \, q-1\right.$ can not be ordered as a group, the traditional notation, `` $0=\xi ^{-\infty }$ '', is rather confusing).

That bijection $L_{\xi }$ can be used to carry the field structure of $\mathrm{GF}\! \left( q \right)$ onto $\mathbb {N}_{q}$ . Obviously, the image of $\times$ inside $\mathrm{GF}\! \left( q \right)$ is $+$ inside $\mathbb {N}_{q}$ . But, since integer arithmetic modulo $q-1$ is far easier than computations of polynomials modulo $P_{\xi }\left( X\right)$ over $\mathbb {Z}\! \left/ p\right.$ , it is of great interest to consider the isomorphic image in $\mathbb {N}_{q}$ of the first law (addition) in $\mathrm{GF}\! \left( q \right)$ .

Let us denote by $\mathbb {A}$ that first law over $\mathbb {N}_{q}$ . From $\xi ^{a}+\xi ^{b}=\xi ^{c}\Rightarrow \xi ^{a+k}+\xi ^{b+k}=\xi ^{c+k}$ , we get $\left( a+k\right) \mathbb {A}\left( b+k\right) =\left( a\mathbb {A}b\right) +k$ , and therefore the whole $\mathbb {A}$ table is known when the function $Z\, :\, x\mapsto x\mathbb {A}0$ is known. The so-called Zech logarithm is nothing but precisely that function $Z$ .