Finite Fields (GF(p) & GF(2^n))

A field is a set where you can add, subtract, multiply, and divide by anything nonzero, with all the usual laws holding. The rationals and reals are infinite fields; what makes finite ones indispensable to computing is that a finite field lets you do exact, reversible arithmetic on fixed-width machine words with no rounding and no overflow — which is why AES, Reed–Solomon, CRCs, secret sharing and erasure coding all quietly live inside one.

The problem: mod a composite is not a field #

Arithmetic mod $n$ always gives you a ring — add, subtract, multiply freely. Division is where it breaks. $a$ has a multiplicative inverse mod $n$ only when $\gcd(a, n) = 1$ , so mod a composite, some elements simply cannot be divided by, and "divide" silently becomes a many-to-one map.

Two repairs give a genuine field:

$GF(p)$ , $p$ prime: integers mod a prime. Every nonzero element is coprime to $p$ , so every one has an inverse (find it with the extended Euclidean algorithm). Simple, but the size is a prime — an awkward fit for byte-oriented hardware.
$GF(p^n)$ : elements are polynomials of degree $< n$ with coefficients in $GF(p)$ , multiplied modulo an irreducible polynomial of degree $n$ . Irreducibility plays exactly the role primality did: it guarantees no zero divisors, hence inverses for all nonzero elements. Every finite field has order $p^n$ for some prime $p$ , and all fields of the same order are isomorphic — so "the" field $GF(2^8)$ is well-defined.

GF(2^n) is the one hardware likes #

Take $p = 2$ : coefficients are bits, a polynomial of degree $< n$ is an $n$ -bit word, and addition of coefficients mod 2 is XOR. So in $GF(2^n)$ :

addition = subtraction = XOR (no carries, no borrows, its own inverse)
multiplication = carry-less polynomial multiply, then reduce mod the irreducible polynomial (shift and conditional XOR)

$GF(2^8)$ has exactly 256 elements, one per byte. That is not a coincidence in AES; it is the reason for the design.

$GF(2^3)$ with $P(x) = x^3 + x + 1$

Eight elements, three bits each. Because the field is finite, the nonzero elements form a cyclic group of order $2^3 - 1 = 7$ under multiplication: every one is a power of a generator $\alpha = x$ (binary 010). Verified by direct computation:

Power	Polynomial	Vector
$\alpha^0$	$1$	`001`
$\alpha^1$	$x$	`010`
$\alpha^2$	$x^2$	`100`
$\alpha^3$	$x + 1$	`011`
$\alpha^4$	$x^2 + x$	`110`
$\alpha^5$	$x^2 + x + 1$	`111`
$\alpha^6$	$x^2 + 1$	`101`

$\alpha^3$ is where the modulus bites: $x \cdot x^2 = x^3$ , which overflows, so reduce — $x^3 \equiv x + 1 \pmod{x^3+x+1}$ . Then $\alpha^7 = 1$ and it wraps.

The two representations are the classic implementation trick: vector form for addition (one XOR), power form for multiplication (add exponents mod 7, i.e. log/antilog table lookup). Software $GF(2^8)$ implementations still ship exactly this pair of 256-byte tables.

Where this shows up #

System	Field	What the field does
AES S-box	$GF(2^8)$ , $x^8+x^4+x^3+x+1$	The S-box is multiplicative inversion in the field, then an affine map — inversion is maximally nonlinear, which is precisely the property a cipher wants
AES MixColumns	same	Each column is a degree-3 polynomial multiplied by a fixed $c(x) = 3x^3+x^2+x+2$ mod $x^4+1$ ; invertible, so decryption works
Reed–Solomon	$GF(2^8)$ / $GF(2^{16})$	Data is polynomial coefficients; evaluation at distinct points gives redundancy. Any $k$ of $n$ symbols reconstruct via Lagrange interpolation — QR codes, CDs, DVB
Erasure coding	$GF(2^8)$	Same math at storage scale: Reed–Solomon(6,3) in HDFS/Ceph/Azure gives 3-failure tolerance at 1.5× overhead instead of 3× replication
CRC	$GF(2)[x]$	Remainder of the message polynomial mod a generator — a ring computation, and why CRC detects burst errors but is not a MAC
Shamir secret sharing	$GF(p)$ or $GF(2^8)$	A secret is a polynomial's constant term; $k$ shares determine it, $k-1$ reveal nothing
AES-GCM authentication	$GF(2^{128})$	GHASH is polynomial evaluation in the field — and its linearity is exactly why nonce reuse leaks the auth key

Source claims audit #

The $GF(2^3)$ table and the mod-128 ambiguity argument were seeded from a university lab manual (polynomial-cipher lab); the applications come from primary specs.

Claim from source	Status	Notes
"Operations mod a prime number don't work — ambiguity on division"	needs correction	The reasoning is right but the wording is wrong: the source's own counterexample uses mod 128, a composite. Mod a prime is a perfectly good field. The real requirement is prime or prime-power modulus
Worked ambiguity example $(25\cdot6) \bmod 128 = 22$	current	Recomputed; $\gcd(6,128)=2$ is the actual cause
$GF(2^3)$ vector/power table with $P(x)=x^3+x+1$	current	Recomputed independently; matches
Source's "polynomial cipher" (multiply message by a fixed polynomial)	outdated — not a cipher	Multiplication by a known fixed polynomial is trivially invertible by anyone; there is no secret. Useful as field arithmetic practice, not as cryptography — kept the math, dropped the framing
"Cyclic method has high cryptographic strength vs Caesar etc."	outdated	False as stated; see above

The problem: mod a composite is not a field #

GF(2^n) is the one hardware likes #

Where this shows up #

Source claims audit #

Related

Sources