Galois Theory

AES encryption works in Galois field GF(2^8) , 256 elements. Every byte is a field element, S-box operations are multiplicative inverses. Galois theory is the mathematics behind every HTTPS handshake and behind the proof that no general quintic formula can exist.

• **AES-128/256:** GF(2^8) underpins ShiftRows, MixColumns, and SubBytes , three of AES's four core operations are defined algebraically over Galois fields
• **Abel-Ruffini theorem:** degree-5 and higher equations are not solvable by radicals , proved through the non-solvability of S₅ in 1824
• **Error-correcting codes:** Reed-Solomon codes (QR codes, CDs, RAID-6) operate over GF(2^m) , Galois theory behind every QR code one scan

Предварительные знания

• Linear Algebra in Interviews

Field Extensions

AES encryption works in Galois field GF(2^8) , 256 elements. Every byte is a field element, S-box operations are multiplicative inverses. GF(2^8) = GF(2)[x]/(x^8+x^4+x^3+x+1) is an extension of GF(2) by an irreducible polynomial of degree 8. The extension degree [GF(2^8):GF(2)] = 8.

Interview shortcut: [ℚ(α):ℚ] = degree of the minimal polynomial of α. For ∛2 that is 3, for ∜2 it is 4, for √2+√3 it is 4 (since [ℚ(√2,√3):ℚ] = 2·2 = 4 by the tower law).

The Galois Group

The Galois group Gal(L/K) is the group of all field automorphisms of L that fix K pointwise. For ℚ(√2)/ℚ: any automorphism σ is determined by its image of √2, which must be another root of x²−2, either +√2 or −√2. So Gal(ℚ(√2)/ℚ) = {id, σ} ≅ ℤ/2ℤ. For Galois extensions, |Gal(L/K)| = [L:K].

**Tower law:** for K ⊂ F ⊂ L: [L:K] = [L:F]·[F:K]. This lets one compute degrees of composite extensions: [ℚ(√2,√3):ℚ] = [ℚ(√2,√3):ℚ(√2)]·[ℚ(√2):ℚ] = 2·2 = 4.

The Fundamental Theorem of Galois Theory

The fundamental theorem establishes a bijection: intermediate fields K ⊂ F ⊂ L correspond exactly to subgroups H ≤ Gal(L/K). This correspondence allowed Galois to prove the unsolvability of the general quintic by radicals: its Galois group is S₅, which is not a solvable group.

**Abel-Ruffini theorem (1824):** the general polynomial of degree n ≥ 5 is not solvable by radicals. Proof: the Galois group of the general degree-n polynomial is Sₙ. For n ≥ 5, Sₙ is not solvable (its derived series does not terminate at {e}).

Key Ideas

• **Field extensions:** [L:K] = dim_K L; degree = deg(minimal polynomial); tower law: [L:K] = [L:F]·[F:K]
• **Galois group:** Gal(L/K) = automorphisms of L fixing K; |Gal(L/K)| = [L:K] for Galois extensions
• **Fundamental theorem:** bijection between intermediate fields and subgroups of Gal(L/K); normal subgroups correspond to normal extensions
• **Quintic unsolvability:** solvable by radicals iff Gal(p) is solvable; S₅ is not solvable, so there is no general quintic formula

Related Topics

Galois theory synthesizes algebra and group theory:

• Group theory — Galois groups are concrete groups; solvable groups determine equation solvability
• Ring theory — Polynomial rings K[x] and quotient rings K[x]/(p(x)) are the main tool for constructing field extensions

Вопросы для размышления

• GF(2^8) = GF(2)[x]/(x^8+x^4+x^3+x+1). Why was this specific irreducible polynomial chosen for AES rather than any other irreducible degree-8 polynomial over GF(2)?
• The group Gal(ℚ(∜2,i)/ℚ) ≅ D₄ (dihedral, order 8). How many intermediate fields exist between ℚ and ℚ(∜2,i)?
• The polynomial x⁵−x−1 has Galois group S₅. How does this imply its roots cannot be expressed by radicals, even though all roots are real?