Navigate: arrow keys or swipe · Press ESC for overview
A field is a set $F$ with two operations ($+$ and $\cdot$) satisfying these axioms:
$a + b \in F$ and $a \cdot b \in F$ for all $a, b \in F$
$(a + b) + c = a + (b + c)$ and $(a \cdot b) \cdot c = a \cdot (b \cdot c)$
$a + b = b + a$ and $a \cdot b = b \cdot a$
$\exists\, 0: a + 0 = a$ and $\exists\, 1: a \cdot 1 = a$
$\forall\, a \in F,\; \exists\, {-a}: a + (-a) = 0$
$\forall\, a \neq 0,\; \exists\, a^{-1}: a \cdot a^{-1} = 1$
A finite field (or Galois Field) has a finite number of elements. A finite field of order $q$ exists if and only if $q = p^n$ for some prime $p$ and positive integer $n$. It is denoted $GF(p^n)$ or $\mathbb{F}_{p^n}$.
French mathematician who developed the foundations of group theory and field theory as a teenager, establishing the conditions under which polynomial equations can be solved by radicals.
A politically active Republican during turbulent times, Galois was expelled from the Ecole Normale and imprisoned twice. On 30 May 1832, aged twenty, he was mortally wounded in a duel.
The night before, he wrote feverishly to his friend Auguste Chevalier, scrawling in the margins:
"Je n'ai pas le temps"
"I have not the time"
His manuscripts, published posthumously in 1846 by Joseph Liouville, laid the groundwork for modern abstract algebra.
The simplest Galois Field: $GF(2) = \{0, 1\}$ with two operations.
| + | 0 | 1 |
|---|---|---|
| 0 | 0 | 1 |
| 1 | 1 | 0 |
$a + b = a \oplus b$
| × | 0 | 1 |
|---|---|---|
| 0 | 0 | 0 |
| 1 | 0 | 1 |
$a \cdot b = a \wedge b$
XOR = GF(2) Addition AND = GF(2) Multiplication
This is not an analogy — it is an exact algebraic correspondence.
Every XOR gate performs GF(2) addition. Every AND gate performs GF(2) multiplication.
Elements of $GF(2^n)$ are polynomials of degree $\leq n{-}1$ with coefficients in $\{0,1\}$. Each polynomial maps to an $n$-bit binary string.
$x^2 + 1$ → 101
$x^2 + x$ → 110
$x^2 + x + 1$ → 111
$x + 1$ → 011
$x$ → 010
$1$ → 001
To work with multi-bit data, we need fields larger than $GF(2)$. Extension fields $GF(2^n)$ contain $2^n$ elements.
Choose an irreducible polynomial $p(x)$ of degree $n$ over $GF(2)$. The field $GF(2^n)$ is:
$$GF(2^n) \cong GF(2)[x] \,/\, p(x)$$
That is: all polynomials over $GF(2)$, reduced modulo $p(x)$. The irreducible polynomial "wraps" higher-degree results back into the field, just as a modulus wraps integers.
$GF(2^3)$
8 elements · 3-bit values
$GF(2^8)$
256 elements · byte-sized (AES)
$GF(2^{32})$
~4B elements · CRC-32
Primitive polynomial: $p(x) = x^3 + x + 1$. The 8 field elements:
| Power of $\alpha$ | Polynomial | Binary | Decimal |
|---|---|---|---|
| — | $0$ | 000 | 0 |
| $\alpha^0$ | $1$ | 001 | 1 |
| $\alpha^1$ | $x$ | 010 | 2 |
| $\alpha^2$ | $x^2$ | 100 | 4 |
| $\alpha^3$ | $x + 1$ | 011 | 3 |
| $\alpha^4$ | $x^2 + x$ | 110 | 6 |
| $\alpha^5$ | $x^2 + x + 1$ | 111 | 7 |
| $\alpha^6$ | $x^2 + 1$ | 101 | 5 |
Addition is bitwise XOR of the binary representations. No carries, no modular reduction needed.
110 and 101
110 $\oplus$ 101 $=$ 011
011 $= x + 1$
Polynomial view:
$(x^2 + x) + (x^2 + 1)$
$= (1{\oplus}1)x^2 + (1{\oplus}0)x + (0{\oplus}1)$
$= x + 1$
Key property:
Every element is its own additive inverse:
$a + a = 0$ (since $1 \oplus 1 = 0$)
So subtraction $=$ addition $=$ XOR.
Multiply as polynomials, then reduce modulo the irreducible polynomial $p(x)$.
Compute $(x^2 + x) \times (x + 1)$ with $p(x) = x^3 + x + 1$
An irreducible polynomial over $GF(2)$ cannot be factored into lower-degree polynomials over $GF(2)$. It plays the role of a prime number — defining the field's modular arithmetic.
| Application | Field | Polynomial | Hex |
|---|---|---|---|
| CRC-8 | $GF(2^8)$ | $x^8 + x^2 + x + 1$ | 0x107 |
| CRC-16-CCITT | $GF(2^{16})$ | $x^{16} + x^{12} + x^5 + 1$ | 0x11021 |
| CRC-32 | $GF(2^{32})$ | $x^{32} + x^{26} + x^{23} + x^{22} + \ldots + 1$ | 0x104C11DB7 |
| AES | $GF(2^8)$ | $x^8 + x^4 + x^3 + x + 1$ | 0x11B |
The field axioms guarantee properties that hardware designers rely on:
The result of any addition or multiplication of field elements is always another field element. An $n$-bit XOR or multiply-and-reduce always yields a valid $n$-bit output.
Every non-zero element $a$ has a unique $a^{-1}$ such that $a \cdot a^{-1} = 1$. Critical for AES SubBytes and Reed-Solomon decoding. By Fermat: $a^{-1} = a^{2^n - 2}$.
$a + a = 0$ for all $a$. Subtraction is identical to addition (both are XOR). Simplifies hardware: no subtractor circuits needed.
$a \cdot (b + c) = a \cdot b + a \cdot c$. Enables matrix formulations of encoding/decoding and parallelised CRC computation.
Cyclic Redundancy Check — polynomial division in $GF(2)$ for error detection.
A CRC treats the message as a polynomial $M(x)$ over $GF(2)$, divides by a generator polynomial $G(x)$, and appends the remainder as a check value. The receiver divides by $G(x)$ — a non-zero remainder indicates an error.
$\text{CRC} = M(x) \cdot x^r \mod G(x)$
Feedback taps correspond to non-zero coefficients of $G(x)$. Each clock cycle shifts data and XORs feedback.
github.com/BrendanJamesLynskey/CRC Ethernet USB PCIe
Linear Feedback Shift Register — multiplication by $x$ in $GF(2^n)$.
An LFSR shifts its register contents by one position each clock cycle. Selected bits are XORed and fed back to the input. The feedback taps are defined by a polynomial over $GF(2)$.
With a primitive polynomial of degree $n$, the LFSR produces a maximum-length sequence of period $2^n - 1$, cycling through every non-zero element of $GF(2^n)$.
The Advanced Encryption Standard operates on bytes as elements of $GF(2^8)$.
The SubBytes step — the core non-linear operation of AES — computes the multiplicative inverse of each byte in $GF(2^8)$ with irreducible polynomial $p(x) = x^8 + x^4 + x^3 + x + 1$, followed by an affine transformation over $GF(2)$.
$$\text{SubBytes}(a) = A \cdot a^{-1} + c \quad \text{in } GF(2^8)$$
where $a^{-1}$ is the multiplicative inverse (with $0 \mapsto 0$), $A$ is a fixed $8 \times 8$ binary matrix, and $c = \texttt{0x63}$.
Lookup Table
256-entry S-box ROM
Fast, constant area
Composite Field
$GF((2^4)^2)$ decomposition
Smaller area, more logic
Fermat's Theorem
$a^{-1} = a^{254}$
Exponentiation by squaring
Reed-Solomon codes are symbol-level error-correcting codes built on $GF(2^m)$ arithmetic. An RS$(n, k)$ code encodes $k$ data symbols into $n$ symbols, correcting up to $t = (n-k)/2$ symbol errors.
They are particularly effective against burst errors, since a burst corrupting one multi-bit symbol counts as a single error.
ECC can be defined over binary extension fields $GF(2^n)$, using curves of the form:
$y^2 + xy = x^3 + ax^2 + b$
where $a, b \in GF(2^n)$. Binary field ECC was historically favoured in hardware because:
NIST binary curves: B-233, B-283, B-409, B-571.
Brendan Lynskey 2025