Finite fields, GF(p) and GF(2^n)

An irreducible polynomial does for polynomials what a prime does for integers

04-06 ended with $\mathbb{Z}_8$ failing to be a field: $2$ has no multiplicative inverse mod $8$, because $2$ and $8$ share a factor. Enlarging the modulus only helps when the modulus is prime. AES needs a field with exactly $2^8 = 256$ elements, one for every possible byte, and $256$ is about as far from prime as a number gets. Finite fields solve this by changing what “multiply and reduce” means: the elements become polynomials, reduced by an irreducible polynomial that plays the role a prime plays for ordinary integers. Every nonzero byte then gets an inverse, and that inverse is the entire mathematical content of the AES S-box.

A prime field $\mathrm{GF}(p)$, also written $F_p$, is the set $\{0, 1, \ldots, p-1\}$ with addition and multiplication taken modulo a prime $p$. 04-06’s $F_7$ is one instance. $\mathrm{GF}(p)$ has characteristic $p$: the smallest number of copies of any element that sum to $0$.

An extension field $\mathrm{GF}(p^n)$, for $n > 1$, has $p^n$ elements. It is built by adjoining to $\mathrm{GF}(p)$ the roots of a degree-$n$ polynomial that cannot be reduced further, an irreducible polynomial over $\mathrm{GF}(p)$. “Irreducible” means it cannot be factored into polynomials of lower degree using coefficients from the base field. $x^2 + 1$ is irreducible over the real numbers, but not over the complex numbers, where it factors as $(x+i)(x-i)$. Irreducibility is always relative to a base field.

In GF(2^3), addition cancels matching terms and multiplication reduces by x^3 + x + 1

Start from $\mathrm{GF}(2) = \{0, 1\}$, where addition and multiplication are mod $2$. Choose an irreducible polynomial of degree $3$ over $\mathrm{GF}(2)$: the lecture uses $p(x) = x^3 + x + 1$, which has no root in $\{0, 1\}$ and cannot be factored over $\mathrm{GF}(2)$. The field then has $2^3 = 8$ elements: every polynomial of degree less than $3$ with coefficients in $\{0, 1\}$.

Try it — worked example

List the eight elements of GF(2^3) as polynomials and as 3-bit strings.

Show answer and steps

AnswerThe eight elements of GF(2^3)

1. $000 = 0$
2. $001 = 1$
3. $010 = x$
4. $011 = x + 1$
5. $100 = x^2$
6. $101 = x^2 + 1$
7. $110 = x^2 + x$
8. $111 = x^2 + x + 1$

Addition and multiplication both work modulo $2$ on the coefficients, and multiplication additionally reduces modulo $p(x) = x^3 + x + 1$ whenever a product’s degree reaches $3$ or higher. Since coefficients are mod $2$, addition is the same operation as subtraction: $1 + 1 = 0$, so “adding” two polynomials just cancels any term that appears in both.

Try it — worked example

In GF(2^3), compute (x^2 + x) + (x + 1).

Show answer and steps

Answer(x^2 + x) + (x + 1) = x^2 + 1

1. $(x^2 + x) + (x + 1) = x^2 + (x + x) + 1$.
2. $x + x = 0$ in $\mathrm{GF}(2)$, since coefficients add mod $2$.
3. $x^2 + 0 + 1 = x^2 + 1$.

Try it — worked example

In GF(2^3) with p(x) = x^3 + x + 1, compute x(x + 1).

Show answer and steps

Answerx(x+1) = x^2 + x

1. $x \cdot (x + 1) = x \cdot x + x \cdot 1 = x^2 + x$.
2. Degree $2$ is below the field’s degree bound of $3$, so no reduction is needed. The product is already one of the eight elements.

Try it — worked example

In GF(2^3) with p(x) = x^3 + x + 1, compute x^2(x + 1).

Show answer and steps

Answerx^2(x+1) reduces to x^2 + x + 1

1. $x^2 \cdot (x + 1) = x^3 + x^2$.
2. Degree $3$ overflows the field, so reduce modulo $p(x) = x^3 + x + 1$. Since $p(x) \equiv 0$, $x^3 \equiv -(x + 1)$, and in $\mathrm{GF}(2)$, subtraction is the same as addition, so $x^3 \equiv x + 1$.
3. Substitute: $x^3 + x^2 \equiv (x + 1) + x^2 = x^2 + x + 1$.
4. $x^2(x+1) = x^2 + x + 1$ in $\mathrm{GF}(2^3)$.

Pitfall

“Subtracting” a polynomial modulo $2$ is not a separate operation to learn: it is addition, because every coefficient is its own additive inverse in $\mathrm{GF}(2)$ ($1 + 1 = 0$, so $1 = -1$). Reduction by an irreducible polynomial is always carried out by XOR-ing bit patterns, never by a signed subtraction.

GF(2^8) is the field AES runs on, and its byte inverse is the S-box

$\mathrm{GF}(2^8)$ is chosen for two reasons the lecture gives directly: it balances security against efficiency (large enough for real cryptographic strength, small enough to implement efficiently in hardware and software), and its elements map naturally onto a byte, since digital systems already work in binary. Every element is a polynomial of degree less than $8$ with coefficients in $\{0, 1\}$: $a_7 x^7 + a_6 x^6 + \ldots + a_1 x + a_0, \qquad a_i \in \{0, 1\}.$ The irreducible polynomial AES reduces by is $m(x) = x^8 + x^4 + x^3 + x + 1,$ written in binary as $100011011$, or $\mathtt{0x11B}$.

Formula

AES irreducible polynomial

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

$m(x)$

the modulus every GF(2^8) multiplication in AES reduces by

Binary 100011011, hex 0x11B.

Addition in $\mathrm{GF}(2^8)$ is bitwise XOR, the same $1+1=0$ rule as $\mathrm{GF}(2^3)$, applied across all eight bit positions independently, with no carrying between them.

Try it — worked example

In GF(2^8), add a = 01010100 and b = 10011010.

Show answer and steps

Answer01010100 XOR 10011010 = 11001110

Let $a = x^6 + x^4 + x^2$ (binary $01010100$) and $b = x^7 + x^4 + x^3 + x$ (binary $10011010$).

1. Line up the bits: $a = 01010100$, $b = 10011010$.
2. XOR bit by bit: $0{\oplus}1, 1{\oplus}0, 0{\oplus}0, 1{\oplus}1, 0{\oplus}1, 1{\oplus}0, 0{\oplus}1, 0{\oplus}0 = 1,1,0,0,1,1,1,0$.
3. $c = a \oplus b = 11001110$, which is $x^7 + x^6 + x^3 + x^2 + x$.

Multiplication combines shifting (to multiply by $x$) with conditional reduction whenever the shift overflows the field’s 8-bit width. AES’s SubBytes and MixColumns steps mostly need it in its simplest form: multiplying a byte by $x$ alone.

Try it — worked example

In AES’s GF(2^8), multiply 11000000 by x.

Show answer and steps

Answer11000000 x x reduces to 10011011

Let $a = x^7 + x^6$, binary $11000000$.

1. Multiplying by $x$ shifts every bit left by one place: $11000000 \times x = 110000000$, a 9-bit result, since $a$‘s top bit was set and the shift pushed a new bit past position $7$. This is the polynomial $x^8 + x^7$.
2. Degree $8$ overflows the field, so reduce modulo $m(x) = x^8+x^4+x^3+x+1$, written as the 9-bit pattern $100011011$.
3. XOR the two 9-bit values: $110000000 \oplus 100011011 = 010011011$.
4. Dropping the leading zero, the result fits in 8 bits: $10011011$, the polynomial $x^7 + x^4 + x^3 + x + 1$.

Multiplying by $x$ this way is often called $\mathtt{xtime}$. Multiplying by any other byte decomposes into $\mathtt{xtime}$ calls and conditional XORs, one pair per bit of the second operand, the same shift-and-add pattern as the $\mathrm{GF}(2^3)$ examples with eight bit positions instead of three. The calculator below shows every step for any pair of bytes.

GF(2^8) calculator

Add, multiply and invert bytes in the AES field GF(2^8), with every reduction step of a multiply shown.

a

b

Operationa ⊕ b (XOR)a × ba⁻¹

Compute

Result

AES’s S-box, the nonlinear step in SubBytes, is defined as: take a byte’s multiplicative inverse in $\mathrm{GF}(2^8)$ (the byte $\mathtt{0x00}$, which has no inverse, maps to itself), then apply a fixed affine transformation on top. The inverse step is the one that matters algebraically. The affine transformation is linear and adds no cryptographic strength on its own; it exists to remove algebraic simplicities the raw inverse function would otherwise have.

Exam detail

The inverse step only works because $\mathrm{GF}(2^8)$ is a genuine field: every one of the $255$ nonzero bytes has exactly one multiplicative inverse, guaranteed by the same field axiom 04-06 builds up to. That guarantee is what makes SubBytes invertible, which is what makes AES decryption possible at all: a substitution built on a function without guaranteed inverses could not be undone. See AES for the S-box in the context of the full cipher, including SubBytes, ShiftRows, MixColumns and AddRoundKey together.

Recall

Why does GF(2^8) need an irreducible polynomial at all, when GF(256) as plain integers mod 256 would also have 256 elements?

$256 = 2^8$ is not prime, so integers mod $256$ would only ever be a commutative ring, the same way $\mathbb{Z}_8$ is on 04-06, and most elements would have no multiplicative inverse. Representing elements as degree-$<8$ polynomials over $\mathrm{GF}(2)$, and reducing products by an irreducible polynomial instead of a composite integer, is what actually delivers a field with $256$ elements. The irreducible polynomial does for polynomial arithmetic exactly what a prime modulus does for integer arithmetic.