Splitting fields and finite fields

Kronecker's construction gives a root of one irreducible polynomial. Usually we want all the roots of a polynomial at once, in the smallest field that contains them, the splitting field. Splitting fields are the stage on which Galois theory takes place, and over the prime fields \(\mathbb{Z}_p\) they produce something remarkable: a complete classification of finite fields. For every prime power \(p^n\) there is exactly one field of that size, up to isomorphism, and its structure is completely explicit. Finite fields were first studied by Galois in 1830 and are now indispensable in coding theory and cryptography.

Splitting fields

Definition. Let \(f \in F[x]\) have degree \(n \ge 1\). An extension \(E\) of \(F\) is a splitting field of \(f\) over \(F\) if \(f\) factors in \(E[x]\) as \(c(x - \alpha_1)\cdots(x - \alpha_n)\) and \(E = F(\alpha_1, \ldots, \alpha_n)\).

Theorem. Every polynomial \(f \in F[x]\) of degree \(n \ge 1\) has a splitting field \(E\), with \([E : F] \le n!\). Any two splitting fields of \(f\) over \(F\) are isomorphic by an isomorphism that fixes \(F\).

Proof of existence: induct on \(n\). Let \(p\) be an irreducible factor of \(f\). By Kronecker, \(K = F[x]/(p)\) contains a root \(\alpha_1\), with \([K : F] = \deg p \le n\). Over \(K\), \(f = (x - \alpha_1)g\) with \(\deg g = n - 1\), and by induction \(g\) has a splitting field over \(K\) of degree at most \((n - 1)!\). The tower law gives \([E : F] \le n \cdot (n - 1)! = n!\). Uniqueness is proved by extending isomorphisms one root at a time, using that \(F(\alpha) \cong F[x]/(p) \cong F(\beta)\) whenever \(\alpha\) and \(\beta\) are roots of the same irreducible \(p\).

Examples over \(\mathbb{Q}\):

• \(x^2 - 2\): splitting field \(\mathbb{Q}(\sqrt 2)\), degree 2.

• \((x^2 - 2)(x^2 - 3)\): \(\mathbb{Q}(\sqrt 2, \sqrt 3)\), degree 4.

• \(x^3 - 2\): roots \(\sqrt[3]{2}, \sqrt[3]{2}\omega, \sqrt[3]{2}\omega^2\), splitting field \(\mathbb{Q}(\sqrt[3]{2}, \omega)\), degree 6, the maximum \(3!\).

• \(x^p - 1\) for prime \(p\): \(\mathbb{Q}(\zeta_p)\), degree \(p - 1\), since all the roots are powers of one of them.

• \(x^4 - 2\): \(\mathbb{Q}(\sqrt[4]{2}, i)\), degree 8, computed in lesson 9.

Multiple roots and the derivative

A root \(\alpha\) of \(f\) is a multiple root if \((x - \alpha)^2\) divides \(f\) in a splitting field. Over any field, define the formal derivative of \(f = \sum a_kx^k\) as \(f' = \sum ka_kx^{k-1}\). No limits are involved, but the product rule still holds, by checking it on monomials. Then \(\alpha\) is a multiple root exactly when \(f(\alpha) = f'(\alpha) = 0\), because \(f = (x - \alpha)^2g\) gives \(f' = 2(x - \alpha)g + (x - \alpha)^2g'\). So \(f\) has no multiple roots if \(\gcd(f, f') = 1\), a condition that can be checked with the Euclidean algorithm without finding any roots.

Over \(\mathbb{Q}\), an irreducible polynomial never has multiple roots, since \(f'\) is nonzero of smaller degree, and \(\gcd(f, f')\) is a divisor of the irreducible \(f\) of smaller degree, hence 1. In characteristic \(p\) a derivative can vanish: \((x^p)' = px^{p-1} = 0\). This is the source of most subtleties of fields of prime characteristic, though for finite fields it causes no trouble, as we now see.

Finite fields

Let \(E\) be a finite field. Its characteristic is a prime \(p\), its prime field is \(\mathbb{Z}_p\), and if \([E : \mathbb{Z}_p] = n\), then \(|E| = p^n\).

Theorem (existence and uniqueness of finite fields). For every prime \(p\) and every \(n \ge 1\) there is a field with \(p^n\) elements, namely the splitting field of \(x^{p^n} - x\) over \(\mathbb{Z}_p\), and any two fields with \(p^n\) elements are isomorphic. It is written \(GF(p^n)\) or \(\mathbb{F}_{p^n}\), after Galois.

Proof: let \(q = p^n\) and \(f = x^q - x\). Its derivative is \(qx^{q-1} - 1 = -1\), so \(\gcd(f, f') = 1\) and \(f\) has \(q\) distinct roots in its splitting field \(E\). The set \(S\) of those roots is closed under addition and multiplication: \((a + b)^q = a^q + b^q\) by the freshman's dream applied \(n\) times, and \((ab)^q = a^qb^q\). It is also closed under negatives and inverses. So \(S\) is a field with \(q\) elements containing \(\mathbb{Z}_p\), and since \(E\) is generated by \(S\), \(E = S\). For uniqueness, any field \(K\) with \(q\) elements has a multiplicative group of order \(q - 1\), so by Lagrange's theorem \(a^{q-1} = 1\) for \(a \ne 0\), and \(a^q = a\) for every \(a\). So \(K\) consists of the \(q\) roots of \(x^q - x\) and is a splitting field of it; splitting fields are unique up to isomorphism.

In practice, \(GF(p^n)\) is built as \(\mathbb{Z}_p[x]/(m(x))\) for any irreducible \(m\) of degree \(n\) over \(\mathbb{Z}_p\). The elements are the polynomials of degree less than \(n\), added coefficientwise and multiplied modulo \(m\). Lesson 7 found the irreducible cubic \(x^3 + x + 1\) over \(\mathbb{Z}_2\), so \(GF(8) = \mathbb{Z}_2[x]/(x^3 + x + 1)\), with elements \(a + b\alpha + c\alpha^2\) and the rule \(\alpha^3 = \alpha + 1\).

The multiplicative group is cyclic

Theorem. The multiplicative group of a finite field is cyclic. More generally, any finite subgroup of the multiplicative group of a field is cyclic.

Proof: let \(G\) be a finite subgroup of \(K^\times\) of order \(m\), and let \(e\) be its exponent, the least common multiple of the orders of its elements. By a lemma on finite abelian groups from MATH-322, \(G\) has an element of order exactly \(e\). Every element of \(G\) is a root of \(x^e - 1\), which has at most \(e\) roots in the field \(K\). So \(m \le e\); and \(e \le m\) since \(e\) divides \(m\). Hence \(e = m\), and an element of order \(m\) generates \(G\).

A generator of \(GF(q)^\times\) is called a primitive element. In \(GF(8)\), the group has prime order 7, so every element other than 0 and 1 is primitive, and \(\alpha\) generates: \(\alpha^3 = \alpha + 1\), \(\alpha^4 = \alpha^2 + \alpha\), \(\alpha^5 = \alpha^2 + \alpha + 1\), \(\alpha^6 = \alpha^2 + 1\), \(\alpha^7 = 1\). The figure displays this cyclic structure: once the nonzero elements are written as powers of \(\alpha\), multiplication is addition of exponents modulo 7. For \(\mathbb{Z}_p\) the theorem says there is a primitive root modulo \(p\), a fact Gauss proved in the Disquisitiones; for instance 3 is a primitive root modulo 7.

The Frobenius automorphism and subfields

In \(GF(p^n)\), the Frobenius map \(\sigma(a) = a^p\) respects addition and multiplication, and it is injective because a field homomorphism is, so on a finite field it is an automorphism. It fixes exactly the roots of \(x^p - x\), which are the elements of \(\mathbb{Z}_p\). Its powers are \(\sigma^k(a) = a^{p^k}\), and \(\sigma^n\) is the identity since \(a^{p^n} = a\). In fact the automorphisms of \(GF(p^n)\) are exactly \(1, \sigma, \ldots, \sigma^{n-1}\), a cyclic group of order \(n\).

The subfields are equally tidy. \(GF(p^m)\) is a subfield of \(GF(p^n)\) exactly when \(m \mid n\): if \(K \subseteq GF(p^n)\) has \(p^m\) elements then \(n = m[GF(p^n) : K]\) by the tower law, and conversely if \(m \mid n\) the roots of \(x^{p^m} - x\), the fixed points of \(\sigma^m\), form such a subfield. So the subfields of \(GF(2^{12})\) correspond to the divisors 1, 2, 3, 4, 6, 12, and they are arranged just as the subgroups of the cyclic group \(\mathbb{Z}_{12}\) are. This exact match between subfields and subgroups of the automorphism group is the first full example of the Galois correspondence.

Finite fields in practice

Finite fields left pure mathematics in the twentieth century. The Advanced Encryption Standard, adopted in 2001 and used to protect most encrypted network traffic, does its byte arithmetic in \(GF(2^8) = \mathbb{Z}_2[x]/(x^8 + x^4 + x^3 + x + 1)\): each byte is an element of the field, and one step of the cipher replaces a byte by its multiplicative inverse. Reed–Solomon codes, mentioned in lesson 6, interpolate over \(GF(2^8)\) as well, which is why they are natural for data stored as bytes. Error-correcting codes for deep-space probes, two-dimensional barcodes and storage systems all rest on the same arithmetic, and the cyclic structure of \(GF(q)^\times\) is exactly what makes discrete-logarithm cryptography possible: given a primitive element \(g\), computing \(g^k\) is fast, while recovering \(k\) from \(g^k\) appears to be hard when \(q\) is large.

Building GF(8) and GF(9) by computer

The program represents elements of \(GF(p^n)\) as coefficient tuples, multiplies modulo an irreducible polynomial, and checks the theory: it lists the powers of \(\alpha\) in \(GF(8)\), finds the primitive elements of \(GF(9) = \mathbb{Z}_3[x]/(x^2 + 1)\), verifies that Frobenius respects sums and products, and finds the elements of \(GF(9)\) that Frobenius fixes.

from itertools import product

def gf(p, m):                      # m: monic modulus, constant term first
    n = len(m) - 1
    elems = [tuple(c) for c in product(range(p), repeat=n)]
    def add(a, b):
        return tuple((x + y) % p for x, y in zip(a, b))
    def mul(a, b):
        r = [0] * (2 * n - 1)
        for i, x in enumerate(a):
            for j, y in enumerate(b):
                r[i + j] = (r[i + j] + x * y) % p
        for k in range(len(r) - 1, n - 1, -1):     # reduce using x^n = -(m_0 + ... )
            c = r[k]
            if c:
                r[k] = 0
                for i in range(n):
                    r[k - n + i] = (r[k - n + i] - c * m[i]) % p
        return tuple(r[:n])
    return elems, add, mul

def name(a):
    t = [("" if c == 1 and i else str(c)) + ("" if i == 0 else ("a" if i == 1 else f"a^{i}"))
         for i, c in enumerate(a) if c]
    return " + ".join(reversed(t)) or "0"

E8, add8, mul8 = gf(2, [1, 1, 0, 1])          # x^3 + x + 1
one, alpha = (1, 0, 0), (0, 1, 0)
z, powers = one, []
for k in range(8):
    powers.append(name(z)); z = mul8(z, alpha)
print("GF(8) powers of a:", powers)

E9, add9, mul9 = gf(3, [1, 0, 1])             # x^2 + 1
def order(a, mul, one):
    k, z = 1, a
    while z != one:
        z, k = mul(z, a), k + 1
    return k
nonzero = [a for a in E9 if any(a)]
prims = [name(a) for a in nonzero if order(a, mul9, (1, 0)) == 8]
print("GF(9) element orders:", sorted(order(a, mul9, (1, 0)) for a in nonzero))
print("GF(9) primitive elements:", prims)

frob = lambda a: mul9(mul9(a, a), a)           # a -> a^3
print("Frobenius respects + and *:",
      all(frob(add9(a, b)) == add9(frob(a), frob(b)) and frob(mul9(a, b)) == mul9(frob(a), frob(b))
          for a in E9 for b in E9))
print("fixed by Frobenius:", [name(a) for a in E9 if frob(a) == a])
print("Frobenius twice is the identity:", all(frob(frob(a)) == a for a in E9))

GF(8) powers of a: ['1', 'a', 'a^2', 'a + 1', 'a^2 + a', 'a^2 + a + 1', 'a^2 + 1', '1']
GF(9) element orders: [1, 2, 4, 4, 8, 8, 8, 8]
GF(9) primitive elements: ['a + 1', '2a + 1', 'a + 2', '2a + 2']
Frobenius respects + and *: True
fixed by Frobenius: ['0', '1', '2']
Frobenius twice is the identity: True

In the output, a stands for the class of \(x\). The powers of a in \(GF(8)\) run through all seven nonzero elements before returning to 1. In \(GF(9)\) the element orders are 1, 2, 4, 4, 8, 8, 8, 8: the group is cyclic of order 8 and has \(\varphi(8) = 4\) generators. The Frobenius map \(a \mapsto a^3\) respects both operations, fixes exactly the three elements of \(\mathbb{Z}_3\), and has order 2, matching \([GF(9) : \mathbb{Z}_3] = 2\).