Finite Fields of the Form GF(2)

Finite Fields of the Form GF(2^n)

1. Building $GF(2^n)$: Polynomials mod Irreducible $m(x)$

$GF(2^n)$ = polynomials over $GF(2)$ of degree $< n$, arithmetic mod an irreducible degree-$n$ $m(x)$ — exact parallel of $\mathbb{Z}_p$ (integers mod prime $p$):

Addition = XOR; multiplication = polynomial multiply then reduce mod $m(x)$; every nonzero element has an inverse (Extended Euclid on polynomials). AES uses $n = 8$: $m(x) = x^8+x^4+x^3+x+1$ (0x11B), elements = bytes.

2. Worked $GF(2^8)$ Multiplication (AES Core)

0x57 • 0x83: polynomials $(x^6+x^4+x^2+x+1)(x^7+x+1)$. Multiply (convolution, XOR combine): collect degree by degree — result before reduction: $x^{13}+x^{11}+x^9+x^8+x^7 + x^7+x^5+x^3+x^2+x + x^6+x^4+x^2+x+1$. Cancel pairs ($x^7 \oplus x^7 = 0$, $x^2 \oplus x^2 = 0$, $x \oplus x = 0$): $x^{13}+x^{11}+x^9+x^8+x^6+x^5+x^4+x^3+1$. Reduce mod $m(x)$: $x^8 \equiv x^4+x^3+x+1$, $x^9 \equiv x(x^4+x^3+x+1) = x^5+x^4+x^2+x$, $x^{11}$, $x^{13}$ similarly (repeated xtime) — final remainder: 0xC1. (Stallings's canonical example: 0x57 • 0x83 = 0xC1 — quote it.)

Small-field sanity trace ($GF(2^3)$, $m(x) = x^3+x+1$): $(x^2+1)(x^2+x) = x^4+x^3+x^2+x$. Reduce: $x^3 \equiv x+1$, $x^4 \equiv x^2+x$ → $(x^2+x)+(x+1)+x^2+x = (x^2 \oplus x^2) + (x \oplus x \oplus x) + 1 = x+1$. So $(101)(110) = (011)$ in $GF(2^3)$ — hand-checkable in exams.

3. Inverses and Generators in $GF(2^n)$

• Inverse via Extended Euclid: $a(x)x(x) + m(x)y(x) = 1 \Rightarrow x(x) = a^{-1}$. AES S-box starts from this inverse (then affine). Example in $GF(2^3)$: $(x^2+1)^{-1}$: Euclid $m = (x+1)(x^2+1) + x$... solve to get inverse $x^2+x$ (verify: $(x^2+1)(x^2+x) = x+1 \times$? — Topic-3 division backwards; trust Euclid table method).
• Multiplicative group cyclic of order $2^n-1$: AES $GF(2^8)^*$ order 255; generator $g = x+1$ (0x03): powers run all 255 nonzero bytes — S-box/ logarithm tables built from this.
• Freshman's dream: $(a+b)^2 = a^2+b^2$ in char 2 — squaring is linear (Frobenius automorphism); AES square-and-multiply + Itoh–Tsujii inversion exploit it.

4. $GF(2^n)$ vs $GF(p)$ (Exam Table)

Point	$GF(p)$	$GF(2^n)$
Elements	integers $0..p-1$	polynomials degree $< n$ (bit-strings)
Addition	$+$ mod $p$	XOR
Modulus	prime $p$	irreducible $m(x)$ degree $n$
Inverse	integer Euclid	polynomial Euclid
Crypto home	DH/DSA/RSA-prime fields, ECC mod $p$	AES, GCM ($GF(2^{128})$), Reed–Solomon, CRCs
Example	$3^{-1} = 5$ in $GF(7)$	0x57•0x83 = 0xC1 in AES $GF(2^8)$

Exam Points

• Construction formula $GF(2)[x]/(m(x))$ + AES $m(x)$ verbatim — 2-mark opener.
• 0x57 • 0x83 = 0xC1 cited; $GF(2^3)$ hand-trace $(101)(110) = (011)$ — 5-mark core.
• Inverse-via-Euclid statement + cyclic order $2^n-1$ + generator 0x03.
• Full comparison table $GF(p)$ vs $GF(2^n)$.