Building Fields from Irreducible Polynomials

F[x]/(p(x)) is a field exactly when p(x) is irreducible, proved through Bezout's identity. Extension fields and Kronecker's theorem, that the class of x is a root of p(x), so every polynomial has a root in some larger field. A square root of 2 adjoined to Z_3, two constructions of the field with nine elements and an explicit isomorphism between them, its multiplication table and a generator of its nonzero elements, x^9 - x as the product of all its linear factors, the prime-power sizes of finite fields, and the 256-element field inside AES.

The squares of the elements of $\mathbb{Z}_3$ are $0^2 = 0$, $1^2 = 1$ and $2^2 = 4 = 1$, so the equation $x^2 = 2$ has no solution in $\mathbb{Z}_3$: there is no square root of 2. In $\mathbb{Z}_7$ there is one, since $3^2 = 9 = 2$, but $\mathbb{Z}_3$ is what it is. Can it be enlarged to a field in which 2 does have a square root, in the way that $\mathbb{R}$ is enlarged to $\mathbb{C}$ to give $-1$ a square root?

The previous article supplies a candidate. In $\mathbb{Z}_3[x]$ the polynomial $x^2 - 2$ is the same as $x^2 + 1$, since $-2 = 1$, and in the ring

$$K = \mathbb{Z}_3[x]/(x^2 + 1)$$

the class $\alpha = [x]$ satisfies $\alpha^2 + 1 = 0$, that is, $\alpha^2 = -1 = 2$. So $K$ contains $\mathbb{Z}_3$ and a square root of 2, and it has $3^2 = 9$ elements $a + b\alpha$. What remains to be seen is whether $K$ is a field, so that the new element can be divided by as well as multiplied. It is, and the reason is that $x^2 + 1$ is irreducible over $\mathbb{Z}_3$.

A field that contains $F$, with the same operations, is an extension field of $F$. First we prove that an irreducible modulus always gives a field. Then we deduce Kronecker's theorem, that every polynomial over a field has a root in some extension field, and follow the running quartic $f(x)$ into two such fields. Next we examine the fields with nine elements. Finally we prove $a^q = a$ in a field with $q$ elements, list the possible sizes, and meet the 256-element field of AES.

This is the last article of Congruence in Polynomial Rings and Field Extensions in the MTH 532 notes, and it builds on the previous article. It covers §5.3 of the course text (Hungerford, 2014), and states, with references, the facts about finite fields that the course text takes up later. Throughout, $F$ is a field and $p(x) \in F[x]$ is nonconstant.

Irreducible moduli give fields

For integers, $\mathbb{Z}_n$ is a field exactly when $n$ is prime (Units and Zero Divisors in the Integers Modulo n). The polynomial counterpart replaces "prime" by "irreducible", and the proof uses Bezout's identity in the same way. The idea: an irreducible $p$ shares no factor with anything it does not divide, so every nonzero class has an inverse; a reducible $p$ splits into smaller factors whose classes are zero divisors.

Theorem. The following are equivalent.

  1. $p(x)$ is irreducible in $F[x]$.
  2. $F[x]/(p(x))$ is a field.
  3. $F[x]/(p(x))$ is an integral domain.

Proof. By the previous article, $F[x]/(p(x))$ is a commutative ring with identity in which $[1] \neq [0]$. So (2) requires only that every nonzero element be a unit, and (3) only that there be no zero divisors.

(1) implies (2). Let $[h] \neq 0$, so $p \nmid h$. Let $d = \gcd(h, p)$. Since $d$ divides the irreducible $p$, it is either a nonzero constant or an associate of $p$; being monic, it is either $1$ or the monic associate of $p$. In the second case $p$ would divide $d$, which divides $h$, contradicting $p \nmid h$. So $d = 1$, and Bezout's identity gives $u, v \in F[x]$ with

$$h(x)u(x) + p(x)v(x) = 1.$$

Then $h u \equiv 1 \pmod p$, that is, $[h][u] = [1]$, and $[h]$ is a unit.

(2) implies (3). Every field is an integral domain: if $ab = 0$ and $a \neq 0$, multiplying by $a^{-1}$ gives $b = 0$.

(3) implies (1). Suppose $p$ is reducible. Then $p = bc$ with $b$ and $c$ of lower degree than $p$, and of positive degree (the degree form of irreducibility). Being nonzero of degree less than $\deg p$, neither $b$ nor $c$ is divisible by $p$, so $[b] \neq 0$ and $[c] \neq 0$. But $[b][c] = [bc] = [p] = 0$. So the ring has zero divisors and is not an integral domain. $\blacksquare$

This is Hungerford's Theorem 5.10. Judson (2026, Theorem 17.3.12) states it in the language of ideals: the multiples of $p(x)$ form a maximal ideal exactly when $p(x)$ is irreducible.

The theorem settles every example so far:

  • $K = \mathbb{Z}_3[x]/(x^2 + 1)$ is a field, because a quadratic with no root in $\mathbb{Z}_3$ is irreducible (its values at 0, 1, 2 are 1, 2, 2). It is the field $\mathbb{Z}_3[i]$ met in integral domains and fields, with $\alpha$ in the role of $i$.
  • $\mathbb{R}[x]/(x^2 + 1)$, which is $\mathbb{C}$, and $\mathbb{Q}[x]/(x^2 - 2)$, which is $\mathbb{Q}(\sqrt 2)$, are fields, since neither quadratic has a root in the coefficient field.
  • $\mathbb{Z}_2[x]/(x^4 + x^3 + 1)$ is a field with sixteen elements, while $\mathbb{Z}_2[x]/(x^4 + 1)$ and $\mathbb{Q}[x]/(f(x))$, for the running example $f(x) = (x^2 - 2)(x^2 + x + 1)$, are not; their zero divisors are described in Congruence-Class Arithmetic in Polynomial Rings.

Check your understanding. Over $\mathbb{Q}$ there are irreducible polynomials of every degree, so the theorem gives fields $\mathbb{Q}[x]/(p(x))$ in which each element needs $\deg p$ rational coefficients. For which degrees $d$ is there a field $\mathbb{R}[x]/(p(x))$ with $\deg p = d$?

Only $d = 1$ and $d = 2$. By the theorem, the ring is a field exactly when $p$ is irreducible in $\mathbb{R}[x]$, and the irreducible real polynomials are those of degree 1 and the quadratics with negative discriminant, because nonreal roots come in conjugate pairs. So over $\mathbb{R}$ the construction never produces a field whose elements need three or more real coefficients; the quadratics give fields like $\mathbb{R}[x]/(x^2 + 1)$. Irreducibility depends on the field, and so does the theorem.

Extension fields and Kronecker's theorem

The opening asked for a field containing $\mathbb{Z}_3$ in which 2 has a square root. The theorem supplies one, and the argument works for every irreducible polynomial. Recall that a field $E$ that contains $F$ as a subfield, with the same operations, is an extension field of $F$ (subrings and subfields). The chain $\mathbb{Q} \subseteq \mathbb{R} \subseteq \mathbb{C}$ is the familiar example. The theorem above, together with the copy of $F$ inside $F[x]/(p(x))$ from the previous article, says that for irreducible $p(x)$ the ring $F[x]/(p(x))$ is an extension field of $F$, once each $c \in F$ is identified with its class $[c]$. The new field always contains a root of $p(x)$.

The idea is one line from the previous article: $p(x) \equiv 0$, so the class of $x$ satisfies $p$.

Theorem (Kronecker). Let $p(x) = c_n x^n + \cdots + c_1 x + c_0$ be irreducible in $F[x]$. Then $E = F[x]/(p(x))$ is an extension field of $F$, and $\alpha = [x] \in E$ is a root of $p(x)$.

Proof. $E$ is a field by the previous theorem, and it contains $F$ through the identification $c = [c]$. The coefficients $c_i$ of $p$ are therefore elements of $E$, and $p(\alpha)$ makes sense. By the definitions of the operations on classes,

$$p(\alpha) = c_n[x]^n + \cdots + c_1[x] + c_0 = [c_n x^n + \cdots + c_1 x + c_0] = [p(x)] = [0],$$

since $p(x) \equiv 0 \pmod{p(x)}$. $\blacksquare$

For the opening field $K$, the theorem gives $\alpha^2 + 1 = 0$, that is, $\alpha^2 = 2$. The corollary's idea: any polynomial has an irreducible factor, and a root of the factor is a root of the polynomial.

Corollary. Every nonconstant polynomial $f(x) \in F[x]$ has a root in some extension field of $F$.

Proof. By unique factorization, $f = pg$ for some irreducible $p$ in $F[x]$. In $E = F[x]/(p)$, the element $\alpha = [x]$ is a root of $p$ by the theorem. Evaluation at $\alpha$ respects products, so $f(\alpha) = p(\alpha)g(\alpha) = 0 \cdot g(\alpha) = 0$. $\blacksquare$

These are Hungerford's Theorem 5.11 and Corollary 5.12. Judson (2026, Theorem 21.1.5) proves the corollary for any nonconstant polynomial, attributes it to Kronecker, and notes that it is often called the fundamental theorem of field theory. Its force is in what it does not assume. Nothing about $F$ is needed beyond its being a field: no completeness, no ordering, no analysis. A root is produced by pure algebra, as the class of $x$, and the question of whether a number with $\alpha^2 = -1$ or $\alpha^2 = 2$ "exists" is answered by constructing one. Applying the corollary repeatedly, to the factor that remains after a root is split off, gives an extension in which $f$ factors completely into linear factors, a splitting field (Judson, 2026, §21.2).

The running example

The quartic $f(x) = x^4 + x^3 - x^2 - 2x - 2 = (x^2 - 2)(x^2 + x + 1)$ has no rational roots. Its irreducible factors give two extensions of $\mathbb{Q}$ that contain a root, $\mathbb{Q}[x]/(x^2 - 2)$ and $\mathbb{Q}[x]/(x^2 + x + 1)$, and in each the script confirms that $f([x]) = 0$. Under the identifications of the previous article, the first root is $\sqrt 2$ and the second is the complex number $\omega = -\tfrac{1}{2} + \tfrac{\sqrt 3}{2}i$.

Check your understanding. The field $\mathbb{Q}[x]/(x^2 - 2)$ was built to contain a root of the first factor. Does it also contain a root of the second factor, $x^2 + x + 1$?

It does not. It is $\mathbb{Q}(\sqrt 2)$, which lies inside $\mathbb{R}$, while the roots of $x^2 + x + 1$ are $\omega$ and its conjugate, neither of them real. Over $\mathbb{Q}$ the construction has to be repeated, as for a splitting field.

Over $\mathbb{Z}_{11}$, $f$ has no roots either, and it factors as $(x^2 + x + 1)(x^2 + 9)$ into two irreducible quadratics (the table of factorizations). Since $9 = -2$ in $\mathbb{Z}_{11}$, the second factor is $x^2 - 2$ again, and the field

$$\mathbb{Z}_{11}[x]/(x^2 + 9),$$

with $11^2 = 121$ elements, contains $\gamma = [x]$ with $\gamma^2 = 2$. The script searches all 121 elements for roots of $f$ and finds four: $\gamma$ and $-\gamma = 10\gamma$, the square roots of 2, and also $\gamma + 5$ and $10\gamma + 5$, which are roots of the other factor $x^2 + x + 1$. Checking one of them: $(\gamma + 5)^2 + (\gamma + 5) + 1 = \gamma^2 + 11\gamma + 31 = 2 + 0 + 31 = 33 = 0$. So the field built for one factor happens to split the other as well, which over $\mathbb{Q}$ was impossible. Finite fields are more accommodating, for reasons explained below.

Two fields with nine elements

Why are finite fields so accommodating? A nine-element field is small enough to examine completely. Return to the field $K = \mathbb{Z}_3[x]/(x^2 + 1)$ of the opening. Its powers of $\alpha$ are

$$\alpha, \quad \alpha^2 = 2, \quad \alpha^3 = 2\alpha, \quad \alpha^4 = 1,$$

so $\alpha$ reaches only four of the eight nonzero elements before returning to 1. Another element does better. The script finds that $1 + \alpha$ has the powers

$$1 + \alpha, \; 2\alpha, \; 2\alpha + 1, \; 2, \; 2\alpha + 2, \; \alpha, \; \alpha + 2, \; 1,$$

which are all eight nonzero elements. A different irreducible quadratic makes the class of $x$ itself do this. The polynomial $x^2 + x + 2$ has the values 2, 1, 2 at $0, 1, 2$, so it is irreducible over $\mathbb{Z}_3$, and

$$L = \mathbb{Z}_3[x]/(x^2 + x + 2)$$

is a second field with nine elements. Write $\beta = [x]$. The modulus gives the reduction rule $\beta^2 = -\beta - 2 = 2\beta + 1$, and each power of $\beta$ follows from the previous one by multiplying by $\beta$ and applying the rule:

$k$ 0 1 2 3 4 5 6 7 8
$\beta^k$ $1$ $\beta$ $2\beta + 1$ $2\beta + 2$ $2$ $2\beta$ $\beta + 2$ $\beta + 1$ $1$

For instance $\beta^3 = \beta(2\beta + 1) = 2\beta^2 + \beta = 2(2\beta + 1) + \beta = 5\beta + 2 = 2\beta + 2$. The eight powers $\beta^0, \ldots, \beta^7$ are the eight nonzero elements of $L$, each once.

The nonzero elements of the nine-element field L = \mathbb{Z}_3[x]/(x^2 + x + 2) as the powers of \beta = [x]. Each arrow multiplies by \beta, using \beta^2 = 2\beta + 1, and after eight steps the cycle closes with \beta^8 = 1. Notice that every nonzero element appears once, and that the elements 1 and 2 of \mathbb{Z}_3 sit opposite each other at \beta^0 and \beta^4; the square roots of 2 = \beta^4 are \beta^2 and \beta^6.
The nonzero elements of the nine-element field $L = \mathbb{Z}_3[x]/(x^2 + x + 2)$ as the powers of $\beta = [x]$. Each arrow multiplies by $\beta$, using $\beta^2 = 2\beta + 1$, and after eight steps the cycle closes with $\beta^8 = 1$. Notice that every nonzero element appears once, and that the elements 1 and 2 of $\mathbb{Z}_3$ sit opposite each other at $\beta^0$ and $\beta^4$; the square roots of $2 = \beta^4$ are $\beta^2$ and $\beta^6$.

An element whose powers run through every nonzero element is a generator of the multiplicative group of the field (also called a primitive element). In $L$ the script finds four generators, $\beta$, $\beta^3 = 2\beta + 2$, $\beta^5 = 2\beta$ and $\beta^7 = \beta + 1$: the powers $\beta^k$ with $k$ odd, that is, with $k$ relatively prime to 8. In $K$, $\alpha$ is not a generator but $1 + \alpha$ is. That every finite field has a generator is a theorem: the nonzero elements of a finite field always form a cyclic group (Judson, 2026, Corollary 22.1.11). The proof uses the structure of finite abelian groups and is beyond this unit, but for nine elements the table above is the proof.

Multiplying with a generator

With a generator, multiplication becomes addition of exponents modulo 8, as multiplication of positive numbers becomes addition of logarithms. The multiplication table of $L$, with the elements listed in the order of their exponents, shows the pattern: each row is the row above shifted one place.

The multiplication table of L = \mathbb{Z}_3[x]/(x^2 + x + 2), with the nonzero elements listed as \beta^0, \beta^1, \ldots, \beta^7 (green labels). Apart from the row and column of 0, each row is the previous row shifted one place to the left, because multiplying by \beta^{i+1} is multiplying by \beta^i and then by \beta. The 1s sit where \beta^i \beta^j = 1, which happens exactly when i + j is a multiple of 8, so the inverse of \beta^i is \beta^{8 - i}.
The multiplication table of $L = \mathbb{Z}_3[x]/(x^2 + x + 2)$, with the nonzero elements listed as $\beta^0, \beta^1, \ldots, \beta^7$ (green labels). Apart from the row and column of 0, each row is the previous row shifted one place to the left, because multiplying by $\beta^{i+1}$ is multiplying by $\beta^i$ and then by $\beta$. The 1s sit where $\beta^i \beta^j = 1$, which happens exactly when $i + j$ is a multiple of 8, so the inverse of $\beta^i$ is $\beta^{8 - i}$.

For example, $1 + 2\beta = \beta^2$ and $2 + 2\beta = \beta^3$, so

$$(1 + 2\beta)(2 + 2\beta) = \beta^{2 + 3} = \beta^5 = 2\beta,$$

which the script confirms by multiplying the polynomials and reducing. The inverse of $1 + 2\beta = \beta^2$ is $\beta^6 = \beta + 2$; directly, $(2\beta + 1)(\beta + 2) = 2\beta^2 + 5\beta + 2 = 2(\beta^2 + \beta + 1) = 2 \cdot 2 = 1$, using $\beta^2 + \beta = -2 = 1$.

Check your understanding. The first article reduced $x^{100}$ modulo $x^3 + x^2 + 1$ using $x^7 \equiv 1$. Predict $\beta^{100}$ in $L$ the same way.

Since $\beta^8 = 1$, only the exponent modulo 8 matters, and $100 = 8 \cdot 12 + 4$. So $\beta^{100} = \beta^4 = 2$, which the script confirms by a hundred multiplications. The method is the same in both cases: the powers of $x$ cycle, and only the position in the cycle matters. In both examples the cycle happens to pass through every nonzero class, but it need not; $\alpha$ in $K$ has a cycle of length 4.

Square roots of 2, again

$L$ was not built to contain a square root of 2, but it does. In $L$, $2 = -1 = \beta^4$, so $(\beta^2)^2 = 2$ and $(\beta^6)^2 = \beta^{12} = \beta^4 = 2$. The square roots of 2 in $L$ are $\beta^2 = 2\beta + 1$ and $\beta^6 = \beta + 2$, as the script confirms by squaring all nine elements.

That suggests that $K$ and $L$ are the same field under different names, and they are. Since $\alpha^2 = 2$ in $K$ and $(2\beta + 1)^2 = 2$ in $L$, try the map

$$\psi(a + b\alpha) = a + b\,(2\beta + 1), \qquad a, b \in \mathbb{Z}_3.$$

It sends the nine elements of $K$ to nine different elements of $L$, and the script checks all 81 pairs of elements of $K$ and finds that $\psi$ respects sums and products. So $\psi$ is an isomorphism. It sends the generator $1 + \alpha$ of $K$ to $2\beta + 2 = \beta^3$, a generator of $L$, as an isomorphism must. The general fact behind the example is stated below: any two fields with the same finite number of elements are isomorphic.

Every element is a root of $x^q - x$

That $x^7 \equiv 1$ modulo the irreducible cubic $x^3 + x^2 + 1$ over $\mathbb{Z}_2$, with its eight classes, and $\alpha^8 = \beta^8 = 1$ in the nine-element fields is no accident. Fermat's little theorem says that $a^p = a$ for every $a$ in $\mathbb{Z}_p$. The same holds in every finite field, with the number of elements in place of $p$, and the proof is the rearrangement argument of Fermat's little theorem. The idea: multiplying all nonzero elements by a fixed $a \neq 0$ only shuffles them, so their product is unchanged except for a factor $a^{q-1}$.

Proposition. Let $E$ be a field with $q$ elements. Then $a^{q-1} = 1$ for every nonzero $a \in E$, and $a^q = a$ for every $a \in E$.

Proof. List the nonzero elements as $e_1, \ldots, e_{q-1}$ and let $a \neq 0$. The products $ae_1, \ldots, ae_{q-1}$ are nonzero (a field has no zero divisors) and different (if $ae_i = ae_j$, multiplying by $a^{-1}$ gives $e_i = e_j$), so they are the same $q - 1$ elements in some order. Multiplying each list together,

$$a^{q-1}\, e_1 e_2 \cdots e_{q-1} = e_1 e_2 \cdots e_{q-1}.$$

The product $e_1 \cdots e_{q-1}$ is nonzero, so it can be canceled, leaving $a^{q-1} = 1$. Multiplying by $a$ gives $a^q = a$, which also holds for $a = 0$. $\blacksquare$

So every element of $E$ is a root of $x^q - x$, and a polynomial of degree $q$ with $q$ roots must factor completely:

Corollary. In $E[x]$,

$$x^q - x = \prod_{c \in E} (x - c).$$

Proof. Both sides are monic of degree $q$, so their difference is 0 or of degree less than $q$. Every $c \in E$ is a root of the right side, visibly, and of the left side, by the proposition. A nonzero polynomial over a field has at most as many roots as its degree (roots and linear factors), so the difference, with $q$ roots, is 0. $\blacksquare$

The script confirms $a^9 = a$ for all nine elements of $L$. For $q = 9$, the polynomial $x^9 - x$ has coefficients in $\mathbb{Z}_3$, and over $\mathbb{Z}_3$ the script factors it as

$$x^9 - x = x\,(x + 1)(x + 2)\,(x^2 + 1)(x^2 + x + 2)(x^2 + 2x + 2).$$

The three quadratics are all the monic irreducible quadratics over $\mathbb{Z}_3$, the count of 3 in the table of irreducibles. By the corollary, each of them splits into linear factors over $L$, and the script locates the roots: $x^2 + 1$ has the roots $\beta^2$ and $\beta^6$, $x^2 + x + 2$ has $\beta$ and $\beta^3$, and $x^2 + 2x + 2$ has $\beta^5$ and $\beta^7$. So a field built from one irreducible quadratic over $\mathbb{Z}_3$ contains the roots of all of them, which is the finite-field phenomenon met above in $\mathbb{Z}_{11}[x]/(x^2 + 9)$.

There is a pattern in the pairs: the second root is always the cube of the first. In a ring in which $3 = 0$, the binomial theorem gives $(a + b)^3 = a^3 + 3a^2b + 3ab^2 + b^3 = a^3 + b^3$, and every $c \in \mathbb{Z}_3$ satisfies $c^3 = c$. Cubing $\beta^2 + \beta + 2 = 0$ therefore gives

$$0 = (\beta^2 + \beta + 2)^3 = (\beta^3)^2 + \beta^3 + 2,$$

so $\beta^3$ is again a root of $x^2 + x + 2$. Indeed $x^2 + x + 2 = (x - \beta)(x - \beta^3)$ in $L[x]$, and the coefficients check: $\beta + \beta^3 = \beta + 2\beta + 2 = 2 = -1$ and $\beta \cdot \beta^3 = \beta^4 = 2$. The identity $(a + b)^p = a^p + b^p$ in characteristic $p$ is Judson's "freshman's dream" (2026, Lemma 22.1.3), and it underlies the general theory of finite fields.

Which sizes occur

The fields so far had 9, 16 and 121 elements, all prime powers. Which sizes can a finite field have? A field $\mathbb{Z}_p[x]/(m(x))$ with $m(x)$ irreducible of degree $n$ has $p^n$ elements, and the counts of irreducible polynomials show irreducibles of every degree tested over $\mathbb{Z}_2$ and $\mathbb{Z}_3$. Taking the first irreducible found by the script in each case:

Elements Construction
4 $\mathbb{Z}_2[x]/(x^2 + x + 1)$
8 $\mathbb{Z}_2[x]/(x^3 + x^2 + 1)$
9 $\mathbb{Z}_3[x]/(x^2 + 1)$
16 $\mathbb{Z}_2[x]/(x^4 + x^3 + 1)$
25 $\mathbb{Z}_5[x]/(x^2 + x + 1)$
27 $\mathbb{Z}_3[x]/(x^3 + 2x^2 + 1)$
32 $\mathbb{Z}_2[x]/(x^5 + x^3 + 1)$

Together with the fields $\mathbb{Z}_p$, these give a field of every prime power size up to 32. No other sizes are possible, and no other fields need to be looked for:

  • every finite field has $p^n$ elements for some prime $p$ and some $n \ge 1$ (Judson, 2026, Proposition 22.1.2), so there is no field with 6, 10, 12 or 15 elements;
  • for every prime power $p^n$ there is a field with $p^n$ elements, and any two such fields are isomorphic (Judson, 2026, Theorem 22.1.6).

These are stated here without proof, as in the course text, which returns to finite fields in a later chapter (Hungerford, 2014, §11.6). The first fact rests on viewing a finite field as a vector space over its copy of $\mathbb{Z}_p$; the second on the polynomial $x^{p^n} - x$, whose roots form the field, as the corollary above suggests. The unique field with $p^n$ elements is written $\mathbb{F}_{p^n}$ or $\mathrm{GF}(p^n)$, the Galois field. The fields $K$ and $L$ above are two constructions of $\mathbb{F}_9$, and $\psi$ is one isomorphism between them.

A field in daily use

Is any of this used outside algebra? The Advanced Encryption Standard (AES), the block cipher standardized by NIST, does part of its arithmetic in $\mathbb{F}_{256}$. The standard reads each byte $b_7 b_6 \ldots b_0$ as the polynomial $b_7 x^7 + \cdots + b_1 x + b_0$ over $\mathbb{Z}_2$, adds bytes by adding coefficients modulo 2, and multiplies them by multiplying the polynomials and reducing modulo

$$m(x) = x^8 + x^4 + x^3 + x + 1$$

(NIST, 2023, §4 to §4.2). That is arithmetic in $\mathbb{Z}_2[x]/(m(x))$, and the script confirms by trial division that $m(x)$ is irreducible over $\mathbb{Z}_2$, so this ring is a field with $2^8 = 256$ elements. Multiplying by the byte $\{02\}$, which is $x$, shifts the bits left, and when a term $x^8$ appears the reduction rule $x^8 = x^4 + x^3 + x + 1$ replaces it, which in bits means adding $\{1b\} = 00011011$. The standard's worked example multiplies $\{57\} = x^6 + x^4 + x^2 + x + 1$ by $\{13\} = x^4 + x + 1$ and obtains $\{fe\}$, which the script reproduces. Inverses, needed for the cipher's substitution step, are computed either as $b^{254}$, the proposition above with $q = 256$, or by the extended Euclidean algorithm applied to $b(x)$ and $m(x)$ (NIST, 2023, §4.4), exactly the two methods of this unit; the script finds $\{57\}^{-1} = \{bf\}$ both ways. In this field the class of $x$ is not a generator: the script finds that its powers repeat after 51 steps, while those of $x + 1 = \{03\}$ run through all 255 nonzero elements.

Parallels with the integers

Prime modulus in $\mathbb{Z}$ Irreducible modulus in $F[x]$
$\mathbb{Z}_n$ is a field if and only if $n$ is prime $F[x]/(p(x))$ is a field if and only if $p(x)$ is irreducible
inverses from Bezout's identity inverses from Bezout's identity
$\mathbb{Z}_p$ has $p$ elements $\mathbb{Z}_p[x]/(p(x))$ has $p^{\deg p}$ elements
$a^p = a$ in $\mathbb{Z}_p$ (Fermat) $a^q = a$ in a field with $q$ elements
$x^p - x = \prod_{a \in \mathbb{Z}_p} (x - a)$ $x^q - x = \prod_{c \in E} (x - c)$
no new elements a new element $[x]$, a root of $p(x)$

Where it leads

What we have learned

$F[x]/(p(x))$ is a field exactly when $p(x)$ is irreducible, as $\mathbb{Z}_n$ is exactly when $n$ is prime. The field contains $F$ and a root of $p(x)$, the class of $x$, so every nonconstant polynomial has a root in some extension field (Kronecker). Over $\mathbb{Z}_p$ this gives finite fields of $p^n$ elements, in which $a^q = a$. It answered the opening question with $K$, and it runs inside AES.

$K$ and $L$ came from different polynomials and turned out to be one field under different names. What exactly is a map that respects both operations, and what does it preserve? The next unit begins with Ring Homomorphisms and Isomorphisms.

References

  • Hungerford, T. W. (2014). Abstract Algebra: An Introduction (3rd ed.), §5.3, with finite fields in §11.6. Brooks/Cole, Cengage Learning. The course text: $F[x]/(p(x))$ is a field if and only if it is an integral domain, if and only if $p(x)$ is irreducible (Theorem 5.10); it is an extension field containing a root of $p(x)$ (Theorem 5.11); every nonconstant polynomial has a root in some extension field (Corollary 5.12). record · 44 pages
  • Judson, T. W. (2026). Abstract Algebra: Theory and Applications (annual edition, August 2026). Theorem 17.3.12 (the ideal generated by $p(x)$ is maximal if and only if $p(x)$ is irreducible); Theorem 21.1.5 (Kronecker's theorem, the fundamental theorem of field theory); §21.2 (splitting fields); Proposition 22.1.2 (a finite field has prime power order); Lemma 22.1.3 (freshman's dream); Theorem 22.1.6 (existence and uniqueness of the field with $p^n$ elements); Corollary 22.1.11 (the multiplicative group of a finite field is cyclic). Free online at judsonbooks.org. record · 44 pages
  • National Institute of Standards and Technology (2023). Advanced Encryption Standard (AES), FIPS 197 (published November 26, 2001; updated May 9, 2023), §4: bytes as polynomials over $\mathbb{Z}_2$ (§4), addition (§4.1), multiplication modulo $m(x) = x^8 + x^4 + x^3 + x + 1$ and the example $\{57\} \bullet \{13\} = \{fe\}$ (§4.2), inverses as $b^{254}$ or by the extended Euclidean algorithm (§4.4). doi:10.6028/NIST.FIPS.197-upd1. record