Mathematics.

field theory

Finite Fields

Abstract Algebra II35 minDifficulty7 out of 10

You should know: fields

Overview

A finite field (also called a Galois field, denoted GF(q) or 𝔽_q) is a field with finitely many elements. Évariste Galois showed such fields exist precisely when the number of elements q is a prime power pⁿ, and for each prime power there is exactly one finite field up to isomorphism. Finite fields underlie error-correcting codes (Reed–Solomon codes), the Advanced Encryption Standard (AES uses arithmetic in GF(2⁸)), and elliptic curve cryptography, largely because their multiplicative group is always cyclic, giving predictable, well-understood algebraic structure.

Intuition

𝔽_p = ℤ/pℤ (p prime) is the simplest finite field, but to get pⁿ elements for n>1 you can't just take ℤ/(pⁿ)ℤ — that ring has zero divisors, since pⁿ is not prime. Instead you build 𝔽_{p^n} by adjoining a root of a degree-n irreducible polynomial over 𝔽_p, the same trick used to build ℂ from ℝ. Because the nonzero elements always form a cyclic group under multiplication, every finite field has a 'generator' (a primitive element) whose powers sweep out every nonzero element exactly once — this predictability is exactly why finite fields are the natural setting for coding theory and cryptography.

Formal Definition

Definition

For every prime p and positive integer n, there exists a finite field with pⁿ elements, unique up to isomorphism:

∣Fq∣=pnfor some prime p,n≥1|\mathbb{F}_q| = p^n \quad \text{for some prime } p, n \geq 1
Every finite field has prime-power order
Fpn exists and is unique up to isomorphism for every prime power pn\mathbb{F}_{p^n} \text{ exists and is unique up to isomorphism for every prime power } p^n
Existence and uniqueness
Fpn× is cyclic of order pn−1\mathbb{F}_{p^n}^\times \text{ is cyclic of order } p^n - 1
Multiplicative group is cyclic
Fpn≅Fp[x]/(f(x))for f irreducible of degree n over Fp\mathbb{F}_{p^n} \cong \mathbb{F}_p[x]/(f(x)) \quad \text{for } f \text{ irreducible of degree } n \text{ over } \mathbb{F}_p
Construction via an irreducible polynomial

Worked Examples

  1. Since 7 is prime, every nonzero residue mod 7 is coprime to 7, hence invertible.

    gcd⁡(a,7)=1 for a=1,…,6\gcd(a,7)=1 \text{ for } a=1,\ldots,6

  2. Compute inverses: 1⁻¹=1, 2⁻¹=4 (2×4=8≡1), 3⁻¹=5 (3×5=15≡1), 6⁻¹=6 (6×6=36≡1 mod 7).

    2×4≡1, 3×5≡1, 6×6≡1(mod7)2 \times 4 \equiv 1,\ 3\times5\equiv1,\ 6\times6\equiv1 \pmod 7

Answer: Every nonzero element of ℤ/7ℤ has an inverse (1⁻¹=1, 2⁻¹=4, 3⁻¹=5, 4⁻¹=2, 5⁻¹=3, 6⁻¹=6), confirming it is a field with 7 elements.

Practice Problems

Difficulty 4/10

Why is there no field with exactly 6 elements?

Difficulty 5/10

Find a generator (primitive element) of 𝔽₇* and verify its powers give all 6 nonzero elements.

Difficulty 6/10

AES encryption performs byte arithmetic in GF(2⁸). Why must this be a field rather than just ℤ/256ℤ?

Quiz

A finite field can have exactly n elements if and only if n is:
The multiplicative group 𝔽_q* of a finite field 𝔽_q (order q, q nonzero elements minus one) is always:
To construct 𝔽_{p^n} for n > 1, the standard method is:

Summary

  • Finite fields exist exactly for orders q = pⁿ (p prime), and are unique up to isomorphism for each such q, denoted 𝔽_q or GF(q).
  • 𝔽_{p^n} is built as 𝔽_p[x]/(f(x)) for f irreducible of degree n — not as ℤ/(pⁿ)ℤ, which has zero divisors when n>1.
  • The multiplicative group 𝔽_q* is always cyclic of order q−1, the algebraic backbone of AES, Reed–Solomon codes, and elliptic curve cryptography.

References

  1. WebsiteWikipedia — Finite field