02f-quotient-rings.ipynb

Kernel: SageMath 10.5

Quotient Rings and Field Extensions

Module 02 | 02-rings-fields-polynomials

quotient(), building GF(4) from F_2, the construction behind every finite field in cryptography

Objectives

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

1. Explain the quotient ring construction and why it generalises "mod" from integers to polynomials.

2. Build GF(4) by hand as $\mathbb{F}_2[x]/(x^2+x+1)$ and verify it is a field.

3. Construct complete addition and multiplication tables for small extension fields.

4. Explain why the modulus polynomial must be irreducible to get a field (and what goes wrong if it isn't).

5. State the general pattern: $\text{GF}(p^n) = \mathbb{F}_p[x]/(\text{irreducible of degree } n)$.

6. Recognise $\text{GF}(256)$ as the AES field and connect this notebook to Module 03.

Prerequisites

• Completion of Polynomial Division and Irreducibility, you need quo_rem and is_irreducible().

• Concepts from Integers Mod n as a Ring, zero divisors, units, $\mathbb{Z}/n\mathbb{Z}$.

• Concepts from What Is a Field?, every nonzero element invertible.

Motivating Question

In notebook 02d we saw that $\mathbb{Z}/p\mathbb{Z}$ is a field whenever $p$ is prime. That gives us fields of size 2, 3, 5, 7, 11, 13, ...

But can we build a field with 4 elements? Or 8? Or 256?

There is no prime equal to 4, 8, or 256. So $\mathbb{Z}/n\mathbb{Z}$ cannot help us. We need a fundamentally different construction.

The answer turns out to be: take polynomials and "mod out" by an irreducible polynomial, exactly the way we take integers and mod out by a prime. This is the quotient ring construction, and it is the single most important algebraic idea behind finite fields in cryptography.

The Core Analogy: Integers vs Polynomials

Let's put the two constructions side by side. The parallel is exact.

	Integers	Polynomials
Start with	$\mathbb{Z}$ (all integers)	$\mathbb{F}_2[x]$ (all polynomials over $\mathbb{F}_2$)
Mod out by	$n$ (an integer)	$p(x)$ (a polynomial)
Elements of quotient	Remainders $\{0, 1, \ldots, n-1\}$	Remainder polynomials of degree $< \deg p(x)$
Arithmetic	Add/multiply, then reduce mod $n$	Add/multiply, then reduce mod $p(x)$
Get a field when	$n$ is prime	$p(x)$ is irreducible
Notation	$\mathbb{Z}/n\mathbb{Z}$	$\mathbb{F}_2[x]/(p(x))$

That's it. Same machine, different raw materials.

Bridge from 02b/02e: In 02b you learned that $\mathbb{Z}/12\mathbb{Z}$ has zero divisors because 12 is composite, while $\mathbb{Z}/7\mathbb{Z}$ is a field because 7 is prime. In 02e you learned that some polynomials are irreducible (the polynomial analogue of "prime"). Now we combine these ideas.

Warm-Up: Z/nZ Revisited

Before we touch polynomials, let's remind ourselves how modular arithmetic works for integers. When we compute in $\mathbb{Z}/5\mathbb{Z}$, every integer gets replaced by its remainder after dividing by 5.

# Z/5Z: integers mod 5
# The elements are {0, 1, 2, 3, 4}, remainders when dividing by 5
R = Zmod(5)
print("Elements of Z/5Z:", list(R))
print("3 + 4 =", R(3) + R(4), " (because 7 mod 5 = 2)")
print("3 * 4 =", R(3) * R(4), " (because 12 mod 5 = 2)")
print("Is Z/5Z a field?", R.is_field(), " (5 is prime)")

# Z/4Z: integers mod 4
# NOT a field, 4 is composite, so we get zero divisors
R = Zmod(4)
print("Elements of Z/4Z:", list(R))
print("2 * 2 =", R(2) * R(2), " --> zero divisor!")
print("Is Z/4Z a field?", R.is_field())

Misconception alert: A common mistake is to think "GF(4) = $\mathbb{Z}/4\mathbb{Z}$." This is wrong! $\mathbb{Z}/4\mathbb{Z}$ has zero divisors ($2 \cdot 2 = 0$) and is therefore NOT a field. GF(4) is a completely different algebraic structure that we build from polynomials, not integers. They both have 4 elements, but their arithmetic is entirely different.

So how DO we build a field with 4 elements? By modding out polynomials instead of integers.

Building GF(4) Step by Step

Step 1: Choose the base field and polynomial ring

We work over $\mathbb{F}_2 = \{0, 1\}$, the field with 2 elements. The polynomial ring $\mathbb{F}_2[x]$ contains all polynomials with coefficients in $\{0, 1\}$.

Step 2: Choose an irreducible polynomial of degree 2

From notebook 02e, we know that $x^2 + x + 1$ is irreducible over $\mathbb{F}_2$. (It has no roots: plugging in 0 gives 1, plugging in 1 gives 1. No root means no linear factor means irreducible for degree 2.)

Step 3: Form the quotient

$$\text{GF}(4) = \mathbb{F}_2[x] / (x^2 + x + 1)$$

The elements are all remainders when dividing by $x^2 + x + 1$. Since the divisor has degree 2, all remainders have degree $< 2$. Over $\mathbb{F}_2$, the possible remainders are:

$$\{0,\; 1,\; x,\; x + 1\}$$

That's 4 elements, exactly what we wanted!

# Step 1: Polynomial ring over F_2
R.<x> = PolynomialRing(GF(2))

# Step 2: Verify our modulus is irreducible
p = x^2 + x + 1
print(f"p(x) = {p}")
print(f"p(0) = {p(0)}, p(1) = {p(1)}  --> no roots in F_2")
print(f"Irreducible? {p.is_irreducible()}")

# Step 3: Build the quotient ring
S.<a> = R.quotient(p)
print(f"\nQuotient ring: {S}")
print(f"Elements: {list(S)}")
print(f"Number of elements: {len(list(S))}")

The element a in the quotient ring plays the role of $x$, but now it satisfies $a^2 + a + 1 = 0$, which means $a^2 = a + 1$ (over $\mathbb{F}_2$, subtraction is the same as addition).

This is exactly like how in $\mathbb{Z}/5\mathbb{Z}$ the number 7 "becomes" 2 because $7 \equiv 2 \pmod{5}$. Here, $x^2$ "becomes" $x + 1$ because $x^2 \equiv x + 1 \pmod{x^2 + x + 1}$.

Addition Table for GF(4)

Addition in $\mathbb{F}_2[x]/(x^2+x+1)$ is just polynomial addition with coefficients mod 2. Since $1 + 1 = 0$ in $\mathbb{F}_2$, this is essentially XOR on the coefficient vectors.

# Complete addition table for GF(4)
R.<x> = PolynomialRing(GF(2))
S.<a> = R.quotient(x^2 + x + 1)
elements = list(S)

print("Addition table for GF(4):")
print("─" * 40)
header = "  +   | " + " | ".join(f"{e}" for e in elements)
print(header)
print("─" * 40)
for a_elem in elements:
    row = f"{a_elem}  | " + " | ".join(f"{a_elem + b_elem}" for b_elem in elements)
    print(row)

print("\nNotice: every element is its own additive inverse (a + a = 0).")
print("This is because we're working over F_2 where 1+1=0.")

Checkpoint: Predict Before You Compute

Before running the next cell, predict: what is $a \cdot a$ in GF(4)?

Think about it: $a$ represents $x$ in the quotient. So $a \cdot a = a^2$. But in our quotient ring, $a^2 + a + 1 = 0$, so $a^2 = -(a + 1) = a + 1$ (since $-1 = 1$ in $\mathbb{F}_2$).

Your prediction: $a \cdot a =$ ?

Now run the cell to check.

# Complete multiplication table for GF(4)
R.<x> = PolynomialRing(GF(2))
S.<a> = R.quotient(x^2 + x + 1)
elements = list(S)

print("Multiplication table for GF(4):")
print("─" * 40)
header = "  *   | " + " | ".join(f"{e}" for e in elements)
print(header)
print("─" * 40)
for a_elem in elements:
    row = f"{a_elem}  | " + " | ".join(f"{a_elem * b_elem}" for b_elem in elements)
    print(row)

print(f"\nCheck: a * a = {S(a * a)}  (this is a + 1, because a^2 = a + 1 in our quotient)")

Let's trace one multiplication by hand to make sure we understand the mechanics.

Example: Compute $a \cdot (a + 1)$ in GF(4).

1. Multiply as polynomials: $x \cdot (x + 1) = x^2 + x$

2. Reduce mod $x^2 + x + 1$: divide $x^2 + x$ by $x^2 + x + 1$:

   • $x^2 + x = 1 \cdot (x^2 + x + 1) + 1$ (remainder is 1, since $(x^2 + x) - (x^2 + x + 1) = -1 = 1$ in $\mathbb{F}_2$)

3. Result: $a \cdot (a + 1) = 1$

This means $a$ and $a + 1$ are multiplicative inverses of each other!

# Verify the hand calculation
R.<x> = PolynomialRing(GF(2))
S.<a> = R.quotient(x^2 + x + 1)

print("Hand calculation: a * (a+1)")
print(f"  Step 1 (polynomial multiply): x * (x+1) = {R(x) * R(x + 1)}")
q, r = (R(x) * R(x + 1)).quo_rem(x^2 + x + 1)
print(f"  Step 2 (divide by x^2+x+1):  quotient = {q}, remainder = {r}")
print(f"  Step 3 (result): a * (a+1) = {a * (a + 1)}")
print(f"\nSo a^(-1) = a+1 and (a+1)^(-1) = a.")
print(f"And of course 1^(-1) = 1.")

Verifying: It's Really a Field!

A ring is a field if and only if every nonzero element has a multiplicative inverse. Let's check all three nonzero elements of GF(4).

# Verify every nonzero element has a multiplicative inverse
R.<x> = PolynomialRing(GF(2))
S.<a> = R.quotient(x^2 + x + 1)

print("Inverses in GF(4):")
for elem in S:
    if elem != S.zero():
        inv = elem^(-1)
        print(f"  {elem}^(-1) = {inv}   (check: {elem} * {inv} = {elem * inv})")

print(f"\nIs GF(4) a field? {S.is_field()}")
print("\nEvery nonzero element is invertible. No zero divisors. It's a field!")

Why Irreducibility Matters

What happens if we mod out by a polynomial that is not irreducible? Let's try $x^2 + 1$ over $\mathbb{F}_2$. Note that $x^2 + 1 = (x+1)^2$ in $\mathbb{F}_2[x]$ (since $-1 = 1$), so it factors.

This is exactly analogous to forming $\mathbb{Z}/4\mathbb{Z}$ instead of $\mathbb{Z}/5\mathbb{Z}$: modding out by something composite gives zero divisors.

# What goes wrong with a REDUCIBLE polynomial?
R.<x> = PolynomialRing(GF(2))

# x^2 + 1 = (x + 1)^2 over F_2. NOT irreducible!
bad_poly = x^2 + 1
print(f"Is x^2 + 1 irreducible over F_2? {bad_poly.is_irreducible()}")
print(f"Factorization: {bad_poly.factor()}")

# Build the quotient ring anyway
T.<b> = R.quotient(bad_poly)
print(f"\nElements: {list(T)}")

# Look for zero divisors: (x+1) is a factor, so (b+1) should be a zero divisor
print(f"\n(b + 1) * (b + 1) = {(b + 1) * (b + 1)}")
print("Zero divisor found! (b+1) != 0 but (b+1)^2 = 0")
print(f"\nIs this a field? {T.is_field()}")
print("\nReducible modulus --> zero divisors --> NOT a field.")
print("Just like: composite modulus in Z/nZ --> zero divisors --> NOT a field.")

The pattern is now clear:

Construction	Condition for field	Failure mode
$\mathbb{Z}/n\mathbb{Z}$	$n$ is prime	Composite $n$ $\Rightarrow$ zero divisors
$\mathbb{F}_p[x]/(f(x))$	$f(x)$ is irreducible	Reducible $f(x)$ $\Rightarrow$ zero divisors

Irreducible polynomials are to polynomial rings what primes are to integers.

Scaling Up: Building GF(8)

Now that we understand the construction, let's build a bigger field. To get $\text{GF}(8) = \text{GF}(2^3)$, we need an irreducible polynomial of degree 3 over $\mathbb{F}_2$.

From 02e, we know $x^3 + x + 1$ is irreducible over $\mathbb{F}_2$. So:

$$\text{GF}(8) = \mathbb{F}_2[x]/(x^3 + x + 1)$$

The elements are all polynomials of degree $< 3$ over $\mathbb{F}_2$: that's $2^3 = 8$ elements.

# Build GF(8) = F_2[x] / (x^3 + x + 1)
R.<x> = PolynomialRing(GF(2))
p = x^3 + x + 1
print(f"Modulus: {p}")
print(f"Irreducible? {p.is_irreducible()}")

S.<a> = R.quotient(p)
elems = list(S)
print(f"\nGF(8) has {len(elems)} elements:")
for e in elems:
    print(f"  {e}")

print(f"\nThe key relation: a^3 = a + 1 (from a^3 + a + 1 = 0)")
print(f"Verify: a^3 = {a^3}")

# Multiplication table for GF(8), now 8x8
R.<x> = PolynomialRing(GF(2))
S.<a> = R.quotient(x^3 + x + 1)
elems = list(S)

print("Multiplication table for GF(8) (nonzero elements only):")
print("─" * 80)
nz = [e for e in elems if e != S.zero()]
header = "    *    | " + " | ".join(f"{str(e)}" for e in nz)
print(header)
print("─" * 80)
for a_elem in nz:
    row = f"{str(a_elem)}  | " + " | ".join(f"{str(a_elem * b_elem)}" for b_elem in nz)
    print(row)

# Verify every nonzero element of GF(8) has an inverse
R.<x> = PolynomialRing(GF(2))
S.<a> = R.quotient(x^3 + x + 1)

print("Inverses in GF(8):")
for elem in S:
    if elem != S.zero():
        inv = elem^(-1)
        print(f"  ({elem})^(-1) = {inv}   check: {elem} * {inv} = {elem * inv}")

print(f"\nIs GF(8) a field? {S.is_field()}")

The General Pattern

We can now state the fundamental theorem that underlies all of finite field cryptography:

Theorem. For every prime $p$ and positive integer $n$, there exists a unique field with $p^n$ elements (up to isomorphism). It can be constructed as: $$\text{GF}(p^n) = \mathbb{F}_p[x] / (f(x))$$ where $f(x)$ is any irreducible polynomial of degree $n$ over $\mathbb{F}_p$.

Different irreducible polynomials give the same field (up to relabelling elements), though the specific representation of elements differs. The choice of irreducible polynomial is like choosing a basis.

# SageMath's GF() command does this construction automatically
# GF(p^n) picks an irreducible polynomial for you

# GF(4) using SageMath's built-in
K.<a> = GF(4)
print("GF(4) built by SageMath:")
print(f"  Modulus used: {K.modulus()}")
print(f"  Elements: {list(K)}")
print(f"  a^2 = {a^2}")

print()

# GF(8) using SageMath's built-in
L.<b> = GF(8)
print("GF(8) built by SageMath:")
print(f"  Modulus used: {L.modulus()}")
print(f"  Elements: {list(L)}")

print()

# GF(9) = GF(3^2), a non-binary example
M.<c> = GF(9)
print("GF(9) = GF(3^2) built by SageMath:")
print(f"  Modulus used: {M.modulus()}")
print(f"  Elements: {list(M)}")
print(f"  Number of elements: {len(list(M))}")

Crypto Foreshadowing: The AES Field GF(256)

The Advanced Encryption Standard (AES), the most widely used symmetric cipher in the world, performs all its internal arithmetic in $\text{GF}(256) = \text{GF}(2^8)$.

Every byte (8 bits) is an element of this field. The specific irreducible polynomial used by AES is:

$$x^8 + x^4 + x^3 + x + 1$$

So $\text{GF}(256) = \mathbb{F}_2[x]/(x^8 + x^4 + x^3 + x + 1)$.

Module 03 builds this field from scratch and uses it to implement AES operations. Everything you just learned, quotient rings, reduction mod an irreducible, multiplication tables, is exactly what AES does with bytes.

# Preview: the AES field GF(256)
R.<x> = PolynomialRing(GF(2))
aes_poly = x^8 + x^4 + x^3 + x + 1
print(f"AES irreducible polynomial: {aes_poly}")
print(f"Irreducible? {aes_poly.is_irreducible()}")
print(f"Degree: {aes_poly.degree()} --> GF(2^8) = GF(256)")

# Build it
AES.<g> = R.quotient(aes_poly)
print(f"\nNumber of elements: {len(list(AES))}")

# Example: multiply two 'bytes' in GF(256)
byte1 = g^7 + g^4 + g    # represents the polynomial x^7 + x^4 + x = bit pattern 10010010
byte2 = g^3 + g + 1       # represents x^3 + x + 1 = bit pattern 00001011
product = byte1 * byte2
print(f"\nExample multiplication in GF(256):")
print(f"  ({byte1}) * ({byte2}) = {product}")
print(f"\nThis is exactly what AES does inside SubBytes/MixColumns!")

Exercises

Exercise 1: GF(4) Arithmetic by Hand (Fully Worked)

Problem: In $\text{GF}(4) = \mathbb{F}_2[x]/(x^2 + x + 1)$, compute $(x + 1) \cdot (x + 1)$ by hand, then verify with SageMath.

Solution:

1. Multiply as polynomials: $(x+1)(x+1) = x^2 + x + x + 1 = x^2 + 1$ (since $2x = 0$ in $\mathbb{F}_2$)

2. Reduce mod $x^2 + x + 1$: compute $(x^2 + 1) \mod (x^2 + x + 1)$

   • $x^2 + 1 = 1 \cdot (x^2 + x + 1) + x$ (remainder is $x$, since $(x^2+1) - (x^2+x+1) = -x = x$ in $\mathbb{F}_2$)

3. Answer: $(x+1)^2 = x$ in GF(4)

# Exercise 1: Verify the hand calculation
R.<x> = PolynomialRing(GF(2))
S.<a> = R.quotient(x^2 + x + 1)

result = (a + 1) * (a + 1)
print(f"(a + 1)^2 = {result}")
assert result == a, "Something went wrong!"
print("Confirmed: (x+1)^2 = x in GF(4)")

# Bonus: this means (x+1) is a square root of x in GF(4)!
# In GF(4), every element has a square root (Frobenius endomorphism).
print("\nSquare roots in GF(4):")
for elem in S:
    print(f"  {elem}^2 = {elem^2}")

Exercise 2: Build GF(16) (Guided)

Problem: Construct $\text{GF}(16) = \text{GF}(2^4) = \mathbb{F}_2[x]/(f(x))$ where $f(x)$ is an irreducible polynomial of degree 4 over $\mathbb{F}_2$.

Steps:

1. Find an irreducible polynomial of degree 4 over $\mathbb{F}_2$

2. Build the quotient ring

3. List all 16 elements

4. Verify it is a field

5. Compute the inverse of $a^3 + a + 1$

# Exercise 2: Build GF(16)
R.<x> = PolynomialRing(GF(2))

# Step 1: Find an irreducible polynomial of degree 4 over F_2
# TODO: List all degree-4 polynomials that are irreducible
# Hint: use a loop over all monic degree-4 polynomials and check is_irreducible()
# irreducibles = [f for f in ??? if f.is_irreducible()]
# print("Irreducible degree-4 polynomials over F_2:", irreducibles)

# Step 2: Pick one and build the quotient ring
# TODO: f = <pick one from your list>
# S.<a> = R.quotient(f)

# Step 3: List all elements
# TODO: print(f"GF(16) has {len(list(S))} elements")

# Step 4: Verify it's a field
# TODO: print(f"Is field? {S.is_field()}")

# Step 5: Compute the inverse of a^3 + a + 1
# TODO: elem = a^3 + a + 1
#        print(f"({elem})^(-1) = {elem^(-1)}")

Exercise 3: Reducible vs Irreducible (Independent)

Problem: Over $\mathbb{F}_3$ (the field with 3 elements), consider the two polynomials:

• $f(x) = x^2 + 1$

• $g(x) = x^2 + x + 2$

For each polynomial:

1. Determine whether it is irreducible over $\mathbb{F}_3$.

2. Build the quotient ring $\mathbb{F}_3[x]/(\text{polynomial})$.

3. Determine if the result is a field.

4. If it is NOT a field, find a pair of zero divisors.

5. If it IS a field, verify by finding the inverse of every nonzero element.

Hint: To check irreducibility of a degree-2 polynomial, test all elements of $\mathbb{F}_3$ as roots.

# Exercise 3: Your code here
# Work over F_3
R.<x> = PolynomialRing(GF(3))

# Investigate f(x) = x^2 + 1
# ...

# Investigate g(x) = x^2 + x + 2
# ...

Summary

Concept	Key idea
Quotient ring construction	$\mathbb{F}_p[x]/(f(x))$ mods polynomials by $f(x)$, exactly the way $\mathbb{Z}/n\mathbb{Z}$ mods integers by $n$
Elements are remainders	In $\mathbb{F}_p[x]/(f(x))$ with $\deg f = n$, elements are all polynomials of degree $< n$ with coefficients in $\mathbb{F}_p$, giving exactly $p^n$ elements
Irreducible = field	The quotient is a field iff the modulus polynomial is irreducible. A reducible modulus gives zero divisors, just like a composite modulus in $\mathbb{Z}/n\mathbb{Z}$
The general pattern	$\text{GF}(p^n) = \mathbb{F}_p[x]/(\text{irreducible of degree } n)$
GF(4) and GF(8) by hand	Built as $\mathbb{F}_2[x]/(x^2+x+1)$ and $\mathbb{F}_2[x]/(x^3+x+1)$, with complete addition and multiplication tables verified
The crypto connection	AES operates in $\text{GF}(256) = \mathbb{F}_2[x]/(x^8 + x^4 + x^3 + x + 1)$. This is Module 03

Module 02 complete. You now have the algebraic foundations, rings, fields, polynomial arithmetic, irreducibility, and quotient rings, to understand how finite fields are built and used in cryptography.

Next: Module 03. Galois Fields and AES