Unit 10: Finite fields

Every finite field, ever

A finite field is a complete number system, with all four operations, that has only finitely many elements. Remarkably, they can be classified completely: there's exactly one of each prime-power size, and none of any other size. They're also among the most useful objects in mathematics, running inside QR codes, data storage and internet encryption.

1234567891011
In this unit
  1. How big can a finite field be?
  2. Building them
  3. Every finite field has a generator
  4. One field of each size
  5. Fields inside fields
  6. Error-correcting codes
  7. Cryptography
  8. Practice set
  9. Summary and glossary

How big can a finite field be?

We know some finite fields already: \(\mathbb{Z}/p\) for each prime \(p\), written \(\mathbb{F}_p\), and the field \(\mathbb{F}_4\) with four elements from Unit 7. Is there a field with 6 elements? With 10?

Theorem

A finite field has \(p^n\) elements for some prime \(p\) and some \(n \ge 1\).

Show proof

Let \(F\) be a finite field. Its characteristic can't be 0 (adding 1 repeatedly can't produce infinitely many different elements), so by Unit 3 it is a prime \(p\), and \(F\) contains a copy of \(\mathbb{F}_p\).

Now think of \(F\) as a vector space over \(\mathbb{F}_p\): you can add elements of \(F\), and multiply them by "scalars" from \(\mathbb{F}_p\). Being finite, it has a finite basis \(e_1, \dots, e_n\), and every element is uniquely \(c_1e_1 + \dots + c_ne_n\) with each \(c_i \in \mathbb{F}_p\). That's \(p\) choices for each of \(n\) coefficients: \(p^n\) elements. ∎

So there's no field with 6, 10, 12 or 15 elements. The possible sizes are \(2, 3, 4, 5, 7, 8, 9, 11, 13, 16, 17, 19, 23, 25, 27, \dots\). The next question: does every prime power actually occur?

Building them

Unit 7 gave the recipe. If \(f\) is an irreducible polynomial of degree \(n\) over \(\mathbb{F}_p\), then \(\mathbb{F}_p[x]/(f)\) is a field. Its elements are the remainders: polynomials \(c_0 + c_1x + \dots + c_{n-1}x^{n-1}\) of degree less than \(n\). That's \(p^n\) elements.

FieldConstructionRule
\(\mathbb{F}_4\)\(\mathbb{F}_2[x]/(x^2 + x + 1)\)\(\alpha^2 = \alpha + 1\)
\(\mathbb{F}_8\)\(\mathbb{F}_2[x]/(x^3 + x + 1)\)\(\alpha^3 = \alpha + 1\)
\(\mathbb{F}_9\)\(\mathbb{F}_3[x]/(x^2 + 1)\)\(i^2 = -1\); the same as \(\mathbb{Z}[i]/(3)\) from Unit 9
\(\mathbb{F}_{16}\)\(\mathbb{F}_2[x]/(x^4 + x + 1)\)\(\alpha^4 = \alpha + 1\)
\(\mathbb{F}_{256}\)\(\mathbb{F}_2[x]/(x^8 + x^4 + x^3 + x + 1)\)the field inside AES encryption

Over \(\mathbb{F}_2\), an element of \(\mathbb{F}_{2^n}\) is just a string of \(n\) bits (its coefficients). Addition is bitwise XOR. For \(\mathbb{F}_{256}\), each element is exactly one byte, which is why computers love it.

For this to build a field of every size \(p^n\), we need an irreducible polynomial of every degree \(n\) over every \(\mathbb{F}_p\). They always exist, as we'll see shortly by counting them.

Every finite field has a generator

In \(\mathbb{F}_8\), let \(\alpha\) be the class of \(x\), so \(\alpha^3 = \alpha + 1\). Keep multiplying by \(\alpha\) and watch what happens:

The seven non-zero elements of the field with 8 elements, as powers of alphaSeven purple circles arranged in a ring, labelled alpha to the 0 through alpha to the 6, with arrows from each to the next meaning multiply by alpha; the arrow from alpha to the 6 returns to alpha to the 0 = 1. Inside each, the element written as a polynomial and as three bits: 1 is 001, alpha is 010, alpha squared is 100, alpha cubed = alpha + 1 is 011, alpha to the 4 = alpha squared + alpha is 110, alpha to the 5 = alpha squared + alpha + 1 is 111, alpha to the 6 = alpha squared + 1 is 101.α⁰1001α¹α010α²α²100α³α + 1011α⁴α² + α110α⁵α² + α + 1111α⁶α² + 1101× α
The powers of \(\alpha\) in \(\mathbb{F}_8\). Each step multiplies by \(\alpha\) and uses \(\alpha^3 = \alpha + 1\) to simplify. For instance \(\alpha^4 = \alpha \cdot \alpha^3 = \alpha^2 + \alpha\). After seven steps you're back at 1, having visited all seven non-zero elements, shown as polynomials and as bit strings.

The powers of \(\alpha\) run through every non-zero element. So \(\alpha\) is a generator, like the primitive roots 3 and 5 of \(\mathbb{F}_7\) in Unit 2. Generators make multiplication easy, the way logarithms do: to multiply, add exponents mod 7.

Example: multiplying with logarithms in \(\mathbb{F}_8\)

\((\alpha^2 + 1)(\alpha + 1) = \alpha^6 \cdot \alpha^3 = \alpha^9 = \alpha^2\). Checking directly: \(\alpha^3 + \alpha^2 + \alpha + 1 = (\alpha + 1) + \alpha^2 + \alpha + 1 = \alpha^2\), since \(2\alpha = 0\) and \(2 = 0\). ✓

Theorem

In every finite field \(\mathbb{F}_q\), the non-zero elements are the powers of a single generator \(g\): \(\mathbb{F}_q^\times = \{1, g, g^2, \dots, g^{q-2}\}\).

Show proof sketch

Every non-zero element has an order: the smallest \(d\) with \(a^d = 1\). By the Fermat argument of Unit 2, \(a^{q-1} = 1\), so \(d\) divides \(q - 1\). Fix a divisor \(d\). If some element \(a\) has order \(d\), then \(1, a, \dots, a^{d-1}\) are \(d\) different roots of \(x^d - 1\), and by Unit 4 there are no others. Exactly \(\varphi(d)\) of these powers have order exactly \(d\). So for each \(d\), there are either 0 or \(\varphi(d)\) elements of order \(d\). But the counts must add up to \(q - 1\), and \(\sum_{d \mid q-1} \varphi(d) = q - 1\). So none of the counts can be 0. In particular, there are \(\varphi(q - 1) \ge 1\) elements of order \(q - 1\): generators. ∎

One field of each size

In a field with \(q\) elements, every non-zero \(a\) satisfies \(a^{q-1} = 1\), so every element (including 0) satisfies \(a^q = a\). That's \(q\) distinct roots of \(x^q - x\), a polynomial of degree \(q\). So

\( x^q - x = \prod_{a \in \mathbb{F}_q} (x - a) \) A field with \(q\) elements is exactly the set of roots of \(x^q - x\). This is the generalisation of \(x^p - x = x(x-1)\cdots(x-(p-1))\) from Unit 4.

This one fact settles everything:

Theorem: classification of finite fields (Galois, Moore)

For every prime power \(q = p^n\) there is a field with \(q\) elements, and any two fields with \(q\) elements are isomorphic. It is written \(\mathbb{F}_q\).

Existence: by Kronecker's theorem (Unit 7), build a field in which \(x^q - x\) splits completely; its \(q\) roots turn out to be closed under \(+\) and \(\times\) (using the freshman's dream for \(+\)), so they form a field with \(q\) elements. Uniqueness: any field with \(q\) elements is "the roots of \(x^q - x\)", and the splitting field of a polynomial is unique up to isomorphism.

Grouping the factors of \(x^{p^n} - x\) by their irreducible factors gives a beautiful identity. Every element of \(\mathbb{F}_{p^n}\) is a root of exactly one monic irreducible polynomial over \(\mathbb{F}_p\), whose degree divides \(n\). So

\[ x^{p^n} - x = \text{the product of all monic irreducibles over } \mathbb{F}_p \text{ of degree dividing } n. \]

Example: \(x^8 - x\) over \(\mathbb{F}_2\)

The degrees dividing 3 are 1 and 3. The sieve in Unit 4 found the monic irreducibles: \(x\), \(x + 1\), \(x^3 + x + 1\), \(x^3 + x^2 + 1\). And indeed

\[ x^8 - x = x\,(x + 1)\,(x^3 + x + 1)\,(x^3 + x^2 + 1). \]

Comparing degrees: \(8 = 1 + 1 + 3 + 3\). In general, if \(N_d\) is the number of monic irreducibles of degree \(d\), then \(p^n = \sum_{d \mid n} d \cdot N_d\). For \(p = 2\), \(n = 4\): \(16 = 1 \cdot 2 + 2 \cdot 1 + 4 N_4\), so \(N_4 = 3\), exactly the three purple tiles of degree 4 in Unit 4's sieve. The formula also shows \(N_n > 0\) for every \(n\), so irreducibles of every degree exist.

Going deeper: the symmetries of a finite field

The Frobenius map \(\phi(a) = a^p\) (Unit 3) is a homomorphism from \(\mathbb{F}_{p^n}\) to itself, one-to-one, hence a bijection: an automorphism. In \(\mathbb{F}_4\) it fixes 0 and 1 and swaps \(\alpha \leftrightarrow \alpha^2 = \alpha + 1\), the two roots of \(x^2 + x + 1\), just as complex conjugation swaps \(i\) and \(-i\).

Applying Frobenius \(n\) times gives \(a^{p^n} = a\): the identity. In fact the automorphisms of \(\mathbb{F}_{p^n}\) are exactly \(\phi, \phi^2, \dots, \phi^n = \text{id}\), a cyclic group of order \(n\). This is the simplest case of Galois theory, where a field's symmetry group controls its structure.

Fields inside fields

\(\mathbb{F}_{p^m}\) sits inside \(\mathbb{F}_{p^n}\) exactly when \(m\) divides \(n\). (If it does, the bigger field is a vector space over the smaller, so \(p^n = (p^m)^k\).) So the subfield diagram of a finite field is the divisor diagram of its exponent:

The subfields of the field with 4096 elementsA diagram of the subfields of the field with 2 to the 12 elements, arranged by inclusion. At the top the field with 4096 elements. Below it the fields with 2 to the 4 = 16 and 2 to the 6 = 64 elements. Below those the fields with 4 and 8 elements; the field with 4 elements lies inside both the 16 and 64 element fields, the field with 8 elements inside the 64 element field. At the bottom the field with 2 elements. The pattern matches the divisors of 12.𝔽 with 2¹² = 4,096𝔽 with 2⁴ = 16𝔽 with 2⁶ = 64𝔽 with 2² = 4𝔽 with 2³ = 8𝔽 with 2¹ = 2
The subfields of \(\mathbb{F}_{4096}\). The shape is the divisor diagram of 12, the same shape as the ideal lattice of \(\mathbb{Z}/12\) in Unit 6, turned upside down. \(\mathbb{F}_8\) is not inside \(\mathbb{F}_{16}\), because 3 doesn't divide 4.

Error-correcting codes

A scratched CD still plays, a smudged QR code still scans, and pictures from the Voyager probes crossed billions of kilometres of noisy space. All of these rely on Reed–Solomon codes, which are built from one fact in Unit 4: a non-zero polynomial of degree less than \(k\) has fewer than \(k\) roots. So two different such polynomials agree in fewer than \(k\) places, and any \(k\) values of a polynomial determine it.

Here's a tiny example over \(\mathbb{F}_7\). Encode the message \((3, 5)\) as the polynomial \(f(x) = 3 + 5x\), and transmit its values at \(x = 0, 1, \dots, 6\): seven numbers instead of two.

The line y = 3 + 5x over the field with 7 elementsA 7 by 7 grid of points with coordinates 0 to 6. Seven purple dots mark the points (x, 3 + 5x mod 7): (0,3), (1,1), (2,6), (3,4), (4,2), (5,0), (6,5). Over a finite field the line looks scattered. The dots at x = 2 and x = 5 are crossed out in pink to show lost data; any two of the remaining five dots are enough to recover the line.00112233445566xy = 3 + 5xover 𝔽₇
A "line" over \(\mathbb{F}_7\). The transmitted values are \(3, 1, 6, 4, 2, 0, 5\). Over a finite field a line looks scattered, but it's still a line: two points determine it. Even with the two crossed-out values lost, any two of the survivors recover \((3, 5)\).

Real Reed–Solomon codes use \(\mathbb{F}_{256}\), so each symbol is a byte, and polynomials of higher degree. With \(n\) values sent for a degree-\(<k\) polynomial, up to \(n - k\) lost symbols can be recovered, and with a cleverer decoder up to \((n - k)/2\) wrong symbols can be corrected. A QR code uses exactly this, which is why it scans even with a logo printed over its middle.

Cryptography

Finite fields are also the arithmetic of secrecy. Two examples:

AES, the cipher protecting most encrypted traffic and disks, scrambles data byte by byte using arithmetic in \(\mathbb{F}_{256}\), including taking inverses: an operation that is easy to compute but hard to "undo by linear algebra".

Diffie–Hellman key exchange (1976) lets two people who've never met agree on a secret over a public channel. It uses a generator \(g\) of \(\mathbb{F}_p^\times\). Computing \(g^a\) is fast (repeated squaring), but recovering \(a\) from \(g^a\), the discrete logarithm problem, is believed to be infeasible for large \(p\).

Example: a toy key exchange in \(\mathbb{F}_{23}\) with \(g = 5\)

  1. Alice picks a secret \(a = 6\) and publishes \(5^6 \equiv 8\).
  2. Bob picks a secret \(b = 15\) and publishes \(5^{15} \equiv 19\).
  3. Alice computes \(19^6 \equiv 2\). Bob computes \(8^{15} \equiv 2\). Both get \(5^{ab} = 5^{90} \equiv 2\).

An eavesdropper sees 23, 5, 8 and 19, but to find the shared secret 2 they'd need to solve \(5^a \equiv 8\). With a 600-digit prime, nobody knows how.

Modern systems often replace \(\mathbb{F}_p^\times\) by the points on an elliptic curve over a finite field, which give the same security with much shorter keys. Elliptic curves over finite fields are also central to the proof of Fermat's Last Theorem.

Practice set

Mixed questions covering the whole unit. Try each one before opening the answer.

1. Is there a field with 12 elements? With 27? With 1,024?

Show answer

12: no, not a prime power. 27: yes, \(3^3\). 1,024: yes, \(2^{10}\).

2. In \(\mathbb{F}_8\) (with \(\alpha^3 = \alpha + 1\)), compute \((\alpha^2 + \alpha)(\alpha^2 + \alpha + 1)\) using the wheel.

Show answer

\(\alpha^2 + \alpha = \alpha^4\) and \(\alpha^2 + \alpha + 1 = \alpha^5\). The product is \(\alpha^9 = \alpha^2\).

3. In \(\mathbb{F}_9 = \mathbb{F}_3[i]\) (with \(i^2 = -1\)), is \(i\) a generator? Is \(1 + i\)?

Show answer

\(i\) has order 4 (\(i^4 = 1\)), but a generator needs order 8, so no. For \(1 + i\): \((1 + i)^2 = 2i\), \((1 + i)^4 = (2i)^2 = -4 = -1\), so \((1 + i)^8 = 1\) and not before: yes, a generator.

4. List the subfields of \(\mathbb{F}_{64}\).

Show answer

\(64 = 2^6\), and the divisors of 6 are 1, 2, 3, 6. So \(\mathbb{F}_2\), \(\mathbb{F}_4\), \(\mathbb{F}_8\), \(\mathbb{F}_{64}\).

5. A Reed–Solomon receiver over \(\mathbb{F}_7\) gets only \(f(1) = 1\) and \(f(3) = 4\), where \(f(x) = a + bx\). Recover the message \((a, b)\).

Show answer

\(a + b = 1\) and \(a + 3b = 4\). Subtract: \(2b = 3\), so \(b = 3 \cdot 2^{-1} = 3 \cdot 4 = 12 \equiv 5\). Then \(a = 1 - 5 = -4 \equiv 3\). The message is \((3, 5)\).

6. How many monic irreducible quadratics are there over \(\mathbb{F}_3\)? Find them.

Show answer

\(3^2 = 1 \cdot N_1 + 2 N_2 = 3 + 2N_2\), so \(N_2 = 3\). They're the monic quadratics with no root in \(\mathbb{F}_3\): \(x^2 + 1\), \(x^2 + x + 2\), \(x^2 + 2x + 2\).

Summary and glossary

  1. A finite field has \(p^n\) elements: it's a vector space over \(\mathbb{F}_p\).
  2. \(\mathbb{F}_{p^n} = \mathbb{F}_p[x]/(f)\) for any irreducible \(f\) of degree \(n\), and such \(f\) always exist.
  3. The non-zero elements are all powers of one generator.
  4. \(\mathbb{F}_q\) is the set of roots of \(x^q - x\); there's exactly one field of each prime-power size.
  5. \(\mathbb{F}_{p^m} \subseteq \mathbb{F}_{p^n}\) iff \(m \mid n\).
  6. Applications: Reed–Solomon codes (polynomials are determined by few values) and cryptography (discrete logarithms are hard).
\(\mathbb{F}_q\)
The field with \(q = p^n\) elements.
Generator
An element whose powers give every non-zero element.
Order of an element
The smallest \(d\) with \(a^d = 1\).
Splitting field
The smallest field in which a polynomial factors completely.
Frobenius automorphism
\(a \mapsto a^p\).
Reed–Solomon code
Encode data as a polynomial, send many of its values.
Discrete logarithm
Finding \(a\) from \(g^a\).
Powered by Webloyt | Report abuse