Codes on every phone and the ciphers behind secure web pages run on arithmetic in finite fields. Besides $\mathbb{Z}_{p}$ there are fields of size $4, 8, 9, 16, 25, \dots$, built with the quotient-ring construction from polynomials over $\mathbb{Z}_{p}$.
Why it works
(1) A finite field $F$ has prime characteristic $p$: the additive order of $1$ is finite, and if it were $ab$ with $a, b \gt 1$, then $(a \cdot 1)(b \cdot 1) = 0$ would give zero divisors. So $F$ contains a copy of $\mathbb{Z}_{p}$.
(2) $|F| = p^{n}$: $F$ is a vector space over $\mathbb{Z}_{p}$ of some dimension $n$, and each vector has $n$ coordinates with $p$ choices each.
(3) For every prime power $p^{n}$ there is a field of that size, unique up to isomorphism, called $\mathrm{GF}(p^{n})$; it is $\mathbb{Z}_{p}[x]/(f)$ for any irreducible $f$ of degree $n$. (Existence and uniqueness are proved in Judson, chapter 22.)
Arithmetic in $\mathbb{Z}_{p}[x]/(f)$. Elements are polynomials of degree less than $n$ with coefficients mod $p$. Add coefficientwise. Multiply, then replace $x^{n}$ using $f = 0$. Invert with the Euclidean algorithm, or by search in small fields.
Worked example: Multiplying in $\mathrm{GF}(8)$
- Multiply: $x^{4} + x^{3} + x^{2} + x$.
- Here $x^{3} = x + 1$ (since $x^{3} + x + 1 = 0$ and $-1 = 1$), so $x^{4} = x^{2} + x$.
- Substitute: $(x^{2} + x) + (x + 1) + x^{2} + x = 2x^{2} + 3x + 1 = x + 1$ (mod 2).
Answer: $x + 1$.
Worked example: An inverse in $\mathrm{GF}(8)$
- Try $x^{2} + x$: $(x + 1)(x^{2} + x) = x^{3} + 2x^{2} + x = x^{3} + x$.
- $x^{3} + x = (x + 1) + x = 1$.
Answer: $(x + 1)^{-1} = x^{2} + x$.
Worked example: The field with 4 elements
- Elements: $0, 1, x, x + 1$, with $x^{2} = x + 1$.
- $x \cdot x = x + 1$, $x(x + 1) = x^{2} + x = 1$, $(x + 1)^{2} = x^{2} + 1 = x$.
Answer: The nonzero elements $1, x, x + 1$ form a cyclic group of order $3$.
Common mistake
Key idea