Finite Fields of the Form GF(p)

Finite Fields of the Form GF(p)

1. The Field $\mathbb{Z}_p$ ($p$ Prime)

Residues $\{0, 1, \dots, p-1\}$ with mod-$p$ addition and multiplication form the finite field $GF(p)$: closure, both identities ($0$, $1$), additive inverses ($-a = p - a$), and — because $p$ prime forces $\gcd(a, p) = 1$ for all $a
e 0$ — every nonzero element has a multiplicative inverse via Extended Euclid (Topic 1).

Worked $GF(7)$ tables (exam favourite): addition $3 + 5 = 8 \equiv 1$; multiplication $3 \times 5 = 15 \equiv 1$ → $3^{-1} = 5$, $5^{-1} = 3$. Full inverse row: $1^{-1} = 1$, $2^{-1} = 4$ ($2 \times 4 = 8 \equiv 1$), $3^{-1} = 5$, $4^{-1} = 2$, $5^{-1} = 3$, $6^{-1} = 6$ ($6 \times 6 = 36 \equiv 1$). Note $a^{p-1} \equiv 1$ check: $3^6 = 729 = 104 \times 7 + 1$ ✓ (Fermat preview, Module 5 Topic 2).

2. Why Primality Is Non-Negotiable

$\mathbb{Z}_6$ fails: $2 \times 3 \equiv 0$ (zero divisors), $2, 3, 4$ have no inverses — not a field, just a ring. $\mathbb{Z}_8$ fails on evens. Only prime modulus gives all-nonzero invertibility:

$n$	Units $\mathbb{Z}_n^*$	Field?
6	$\{1, 5\}$ ($\phi = 2$)	✗ (2,3,4 dead)
8	$\{1,3,5,7\}$ ($\phi = 4$)	✗ (evens dead)
7	$\{1..6\}$ ($\phi = 6$)	✓ $GF(7)$
11	$\{1..10\}$ ($\phi = 10$)	✓ $GF(11)$

$\phi(p) = p - 1$ always; composite $n$ loses $\phi(n) < n-1$ elements to non-invertibility.

3. Cyclic Multiplicative Group and Primitive Roots

$GF(p)^*$ is cyclic of order $p-1$: some primitive root $g$ generates all nonzero elements. $GF(7)$: $g = 3$: $3^1..3^6 = 3, 2, 6, 4, 5, 1$ ✓ (all six). Test: $g$ primitive ⟺ $g^{(p-1)/q}
ot\equiv 1$for every prime factor$q$of$p-1$($p = 7$:$p-1 = 6 = 2 \times 3$;$3^{6/2} = 3^3 = 27 \equiv 6
e 1$;$3^{6/3} = 3^2 = 2
e 1$→ primitive ✓). Contrast$g = 2$:$2^3 = 8 \equiv 1$→ order 3, NOT primitive (generates${1,2,4}$ only).

4. $GF(p)$ in Real Cryptography

• Diffie–Hellman/ElGamal/DSA: public parameters $(p, g)$ with $g$ primitive; security = discrete log in $GF(p)^*$ (Module 5 Topic 6). Standard primes: RFC 3526 MODP groups ($p$ = 2048–8192-bit safe primes).
• Elliptic curves mod $p$: curve points use $GF(p)$ coordinates — same field, richer group.
• Schnorr/EdDSA nonce fields: scalars live in prime-order subgroups of $GF(p)^*$.
• Safe-prime choice $p = 2q+1$ ($q$ prime) kills small-subgroup confinement (only subgroups orders $1, 2, q, 2q$).

Exam Points

• $GF(7)$ addition/multiplication traces + full inverse row — standard 5-marker.
• "$\mathbb{Z}_n$ field ⟺ $n$ prime" + $\mathbb{Z}_6$/$\mathbb{Z}_8$ failing elements — 2–3 marks.
• Primitive-root test $g^{(p-1)/q}
  e 1$with$g = 3$vs$g = 2$ mod 7 — favourite numerical.
• DH $(p, g)$ parameter link.