03b-extension-fields-gf2n.ipynb

Kernel: SageMath 10.5

Extension Fields: GF($2^n$)

Module 03b | Galois Fields and AES

Building larger fields from GF(2) using irreducible polynomials.

Question: GF(2) has only two elements, not enough to represent a byte (256 values). We need a field with exactly 256 elements. But there's no prime equal to 256. So how do you build a field whose size is a power of a prime?

The answer: take the polynomial ring GF(2)$[x]$ from notebook 03a, pick an irreducible polynomial of degree $n$, and quotient. The result is GF($2^n$), a field with $2^n$ elements. This is the same construction you saw in Module 02 for quotient rings, but now applied to binary polynomials.

Objectives

By the end of this notebook you will be able to:

1. Explain why GF(2)$[x]$ is not a field and what we need to fix

2. Identify irreducible polynomials over GF(2) and explain their role

3. Construct GF($2^n$) as a quotient ring GF(2)$[x]/(p(x))$

4. Perform addition and multiplication in GF($2^n$)

5. Find multiplicative inverses in GF($2^n$)

Bridge from 03a

In 03a you saw that GF(2) polynomials correspond to bit-strings: addition is XOR, and multiplication produces higher-degree polynomials. But GF(2)$[x]$ is a ring, not a field, polynomials of degree $\geq 1$ have no multiplicative inverse.

In Module 02 (notebook 02f) you learned the fix: quotient by an irreducible polynomial. This is exactly how we build GF($2^n$).

$$\text{GF}(2^n) = \text{GF}(2)[x]\,/\,(p(x))$$

where $p(x)$ is irreducible of degree $n$. Elements are polynomials of degree $< n$, and multiplication is done modulo $p(x)$.

Why GF(2)$[x]$ Is Not a Field

Let's see the problem concretely:

# GF(2)[x] is a ring, not a field
R.<x> = GF(2)[]
print(f'Ring: {R}')
print(f'Is a field? {R in Fields()}')
print()

# The problem: polynomials of degree >= 1 have no multiplicative inverse
p = x + 1
print(f'p = {p}')
print(f'Can we find q such that p * q = 1?')
print(f'  p * 1 = {p * R(1)}  (degree 1, not 1)')
print(f'  p * x = {p * x}  (degree 2, even worse)')
print()
print('No polynomial in GF(2)[x] is the inverse of (x+1).')
print('The ring has infinitely many elements but most lack inverses.')
print()
print('Fix: quotient by an irreducible polynomial to force degree < n.')

Irreducible Polynomials over GF(2)

A polynomial $p(x) \in \text{GF}(2)[x]$ is irreducible if it cannot be factored into lower-degree polynomials over GF(2). This is the polynomial analogue of a prime number.

Checkpoint: Is $x^2 + 1$ irreducible over GF(2)? Before running the next cell, try to factor it. Hint: in GF(2), $1 + 1 = 0$, so $x^2 + 1 = x^2 - 1 = ?$

# Irreducible polynomials over GF(2)
R.<x> = GF(2)[]

# x^2 + 1 over GF(2): is it irreducible?
p = x^2 + 1
print(f'{p} = {p.factor()}')
print(f'Irreducible? {p.is_irreducible()}')
print(f'Because in GF(2): x^2 + 1 = (x+1)^2  (since -1 = 1)')
print()

# x^2 + x + 1 over GF(2): is it irreducible?
q = x^2 + x + 1
print(f'{q} = {q.factor()}')
print(f'Irreducible? {q.is_irreducible()}')
print(f'Check: q(0) = {q(GF(2)(0))}, q(1) = {q(GF(2)(1))} , no roots in GF(2)!')
print()

# List all irreducible polynomials of small degree
for d in range(2, 6):
    irreds = [f for f in R.polynomials(of_degree=d) if f.is_irreducible()]
    print(f'Degree {d}: {len(irreds)} irreducible polynomials: {irreds}')

Key observations:

• $x^2 + 1 = (x+1)^2$ over GF(2), reducible (because $-1 = 1$ in characteristic 2)

• $x^2 + x + 1$ is the only irreducible quadratic over GF(2)

• The number of irreducible polynomials grows with degree, there are always enough to build extension fields

Building GF($2^2$): A Tiny Example

Let's build the smallest non-trivial binary extension field: GF(4) = GF($2^2$).

# GF(4) = GF(2)[x] / (x^2 + x + 1)
F.<a> = GF(2^2)
print(f'Field: {F}')
print(f'Modulus (irreducible polynomial): {F.modulus()}')
print(f'Number of elements: {F.order()}')
print(f'Is a field? {F in Fields()}')
print()

# List all 4 elements
print('All elements of GF(4):')
for elem in F:
    print(f'  {elem}  (as polynomial: {elem.polynomial()})')

print()
print('Elements are polynomials of degree < 2 with GF(2) coefficients:')
print('  0, 1, a, a+1  (where a is a root of x^2 + x + 1)')

GF(4) has exactly 4 elements: $\{0, 1, a, a+1\}$, where $a$ satisfies $a^2 + a + 1 = 0$, i.e., $a^2 = a + 1$.

Addition in GF($2^n$)

Addition is polynomial addition with GF(2) coefficients, which is just XOR of coefficients. No reduction needed because adding polynomials of degree $< n$ gives a polynomial of degree $< n$.

# Addition table for GF(4)
F.<a> = GF(2^2)
elems = list(F)

print('Addition table for GF(4):')
print('', end='')for b in elems:
    print(f'{str(b)}', end='')
print()
for x in elems:
    print(f'{str(x)}', end='')
    for y in elems:
        print(f'{str(x+y)}', end='')
    print()

print()
print('Notice: every element is its own additive inverse (a + a = 0).')
print('This is characteristic 2, same as GF(2), but now with 4 elements.')

Multiplication in GF($2^n$)

Multiplication is polynomial multiplication reduced modulo the irreducible polynomial. This is where the quotient ring structure matters, without reduction, the degree would grow beyond $n-1$.

Checkpoint: In GF(4), compute $a \times a$ by hand. You get $a^2$, but $a^2 + a + 1 = 0$ means $a^2 = a + 1$. Verify with SageMath:

# Multiplication in GF(4): polynomial multiplication mod (x^2 + x + 1)
F.<a> = GF(2^2)

print('Key relation: a^2 + a + 1 = 0, so a^2 = a + 1')
print(f'a * a = a^2 = {a * a}  (= a + 1, as expected)')
print()

# Full multiplication table
elems = list(F)
print('Multiplication table for GF(4):')
print('', end='')for b in elems:
    print(f'{str(b)}', end='')
print()
for x in elems:
    print(f'{str(x)}', end='')
    for y in elems:
        print(f'{str(x*y)}', end='')
    print()

print()
print('Every nonzero element has a multiplicative inverse:')
for x in elems:
    if x != 0:
        print(f'  {x}^(-1) = {x^(-1)}  (check: {x} * {x^(-1)} = {x * x^(-1)})')

Every nonzero element has an inverse, this is what makes GF(4) a field, not just a ring. The irreducible polynomial is what guarantees this.

What Happens with a Reducible Polynomial?

Common mistake: "Any degree-$n$ polynomial works for building GF($2^n$)." No! If you quotient by a reducible polynomial, you get a ring with zero divisors, not a field. The polynomial MUST be irreducible.

# What goes wrong with a reducible polynomial?
R.<x> = GF(2)[]

# x^2 + 1 = (x+1)^2 is REDUCIBLE over GF(2)
bad_mod = x^2 + 1
Q = R.quotient(bad_mod, 'b')
b = Q.gen()

print(f'Quotient ring: GF(2)[x] / ({bad_mod})')
print(f'Generator: b (satisfying b^2 + 1 = 0, i.e., b^2 = 1)')
print()

# b^2 = 1 means (b+1)^2 = b^2 + 1 = 1 + 1 = 0
print(f'(b + 1)^2 = {(b + Q(1))^2}')
print(f'So (b+1) * (b+1) = 0, but b+1 ≠ 0!')
print(f'This means b+1 is a ZERO DIVISOR, this is NOT a field.')
print()

# Compare with the irreducible x^2 + x + 1
good_mod = x^2 + x + 1
print(f'{good_mod} is irreducible? {good_mod.is_irreducible()}')
print(f'{bad_mod} is irreducible? {bad_mod.is_irreducible()}')
print()
print('Lesson: ONLY irreducible polynomials produce fields.')

Scaling Up: GF($2^4$)

GF(4) is tiny. Let's build GF($2^4$) = GF(16) to see the pattern at a more interesting size.

# GF(16) = GF(2^4)
F.<a> = GF(2^4)
print(f'Field: {F}')
print(f'Modulus: {F.modulus()}')
print(f'Elements: {F.order()}')
print()

# All 16 elements as polynomials in a
print('All elements (as polynomials of degree < 4):')
for i, elem in enumerate(F):
    bits = ''.join(str(int(elem.polynomial()[j])) for j in range(3, -1, -1))
    print(f'  {i:2d}: {str(elem)}  bits: {bits}')

print()
print(f'Each element is a polynomial a3*a^3 + a2*a^2 + a1*a + a0')
print(f'with coefficients in GF(2). That is 4 bits = one nibble.')

# Arithmetic in GF(16)
F.<a> = GF(2^4)

x = a^3 + a + 1       # bits: 1011
y = a^2 + a            # bits: 0110

print(f'x = {x}')
print(f'y = {y}')
print()

# Addition = XOR of coefficients
print(f'x + y = {x + y}   (XOR of bit patterns: 1011 XOR 0110 = 1101)')
print()

# Multiplication = polynomial multiply then reduce mod modulus
product = x * y
print(f'x * y = {product}')
print(f'  (multiply polynomials, then reduce mod {F.modulus()})')
print()

# Inverse
print(f'x^(-1) = {x^(-1)}')
print(f'Check: x * x^(-1) = {x * x^(-1)}')
print()

# Powers of a generate the entire multiplicative group
print('Powers of a (the generator):')
for i in range(16):
    print(f'  a^{i:2d} = {a^i}')
print(f'a^15 = {a^15} (back to 1, the multiplicative group has order 15)')

Checkpoint: In GF($2^4$), $a$ is a generator of the multiplicative group (order 15). Is every nonzero element a power of $a$? Count the distinct values in the power table above. You should see all 15 nonzero elements.

The Choice of Irreducible Polynomial

Different irreducible polynomials of the same degree give isomorphic fields, same structure, different representation. But the choice matters for implementation efficiency.

# Different irreducible polynomials for GF(2^4)
R.<x> = GF(2)[]

irreds = [f for f in R.polynomials(of_degree=4) if f.is_irreducible()]
print(f'There are {len(irreds)} irreducible polynomials of degree 4 over GF(2):')
for p in irreds:
    print(f'  {p}')
print()

# Build GF(16) with two different moduli and show they're isomorphic
F1.<a> = GF(2^4, modulus=irreds[0])
F2.<b> = GF(2^4, modulus=irreds[1])

print(f'F1 uses modulus {F1.modulus()}')
print(f'F2 uses modulus {F2.modulus()}')
print(f'Both have {F1.order()} elements and are fields.')
print(f'They are isomorphic: same algebraic structure, different polynomial basis.')
print()
print('For AES, the specific choice is x^8 + x^4 + x^3 + x + 1 (notebook 03c).')

The Construction, Summarized

Here is the recipe for GF($2^n$):

1. Start with the polynomial ring GF(2)$[x]$

2. Choose an irreducible polynomial $p(x)$ of degree $n$

3. Form the quotient: GF($2^n$) = GF(2)$[x]\,/\,(p(x))$

4. Elements are polynomials of degree $< n$ (equivalently, $n$-bit strings)

5. Addition = polynomial addition = XOR of bit-strings

6. Multiplication = polynomial multiplication mod $p(x)$

7. Every nonzero element has a multiplicative inverse (because $p(x)$ is irreducible)

$$\boxed{\text{GF}(2^n) = \text{GF}(2)[x]\,/\,(p(x)) \quad\text{where } p(x) \text{ is irreducible of degree } n}$$

Exercises

Exercise 1 (Worked)

In GF($2^3$) with modulus $x^3 + x + 1$, compute $(x^2 + 1) \times (x + 1)$ by hand, then verify with SageMath.

# Exercise 1 (Worked), Multiplication in GF(8)
R.<x> = GF(2)[]
mod = x^3 + x + 1
print(f'Modulus: {mod}  (irreducible? {mod.is_irreducible()})')
print()

# Step 1: Polynomial multiplication (ignoring mod)
a = x^2 + 1
b = x + 1
product = a * b
print(f'({a}) * ({b}) = {product}')
print(f'  x^2*x + x^2*1 + 1*x + 1*1 = x^3 + x^2 + x + 1')
print()

# Step 2: Reduce mod (x^3 + x + 1)
# x^3 = x + 1 (from x^3 + x + 1 = 0)
# So x^3 + x^2 + x + 1 = (x+1) + x^2 + x + 1 = x^2 + 2x + 2 = x^2 (in GF(2)!)
remainder = product % mod
print(f'Reduce mod ({mod}):')
print(f'  x^3 = x + 1 (substitute)')
print(f'  (x+1) + x^2 + x + 1 = x^2 (since 2x = 0 and 2 = 0 in GF(2))')
print(f'  Result: {remainder}')
print()

# Verify using GF(8) directly
F.<a> = GF(2^3, modulus=mod)
result = (a^2 + 1) * (a + 1)
print(f'SageMath verification: ({a^2 + 1}) * ({a + 1}) = {result}')

Exercise 2 (Guided)

Find all irreducible polynomials of degree 3 over GF(2). For each one, build GF($2^3$) and verify that the generator $a$ has multiplicative order 7 (= $2^3 - 1$).

# Exercise 2 (Guided), Irreducible cubics and GF(8)
R.<x> = GF(2)[]

# TODO: Find all irreducible polynomials of degree 3
# Hint: [f for f in R.polynomials(of_degree=3) if f.is_irreducible()]
irreds_3 = []  # TODO: fill this in
print(f'Irreducible cubics over GF(2): {irreds_3}')
print()

# TODO: For each irreducible polynomial, build GF(8) and check generator order
for mod in irreds_3:
    # Hint: F.<a> = GF(2^3, modulus=mod)
    # Then check: a.multiplicative_order()
    pass  # TODO: replace with your code

# Question: do you always get order 7? Or does the generator
# sometimes have a smaller order? (Hint: 7 is prime...)

Exercise 3 (Independent)

In GF($2^4$) with SageMath's default modulus:

1. Find the multiplicative inverse of every nonzero element. Verify each satisfies $a \cdot a^{-1} = 1$.

2. Compute the discrete logarithm: for each nonzero element $g$, find $k$ such that $a^k = g$ (where $a$ is the generator). Build a log table.

3. Using your log table, verify that multiplication can be done as: $g \cdot h = a^{(\log_a g + \log_a h) \mod 15}$. This is how hardware implements GF multiplication efficiently!

# Exercise 3 (Independent), Your code here

Summary

Concept	Key idea
GF(2)$[x]$ is not a field	Polynomials of degree $\geq 1$ have no multiplicative inverse in the polynomial ring
Irreducible polynomials	The polynomial analogue of primes. Quotienting by one of degree $n$ produces GF($2^n$), a field with $2^n$ elements
Reducible polynomials fail	Using a reducible polynomial creates zero divisors, not a field
Addition = XOR	Adding polynomials in GF($2^n$) is just XOR of coefficient bit-strings, no reduction needed
Multiplication needs reduction	Multiply the polynomials, then reduce mod $p(x)$ to keep the degree below $n$
Isomorphic fields	Different irreducible polynomials of the same degree give isomorphic fields. The choice affects implementation, not algebra

Crypto foreshadowing: AES uses GF($2^8$) = GF(2)$[x]\,/\,(x^8 + x^4 + x^3 + x + 1)$. In notebook 03c, we build this exact field and do byte-level arithmetic inside it. The S-box, MixColumns, and key schedule all live here.

Next: GF(256) Arithmetic, the specific field that powers AES.