Characterising Finite Fields

Building Fields out of Polynomial Rings#

In Polynomial Congruences we built the ring $F[x]/\langle m(x)\rangle$, whose elements are the polynomials of degree less than $\deg m$ with addition and multiplication carried out modulo $m(x)$. The whole point of this lecture is to work out exactly when that construction produces a field, because the fields it produces turn out to be every finite field there is.

Proof. The elements are the possible remainders modulo $m(x)$, and addition and multiplication are defined by doing the operation in $R[x]$ and then reducing mod $m(x)$. Reduction is well defined because the Division Theorem gives a unique remainder of degree less than $\deg m$. Associativity, commutativity and distributivity are then inherited straight from $R[x]$ (reducing at the end never changes which class you land in), the zero polynomial is the additive identity, $-a(x)$ is the additive inverse of $a(x)$, and the constant polynomial $1$ is the multiplicative identity. So every ring axiom holds. $\blacksquare$

So the ring structure is free; what is interesting is division. Recall from Rings and Fields that a field is a commutative unital ring in which every nonzero element has a multiplicative inverse. Whether $R[x]/\langle m(x)\rangle$ manages that depends entirely on $m(x)$.

Proof. ($\Leftarrow$) Suppose $m(x)$ is irreducible, and take any nonzero $a(x)$ in the quotient, so $\deg a < \deg m$ and $m(x) \nmid a(x)$. The only monic divisors of an irreducible $m(x)$ are $1$ and $m(x)$ itself, and $m(x) \nmid a(x)$, so $\gcd(a(x), m(x)) = 1$. By Bézout's identity for polynomials there are $p(x), q(x)$ with

$$a(x)p(x) + m(x)q(x) = 1,$$

and reducing mod $m(x)$ kills the middle term, leaving $a(x)p(x) = 1$ in $F[x]/\langle m(x)\rangle$. So $p(x)$ is the inverse of $a(x)$, and every nonzero element is invertible; the quotient is a field.

($\Rightarrow$) We prove the contrapositive: if $m(x)$ is reducible, the quotient is not a field. Write $m(x) = f(x)g(x)$ with $1 \leq \deg f, \deg g < \deg m$. Then in the quotient both $f(x)$ and $g(x)$ are nonzero (their degrees are too small to be multiples of $m(x)$), yet

$$f(x)\,g(x) = m(x) = 0 \text{ in } F[x]/\langle m(x)\rangle.$$

So $f(x)$ and $g(x)$ are zero divisors, and as we saw in Rings and Fields a zero divisor can never be a unit; hence $f(x)$ has no inverse and the quotient is not a field. (If instead $m(x)$ is a nonzero constant then the quotient collapses to $\{0\}$, and if $m(x) = 0$ it is all of $F[x]$, which is not a field either.) $\blacksquare$

Basically, irreducible polynomials are to $F[x]$ what primes are to $\mathbb{Z}$: just as $\mathbb{Z}_n$ is a field exactly when $n$ is prime (from Rings and Fields), $F[x]/\langle m(x)\rangle$ is a field exactly when $m(x)$ is irreducible. The reducible case fails for the same reason $\mathbb{Z}_6$ fails — a nontrivial factorisation of the modulus hands you two zero divisors.

Example. Which of $\mathbb{Z}_2[x]/\langle x^2+x+1\rangle$ and $\mathbb{Z}_2[x]/\langle x^2+1\rangle$ are fields?
By the theorem we only need to know whether each modulus is irreducible over $\mathbb{Z}_2$, and for a quadratic that just means checking for roots (a quadratic factors over a field if and only if it has a root).

• $x^2+x+1$: testing both elements of $\mathbb{Z}_2$, we get $0^2+0+1 = 1$ and $1^2+1+1 = 1$, so there is no root. Hence $x^2+x+1$ is irreducible and $\mathbb{Z}_2[x]/\langle x^2+x+1\rangle$ is a field.
• $x^2+1$: here $1^2 + 1 = 0$ in $\mathbb{Z}_2$, so $1$ is a root and $x^2+1 = (x+1)^2$ over $\mathbb{Z}_2$. Hence $x^2+1$ is reducible and $\mathbb{Z}_2[x]/\langle x^2+1\rangle$ is not a field.

Therefore the first is a field and the second is not. As a sanity check on the second, $(x+1)^2 = x^2 + 1 = 0$ in that quotient even though $x+1 \neq 0$; the element $x+1$ squares to zero, which no element of a field can do.

The Characteristic of a Finite Field#

Basically, the characteristic measures how many times you have to add the multiplicative identity to itself before you loop back round to $0$. Such an $n$ always exists in a finite field, because the list $1, 1+1, 1+1+1, \dots$ cannot go on forever without a repeat, and once two of them are equal their difference is a run of $1$s summing to $0$.

The freshly built fields make the characteristic concrete. Consider $F = \mathbb{Z}_p[x]/\langle m(x)\rangle$ where $p$ is prime and $m(x)$ is irreducible over $\mathbb{Z}_p$ of degree $k$. Then:

• $F$ has characteristic $p$, because the constant $1$ lives in the $\mathbb{Z}_p$ part and adding it to itself $p$ times gives $0$ (and no fewer, since $p$ is the characteristic of $\mathbb{Z}_p$).
• $F$ has $p^k$ elements, because each element is a polynomial $a_0 + a_1x + \cdots + a_{k-1}x^{k-1}$ of degree less than $k$, and there are $p$ independent choices for each of the $k$ coefficients. We say $F$ has order $p^k$. Be careful: "order" here means the number of elements of the whole field, which is a completely different thing from the order of a single element; both words are unavoidable, so always check from context which one is meant.

That the characteristic came out prime was not a fluke.

Proof. Let $F$ be a finite field with characteristic $n$, and write $n\cdot 1$ for the sum of $n$ copies of $1$. We know $n \geq 2$, since $1 \neq 0$ in any field. Suppose for contradiction that $n$ is composite, say $n = ab$ with $1 < a, b < n$. Using distributivity,

$$(a\cdot 1)(b\cdot 1) = (ab)\cdot 1 = n\cdot 1 = 0 \text{ in } F.$$

Since $F$ is a field it has no zero divisors, so either $a\cdot 1 = 0$ or $b\cdot 1 = 0$. But $a$ and $b$ are both smaller than $n$, and $n$ was the smallest positive integer with $n\cdot 1 = 0$ — a contradiction. Hence $n$ has no such factorisation; that is, $n$ is prime. $\blacksquare$

Notice this is the exact same argument that made $\mathbb{Z}_n$ a field only for prime $n$: a composite modulus splits into factors that multiply to zero. The next theorem goes much further, and its proof is genuinely hard, so it is quoted rather than proved.

The proof is beyond this course, but the result is enormously important: it says that the only possible sizes for a finite field are prime powers. So there is no field with $6$, $10$ or $12$ elements, no matter how cleverly you try to build one — and in particular $\mathbb{Z}_6$ was never going to be a field. A finite field of size $n$ can exist only when $n$ is a prime power; commit that to memory, because half the questions in this topic are secretly just asking whether $n$ is a prime power.

Every Prime Power Really Occurs#

The size theorem rules sizes out. The next result says nothing more is ruled out: every prime power genuinely is achieved, and in essentially only one way.

To even state uniqueness we need to say when two fields count as "the same".

For example $\mathbb{Z}[x]/\langle x^2+1\rangle \cong \mathbb{Z}[i]$, the Gaussian integers, via the matching $x \mapsto i$: the relation $x^2 = -1$ in the quotient becomes exactly $i^2 = -1$, so all the arithmetic lines up. Basically, isomorphic rings are the same object wearing different clothes; only the names of the elements differ.

Together these theorems completely characterise the finite fields, which is what the lecture's title is about. They also hand us a recipe: to build the field of order $p^k$, pick any irreducible polynomial of degree $k$ over $\mathbb{Z}_p$ and form the quotient — which is a field by the irreducibility criterion. Different choices of $m(x)$ give fields that look superficially different but are all isomorphic, so it genuinely does not matter which irreducible you grab.

Example. Construct a finite field of order $n$ for each $n$ from $1$ to $10$, or explain why none exists.
A field of order $n$ exists exactly when $n$ is a prime power $p^k$; then $\mathbb{F}_n = \mathbb{Z}_p$ when $k = 1$, and $\mathbb{F}_n = \mathbb{Z}_p[x]/\langle m(x)\rangle$ for an irreducible degree-$k$ modulus when $k > 1$.

The three composite prime powers need a short justification of the modulus:

• $n = 4 = 2^2$: we need an irreducible quadratic over $\mathbb{Z}_2$, and $x^2+x+1$ has no root in $\mathbb{Z}_2$ (checked above), so it works. Note that $\mathbb{F}_4$ is not $\mathbb{Z}_4$: the ring $\mathbb{Z}_4$ is not even a field, since $2$ is a zero divisor there. This is the single most common mistake in the topic — for a prime power $p^k$ with $k > 1$, the field of that order is a polynomial quotient, never $\mathbb{Z}_{p^k}$.
• $n = 8 = 2^3$: we need an irreducible cubic over $\mathbb{Z}_2$. Now $x^3+x+1$ has no root ($0^3+0+1 = 1$ and $1^3+1+1 = 1$), and a cubic with no root is irreducible (any factorisation would force a linear factor, i.e. a root), so $x^3+x+1$ works.
• $n = 9 = 3^2$: we need an irreducible quadratic over $\mathbb{Z}_3$, and $x^2+1$ has no root in $\mathbb{Z}_3$ (the values are $1, 2, 2$ at $x = 0, 1, 2$), so it works.

Order and Primitive Elements in Finite Fields#

For the rest of the lecture write $\mathbb{F}_q = \mathbb{F}_{p^k}$, so $q = p^k$. Recall from Rings and Fields that in any field every nonzero element is a unit, so the unit group is simply

$$\mathbb{F}_q^* = \mathbb{F}_q - \{0\},$$

a set of $q-1$ elements. Everything we proved about orders and primitive elements in $\mathbb{Z}_p^*$ in Order and Primitive Elements now transplants wholesale, with $q-1$ playing the role that $\phi(p) = p-1$ played before.

This is the same definition as $\operatorname{ord}_n(a) = \operatorname{ord}_{\mathbb{Z}_n}(a)$ from before, just with the field $\mathbb{F}_q$ in place of $\mathbb{Z}_n$. The proofs of the next few results are word-for-word the proofs from Order and Primitive Elements and Fermats Little Theorem and Eulers Theorem, so we state them and move on.

The two forms are equivalent: multiplying $\alpha^{q-1} = 1$ by $\alpha$ gives $\alpha^q = \alpha$ for units, and $\alpha^q = \alpha$ obviously also holds for $\alpha = 0$. This is exactly Fermat's Little Theorem $a^{p-1} = 1$ in $\mathbb{Z}_p$, promoted from the prime field $\mathbb{Z}_p$ to every finite field.

Basically, this is why computing an order is fast: it must be one of the divisors of $q-1$, so you only ever test those. It follows from the generalised Fermat theorem and the fact that the exponents giving $1$ are exactly the multiples of the order, just as in $\mathbb{Z}_n$.

So a primitive element's powers sweep out every single nonzero element of the field before returning to $1$. Where finite fields improve on $\mathbb{Z}_n$ is that a primitive element is guaranteed to exist.

The proof is again difficult and omitted. This is a genuine upgrade on the situation in $\mathbb{Z}_n^*$: back in Order and Primitive Elements only some moduli (namely $1, 2, 4, p^k, 2p^k$ for odd $p$) had primitive elements, and $\mathbb{Z}_8^*$ notoriously did not. Here there is no such restriction, and in particular $p$ is allowed to be $2$ — the awkward "odd prime" condition from $\mathbb{Z}_n$ has vanished, because $\mathbb{F}_{2^k}$ is a genuine field rather than a ring of residues.

There is still no efficient way to find a primitive element; the method is the same trial-and-error as before. To find a primitive element of $\mathbb{F}_q = \mathbb{Z}_p[x]/\langle m(x)\rangle$:

• Start with $\alpha = x$, the root of $m(x)$ inside the field (it satisfies $m(\alpha) = 0$ by construction).
• For each prime divisor $p_i$ of $q-1$, compute $\alpha^{(q-1)/p_i}$ in $\mathbb{F}_q$.
• If $\alpha^{(q-1)/p_i} \neq 1$ for all such $p_i$, then $\alpha$ is primitive.
• Otherwise try $\beta = \alpha + 1$, then $\alpha + 2$, and so on, until one passes.

This is the identical test to the $\mathbb{Z}_n$ case: the order must divide $q-1$, and it equals $q-1$ precisely when it is missing none of the prime factors, which is exactly what the exponents $(q-1)/p_i$ detect.

Once you have one primitive element you have them all, and there are $\phi(q-1)$ of them — the same counting result as in Order and Primitive Elements, with $q-1$ replacing $\phi(n)$.

Finding Primitive Elements#

Both examples below hunt for primitive elements by the trial-and-error test above, and both illustrate a different outcome.

Example. Find the primitive elements of $F = \mathbb{Z}_2[x]/\langle x^2+x+1\rangle$.
This is $\mathbb{F}_4$, so $q = 4$ and $q-1 = 3$. The nonzero elements are $\{1, x, x+1\}$, and the only prime divisor of $3$ is $3$ itself, so the test exponent is $\tfrac{q-1}{3} = 1$; an element is primitive exactly when it is not $1$. Start with the root $\alpha = x$, using $x^2 = x+1$ (from $x^2+x+1 = 0$ and $-1 = 1$ in $\mathbb{Z}_2$):

$$\begin{align*} x^1 &= x \neq 1, \\ x^2 &= x+1, \\ x^3 &= x\cdot x^2 = x(x+1) = x^2 + x = (x+1) + x = 1 \text{ in } F, \end{align*}$$

so $\operatorname{ord}_F(x) = 3 = q-1$ and $x$ is primitive. For $\beta = x+1$,

$$\begin{align*} (x+1)^2 &= x^2 + 1 = (x+1) + 1 = x, \\ (x+1)^3 &= (x+1)\cdot x = x^2 + x = 1 \text{ in } F, \end{align*}$$

so $x+1$ has order $3$ too and is also primitive. Therefore the primitive elements of $\mathbb{F}_4$ are $x$ and $x+1$ — and indeed $\phi(q-1) = \phi(3) = 2$ of them, as the corollary predicts. Here every non-identity element turned out to be primitive, which happens exactly because $q - 1 = 3$ is prime.

Example. Find the primitive elements of $F = \mathbb{Z}_3[x]/\langle x^2+1\rangle$.
This is $\mathbb{F}_9$, so $q = 9$ and $q-1 = 8 = 2^3$. The only prime divisor of $8$ is $2$, so the single test is whether $\alpha^{(q-1)/2} = \alpha^4 \neq 1$. Work with $x^2 = -1 = 2$ throughout. Start with the root $\alpha = x$:

$$\begin{align*} x^2 &= 2, \\ x^4 &= (x^2)^2 = 2^2 = 4 = 1 \text{ in } F, \end{align*}$$

so $x^4 = 1$ and $x$ fails the test — in fact $\operatorname{ord}_F(x) = 4 \neq 8$, so the root itself is not primitive. Move to $\beta = x+1$:

$$\begin{align*} (x+1)^2 &= x^2 + 2x + 1 = 2 + 2x + 1 = 2x, \\ (x+1)^4 &= \big((x+1)^2\big)^2 = (2x)^2 = 4x^2 = 4\cdot 2 = 8 = 2 \neq 1 \text{ in } F, \end{align*}$$

so $\beta = x+1$ passes the only test and is primitive, with $\operatorname{ord}_F(x+1) = 8$. Therefore $x+1$ is a primitive element of $\mathbb{F}_9$, and by the corollary there are $\phi(8) = 4$ primitive elements in total. Notice that the root $x$ was not primitive here; the method's first candidate is not guaranteed to work, which is exactly why the "otherwise try $\alpha+1$" step exists.

Arithmetic Using a Log Table#

Once you have a primitive element $\beta$, every nonzero element of $\mathbb{F}_q$ is a power of $\beta$, so you can tabulate those powers once and then do all your multiplying, dividing and exponentiating by adding and subtracting exponents modulo $q-1$. This is the finite-field version of the log-table trick from Order and Primitive Elements. Building the table for $\beta = x+1$ in $\mathbb{F}_9 = \mathbb{Z}_3[x]/\langle x^2+1\rangle$ (each step multiplies the previous entry by $x+1$ and reduces using $x^2 = 2$):

The table has period $8 = q-1$, as it must, and its eight distinct entries before repeating are precisely the eight nonzero elements of $\mathbb{F}_9$ — confirming that $x+1$ generates $\mathbb{F}_9^*$.

Example. Evaluate the following in $F = \mathbb{Z}_3[x]/\langle x^2+1\rangle$, using the table above.
(i) $(2x+1)^5$. From the power table $2x+1 = \beta^3$, so reduce the exponent modulo $q-1 = 8$:

$$(2x+1)^5 = (\beta^3)^5 = \beta^{15} = \beta^{15 \bmod 8} = \beta^7 = x+2.$$

(ii) $\dfrac{(x+2)^2}{x^3}$. From the table $x+2 = \beta^7$ and $x = \beta^6$, so

$$\frac{(x+2)^2}{x^3} = \frac{(\beta^7)^2}{(\beta^6)^3} = \frac{\beta^{14}}{\beta^{18}} = \beta^{14-18} = \beta^{-4} = \beta^{4} = 2,$$

where $\beta^{-4} = \beta^{-4+8} = \beta^4$. Division is where the log table really earns its keep: instead of hunting for a multiplicative inverse, you just subtract exponents.
(iii) $\beta^5 + \beta^3$. Addition is the one operation the table does not simplify, so we convert back to polynomials, add, and (if wanted) convert forward again:

$$\beta^5 + \beta^3 = (2x+2) + (2x+1) = 4x + 3 = x = \beta^6 \text{ in } F,$$

using $4x = x$ and $3 = 0$ in $\mathbb{Z}_3$.
(iv) $\beta^3 + \beta^2 + 1$. Likewise

$$\beta^3 + \beta^2 + 1 = (2x+1) + 2x + 1 = 4x + 2 = x+2 = \beta^7 \text{ in } F.$$

Therefore the four answers are $x+2$, $2$, $x$ and $x+2$. The moral is that powers, products and quotients are trivial in exponent form, but sums force you back to polynomial form; a log table turns multiplication into addition but can do nothing to help genuine addition.

Finite Fields as Vector Spaces#

There is one more way to look at $\mathbb{F}_9 = \mathbb{Z}_3[x]/\langle x^2+1\rangle$. Writing $\beta = x+1$ again, every element can be written uniquely as a combination $a + b\beta$ with $a, b \in \mathbb{Z}_3$:

For instance $2 + 1\beta = 2 + (x+1) = x$ and $1 + 2\beta = 1 + 2(x+1) = 2x + 3 = 2x$, both in $\mathbb{Z}_3$. So $\mathbb{F}_9$ is a vector space over $\mathbb{Z}_3$ with basis $\{1, \beta\}$ — nine elements, being all $3^2$ combinations of two basis vectors with scalars from $\mathbb{Z}_3$, exactly matching the count $q = p^k$. This is the same notion of basis and dimension from Vector Spaces, now with the scalars drawn from a finite field.

Proof (sketch). There are $k$ vectors $1, \alpha, \dots, \alpha^{k-1}$, and the number of linear combinations of them with coefficients in $\mathbb{Z}_p$ is $p^k = q$, exactly the number of elements of $\mathbb{F}_q$. So it is enough to know the combinations are all distinct, i.e. that the vectors are linearly independent — and they are, because a nontrivial dependence $c_0 + c_1\alpha + \cdots + c_{k-1}\alpha^{k-1} = 0$ would make $\alpha$ a root of a nonzero polynomial of degree less than $k$ over $\mathbb{Z}_p$, contradicting the fact that $\alpha$'s minimal polynomial has degree $k$. With $q$ distinct combinations landing on $q$ elements, every element is hit exactly once. $\blacksquare$

(Both the handout's example and this theorem say "vector space over $\mathbb{Z}_p[x]$", but that is a slip: the scalars must come from a field, and $\mathbb{Z}_p$ is a field whereas $\mathbb{Z}_p[x]$ is only a ring. The base field is $\mathbb{Z}_p$.) Basically, this is the cleanest way to see why $|\mathbb{F}_q| = p^k$: a $k$-dimensional vector space over a field of $p$ elements has exactly $p^k$ vectors, no more and no less. It also ties the whole topic back to first-year linear algebra — a finite field is, underneath, just a finite-dimensional vector space that happens to also support multiplication.