5 Finite fields

5.1 Existence and Uniqueness

Finite fields are very useful objects in many areas of mathematics such as Algebra, Number Theory and Combinatorics. They also have many practical applications, for instance, they are crucial in Coding Theory and Cryptography. They also form a nice demonstration of Galois Theory, and in this chapter, we’ll completely classify them and determine their subfield structure.

The first basic result limits the possible sizes of a finite field.

Lemma 5.1 Let $K$ be a finite field. Then $K$ is a field extension of $\mathbb{F}_p$ for some prime $p$, and $|K|=p^n$ where $n=[K:\mathbb{F}_p]$.

Proof. Every field contains a prime subfield and since $K$ is finite, this must be of the form $\mathbb{F}_p$ for some prime $p$. Furthermore, $K$ is a vector space over $\mathbb{F}_p$ of dimension $n=[K:\mathbb{F}_p]<\infty$ so, as a vector space over $\mathbb{F}_p$ is isomorphic to $\mathbb{F}_p^{\,n}$. Thus, $|K|=|\mathbb{F}_p^{\,n}|=|\mathbb{F}_p|^n=p^n$.

Thus, the number of elements in a finite field must be a prime power so, for instance, there is no finite field with $6$ elements. We are led to ask: given a prime power $p^n$, is there always a field with $p^n$ elements, and if so, how many are there?

Lemma 5.2 Given a prime number $p$ and integer $n\geq 1$, there is a field $K$ with $q=p^n$ elements.

Proof. Let $L$ be an extension of $\mathbb{F}_p$ such that $f(x)=x^q-x$ splits completely over $L$. Any repeated root of $f(x)$ in $L$ must also be a root of the formal derivative $Df(x)$. However, $Df(x)=p^nx^{p^n-1}-1=-1$ never vanishes, so $f(x)$ has $\deg f(x)=q$ distinct roots in $L$. This means $K=\{\alpha\in L\,\mid\, \alpha^q=\alpha\}$ is a subset of $L$ containing $q$ elements. We claim that $K$ is a subfield of $L$. Indeed, given $\alpha,\beta\in K$, then \[(\alpha\beta)^{q}=\alpha^q\beta^q=\alpha\beta\quad\text{and}\quad (\alpha/\beta)^{q}=\alpha^q/\beta^q=\alpha/\beta\quad\text{for $\beta\neq 0$.}\] Furthermore, repeated use of the Child’s Binomial Theorem gives \[(\alpha\pm\beta)^{q}=(\alpha\pm\beta)^{p^n}=(\alpha^p\pm\beta^p)^{p^{n-1}}=\cdots=\alpha^{p^n}\pm\beta^{p^n}=\alpha\pm\beta.\] Thus $K$ is closed under addition, subtraction, multiplication and division (by non-zero elements) and is hence a field with $q=p^n$ elements.

Theorem 5.1 Let $K$ be a finite field with $|K|=q=p^n$ elements. Then

$\;\;(i)$ $\alpha^q=\alpha$ for every $\alpha\in K$,

$\;(ii)$ $x^q-x=\prod_{\alpha\in K}(x-\alpha)$,

$(iii)$ $K$ is a splitting field of $x^q-x$ over $\mathbb{F}_p$.

Proof. Consider the multiplicative group $K^\times=K\setminus\{0\}$. This is a group with $q-1$ elements so Lagrange’s Theorem implies that $\alpha^{q-1}=1$ for $\alpha\in K^\times$. Clearly we have $\alpha^q=\alpha$ for each $\alpha\in K$, proving part $(i)$.

The $q$ elements of $K$ are thus roots of $x^q-x$ and part $(ii)$ follows since $x^q-x$ is monic of degree $q$.

Finally, $x^q-x$ splits completely in $K$, and since every element of $K$ is a root, $x^q-x$ can’t split over a strictly smaller field. Thus $K$ is a splitting field of $x^q-x\in\mathbb{F}_p[x]$.

Noting that splitting fields are unique up to isomorphism, we’ve found there is precisely one field (up to isomorphism) with $q=p^n$ elements. Hence we can speak of “the” finite field with $q=p^n$ elements, which we denote by $\mathbb{F}_q$. These general finite fields were discovered by Galois, and are sometimes denoted by $\textrm{GF}(q)$ where “$\textrm{GF}$” stands for “Galois Field”.

Warning: We’ve mentioned this before, but it’s worth repeating: $\mathbb{F}_q$ is not the same thing as $\mathbb{Z}/q$ unless $q$ is itself a prime. When $q$ is composite, the ring $\mathbb{Z}/q$ will have zero divisors so is not a field. The splitting field description above is pretty much the simplest way to define general finite fields.

The multiplicative structure of a finite field is a easy as it could possibly be: the multiplicative subgroup $\mathbb{F}_q^{\,\times}$ is a cyclic group. In fact, we’ll prove a slightly more general statement that will be useful in future chapters:

Theorem 5.2 If $G$ is a finite subgroup of the multiplicative group $K^\times$ of a field $K$, then $G$ is a cyclic group.

Proof. Since multiplication in $K$ is commutative, $G$ is a finite abelian group. When $|G|=1$, there is nothing to prove as $G$ is just the trivial group $\{1\}\subset K^\times$. When $|G|>1$, the Classification of finite abelian groups (Theorem 0.4) tells us \[G\cong\mathbb{Z}/d_1\,\times\,...\,\times\,\mathbb{Z}/d_k\] for some integers $1<d_1\leq d_2\leq\cdots\leq d_k$ with $d_1\,|\,d_2\,|\,...\,|\,d_k$. In particular, $|G|=d_1d_2\cdots d_k$.

On the other hand, notice that any element in $\mathbb{Z}/d_i$ has order dividing $d_i$ and this divides $d_k$. In particular, every $g\in G$ has order dividing $d_k$. In other words, the elements $g\in G$ are all roots of the polynomial $x^{d_k}-1=0$ in $K^\times$. If $k>1$, then we would have $d_1>1$ and so $|G|=d_1d_2\cdots d_k>d_k$. But this gives a contradiction since $K$ is a field and a polynomial can’t have more roots than its degree. Hence $k=1$ and $G$ is cyclic as required.

The special case $G=\mathbb{F}_q^{\,\times}$ in $\mathbb{F}_q$ shows that \[\mathbb{F}_q^{\,\times}\cong\mathbb{Z}/(q-1)\] as groups, where $\mathbb{F}_q^{\,\times}$ uses multiplication and $\mathbb{Z}/(q-1)$ uses addition.

Remark. Those who did Elementary Number Theory II might recall the concept of a primitive root modulo $p$ for a prime $p$. These are integers $a\in\mathbb{Z}$ such that $1,a,a^2,...,a^{p-2}$ runs through all elements of $\{1,2,...,p-1\}$ when taken mod $p$. The fact that $\mathbb{F}_p^{\,\times}\cong\mathbb{Z}/(p-1)$ is cyclic is saying that primitive roots mod $p$ exist. For example, one can check that $3$ is a primitive root mod $7$, but $2$ isn’t, since $2^3\equiv 1\bmod 7$.

An immediate consequence of the above Theorem is that any finite field can be constructed as a simple field extension $\mathbb{F}_{p^n}=\mathbb{F}_p(\alpha)$ for some $\alpha\in\mathbb{F}_{p^n}$. Just let $\alpha$ be any generator of $\mathbb{F}_{p^n}^{\,\times}$. Finding an explicit $\alpha$ is generally a non-trivial problem, but we can do so when the numbers are small enough. And once we have such an $\alpha$ (or more precisely, the minimal polynomial of $\alpha$ over $\mathbb{F}_p$), we can use it to do explicit calculations and implement finite fields in a computer algebra package.

Example 5.1 $(i)$ The polynomial $f(x)=x^2+x+1\in\mathbb{F}_2[x]$ is irreducible over $\mathbb{F}_2$. Let $\theta$ be a root and consider \[\mathbb{F}_2(\theta)=\{a+b\theta\,\mid\, a,b\in\mathbb{F}_2\}=\{0,1,\theta,1+\theta\}.\] This is a degree $2$ extension of $\mathbb{F}_2$ and so we must have $\mathbb{F}_4=\mathbb{F}_2(\theta)$. Furthermore, the multiplicative subgroup $\mathbb{F}_4^{\,\times}=\{1,\theta,1+\theta\}$ is cyclic of order $3$. This is generated by either of the non-unit elements $\theta$ and $1+\theta$, and in fact we have \[\theta^2=1+\theta,\qquad (1+\theta)^2=\theta.\] Notice that in $\mathbb{F}_2[x]$, \[x(x+1)f(x)=x(x+1)(x^2+x+1)=x^4-x\in\mathbb{F}_2[x]\] is the product of all the irreducible polynomials of degrees $1$ and $2$ in $\mathbb{F}_2[x]$. Using this product (or computing directly), we see that $\alpha^4=\alpha$ for each of the four elements $\alpha\in\mathbb{F}_4$.

$(ii)$ There are exactly two irreducible (monic) cubic polynomials in $\mathbb{F}_2[x]$: \[f_1(x)=x^3+x+1\quad\text{and}\quad f_2(x)=x^3+x^2+1.\] Let $\theta_1,\theta_2$ be roots of $f_1(x),f_2(x)$ respectively. It appears that we have two extensions $\mathbb{F}_2(\theta_1)$ and $\mathbb{F}(\theta_2)$ which are both of degree $3$ over $\mathbb{F}_2$. But our work in this section tells us these are just two different ways of describing the unique field $\mathbb{F}_8=\mathbb{F}_{2^3}$ of degree $3$ over $\mathbb{F}_2$, i.e. there must be a field isomorphism $\varphi$ from one to the other. To find it, notice that \[f_2(\theta_2)=\theta_2^3+\theta_2^2+1=0\;\;\;\implies\;\;\; \theta_2^{3}(1+\theta_2^{-1}+\theta_2^{-3})=0\;\;\;\implies\;\;\; f_1(\theta_2^{-1})=0.\] Thus we can set $\varphi(\theta_1)=\theta_2^{-1}$ and obtain the isomorphism \[\begin{align*} \varphi:\mathbb{F}_2(\theta_1) & \longrightarrow \mathbb{F}_2(\theta_2) \\ a+b\theta_1+c\theta_1^2 & \longmapsto a+b\theta_2^{-1}+c\theta_2^{-2}. \end{align*}\] Finally, we note that $f_1(x)f_2(x)=x^6+x^5+x^4+x^3+x^2+x+1=(x^7-1)/(x-1)$ and \[x(x+1)(x^3+x+1)(x^3+x^2+1)=x^8-x\in\mathbb{F}_2[x]\] is the product of all the irreducible polynomials of degrees $1$ and $3$ in $\mathbb{F}_2[x]$. In particular, whichever description $\mathbb{F}_2(\theta_1)\cong\mathbb{F}_2(\theta_2)$ we use for $\mathbb{F}_8$, we have $\alpha^8=\alpha$ for every element. Finding a specific $\alpha\in\mathbb{F}_8$ that generates the multiplicative group $\mathbb{F}_8^{\,\times}$ is part of the first problem in Problem Sheet 5.

5.2 Galois groups for finite fields

Given $q=p^n$ for some prime number $p$ and integer $n\geq 1$, consider the $p\,$th power map on $\mathbb{F}_q$: \[\begin{align*} \sigma:\mathbb{F}_q &\longrightarrow \mathbb{F}_q \\ \alpha &\longmapsto \sigma(\alpha)=\alpha^p \end{align*}\] This is a field homomorphism, since $\sigma(1)=1^p=1$ and for $\alpha,\beta\in\mathbb{F}_q$, we have \[\begin{align*} \sigma(\alpha+\beta)&=(\alpha+\beta)^p=\alpha^p+\beta^p=\sigma(\alpha)+\sigma(\beta), \\ \sigma(\alpha\beta)&=(\alpha\beta)^p=\alpha^p\beta^p=\sigma(\alpha)\sigma(\beta). \end{align*}\] Field homomorphisms are always injective, so being an injection from $\mathbb{F}_q$ into itself, it must be bijective. Furthermore, by Fermat’s Little Theorem, $\sigma$ is the identity map on the subfield $\mathbb{F}_p\subset\mathbb{F}_q$. In particular, $\sigma$ is an $\mathbb{F}_p$-automorphism of $\mathbb{F}_q$. This special automorphism, called the Frobenius automorphism, is the key to determining the Galois group of $\mathbb{F}_q/\mathbb{F}_p$.

Theorem 5.3 Let $q=p^n$ for some prime number $p$ and integer $n\geq 1$. Then

$\;(i)$ the field extension $\mathbb{F}_{q}/\mathbb{F}_p$ is a Galois extension of degree $n$,

$(ii)$ the Frobenius automorphism $\sigma$ generates $\Gal(\mathbb{F}_{q}/\mathbb{F}_p)$ and there is a group isomorphism \[\begin{align*} \Gal(\mathbb{F}_{p^n}/\mathbb{F}_p) & \longrightarrow \;\;\mathbb{Z}/n \\ \sigma & \longmapsto 1\bmod n. \end{align*}\]

Proof. $(i)$ From the previous section, $\mathbb{F}_q$ is a splitting field of $x^q-x$ over $\mathbb{F}_p$ so the extension is normal. Suppose $\alpha\in\mathbb{F}_q$ has minimal polynomial $f(x)$ over $\mathbb{F}_p$. Then $f(x)$ divides $x^q-x$, but we showed this polynomial has no repeated roots hence $f(x)$ doesn’t either. Hence the extension is also separable. (Alternatively, one can use the sufficient conditions for separability in Theorem 4.7). Finally, the degree $[\mathbb{F}_q:\mathbb{F}_p]=n$ by 5.1 since $q=p^n$.

$(ii)$ Since $\mathbb{F}_q/\mathbb{F}_p$ is a Galois extension of degree $n$, we know that $|\Gal(\mathbb{F}_q/\mathbb{F}_p)|=n$ and so $\sigma^n=\id$ by Lagranges’s Theorem. (Actually, we can see this directly since $\sigma^n(\alpha)=\alpha^{p^n}=\alpha^q=\alpha$ for each $\alpha\in\mathbb{F}_q$.)

We need to show that $\sigma$ has order exactly $n$. If $\sigma^m=\id$ for some positive integer $m$, then $\sigma^m(\alpha)=\alpha^{p^m}=\alpha$ for all $\alpha\in\mathbb{F}_q$ and the polynomial $x^{p^m}-x$ has $q=p^n$ roots. Thus $p^n\leq p^m$, i.e. $n\leq m$ and we deduce $\sigma$ has order $n$ as required and we easily obtain the desired isomorphism.

The subgroup structure of the cyclic group \[G=\Gal(\mathbb{F}_q/\mathbb{F}_p)=\langle\,\sigma\,\rangle\cong\mathbb{Z}/n\] is as easy as it could be: all subgroups are cyclic and there is a unique cyclic subgroup \[H=\langle\,\sigma^{n/k}\,\rangle\cong\mathbb{Z}/k\] for each divisor $k\mid n$. Hence the Galois correspondence tells us there is a unique subfield $\mathbb{F}_q^{\,H}$ for each choice of $k\mid n$. If we write $m=n/k$, then \[\mathbb{F}_q^{\,H}=\{\alpha\in\mathbb{F}_q\,\mid\, \alpha^{p^m}=\alpha\}\] By the Tower Law and the Fundamental Theorem, \[[\mathbb{F}_q^{\,H}:\mathbb{F}_p]=\frac{[\mathbb{F}_q:\mathbb{F}_p]}{[\mathbb{F}_q:\mathbb{F}_q^{\,H}]}=\frac{n}{|H|}=\frac{n}{k}=m\] so this fixed field is $\mathbb{F}_q^{\,H}\cong\mathbb{F}_{p^m}$. As $k$ runs through the divisors of $n$, so does $m=n/k$ and hence there is a unique subfield isomorphic to $\mathbb{F}_{p^m}$ for each divisor $m\mid n$. Since this subfield is unique, we can talk unambiguously about the extension $\mathbb{F}_{p^n}/\mathbb{F}_{p^m}$ when $m\mid n$. We note that as the Galois group $G$ is abelian, any subgroup $H\subset G$ is automatically normal. The Fundamental Theorem identifies the Galois group $\Gal(\mathbb{F}_{p^m}/\mathbb{F}_p)$ with the quotient of $G/H$: the isomorphism \[\Gal(\mathbb{F}_{p^m}/\mathbb{F}_p)\cong\frac{\Gal(\mathbb{F}_{p^n}/\mathbb{F}_p)}{\Gal(\mathbb{F}_{p^n}/\mathbb{F}_{p^m})}\] amounts to the isomorphism \[\mathbb{Z}/m\cong\frac{\mathbb{Z}/n}{\mathbb{Z}/(n/m)}.\]

Example 5.2 Let’s apply the above to the degree $30$ extension $\mathbb{F}_{2^{30}}/\mathbb{F}_{2}$. The divisors of $30$ are \[\{1,2,3,5,6,10,15,30\}\] and for each $m$ in this set, the intermediate field $\mathbb{F}_2\subset\mathbb{F}_{2^m}\subset\mathbb{F}_{2^{30}}$ corresponds to the subgroup \[\Gal\left(\mathbb{F}_{2^{30}}/\mathbb{F}_{2^m}\right)\cong\mathbb{Z}/(30/m)\subset\mathbb{Z}/30\cong\Gal\left(\mathbb{F}_{2^{30}}/\mathbb{F}_{2}\right).\] Running through each divisor, we get the following diagrams

Remark. It is important to remember that $\mathbb{F}_{p^m}$ is a subfield of $\mathbb{F}_{p^n}$ precisely when $m$ divides $n$, not just when $m\leq n$. For instance, $\mathbb{F}_{8}=\mathbb{F}_{2^3}$ does not have a subfield isomorphic to $\mathbb{F}_4=\mathbb{F}_{2^2}$, since $2\nmid 3$.

5.3 Counting irreducible polynomials over finite fields

Our construction of the finite field $\mathbb{F}_{p^n}$ as the splitting field of $x^{p^n}-x$ over $\mathbb{F}_p$ is quite abstract. On the other hand, if $f(x)\in\mathbb{F}_p[x]$ is irreducible of degree $n$ with root $\alpha$, then $\mathbb{F}_p(\alpha)=\mathbb{F}_p[x]/(f(x))$ is a degree $n$ extension of $\mathbb{F}_p$ so must be isomorphic to $\mathbb{F}_{p^n}$. Representing finite fields in this way is much more approachable, for example in computer implementations, since one works with an irreducible degree $n$ polynomial rather than the (very reducible) degree $p^n$ polynomial $x^{p^n}-x$. The problem is, how do we find an explicit irreducible polynomial of degree $n$ that does the job? This is quite difficult in general, though in a later chapter we’ll see at trick that can turn small degree irreducible polynomials into larger ones. But in this section, we’ll at least attempt to count them.

We can quickly reduce to the monic case, since we can divide through by the top (non-zero) coefficient. So define \[N_p(m)=|\{f(x)\in\mathbb{F}_p[x]\,\mid\, \text{$f(x)$ is monic irreducible of degree $m$}\}|.\] For a first attempt, (recalling questions from Problem Sheet 1),

For degree $1$, the polynomials $x+a$ for each $a\in\mathbb{F}_p$ are irreducible, so $N_p(1)=p$.
For degree $2$, the reducible monic polynomials are $(x-a)(x-b)$ where $a,b\in\mathbb{F}_p$. There will be $p$ of these with $a=b$ and $\binom{p}{2}=\frac{1}{2}p(p-1)$ with $a\neq b$ so \[N_p(2)=p^2-p-\frac{1}{2}p(p-1)=\frac{p^2-p}{2}.\]

For degree $3$ and above, this approach gets very laborious. However, with our new knowledge of subfields of finite fields, we can do better with the following simple observation.

Lemma 5.3 With $N_p(m)$ defined as above, we have $mN_p(m)=|\{\alpha\in\mathbb{F}_{p^m}\,\mid\, \mathbb{F}_p(\alpha)=\mathbb{F}_{p^m}\}|$.

Proof. Counting elements in the right-hand side, any $\alpha\in\mathbb{F}_{p^m}$ with $\mathbb{F}_p(\alpha)=\mathbb{F}_{p^m}$ is a root of exactly one of the $N_p(m)$ monic irreducible $f(x)\in\mathbb{F}_p[x]$. Furthermore, each of these has exactly $m$ roots.

To use this, we notice that $\mathbb{F}_p(\alpha)\neq \mathbb{F}_{p^m}$ if and only if $\alpha$ belongs to a proper subfield of $\mathbb{F}_{p^m}$. For example, since $\mathbb{F}_{p^3}$ only contains one proper subfield $\mathbb{F}_p\subset\mathbb{F}_{p^3}$, we have \[3N_p(3)=|\mathbb{F}_{p^3}|-|\mathbb{F}_{p}|=p^3-p\quad\implies\quad N_p(3)=\frac{p^3-p}{3}.\] Similarly, if $m$ is prime then $\mathbb{F}_{p^m}$ only contains one proper subfield $\mathbb{F}_p$ and $N_p(m)=(p^m-p)/m$.

When $m$ is not prime, we only have to do a little more work using the subfield structure developed in the last section. For instance, $\mathbb{F}_{p^4}$ only has subfields $\mathbb{F}_p\subset\mathbb{F}_{p^2}\subset\mathbb{F}_{p^4}$ so \[4N_p(4)=|\mathbb{F}_{p^4}|-|\mathbb{F}_{p^2}|=p^4-p^2\quad\implies\quad N_p(4)=\frac{p^4-p^2}{4}.\]

Similarly, we have $\mathbb{F}_p(\alpha)\neq\mathbb{F}_{p^6}$ if and only if $\alpha\in\mathbb{F}_{p^3}\cup\mathbb{F}_{p^2}$ and since $\mathbb{F}_{p^3}\cap\mathbb{F}_{p^2}=\mathbb{F}_p$, we obtain \[6N_p(6)=p^6-p^3-p^2+p\quad\implies\quad N_p(6)=\frac{p^6-p^3-p^2+p}{6}.\] Generally, the top term dominates for large $p$, and out of the $p^m$ monic polynomials of degree $m$, approximately $p^m/m$ are irreducible.

Remark. Working a bit harder, one can turn the above ideas into a general formula. Let $\mathcal{N}_p(m)$ denote the set of irreducible monic polynomials $f(x)\in\mathbb{F}_p[x]$ of degree $m$, so that $|\mathcal{N}_p(m)|=N_p(m)$. Then one can show that \[x^{p^n}-x=\prod_{m\mid n}\;\prod_{f(x)\in\mathcal{N}_p(m)} f(x).\] Then by comparing degrees, we obtain a formula $\displaystyle p^n=\sum_{m\mid n} mN_p(m)$ which can be used recursively to compute any $N_p(n)$. For example, \[p^6=N_p(1)+2N_p(2)+3N_p(3)+6N_p(6)\] and the formulas $N_p(1)=p$, $N_p(2)=(p^2-p)/2$, $N_p(3)=p^3-p$ leads to the formula for $N_p(6)$ above.

Working even harder, using a technique from Number Theory called Möbius inversion, one can turn this into a remarkable formula \[N_p(n)=\frac{1}{n}\sum_{m\mid n}\;\mu\left(\frac{n}{m}\right)p^m\quad\text{where}\quad \mu(r)=\begin{cases} 1 & \text{if $r=1$,} \\ (-1)^k & \text{if $r$ is a product of $k$ distinct primes,} \\ 0 & \text{if $r$ is divisible by a square of a prime.} \end{cases}\] See Exercise 5.6 and 5.7 in Brzezinski’s book for details, if you’re interested…