Table of Contents
In this blog post, we will discuss the construction of finite fields (also known as Galois fields, named so in honour of Évariste Galois). We will see how to construct fields of order \(p^k\) using irreducible polynomials over the field \(\mathbb{F}_p\), and furthermore see that all fields have an order of this form. We begin our discussion with the finite fields of order \(p\), where \(p\) is a prime.
Finite fields of prime order
THe first step in constructing finite fields is understanding how to construct finite fields of prime order. To do this, first let us consider the family of commutative rings \(\mathbb{Z}/n\mathbb{Z}\) consisting of equivalence classes of integers modulo \(n\), where \(n > 0\). These rings inherit their addition and multiplication from \(\mathbb{Z}\) in the obvious way, so that the natural quotient maps \(q_n: \mathbb{Z} \rightarrow \mathbb{Z}/n\mathbb{Z}\) are ring homomorphisms.
For which values of \(n\) do we get, not just a ring but a field?
As each \(\mathbb{Z}/n\mathbb{Z}\) is a commutative ring, all that’s left to check is that non-zero elements are invertible. Suppose \(n\) is composite, and let us write \(n = ab\) where \(a,b \in \mathbb{Z}_{\geq 1}\), \(a,b < n\). Then inside \(\mathbb{Z}/n\mathbb{Z}\) we have \(\bar{a}\cdot\bar{b} = \bar{n} = \bar{0}\) and so \(\mathbb{Z}/n\mathbb{Z}\) contains non-zero zero divisors, and therefore cannot be a field.
On the other hand, suppose \(n\) is prime, that is, \(n = p\) for some prime \(p\). Then one confirms that all non-zero integers modulo \(p\) are invertible. There are a few ways to see this, one such way is to observe that for all \(1 \leq a < p\) we have \(\text{gcd}(a,p) = 1\) and so by the Euclidean algorithm there exists \(m,n \in \mathbb{Z}\) such that \(ma + np = 1\), which in \(\mathbb{Z}/p\mathbb{Z}\) reads \(\bar{m} \cdot \bar{a} = \bar{1}\) and so \(\bar{m}\) is the multiplicative inverse of \(\bar{a}\).
Therefore \(\mathbb{Z}/n\mathbb{Z}\) is a field if and only if \(n\) is a prime. It is conventional to denote these fields by \(\mathbb{F}_p\), where \(p\) is prime. It is also somewhat common to see this field denoted by \(\text{GF}(p)\), which means “Galois Field of order \(p\)”.
Note: such fields are also prime fields, and in fact the fields of the form \(\mathbb{F}_p\) along with the rational numbers \(\mathbb{Q}\) give a complete list of all the prime fields.
Example – the field \(\mathbb{F}_5\) a.k.a. \(\text{GF}(5)\)
Let’s have a look at the finite field \(\mathbb{F}_5\), which consists of classes of integers modulo \(5\). We will write \(\mathbb{F}_5 = \{\bar{0},\bar{1},\bar{2},\bar{3},\bar{4}\}\) with addition given by \(\bar{a} + \bar{b} = \overline{a+b}\) and multiplication by \(\bar{a}\cdot\bar{b} = \overline{ab}.\) Let us write out the multiplication table, which will allow us to read off the multiplicative inverses.
| \(\times \) | \(\bar{0}\) | \(\bar{1}\) | \(\bar{2}\) | \(\bar{3}\) | \(\bar{4}\) |
| \(\bar{0}\) | \(\bar{0}\) | \(\bar{0}\) | \(\bar{0}\) | \(\bar{0}\) | \(\bar{0}\) |
| \(\bar{1}\) | \(\bar{0}\) | \(\bar{1}\) | \(\bar{2}\) | \(\bar{3}\) | \(\bar{4}\) |
| \(\bar{2}\) | \(\bar{0}\) | \(\bar{2}\) | \(\bar{4}\) | \(\bar{1}\) | \(\bar{3}\) |
| \(\bar{3}\) | \(\bar{0}\) | \(\bar{3}\) | \(\bar{1}\) | \(\bar{4}\) | \(\bar{2}\) |
| \(\bar{4}\) | \(\bar{0}\) | \(\bar{4}\) | \(\bar{3}\) | \(\bar{2}\) | \(\bar{1}\) |
Thus, we see that \(\bar{2} \cdot \bar{3} = \bar{1}\) and so \(\bar{2}\) and \(\bar{3}\) are inverse to one another. Also we have \(\bar{4} \cdot \bar{4} = \bar{1}\) and therefore \(\bar{4}\) is its own inverse, this should be no surprise since in \(\mathbb{F}_5\) we have \(\bar{4} = \bar{-1}\) and so we should expect \(\bar{4}\) to behave like \(\overline{-1}\).
Irreducible polynomials over \(\mathbb{F}_p\)
To construct fields of order \(p^k\) where \(k > 1\) we first must get to grips with irreducible polynomials over \(\mathbb{F}_p\). By a polynomial over \(\mathbb{F}_p\) we mean a polynomial with coefficients in the field \(\mathbb{F}_p\), with the set of such polynomials being denoted by \(\mathbb{F}_p[x]\). That is, we have:
$$ \mathbb{F}_p[x] = \{a_0 + a_1x + \ldots + a_nx^n : a_i \in \mathbb{F}_p, n \in \mathbb{N} \}.$$
Now, what is an irreducible polynomial? Simply put, an irreducible polynomial (over a field \(\mathbb{F}\)) is a non-constant polynomial which cannot be factored into the product of two non-constant polynomials (over the same field \(\mathbb{F}\)). Note that it is very important to specify which field we are working over. Let’s see an example of how the same polynomial can be both reducible and irreducible, depending on which field we are working over.
Example – irreducible polynomials
- Consider the polynomial \(x^2 + 1 \in \mathbb{C}[x]\). As this polynomial is degree \(2\), it is either irreducible or it can be factored into the product of two degree \(1\) polynomials. Finding roots of this polynomial yields \(x = \pm i\) . Therefore we have \(x^2 + 1 = (x + i)(x – i)\) and so this polynomial is reducible over \(\mathbb{C}.\)
- However, consider the previous polynomial but inside \(\mathbb{R}[x]\) instead. Now we do NOT have the factorisation \(x^2 + 1 = (x + i)(x – i)\) since the coefficients of the degree \(1\) polynomials are not real numbers. Therefore we cannot factor \(x^2 + 1\) over \(\mathbb{R}\) and so it is irreducible over \(\mathbb{R}\).
- Let’s see an example involving finite fields. Once again let’s consider the same polynomial but with coefficients in \(\mathbb{F}_2\). That is, let’s consider \(x^2 + \bar{1} \in \mathbb{F}_2[x]\). Can this be factored into the product of two linear factors? To find out, observe that \(x – \alpha\) is a linear factor if and only if \(\alpha\) is a root. So we will exhaustively check whether any elements of \(\mathbb{F}_2 = \{\bar{0},\bar{1}\}\) are roots of the polynomial. We have:
-> \((\bar{0}^2) + \bar{1} = \bar{1}\) and so \(\bar{0}\) is not a root of the polynomial.
-> \((\bar{1}^2) + \bar{1} = \bar{2} = \bar{0}\) and so \(\bar{1}\) is a root of the polynomial.
Differentiating \(x^2 + \bar{1}\) (inside \(\mathbb{F}_2)\) gives \(\bar{2}x = \bar{0}\) and so \(\bar{1}\) is (trivially) a root of the first derivative. Therefore \(\bar{1}\) is a double root of our original polynomial, and so we have \(x^2 + \bar{1} = (x + \bar{1})^2\).
If you are not used to working with finite fields, then this factorisation may look strange. So, let’s expand the brackets on the right-hand side to check we do in fact have equality. Doing so gives \((x + \bar{1})^2 = x^2 + \bar{2}x + \bar{1} = x^2 + \bar{1}\) as we hoped. (Crucially, we have used that \(\bar{2} = \bar{0}\) in \(\mathbb{F}_2\)!) Such a factorisation is sometimes referred to as the Freshman’s dream.
If we have a polynomial over any field of degree \(2\) or \(3\), then by degree considerations it will be reducible if and only if it has a root (since any valid factorisation must contain a degree \(1\) polynomial). This is not true for polynomials of degree \(4\) or higher, since they may factorise into a product of two degree \(\geq 2\) polynomials which are themselves irreducible (take \((x^2+1)^2 = x^4 + 2x^2 + 1 \in \mathbb{R}[x]\) for example).
Unfortunately, in general, there is no way to easily determine whether a polynomial is irreducible or not, however, there are a number of criterion which can be applied to determine if a polynomial is irreducible or not. Despite this, in almost all practical situations computers are more than capable of checking irreducibility, so we will not be put off by this issue.
Constructing finite fields of order \(p^k\)
With knowledge of irreducible polynomials under our belt, we can tackle the construction of finite fields of order \(p^k\). In order to construct such a field we must find a degree \(k\) irreducible polynomial over the field \(\mathbb{F}_p\). Suppose this polynomial is \(f(x) \in \mathbb{F}_p[x]\). Then we define \(\mathbb{F}_{p^k} = \text{GF}(p^k)\) to be the quotient \(\mathbb{F}_p[x] \big/\big(f(x)\big)\).
Let’s check that this definition makes sense, i.e. that the quotient really is a field consisting of \(p^k\) elements. We will argue just as we did to determine that \(\mathbb{F}_p\) was a field. To begin with, the quotient \(\mathbb{F}_p[x] \big/\big(f(x)\big)\) naturally inherits addition and multiplication from \(\mathbb{F}_p[x]\), thus \(\mathbb{F}_p[x] \big/\big(f(x)\big)\) is certainly a commutative ring. Therefore, we are just left to check that all non-zero elements of our quotient ring are invertible, and this is where the irreducibility of our degree \(k\) polynomial comes in…
Let \(\overline{p(x)} \in \mathbb{F}_p[x] \big/\big(f(x)\big)\) be a non-zero polynomial, pick any representative of the class \(\overline{p(x)}\) and denote it by \(p(x)\) (so \(p(x) \in \mathbb{F}_p[x]\)). Then since \(f(x)\) is irreducible we must have \(\text{gcd}\big(p(x),f(x)\big) = 1\) and so by Bézout’s identity for polynomials there exists polynomials \(a(x), b(x) \in \mathbb{F}_p[x]\) with \(a(x)p(x) + b(x)f(x) = 1\). In the quotient \(\mathbb{F}_p[x] \big/\big(f(x)\big)\) this gives us \(\overline{a(x)}\overline{p(x)} = \overline{1}\) and therefore \(\overline{a(x)}\) is the multiplicative inverse of \(\overline{p(x)}\). So the quotient is indeed a field!
Finally, to see that \(\mathbb{F}_p[x] \big/\big(f(x)\big)\) has exactly \(p^k\) elements, notice that since \(f(x)\) is of degree \(k\), all elements of the quotient have a representative polynomial \(p(x) \in \mathbb{F}_p[x]\) with \(0 \leq \text{deg}\big(p(x)\big) < k\), i.e. \(p(x)\) takes the form \(a_0 + a_1x + \dots + a_{k-1}x^{k-1}\) with each \(a_i \in \mathbb{F}_p\). As there are \(p\) elements in \(\mathbb{F}_p\) there are \(\underbrace{p \times p \times \dots \times p}_{\text{k times}} = p^k\) different polynomials, i.e. our quotient has exactly \(p^k\) elements.
The upshot of the previous three paragraphs is that we are justified in referring to \(\mathbb{F}_p[x] \big/\big(f(x)\big)\) as \(\mathbb{F}_{p^k} = \text{GF}(p^k)\), the field with \(p^k\) elements.
There is a looming question of existence… How can we be sure that there exists an irreducible polynomial in each degree? It turns out that there does, the proof (or rather one of the many proofs) makes use of the fact that the multiplicative group of a finite field is cyclic, as well as the notion of splitting fields.
Warning: For fields of order \(p\) we have that \(\mathbb{F}_p = \mathbb{Z}/p\mathbb{Z}\) as rings. This is not the case for fields of order \(p^k, k > 1\), i.e. \(\mathbb{F}_{p^k} \neq \mathbb{Z}/{p^k}\mathbb{Z}\) as rings.
Example – \(\mathbb{F}_4\), the field with \(4\) elements
Let us construct the finite field with \(4\) elements. Since \(4 = 2^2\) we wish to find an irreducible polynomial of degree \(k = 2\) over the field \(\mathbb{F}_2\). Let’s list all degree \(2\) polynomials with their factorisations:
- \(x^2 = (x)(x)\) – reducible
- \(x^2 + 1 = (x+1)^2\) – reducible
- \(x^2 + x = x(x+1)\) – reducible
- \(x^2 + x + 1\) – irreducible (just check that both \(\bar{0}\) and \(\bar{1}\) are not factors).
Therefore we will take \(f(x) = x^2 + x + 1 \in \mathbb{F}_2[x]\) and consider the quotient polynomial ring \(\mathbb{F}_2[x] \big/ (x^2 + x + 1)\). As \(f(x)\) has degree \(2\), all elements in this quotient have a representative polynomial of degree \(0\) or \(1\). Explicitly we can write
\(\mathbb{F}_2[x] \big/ (x^2 + x + 1) = \{\overline{0}, \overline{1}, \overline{x}, \overline{x+1} \}\).
Let’s write out the multiplication table in order to identify the inverses, making use of the fact that \(\overline{x^2 + x + 1} = \overline{0}\) in the quotient ring. For example, \(\overline{x} \cdot \overline{x} = \overline{x^2} = \overline{-(x+1)} = \overline{x+1} \) (also using that \(\overline{1} = \overline{-1}\) in \(\mathbb{F}_2\)).
| \(\times \) | \(\overline{0}\) | \(\overline{1}\) | \(\overline{x}\) | \(\overline{x+1}\) |
| \(\overline{0}\) | \(\overline{0}\) | \(\overline{0}\) | \(\overline{0}\) | \(\overline{0}\) |
| \(\overline{1}\) | \(\overline{0}\) | \(\overline{1}\) | \(\overline{x}\) | \(\overline{x+1}\) |
| \(\overline{x}\) | \(\overline{0}\) | \(\overline{x}\) | \(\overline{x+1}\) | \(\overline{1}\) |
| \(\overline{x+1}\) | \(\overline{0}\) | \(\overline{x+1}\) | \(\overline{1}\) | \(\overline{x}\) |
Therefore we see that \(\overline{x}\) and \(\overline{x+1}\) are inverse to one another.
Let’s finish the post by addressing a couple of common questions about the construction of finite fields.
Are finite fields of the same order isomorphic?
When explicitly constructing a finite field of order \(p^k\) we must choose an irreducible degree \(k\) polynomial over \(\mathbb{F}_p\). What happens if there is more than one choice? Are the fields we get isomorphic? The answer is yes! The idea is the following:
Suppose we have constructed two fields of order \(p^k\), let’s denote them \(F = \mathbb{F}_p[x]\big/ \big(f(x)\big)\) and \(G = \mathbb{F}_p[x]\big/ \big(g(x)\big)\). Then the elements of \(F\) are exactly the roots of the polynomial \(t^{p^k} – t \in F[t]\) (to see this, obverse that the order of the multiplicative group \(F^\times\) is \(p^k-1\) and so \(g^{p^k-1} = 1\) for all \(g \in F^\times\)). Therefore \(f(t)\) is a factor of \(t^{p^k} – t\).
Similarly, the elements of \(G\) are roots of the polynomial \(t^{p^k} – t \in G[t]\). Therefore the field \(G\) must contain roots of the polynomial \(f(t) \in G[t]\) (since it is a factor of \(t^{p^k} – t\)). Pick one of the roots of \(f(t) \in G[t]\), let’s call it \(\alpha \in G\). Then the map \(F \rightarrow G;\, x \mapsto \alpha\) is a field isomorphism.
Warning: The above debunks the following misconception (or perhaps hope).
“Since \(F\) and \(G\) can be viewed as sets of polynomials of degree \(<k\), the map given by \(F \rightarrow G;\, x \mapsto x\) must be a field isomorphism.”
The problem here is that although \(f(x) = 0 \in F\) we do not have \(f(x) = 0 \in G\) and so this map is not well defined. This is why we must map \(x \in F\) to a root \(\alpha \in G\) of \(f(t) \in G[t]\).
The ideas used here are by no means easy! So let’s see a concrete example – this will also give us another opportunity to see the construction of finite fields using irreducible polynomials.
Example – isomorphism between two fields of order \(8\)
Let’s construct two different copies of the finite field of order \(8 = 2^3\) and explicitly describe an isomorphism between them. To begin, we must find two different irreducible polynomials of degree \(3\) over the field \(\mathbb{F}_2\). Recall that a degree \(3\) polynomial is irreducible if and only if it has no linear factors if and only if it has no roots in \(\mathbb{F}_2 = \{\bar{0},\bar{1}\}\). So let’s list all degree \(3\) polynomials, and find out whether any of \(\bar{0}\) or \(\bar{1}\) is a root:
- \(x^3\) — reducible, as \(\bar{0}\) is a root.
- \(x^3 + x^2 \) — reducible, as \(\bar{0}\) and \(\bar{1}\) are roots.
- \(x^3 + x \) — reducible, as \(\bar{0}\) and \(\bar{1}\) are roots.
- \(x^3 + x^2 + x\) — reducible, as \(\bar{0}\) is a root.
- \(x^3 + 1\) — reducible, as \(\bar{1}\) is a root.
- \(x^3 + x^2 + x + 1\) — reducible, as \(\bar{1}\) is a root.
- \(x^3 + x^2 + 1 \) — irreducible.
- \(x^3 + x + 1\) — irreducible.
So, we only have two irreducible polynomials to choose from. So, set \(f(x) = x^3 + x^2 + 1 \) and \(g(x) = x^3 + x + 1 \). Then we have two fields of order \(8\) given by \(F = \mathbb{F}_2[x]\big/ \big( f(x) \big)\) and \(G = \mathbb{F}_2[y]\big/ \big( g(y) \big)\) (we will write \(G\) using polynomials with indeterminate \(‘y’\) for clarity).
We now have to find roots of the polynomial \(f(t) = t^3 + t^2 + 1 \in G[t].\) (Note that the indeterminate ‘\(t\)’ is used for clarity, as \(‘x’\) and \(‘y’\) are already in use within the descriptions of the fields \(F\) and \(G\)). Recall that each element of \(G\) has a representative of degree less than or equal to \(2\), so we may write \(G\) as:
\(G = \big\{\overline{a_0 + a_1y + a_2y^2} : a_i \in \mathbb{F}_2 \big\}\)
along with the relation \(\overline{p(y)} \equiv \overline{q(y)} \iff g(y) | \big(p(y) – q(y)\big).\) For each of the \(8\) elements \(\alpha \in G\) we compute \(f(\alpha) = \alpha^3 + \alpha^2 + 1 \in G\) and record the results in a table. We will omit the bars above the elements for ease of notation.
| \(\alpha \in G\) | \(f(\alpha) \in G\) | Is \(\alpha\) a root of \(f\)? |
| \(0\) | \(1\) | No |
| \(1\) | \(1\) | No |
| \(y\) | \(y\) | No |
| \(y^2\) | \(y\) | No |
| \(1 + y\) | \(0\) | Yes |
| \(1 + y^2\) | \(0\) | Yes |
| \(y + y^2\) | \(y^2\) | No |
| \(1 + y + y^2\) | \(0\) | Yes |
Therefore choosing any of the maps \(x \mapsto 1 + y,\,\, x \mapsto 1 + y^2\), or \(x \mapsto 1 + y + y^2\) gives a field isomorphism between \(F\) and \(G\).
Are there finite fields of order not of the form \(p^k\)?
In short, no! The key idea behind this is that any field is a vector space over any of its subfields. In particular, it is a vector space over its prime subfield. As our field is finite we know that the prime subfield must be isomorphic to \(\mathbb{F}_p\) for some prime \(p\). Therefore as a vector space, our field is isomorphic to \(\mathbb{F}_p^k\) for some \(k \geq 1\) and so has order \(p^k\).