02e-polynomial-division-irreducibility.ipynb

Kernel: SageMath 10.5

Polynomial Division & Irreducibility

Module 02 | 02-rings-fields-polynomials

divmod for polys, is_irreducible(), the primes of polynomial rings

Objectives

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

1. Perform polynomial long division over $\mathbb{F}_p[x]$ and verify the division algorithm.

2. Test irreducibility of polynomials over finite fields using SageMath.

3. Explain why irreducibility depends on the base field.

4. Articulate the parallel: irreducible polynomials are to polynomial rings what primes are to integers.

5. Understand why irreducible polynomials are the key ingredient for constructing extension fields $\mathrm{GF}(p^n)$.

Prerequisites

• Completion of Polynomial Rings (polynomial arithmetic in $\mathbb{F}_p[x]$).

• Completion of What Is a Field? (fields, $\mathbb{Z}/p\mathbb{Z}$).

• Comfort with modular arithmetic from Module 01.

Motivating Question

You already know that $x^2 + 1$ has no real roots (since $x^2 \ge 0$ for all $x \in \mathbb{R}$). Over $\mathbb{R}$, we cannot factor it, so we call it irreducible.

But what happens if we change the field?

• Over $\mathbb{C}$, we get $x^2 + 1 = (x + i)(x - i)$. Reducible!

• Over $\mathbb{F}_2 = \{0, 1\}$, is $x^2 + 1$ irreducible? Let's check: $0^2 + 1 = 1 \ne 0$, and $1^2 + 1 = 2 = 0$ in $\mathbb{F}_2$. So $x = 1$ is a root, meaning $(x - 1) = (x + 1)$ divides it. In fact, $x^2 + 1 = (x+1)^2$ over $\mathbb{F}_2$.

• Over $\mathbb{F}_3$? We check: $0^2 + 1 = 1$, $1^2 + 1 = 2$, $2^2 + 1 = 5 = 2$. No roots! For a degree-2 polynomial, no roots means irreducible. So $x^2 + 1$ is irreducible over $\mathbb{F}_3$.

The same polynomial can be irreducible over one field and reducible over another. This is not a minor technicality, it is the central idea that makes finite field extensions (and therefore AES, elliptic curves, and post-quantum crypto) work.

To understand irreducibility properly, we first need the tool that underpins it: polynomial division.

---

1. Polynomial Long Division

Bridge from 02c: In the polynomial rings notebook, we learned how to add and multiply polynomials in $\mathbb{F}_p[x]$. Now we add the final arithmetic operation: division with remainder.

The Division Algorithm for Polynomials

Recall the division algorithm for integers: given $a, b \in \mathbb{Z}$ with $b \ne 0$, there exist unique $q, r$ such that $$a = q \cdot b + r, \qquad 0 \le r < |b|.$$

The polynomial version is almost identical. Given polynomials $f, g \in F[x]$ with $g \ne 0$, there exist unique polynomials $q$ (quotient) and $r$ (remainder) such that:

$$f = q \cdot g + r, \qquad \deg(r) < \deg(g).$$

The role of "less than" in the integer case ($r < |b|$) is played by "lower degree" in the polynomial case ($\deg(r) < \deg(g)$).

Step-by-step example: dividing over $\mathbb{Q}[x]$

Let's divide $f = x^4 + x^2 + 1$ by $g = x^2 + x + 1$ step by step.

Step 1: Leading term of $f$ is $x^4$, leading term of $g$ is $x^2$. Divide: $x^4 / x^2 = x^2$. Multiply $g$ by $x^2$: $x^4 + x^3 + x^2$. Subtract from $f$: $$( x^4 + x^2 + 1 ) - ( x^4 + x^3 + x^2 ) = -x^3 + 1$$

Step 2: Leading term of remainder is $-x^3$. Divide: $-x^3 / x^2 = -x$. Multiply $g$ by $-x$: $-x^3 - x^2 - x$. Subtract: $$( -x^3 + 1 ) - ( -x^3 - x^2 - x ) = x^2 + x + 1$$

Step 3: Leading term is $x^2$. Divide: $x^2 / x^2 = 1$. Multiply $g$ by $1$: $x^2 + x + 1$. Subtract: $$(x^2 + x + 1) - (x^2 + x + 1) = 0$$

So $q = x^2 - x + 1$ and $r = 0$. The remainder is zero, meaning $g$ divides $f$ exactly.

Let's verify with SageMath:

# Polynomial long division over Q[x]
R.<x> = PolynomialRing(QQ)

f = x^4 + x^2 + 1
g = x^2 + x + 1

q, r = f.quo_rem(g)    # quotient and remainder
print(f'f = {f}')
print(f'g = {g}')
print(f'Quotient  q = {q}')
print(f'Remainder r = {r}')
print()

# Verify the division algorithm: f == q*g + r
print(f'Verification: q*g + r = {q*g + r}')
print(f'Equals f? {q*g + r == f}')

SageMath provides three ways to do polynomial division:

Operation	SageMath syntax	Returns
Full division	f.quo_rem(g)	Tuple (q, r)
Quotient only	f // g	q
Remainder only	f % g	r

These mirror Python's integer divmod, //, and %.

# The //, %, and divmod shortcuts
R.<x> = PolynomialRing(QQ)

f = x^3 + 2*x^2 - x + 3
g = x - 2

print(f'f // g = {f // g}')           # quotient
print(f'f %  g = {f % g}')            # remainder
print(f'divmod = {f.quo_rem(g)}')      # both
print()

# Note: f(2) should equal the remainder (Remainder Theorem!)
print(f'f(2) = {f(2)}')
print(f'Remainder = {f % g}')
print(f'Match? {f(2) == (f % g)}')     # Polynomial Remainder Theorem

Division over finite fields $\mathbb{F}_p[x]$

Everything works identically over $\mathbb{F}_p$. The only difference is that all coefficients are reduced mod $p$. This is exactly where cryptography lives.

# Polynomial division over F_5[x]
R.<x> = PolynomialRing(GF(5))

f = x^4 + 3*x^3 + 2*x + 1
g = x^2 + 4*x + 2

q, r = f.quo_rem(g)
print(f'Over F_5[x]:')
print(f'f = {f}')
print(f'g = {g}')
print(f'q = {q}')
print(f'r = {r}')
print(f'deg(r) = {r.degree()} < deg(g) = {g.degree()}? {r.degree() < g.degree()}')
print(f'Verification: q*g + r == f? {q*g + r == f}')

Checkpoint: Before running the next cell, compute by hand: in $\mathbb{F}_3[x]$, divide $x^3 + 2x + 1$ by $x + 2$. What are $q$ and $r$?

Hint: The leading coefficient of $g$ is $1$, so no inversions needed. Remember all arithmetic is mod 3.

# Check your hand calculation
R.<x> = PolynomialRing(GF(3))

f = x^3 + 2*x + 1
g = x + 2

q, r = f.quo_rem(g)
print(f'q = {q}')
print(f'r = {r}')
print(f'f = q*g + r? {q*g + r == f}')

---

2. Irreducible Polynomials: The "Primes" of Polynomial Rings

Bridge from 02d: We saw that $\mathbb{Z}/p\mathbb{Z}$ is a field precisely when $p$ is prime. Primes are the "atoms" of the integers, they cannot be broken into smaller factors. Polynomials have an exact analogue.

Definition

A polynomial $f \in F[x]$ of degree $\ge 1$ is irreducible over $F$ if it cannot be written as $f = g \cdot h$ where both $g$ and $h$ have degree $\ge 1$.

In other words: the only way to factor $f$ is trivially, as $f = c \cdot (c^{-1} f)$ for some constant $c \in F^*$.

The parallel

Integers $\mathbb{Z}$	Polynomials $F[x]$
Primes $p$	Irreducible polynomials
Every integer factors uniquely into primes	Every polynomial factors uniquely into irreducibles
$\mathbb{Z}/p\mathbb{Z}$ is a field iff $p$ is prime	$F[x]/(f)$ is a field iff $f$ is irreducible
Primes are the building blocks of $\mathbb{Z}$	Irreducibles are the building blocks of $F[x]$

The last row in this table is exactly what we will use in notebook 02f to build extension fields like $\mathrm{GF}(2^8)$.

Testing irreducibility with SageMath

SageMath provides two key methods:

• f.is_irreducible(), returns True/False

• f.factor(), returns the complete factorization

# Irreducibility testing over GF(2)
R.<x> = PolynomialRing(GF(2))

test_polys = [x^2 + 1, x^2 + x + 1, x^3 + x + 1, x^3 + x^2 + 1, x^3 + 1]

print('Polynomial Irreducible? Factorization')for f in test_polys:
    print(f'{str(f)} {str(f.is_irreducible())} {f.factor()}')

Notice that $x^2 + 1 = (x+1)^2$ over $\mathbb{F}_2$. This is because $-1 = 1$ in $\mathbb{F}_2$, so $x^2 + 1 = x^2 - 1 = (x-1)(x+1) = (x+1)(x+1)$.

Meanwhile, $x^2 + x + 1$ is irreducible over $\mathbb{F}_2$: we check $f(0) = 1 \ne 0$ and $f(1) = 1 + 1 + 1 = 1 \ne 0$, so no roots, and for degree 2, no roots implies irreducible.

---

3. Irreducibility Depends on the Field!

This is the single most important thing to understand about irreducibility: it is not a property of the polynomial alone, but of the polynomial together with the field.

Let's see $x^2 + 1$ across several fields:

# x^2 + 1 over different fields
print('Field Irreducible? Factorization')
for F, name in [(GF(2), 'F_2'), (GF(3), 'F_3'), (GF(5), 'F_5'), 
                (GF(7), 'F_7'), (GF(11), 'F_11'), (GF(13), 'F_13')]:
    R.<x> = PolynomialRing(F)
    f = x^2 + 1
    print(f'{name} {str(f.is_irreducible())} {f.factor()}')

Checkpoint: Look at the pattern above. Over which primes $p$ is $x^2 + 1$ irreducible?

Hint: $x^2 + 1$ has a root in $\mathbb{F}_p$ iff $-1$ is a quadratic residue mod $p$, which happens iff $p \equiv 1 \pmod{4}$ (or $p = 2$). So $x^2+1$ is irreducible over $\mathbb{F}_p$ precisely when $p \equiv 3 \pmod{4}$.

Verify: $3 \equiv 3$, $7 \equiv 3$, $11 \equiv 3 \pmod{4}$, all irreducible. $5 \equiv 1$, $13 \equiv 1 \pmod{4}$, all reducible. And $p=2$ is special ($-1 = 1$).

Misconception Alert

"If a polynomial has no roots, then it must be irreducible."

This is only true for polynomials of degree 2 or 3! For degree $\ge 4$, a polynomial can have no roots and still factor into two polynomials of degree $\ge 2$.

Example: over $\mathbb{F}_2$, the polynomial $x^4 + x^2 + 1$ has no roots ($f(0) = 1$, $f(1) = 1$), but it is not irreducible:

# Misconception buster: no roots does NOT always mean irreducible
R.<x> = PolynomialRing(GF(2))
f = x^4 + x^2 + 1

# Check roots
print(f'f(0) = {f(0)}')
print(f'f(1) = {f(1)}')
print(f'Has any roots? No!')
print()

# But is it irreducible?
print(f'Is irreducible? {f.is_irreducible()}')
print(f'Factorization:  {f.factor()}')
print()
print('It factors as a product of two degree-2 polynomials!')
print('Neither factor has degree 1, so the original polynomial has no LINEAR factors (= no roots),')
print('but it is still reducible.')

Takeaway: For degree 2 or 3, checking for roots is sufficient to test irreducibility (because if it factors, at least one factor must have degree 1, i.e., it has a root). For degree $\ge 4$, you must use proper factorization or is_irreducible().

---

4. Unique Factorization: Every Polynomial Factors into Irreducibles

Just as the Fundamental Theorem of Arithmetic says every integer $> 1$ factors uniquely into primes, we have:

Unique Factorization in $F[x]$: Every polynomial of degree $\ge 1$ in $F[x]$ can be written uniquely (up to ordering and constant multiples) as a product of irreducible polynomials.

SageMath's .factor() gives us this decomposition directly.

# Unique factorization in F_5[x]
R.<x> = PolynomialRing(GF(5))

polys = [
    x^4 + 1,
    x^5 - x,               # Hint: Fermat's little theorem!
    x^6 + x^3 + 2*x + 1,
]

for f in polys:
    print(f'{f}  =  {f.factor()}')
    print()

Notice $x^5 - x = x(x-1)(x-2)(x-3)(x-4) = x(x+4)(x+3)(x+2)(x+1)$ over $\mathbb{F}_5$. Every element of $\mathbb{F}_5$ is a root! This is Fermat's Little Theorem in disguise: $a^p = a$ for all $a \in \mathbb{F}_p$, so $x^p - x$ has all $p$ elements as roots.

---

5. Counting Irreducibles: How Many Are There?

If we want to build a field $\mathrm{GF}(p^n)$, we need an irreducible polynomial of degree $n$ over $\mathbb{F}_p$. But do they always exist? How many are there?

The number of monic irreducible polynomials of degree $n$ over $\mathbb{F}_p$ is given by the necklace formula:

$$N_p(n) = \frac{1}{n} \sum_{d \mid n} \mu(n/d) \, p^d$$

where $\mu$ is the Mobius function. For large $n$, this is approximately $p^n / n$.

The key fact: $N_p(n) \ge 1$ for all $p$ and $n \ge 1$. So irreducible polynomials of every degree always exist, and we can always build $\mathrm{GF}(p^n)$.

# Count monic irreducibles of each degree over F_2
print('Monic irreducible polynomials over F_2 by degree:')
print('Degree Count Approx 2^n/n Examples')
for n in range(1, 9):
    R.<x> = PolynomialRing(GF(2))
    # List all monic polynomials of degree n and filter irreducibles
    count = 0
    examples = []
    for f in R.polynomials(of_degree=n):
        if f.is_monic() and f.is_irreducible():
            count += 1
            if len(examples) < 2:
                examples.append(str(f))
    approx = round(2^n / n, 1)
    print(f'{n} {count} {approx} {" , ".join(examples)}')

For degree 8 over $\mathbb{F}_2$, there are 30 monic irreducible polynomials. AES uses one specific choice: $x^8 + x^4 + x^3 + x + 1$. Let's verify:

# The AES irreducible polynomial
R.<x> = PolynomialRing(GF(2))
aes_poly = x^8 + x^4 + x^3 + x + 1

print(f'AES polynomial: {aes_poly}')
print(f'Is irreducible over F_2? {aes_poly.is_irreducible()}')
print(f'Degree: {aes_poly.degree()}')
print()
print('This polynomial is used to construct GF(2^8) = GF(256),')
print('the field in which all AES byte-level operations take place.')
print(f'GF(2^8) has {2^8} elements, one for each possible byte value.')

Crypto Foreshadowing: In Module 03, we will build $\mathrm{GF}(2^8)$ explicitly using this polynomial and see how AES performs its MixColumns and SubBytes operations as polynomial arithmetic modulo $x^8 + x^4 + x^3 + x + 1$. The choice of irreducible polynomial does not affect the field structure (all choices give isomorphic fields), but it does affect implementation efficiency.

---

Exercises

Exercise 1: Division Algorithm Verification (Fully Worked)

Task: Divide $f = x^5 + 3x^3 + x + 2$ by $g = x^2 + 1$ over $\mathbb{F}_7[x]$. Verify the division algorithm.

# Exercise 1: Fully worked solution
R.<x> = PolynomialRing(GF(7))

f = x^5 + 3*x^3 + x + 2
g = x^2 + 1

# Step 1: Compute quotient and remainder
q, r = f.quo_rem(g)
print(f'f = {f}')
print(f'g = {g}')
print(f'q = {q}')
print(f'r = {r}')
print()

# Step 2: Verify f = q*g + r
print(f'q * g + r = {q*g + r}')
print(f'Equals f?  {q*g + r == f}')
print()

# Step 3: Verify deg(r) < deg(g)
print(f'deg(r) = {r.degree()}')
print(f'deg(g) = {g.degree()}')
print(f'deg(r) < deg(g)? {r.degree() < g.degree()}')
print()

# Step 4: Alternative syntax
print(f'f // g = {f // g}')   # same as q
print(f'f %  g = {f % g}')    # same as r

Exercise 2: Finding Irreducibles (Guided)

Task: Find all monic irreducible polynomials of degree 3 over $\mathbb{F}_3$. There should be 8 of them (since $N_3(3) = (3^3 - 3)/3 = 8$).

Fill in the TODOs below.

# Exercise 2: Find all monic irreducible cubics over F_3
R.<x> = PolynomialRing(GF(3))

irreducibles = []

# TODO 1: Loop over all monic polynomials of degree 3 over F_3.
#         A monic cubic has the form x^3 + a*x^2 + b*x + c
#         where a, b, c are each in {0, 1, 2}.
#
# for a in GF(3):
#     for b in GF(3):
#         for c in GF(3):
#             f = x^3 + a*x^2 + b*x + c


# TODO 2: For each polynomial, check if it is irreducible.
#         If so, append it to the irreducibles list.
#
#             if f.is_irreducible():
#                 irreducibles.append(f)


# Print results
print(f'Found {len(irreducibles)} monic irreducible cubics over F_3:')
for f in irreducibles:
    print(f'  {f}')

# TODO 3: Verify: for each irreducible you found, check that it has
#         no roots in F_3. (Why is this sufficient for degree 3?)
#
# for f in irreducibles:
#     roots = [a for a in GF(3) if f(a) == 0]
#     print(f'{f} has roots: {roots}')

Exercise 3: Field-Dependent Irreducibility (Independent)

Task: Consider the polynomial $f = x^4 + 1$.

1. Factor $f$ over $\mathbb{F}_2$, $\mathbb{F}_3$, $\mathbb{F}_5$, $\mathbb{F}_7$, $\mathbb{F}_{11}$, and $\mathbb{F}_{13}$.

2. Is $f$ irreducible over any of these fields?

3. Investigate: is $x^4 + 1$ irreducible over $\mathbb{F}_p$ for any prime $p$? What do you observe?

Hint: This is a famous example. The answer may surprise you, $x^4 + 1$ is irreducible over $\mathbb{Q}$ but reducible over every finite field $\mathbb{F}_p$.

# Exercise 3: Your code here
# Factor x^4 + 1 over various finite fields and investigate.

Summary

Concept	Key idea
Division algorithm	For any $f, g \in F[x]$ with $g \ne 0$, unique $q, r$ exist with $f = q \cdot g + r$ and $\deg(r) < \deg(g)$. SageMath: f.quo_rem(g), f // g, f % g
Irreducible polynomials	The polynomial analogue of prime numbers. They cannot be factored into lower-degree polynomials, and they build all polynomials via unique factorization
Irreducibility depends on the field	The same polynomial can be irreducible over one field and reducible over another. Always specify the field!
No-roots test (degree 2 and 3 only)	For degree $\ge 4$, a polynomial can have no roots yet still be reducible, factoring into two quadratics for example
Counting irreducibles	There are approximately $p^n / n$ monic irreducible polynomials of degree $n$ over $\mathbb{F}_p$, and at least one always exists. This guarantees we can always construct $\mathrm{GF}(p^n)$
Crypto connection	AES uses the irreducible $x^8 + x^4 + x^3 + x + 1$ over $\mathbb{F}_2$ to build $\mathrm{GF}(2^8)$, the field where all byte-level AES operations live

Next: Quotient Rings and Field Extensions, where we use irreducible polynomials to actually construct new fields.