02c-polynomial-rings.ipynb

Kernel: SageMath 10.5

Polynomial Rings

Module 02 | 02-rings-fields-polynomials

Polynomials as formal objects, PolynomialRing(), arithmetic, the polynomial-vs-function trap

Objectives

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

1. Explain why a polynomial is a formal algebraic object (a sequence of coefficients), not a function.

2. Create polynomial rings over different coefficient rings in SageMath using PolynomialRing().

3. Perform polynomial arithmetic (addition, multiplication) and predict degrees of results.

4. Identify the crucial difference between "polynomial" and "polynomial function" over finite fields.

5. See the structural parallel: Z is to Z/nZ as F is to F[x]/(p(x)).

Prerequisites

• Completion of Integers Mod n as a Ring.

• You know what a ring is (two operations, axioms) and have seen Z/nZ as a concrete example.

• Basic comfort with SageMath syntax.

Bridge: From Number Rings to Polynomial Rings

In notebook 02b, we built the ring Z/nZ by taking the integers and "wrapping around" modulo $n$. The elements were numbers, the operations were addition and multiplication mod $n$, and we verified all the ring axioms.

Now here is the key insight: numbers are not the only things that form rings.

Polynomials do too. You can add them, multiply them, there is a zero polynomial, a one polynomial, and all the ring axioms hold. This is not a metaphor --- polynomial rings are one of the most important structures in all of algebra and cryptography.

But to see polynomials as ring elements, we need to change how we think about them. In calculus, you probably thought of $x^2 + 1$ as a function that takes an input and produces an output. That intuition will mislead you here. We need to think of polynomials as formal expressions --- objects defined entirely by their list of coefficients.

Motivating Question

Over the real numbers, if two polynomials give the same output for every input, they must be the same polynomial. You probably take this for granted.

Question: Over $\text{GF}(2) = \{0, 1\}$, can two different polynomials give the same output for every possible input?

Think about it for a moment. There are only two possible inputs: 0 and 1. A polynomial like $x^2 + x$ can be evaluated at both. What do you get?

Let us find out.

# Evaluate x^2 + x at every element of GF(2)
F = GF(2)
R.<x> = PolynomialRing(F)

f = x^2 + x
print(f"The polynomial f = {f}")
print(f"f(0) = {f(F(0))}")
print(f"f(1) = {f(F(1))}")
print()
print(f"The zero polynomial: g = {R.zero()}")
print(f"g(0) = {R.zero()(F(0))}")
print(f"g(1) = {R.zero()(F(1))}")
print()
print(f"Are f and g the same polynomial? {f == R.zero()}")
print(f"Do they agree on ALL inputs?  YES --- both give 0 everywhere!")

What Just Happened?

The polynomial $x^2 + x$ over $\text{GF}(2)$ evaluates to $0$ on every input:

• $f(0) = 0^2 + 0 = 0$

• $f(1) = 1^2 + 1 = 1 + 1 = 0$ (remember, in $\text{GF}(2)$, $1 + 1 = 0$)

So $f = x^2 + x$ defines the zero function on $\text{GF}(2)$. But it is not the zero polynomial --- the zero polynomial has all coefficients equal to 0, while $x^2 + x$ has nonzero coefficients.

Misconception Alert: Over finite fields, "same function on all inputs" does NOT mean "same polynomial." A polynomial is defined by its coefficients, not by the function it computes. This distinction is invisible over $\mathbb{R}$ or $\mathbb{Q}$ (infinite fields), which is why your calculus intuition hides it.

Polynomials as Formal Objects

A polynomial over a ring $R$ is a finite formal sum:

$$f = a_0 + a_1 x + a_2 x^2 + \cdots + a_n x^n, \qquad a_i \in R$$

The key word is formal. The symbol $x$ is not a variable that takes values --- it is an indeterminate, a placeholder that organizes the coefficients. Two polynomials are equal if and only if all their coefficients match, regardless of what happens when you "plug in" values.

Concept	Polynomial (formal)	Polynomial function
What is it?	A sequence of coefficients $(a_0, a_1, \ldots, a_n)$	A map $f: R \to R$
When are two equal?	All coefficients match	Same output on all inputs
Over $\mathbb{R}$:	These agree	These agree
Over $\text{GF}(2)$:	$x^2 + x \neq 0$	$x^2 + x$ and $0$ define the same function!

Checkpoint 1: Predict Before You Run

Over $\text{GF}(3) = \{0, 1, 2\}$, consider the polynomial $f = x^3 - x$ (equivalently $x^3 + 2x$ since $-1 \equiv 2$).

Predict: what is $f(0)$? $f(1)$? $f(2)$?

Is this the zero polynomial? Is it the zero function on $\text{GF}(3)$?

# Checkpoint 1: Evaluate x^3 - x over GF(3)
F = GF(3)
R.<x> = PolynomialRing(F)

f = x^3 - x
print(f"f = {f}")
print(f"Coefficients: {f.list()}")
print()
for a in F:
    print(f"f({a}) = {f(a)}")

print(f"\nIs f the zero polynomial? {f == R.zero()}")
print(f"Is f the zero function on GF(3)? {all(f(a) == 0 for a in F)}")
print("\n--> By Fermat's little theorem, a^p = a for all a in GF(p).")
print("    So x^3 - x vanishes on all of GF(3), but it is NOT the zero polynomial!")

Creating Polynomial Rings in SageMath

SageMath makes it easy to construct polynomial rings. The key function is PolynomialRing(R, 'x') where:

• R is the coefficient ring (where the $a_i$ live)

• 'x' is the name of the indeterminate

Common coefficient rings:

• ZZ --- the integers $\mathbb{Z}$, giving $\mathbb{Z}[x]$

• QQ --- the rationals $\mathbb{Q}$, giving $\mathbb{Q}[x]$

• GF(p) --- the finite field with $p$ elements, giving $\mathbb{F}_p[x]$

# Three polynomial rings with different coefficient rings
R_Z.<x> = PolynomialRing(ZZ)      # Z[x]
R_Q.<y> = PolynomialRing(QQ)      # Q[x] (using 'y' just to show the name is arbitrary)
R_F.<t> = PolynomialRing(GF(5))   # F_5[t]

print(f"Ring 1: {R_Z}")
print(f"  Base ring: {R_Z.base_ring()}")
print(f"  Indeterminate: {R_Z.gen()}")
print()
print(f"Ring 2: {R_Q}")
print(f"  Base ring: {R_Q.base_ring()}")
print()
print(f"Ring 3: {R_F}")
print(f"  Base ring: {R_F.base_ring()}")
print()

# Each is a ring --- let's verify
print(f"Is R_Z a ring? {R_Z in Rings()}")
print(f"Is R_F a ring? {R_F in Rings()}")

Polynomial Arithmetic

The ring operations on polynomials are defined coefficient by coefficient for addition, and by the usual convolution (distribute-and-collect) rule for multiplication.

Addition: $(a_0 + a_1 x + \cdots) + (b_0 + b_1 x + \cdots) = (a_0+b_0) + (a_1+b_1)x + \cdots$

Multiplication: Multiply every term by every term, then collect like powers of $x$.

The zero element is the polynomial $0$; the identity is the polynomial $1$ (constant polynomial). Let us see this in action.

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

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

print(f"f = {f}")
print(f"g = {g}")
print(f"f.list() = {f.list()}   (coefficients, lowest degree first)")
print(f"g.list() = {g.list()}")
print()
print(f"f + g = {f + g}")
print(f"f - g = {f - g}")
print(f"f * g = {f * g}")
print()
print("Ring axioms in action:")
print(f"  f + g == g + f?  {f + g == g + f}   (commutativity of +)")
print(f"  f * g == g * f?  {f * g == g * f}   (commutativity of *)")
print(f"  f * 1 == f?      {f * R.one() == f}       (multiplicative identity)")
print(f"  f + 0 == f?      {f + R.zero() == f}      (additive identity)")

Degree Rules

The degree of a polynomial $f = a_n x^n + \cdots + a_0$ (with $a_n \neq 0$) is $n$. Degree tells you the "size" of a polynomial. It obeys clean rules:

1. $\deg(f \cdot g) = \deg(f) + \deg(g)$ (over a domain --- no zero divisors in coefficients)

2. $\deg(f + g) \leq \max(\deg(f), \deg(g))$ --- and it can be strictly less if leading terms cancel!

By convention, $\deg(0) = -1$ in SageMath (some texts use $-\infty$).

# Degree rules in action
R.<x> = PolynomialRing(QQ)

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

print(f"f = {f},  deg(f) = {f.degree()}")
print(f"g = {g},  deg(g) = {g.degree()}")
print()

# Rule 1: deg(f*g) = deg(f) + deg(g)
print(f"f * g = {f * g}")
print(f"deg(f*g) = {(f*g).degree()} = {f.degree()} + {g.degree()} = {f.degree() + g.degree()}  ✓")
print()

# Rule 2: deg(f+g) <= max(deg(f), deg(g))
print(f"f + g = {f + g}")
print(f"deg(f+g) = {(f+g).degree()} <= max({f.degree()}, {g.degree()}) = {max(f.degree(), g.degree())}  ✓")
print()

# When leading terms cancel: strict inequality!
h = -2*x^3 + 7*x^2
print(f"h = {h},  deg(h) = {h.degree()}")
print(f"f + h = {f + h}")
print(f"deg(f+h) = {(f+h).degree()} < max({f.degree()}, {h.degree()}) = {max(f.degree(), h.degree())}  (strict!)")

Checkpoint 2: Degree Predictions

Before running the next cell, predict:

1. If $f$ has degree 4 and $g$ has degree 3, what is $\deg(f \cdot g)$?

2. If $f = 3x^5 + x$ and $g = -3x^5 + 2x^2$, what is $\deg(f + g)$?

3. What is $\deg(0)$ in SageMath?

# Checkpoint 2: Check your predictions
R.<x> = PolynomialRing(QQ)

# 1. deg(f*g) where deg(f)=4, deg(g)=3
f1 = x^4 + 1
g1 = x^3 + x
print(f"1. deg(f*g) = {(f1*g1).degree()}  (predicted: 7)")

# 2. Leading terms cancel
f2 = 3*x^5 + x
g2 = -3*x^5 + 2*x^2
print(f"2. f + g = {f2 + g2}, deg = {(f2+g2).degree()}  (predicted: 2, not 5!)")

# 3. Degree of zero
print(f"3. deg(0) = {R.zero().degree()}  (SageMath convention: -1)")

Same Polynomial, Different Coefficient Rings

Here is something that catches people off guard: the "same" polynomial behaves very differently depending on which ring the coefficients live in.

Consider $f = x^2 + 1$.

• Over $\mathbb{Q}$: irreducible (no rational roots).

• Over $\mathbb{R}$: still irreducible.

• Over $\text{GF}(2)$: $x^2 + 1 = (x+1)^2$ because $1 + 1 = 0$!

• Over $\text{GF}(5)$: $x^2 + 1 = (x+2)(x+3)$ because $2^2 + 1 = 5 \equiv 0$ and $3^2 + 1 = 10 \equiv 0$.

The coefficient ring fundamentally changes the algebra.

# x^2 + 1 over four different coefficient rings
rings = {
    'Q[x]':     PolynomialRing(QQ, 'x'),
    'GF(2)[x]': PolynomialRing(GF(2), 'x'),
    'GF(3)[x]': PolynomialRing(GF(3), 'x'),
    'GF(5)[x]': PolynomialRing(GF(5), 'x'),
}

for name, ring in rings.items():
    x = ring.gen()
    f = x^2 + 1
    print(f"{name}:  x^2 + 1  factors as  {f.factor()}")
    print(f"         irreducible? {f.is_irreducible()}")
    print()

Checkpoint 3: Coefficient Arithmetic

In $\text{GF}(2)[x]$, we have $1 + 1 = 0$. So:

• What is $(x + 1) + (x + 1)$ in $\text{GF}(2)[x]$?

• What is $(x + 1)^2$ in $\text{GF}(2)[x]$? (Expand it by hand first!)

Remember: $x^2 + 2x + 1 = x^2 + 0 \cdot x + 1 = x^2 + 1$ over $\text{GF}(2)$.

# Checkpoint 3: Arithmetic in GF(2)[x]
R.<x> = PolynomialRing(GF(2))

a = x + 1
print(f"(x+1) + (x+1) = {a + a}       (predicted: 0, since 1+1=0 and x+x=0)")
print(f"(x+1)^2       = {a^2}   (predicted: x^2 + 1, since the middle term 2x vanishes)")
print()
print("This is why x^2 + 1 = (x+1)^2 over GF(2) --- a perfect square!")
print("Over Q, x^2 + 1 has no roots. Same expression, completely different algebraic behavior.")

The Structural Parallel: Integers and Polynomials

Here is the deepest idea in this notebook, and one that will pay off enormously in Module 03 (AES) and beyond.

Integers	Polynomials
$\mathbb{Z}$ = the ring of integers	$F[x]$ = the ring of polynomials over a field $F$
Divide: $a = qn + r$, $0 \leq r < n$	Divide: $f = q \cdot p + r$, $\deg(r) < \deg(p)$
Quotient ring: $\mathbb{Z}/n\mathbb{Z}$	Quotient ring: $F[x]/(p(x))$
Elements: remainders $\{0, 1, \ldots, n-1\}$	Elements: remainders of degree $< \deg(p)$
When is $\mathbb{Z}/n\mathbb{Z}$ a field? When $n$ is prime	When is $F[x]/(p(x))$ a field? When $p(x)$ is irreducible

We will make this precise in notebooks 02e and 02f. For now, just notice the pattern.

Crypto Foreshadowing: AES (the Advanced Encryption Standard) does all of its internal arithmetic in the ring $\text{GF}(2)[x]/(x^8 + x^4 + x^3 + x + 1)$. That is a polynomial quotient ring --- exactly the construction in the right column of the table above. The polynomial $x^8 + x^4 + x^3 + x + 1$ is irreducible over $\text{GF}(2)$, which makes this quotient ring a field with $2^8 = 256$ elements. Every byte in AES is an element of this field. We will build this from scratch in Module 03.

# Preview: the AES polynomial is irreducible over GF(2)
R.<x> = PolynomialRing(GF(2))

aes_poly = x^8 + x^4 + x^3 + x + 1
print(f"AES polynomial: {aes_poly}")
print(f"Degree: {aes_poly.degree()}")
print(f"Irreducible over GF(2)? {aes_poly.is_irreducible()}")
print()
print("This means GF(2)[x] / (x^8 + x^4 + x^3 + x + 1) is a FIELD with 2^8 = 256 elements.")
print("Every byte in AES lives in this field. More in Module 03!")

Exercises

Three exercises with graduated scaffolding: fully worked, guided, then independent.

Exercise 1: Polynomial vs. Function (Fully Worked)

Task: Find all polynomials of degree $\leq 2$ over $\text{GF}(2)$ that define the zero function (evaluate to 0 on every element of $\text{GF}(2)$).

Strategy: There are $2^3 = 8$ polynomials of degree $\leq 2$ over $\text{GF}(2)$ (each of the 3 coefficients is 0 or 1). We will test each one.

# Exercise 1 (Fully Worked): Find all zero-function polynomials of degree <= 2 over GF(2)
F = GF(2)
R.<x> = PolynomialRing(F)

zero_function_polys = []

# Enumerate all polynomials a0 + a1*x + a2*x^2 with coefficients in {0, 1}
for a0 in F:
    for a1 in F:
        for a2 in F:
            f = a0 + a1*x + a2*x^2
            # Check if f(a) == 0 for all a in GF(2)
            if all(f(a) == 0 for a in F):
                zero_function_polys.append(f)

print(f"Polynomials of degree <= 2 over GF(2) that define the zero function:")
for p in zero_function_polys:
    print(f"  {p}  (coefficients: {p.list()}, is zero poly? {p == R.zero()})")

print(f"\nTotal: {len(zero_function_polys)} out of 8 polynomials.")
print("")
print("Observation: Both '0' and 'x^2 + x' define the zero function,")
print("but only '0' is the zero polynomial. This is the polynomial != function distinction.")

Exercise 2: Degree Arithmetic (Guided)

Task: Given $f = x^4 + x^2 + x + 1$ and $g = x^3 + x^2 + 1$ in $\text{GF}(2)[x]$:

1. Compute $f + g$ and verify $\deg(f + g) \leq \max(\deg(f), \deg(g))$.

2. Compute $f \cdot g$ and verify $\deg(f \cdot g) = \deg(f) + \deg(g)$.

3. Find a polynomial $h$ in $\text{GF}(2)[x]$ such that $\deg(f + h) < \deg(f)$.

Fill in the TODO lines below.

# Exercise 2 (Guided): Degree arithmetic in GF(2)[x]
R.<x> = PolynomialRing(GF(2))

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

# Part 1: Compute f + g
s = f + g    # TODO: uncomment and verify
print(f"f = {f}, deg = {f.degree()}")
print(f"g = {g}, deg = {g.degree()}")
print(f"f + g = {s}, deg = {s.degree()}")
print(f"deg(f+g) <= max(deg(f),deg(g))? {s.degree()} <= {max(f.degree(), g.degree())}: {s.degree() <= max(f.degree(), g.degree())}")
print()

# Part 2: Compute f * g
p = f * g    # TODO: uncomment and verify
print(f"f * g = {p}, deg = {p.degree()}")
print(f"deg(f) + deg(g) = {f.degree()} + {g.degree()} = {f.degree() + g.degree()}")
print(f"Match? {p.degree() == f.degree() + g.degree()}")
print()

# Part 3: Find h such that deg(f + h) < deg(f)
# TODO: Define h so that the x^4 term of f cancels out.
# Hint: h needs to have x^4 as its leading term (in GF(2), 1+1=0).
# h = ???
# print(f"h = {h}")
# print(f"f + h = {f + h}, deg = {(f+h).degree()}")
# print(f"deg(f+h) < deg(f)? {(f+h).degree()} < {f.degree()}: {(f+h).degree() < f.degree()}")

Exercise 3: Exploration (Independent)

Task: Over $\text{GF}(3)$, find all polynomials of degree exactly 1 (i.e., $a_1 x + a_0$ with $a_1 \neq 0$) that are zero functions on $\text{GF}(3)$.

Then answer: over $\text{GF}(p)$, what is the lowest-degree nonzero polynomial that defines the zero function? Can you conjecture a general formula? (Hint: think about Fermat's little theorem --- $a^p \equiv a \pmod{p}$ for all $a$.)

# Exercise 3 (Independent): Your code here
# Part A: Find all degree-1 zero functions over GF(3)


# Part B: For p = 2, 3, 5, 7, find the lowest-degree nonzero polynomial
#         that defines the zero function over GF(p).
#         Conjecture: what is the general answer?

Summary

Concept	Key idea
Polynomials are formal objects	Defined by their coefficients, not the functions they compute. Over finite fields, distinct polynomials can define the same function
Polynomial rings $R[x]$	Genuine rings satisfying all axioms, with coefficient-wise addition and convolution multiplication
Degree rules	$\deg(fg) = \deg(f) + \deg(g)$ and $\deg(f+g) \leq \max(\deg(f), \deg(g))$
Coefficient ring matters	The same expression (like $x^2 + 1$) can be irreducible over one ring and factorable over another
The big parallel	$\mathbb{Z} \to \mathbb{Z}/n\mathbb{Z}$ mirrors $F[x] \to F[x]/(p(x))$, and this construction builds the finite fields used in AES, elliptic curves, and beyond

Next: What Is a Field?, where we see what makes certain rings special enough to have division.