Finite Fields

The theory of finite fields is a key part of number theory, abstract algebra, arithmetic algebraic geometry, and cryptography, among others. Many questions about the integers or the rational numbers can be translated into questions about the arithmetic in finite fields, which tends to be more tractable. As finite fields are well-suited to computer calculations, they are used in many modern cryptographic applications.

A field is a commutative ring in which every nonzero element has a multiplicative inverse.
That is, a field is a set $F$ with two operations, $+$ and $\cdot$, such that

(1) $F$ is an abelian group under addition;
(2) $F^* = F - \{ 0 \}$ is an abelian group under multiplication, where $0$ is the additive identity in $F$;
(3) $a\cdot (b+c) = a\cdot b + a\cdot c$ for all $a,b,c \in F$.

The rational numbers $\mathbb Q$, the real numbers $\mathbb R$, and the complex numbers $\mathbb C$ are all fields.

If $\alpha$ is an algebraic integer, then $Q(\alpha)$ is also a field.

The quotient ring ${\mathbb Z}/(p)$ is a field with $p$ elements. (This is sometimes written ${\mathbb Z}_p$, but most textbooks reserve this notation for a different ring involving $p$-adic integers.)

The last example is a finite field, with $p$ elements. From now on, it will be written ${\mathbb F}_p$ and called "the field with $p$ elements." This requires some justification: why is there only one field with $p$ elements? To make sense of this, it is necessary to define a notion of when two fields are the same.

A homomorphism between two rings $F$ and $G$ is a function $f \colon F \to G$ such that

(1) $f(a +_F b) = f(a) +_G f(b)$

(2) $f(a \times_F b) = f(a) \times_G f(b)$

(3) $f(1_F)=1_G.$

An isomorphism is an homomorphism that is also a bijection. If there is an isomorphism between two rings, the rings are said to be isomorphic.

Here is a warmup that demonstrates some of the ideas involved in the classification of finite fields:

In a field $F$, let $p$ be the smallest positive integer such that $p \cdot 1 = \underbrace{1+1+\cdots+1}_{p\text{ times}} = 0$ in $F$. If $p$ does not exist, say that $F$ has characteristic $0$, and if $p$ exists, say that $F$ has characteristic $p$.

The characteristic helps classify finite fields:

If $F$ has characteristic $p \ne 0$, then $p$ is prime and there is a one-to-one homomorphism ${\mathbb F}_p \to F$. In the latter case, if $F$ is finite, then it has $p^k$ elements for some positive integer $k$.

The first step is to show that $p$ is prime. This is clear: suppose $p$ is not prime and write $p = ab$, $a,b<p$. Then $$(a \cdot 1) \cdot (b \cdot 1) = \underbrace{(1+1+\cdots+1)}_{a \text{ times}}\underbrace{(1+1+\cdots+1)}_{b \text{ times}} = \underbrace{1+1+ \cdots + 1}_{ab \text{ times}} = ab \cdot 1 = p \cdot 1 = 0,$$ and since this is in a field, this implies that $a \cdot 1 = 0$ or $b\cdot 1 = 0$, which violates the minimality of $p$.

Next, define a homomorphism $f \colon {\mathbb F}_p \to F$ by $f(a \cdot 1) = a\cdot 1$; this is clearly one-to-one and clearly a homomorphism. So there is a copy of ${\mathbb F}_p$ inside $F$.

The rest of the statement follows from the theory of vector spaces: $F$ is a vector space over ${\mathbb F}_p$, and since it is finite it has some dimension $k$, and some basis $x_1, \ldots, x_k$, such that every element of $F$ can be written uniquely in the form $a_1x_1 + \cdots + a_k x_k$ for $a_i \in {\mathbb F}_p$, so there are $p^k$ choices for elements of $F$.

The above result is the first step in the classification of finite fields. This full classification is quite exact and quite strong. A partial proof will be given in the sections below.

(1) Every finite field has $p^k$ elements for some prime $p$ and some positive integer $k$.

(2) For every prime $p$ and positive integer $k$, there is a finite field with $p^k$ elements.

(3) Any two finite fields of the same size are isomorphic.

So: there is exactly one finite field ${\mathbb F}_{p^k}$ with $p^k$ elements (up to isomorphism).

Note that (1) has been proved above. Proving (2) requires a quotient construction and an existence theorem about irreducible polynomials, and the proof of (3) follows quickly from the proof of (2).

As seen above, finite fields with $p^k$ elements contain a copy of ${\mathbb F}_p$. The construction of these fields starts with the polynomial ring ${\mathbb F}_p[x]$ of polynomials in one variable with coefficients in ${\mathbb F}_p$. The finite field with $p^k$ elements will be a suitable quotient of this ring.

The polynomial $x^2+x+1$ is irreducible in ${\mathbb F}_2[x]$ (in fact, it is the only irreducible quadratic polynomial in ${\mathbb F}_2[x]$). Consider the quotient $$F = {\mathbb F}_2[x]/(x^2+x+1).$$ Letting $\alpha = {\overline x}$, $F$ can be thought of as ${\mathbb F}_2[\alpha]$ where $\alpha^2 +\alpha+1 = 0$.

Then the elements of $F$ are $0,1,\alpha,\alpha+1$. Polynomials in $\alpha$ of larger degree can be reduced to linear polynomials in $\alpha$ by using the relation $\alpha^2 = \alpha+1$. So $F$ has four elements, and in fact it is not hard to check that $F$ is a field. In particular, $\alpha(\alpha+1) = 1$, so $\alpha$ and $\alpha+1$ are multiplicative inverses (and $1$ is its own inverse).

This field is denoted ${\mathbb F}_4$. Note that the characteristic of ${\mathbb F}_4$ is $2$. Do not mistake ${\mathbb F}_4$ for the integers modulo $4$: for example, ${\mathbb Z}/(4)$ is not a field, and $1+1 \ne 0$ in ${\mathbb Z}/(4)$.

In general, if $K$ is a field, $K[x]/(f(x))$ will be a field if and only if $f(x)$ is irreducible. The proof is the same as the proof that ${\mathbb Z}/(n)$ is a field if and only if $p$ is prime: if $a(x)$ is relatively prime with $f(x)$, there is a form of Bezout's identity that produces polynomials $b(x),g(x)$ such that $a(x)b(x)+f(x)g(x) = 1$. Since all nonzero $a(x)$ whose degree are less than that of $f(x)$ are relatively prime to $f(x)$, because $f(x)$ is irreducible, this gives multiplicative inverses for all the nonzero elements of $K[x]/(f(x)).$

The number of elements in ${\mathbb F}_p[x]/(f(x))$ will be $p^k$, where $k$ is the degree of $f(x)$, because every element of this field can be written uniquely as $$a_0 + a_1 {\overline x} + \cdots + a_{k-1}{\overline x}^{k-1},$$ since all higher powers of $\overline x$ can be reduced to lower powers via the relation $f({\overline x}) = 0$.

So this construction gives a finite field of size $p^k$ for all primes $p$ and positive integers $k$, if there is always an irreducible polynomial of any degree in ${\mathbb F}_p[x]$. This is not immediately obvious.

Here is a fundamental fact that is essential in the proof of the classification theorem:

Let $p$ be a prime and $n$ a positive integer. Then, in ${\mathbb F}_p[x]$,
\[
x^{p^n}-x = \prod_{d|n} \prod_{\stackrel{f(x) \text{ monic, irred.}}{\text{deg}(f)=d}} f(x).
\]

For example, in ${\mathbb F}_2[x]$, $$x^{16}-x = x(x+1)(x^2+x+1)(x^4+x+1)(x^4+x^3+1)(x^4+x^3+x^2+x+1).$$

The right side is the product of all the irreducible polynomials in ${\mathbb F}_2[x]$ of degree $1,2,$ or $4$.

Proof of the fact:
There are a few steps. First note that $x^{p^n}-x$ has no repeated factors: if it did, its derivative would share a common factor with it, but its derivative is just $-1$, which has no nontrivial factors.

Now, suppose $f(x)$ is irreducible of degree $d|n$. Then ${\mathbb F}_p[x]/(f(x))$ is a finite field of order $p^d$. So if $f(x) \ne x$, in that field ${\overline x}^{p^d-1} = 1$, by a generalization of Fermat's little theorem. This means that $f(x)$ divides $x^{p^d-1} -1$. If $d|n$, $(p^d-1) | (p^n-1)$, so $f(x)$ divides $x^{p^n-1}-1,$ hence divides $x^{p^n}-x$.

The last step is to show that no other factors divide $x^{p^n}-x$. This is best done by induction and using the fact that $\text{gcd}(p^k-1,p^n-1) = p^{\text{gcd}(k,n)}-1$, but the details are omitted. $_\square$

Taking the degrees of both sides gives a useful corollary:

Corollary:
For primes $p$ and positive integers $n$, let $\nu_p(n)$ be the number of monic irreducible polynomials of degree $n$. Then
\[
p^n = \sum_{d|n} d\nu_p(d)
\]
and by Möbius inversion,
\[
\nu_p(n) = \frac1{n} \sum_{d|n} \mu(n/d) p^d.
\]

It is not hard to see from the second formula that $\nu_p(n)$ is always strictly greater than $0$. (The $p^n$ term of the sum is strictly bigger than the sum of the absolute values of all the rest of the terms.) So there is always an irreducible polynomial in ${\mathbb F}_p$ of degree $n$, and hence a finite field of size $p^n$.

Continuing the above example, $$\nu_2(4) = \frac14(\mu(1)2^4 + \mu(2)2^2+\mu(4)2^1) = \frac14(16-4+0) = 3.$$

All that remains is to show that any two finite fields of the same size are isomorphic. So suppose $F$ is a finite field of size $p^k$, and let $F_1 = {\mathbb F}_p[x]/(f(x))$ where $f(x)$ is irreducible of degree $k$. To show that $F$ is isomorphic to $F_1$, it suffices to show that there is a root of $f(x)$ in $F$. (Then there is a nontrivial homomorphism from $F_1 \to F$ defined by sending $x$ to the root, and any nontrivial homomorphism of fields is injective (why?), and any injective map between two sets of the same size is bijective.)

But consider the polynomial $x^{p^k}-x$ in $F$; by the generalization of Fermat's little theorem, this polynomial splits into linear factors over $F$: $$x^{p^k}-x = \prod_{\alpha \in F} (x-\alpha)$$ and since $f(x)|(x^{p^k}-x)$, it must also split into linear factors over $F$, so in fact it has $k$ distinct roots in $F$. $_\square$

The classification theorem implies that "the field ${\mathbb F}_{p^k}$ with $p^k$ elements" exists and is well-defined (up to isomorphism).

The subfields of ${\mathbb F}_{p^k}$ are easy to classify, given the above discussion. The interested reader is invited to supply a proof.

${\mathbb F}_{p^d}$ is a subfield of ${\mathbb F}_{p^k}$ if and only if $d|k$. In this case, ${\mathbb F}_{p^d}$ consists of the elements $\beta \in {\mathbb F}_{p^k}$ satisfying $\beta^{p^d} = \beta$.

Start with $F_{16} = {\mathbb F}_2[x]/(x^4+x^3+x^2+x+1) = {\mathbb F}_2[\alpha]$. Then there is a copy of ${\mathbb F}_4$ inside ${\mathbb F}_{16}$. It consists of $0,1,\alpha^3+\alpha^2,\alpha^3+\alpha^2+1$. It is straightforward to verify that these are the four roots of $x^4-x$ in ${\mathbb F}_{16}$.

One application of finite fields is in the construction of linear feedback shift registers, which are built from linear recurrence relations in ${\mathbb F}_q.$ The idea is that the sequence of solutions to a linear recurrence relation over a finite field is periodic, and the period is related to the characteristic polynomial $f(x)$ of the recurrence, and to the arithmetic in the finite field ${\mathbb F}_q[x]/(f(x)) = {\mathbb F}_{q^d}$ where $d = \text{deg}(f).$ LFSRs are used in cryptography (to create pseudorandom number generators), circuit testing, digital communications, and many other areas.

In number theory, solutions to Diophantine equations are often analyzed by reducing the equations mod $p$ for prime $p.$ Analysis of solutions to equations in ${\mathbb F}_p$ is often easier than analysis over $\mathbb Q.$ For instance, the structure of the points on a curve over $\mathbb Q$ is difficult to determine in general, but there are quite precise bounds on points over ${\mathbb F}_q$ for curves with certain properties: if the number of points is $N_q,$ then $$|N_q-(q+1)|\le 2g\sqrt{q},$$ where $g$ is an easily computable number called the genus of the curve. These are the famous Hasse-Weil bounds, proved in 1974. Note that this implies that for all but finitely many $q,$ $N_q > 0,$ i.e. there is a point.

The arithmetic of finite fields is used extensively in cryptographic applications, including elliptic curve public-key cryptography and the AES (Advanced Encryption Standard) for the encryption of electronic data, which uses the arithmetic in ${\mathbb F}_{256}.$