Polynomials and the Polynomial Ring

So far the elements of our rings have been numbers: integers, residues, things you can write on a single line. The next step is to allow elements that are several numbers in a row. A polynomial is exactly that: a finite list of numbers, written in a particular notation that makes addition and multiplication look natural. This note introduces polynomials, defines the polynomial ring $\mathbb{Z}_q[X]$, walks through addition and multiplication by hand, and points at the one inconvenience that the next note will fix.

01.What a polynomial is, concretely

A polynomial in the variable $X$ with integer coefficients looks like

$$3X^4 - 2X^2 + X + 7.$$

It has four terms. Each term is a coefficient (here $3$, $-2$, $1$, $7$) multiplied by a power of $X$ (here $X^4$, $X^2$, $X$, and $X^0 = 1$). The largest power of $X$ that appears is the degree of the polynomial. In this example the degree is $4$.

The variable $X$ is purely a placeholder. You should not, at this stage, think of it as a number that you might evaluate the polynomial at. Think of $X$ as a tag that keeps track of which slot a coefficient sits in. The polynomial above is just the list of numbers

$$(7, 1, 0, -2, 3),$$

read as "the constant term is $7$, the $X$ term is $1$, the $X^2$ term is $-2$, the $X^3$ term is $0$, and the $X^4$ term is $3$." Writing it as $3X^4 - 2X^2 + X + 7$ instead of as a list of five numbers is a notational habit that makes the arithmetic rules easy to remember. Nothing is hidden in the powers of $X$. They are book-keeping.

A polynomial is allowed to have a coefficient of zero, in which case that term is usually dropped from the written form. The polynomial $3X^4 - 2X^2 + X + 7$ has a zero coefficient at the $X^3$ slot, and we just do not write $0 \cdot X^3$. The list view (with explicit zeros) and the symbolic view (with zeros suppressed) are the same polynomial.

02.Polynomials with coefficients in a ring

The same idea works if the coefficients are not integers but residues modulo $n$. Consider a polynomial whose coefficients are in $\mathbb{Z}_5 = \{0, 1, 2, 3, 4\}$:

$$2X^3 + 4X + 1.$$

This is a polynomial of degree $3$ with coefficient list $(1, 4, 0, 2)$. Each entry of the list is a residue class modulo $5$, not an arbitrary integer. The coefficient at the $X^2$ slot is $0$, and the rest are $1$, $4$, and $2$, all in $\{0, 1, 2, 3, 4\}$.

The general definition. Given any commutative ring $R$, the polynomial ring in one variable, written

$$R[X],$$

is the set of all polynomials with coefficients drawn from $R$. So $\mathbb{Z}[X]$ is the set of polynomials whose coefficients are integers, $\mathbb{Q}[X]$ those with rational coefficients, and $\mathbb{Z}_q[X]$ those whose coefficients live in $\mathbb{Z}_q$ for some chosen $q$. Cryptography wants $\mathbb{Z}_q[X]$ for a specific cryptographic-size $q$.

The operations on $R[X]$ are inherited from $R$, plus a rule for how the powers of $X$ multiply. We will see both rules in worked form below.

03.Adding polynomials

Addition of two polynomials happens slot by slot. Line up the two polynomials so that matching powers of $X$ sit in the same column, then add the coefficients in each column. The coefficient sum is computed in the underlying ring $R$.

A small example over $\mathbb{Z}_5$. Add $2X^2 + 3X + 4$ and $X^2 + 4X + 2$.

Arrange:

The $X^2$ column: $2 + 1 = 3$. The $X$ column: $3 + 4 = 7 \equiv 2 \pmod 5$. The constant column: $4 + 2 = 6 \equiv 1 \pmod 5$. So the answer is $3X^2 + 2X + 1$. Notice that the addition of coefficients is reduced modulo $5$, exactly as in $\mathbb{Z}_5$.

If the two polynomials have different degrees, the lower-degree one has implicit zeros in the missing slots, and the column sum just copies the value of the higher-degree polynomial there.

Addition is straightforward. The interesting operation is multiplication.

04.Multiplying polynomials, schoolbook style

Polynomial multiplication is the rule "multiply each term of the first polynomial by each term of the second, then add up everything that lands in the same column." The rule for combining a power of $X$ with another power is the obvious one:

$$X^i \cdot X^j \;=\; X^{i+j}.$$

That is the only new rule. Everything else follows from distributivity.

A worked example over $\mathbb{Z}_7$. Compute $(2X + 3)(X + 4)$ in $\mathbb{Z}_7[X]$.

Multiply each pair of terms:

• $(2X) \cdot (X) = 2X^2$
• $(2X) \cdot 4 = 8X = X$ (since $8 \equiv 1 \pmod 7$)
• $3 \cdot X = 3X$
• $3 \cdot 4 = 12 = 5$ (since $12 \equiv 5 \pmod 7$)

Now group by power of $X$ and add:

• $X^2$ column: $2X^2$.
• $X$ column: $X + 3X = 4X$.
• Constant: $5$.

So $(2X + 3)(X + 4) = 2X^2 + 4X + 5$ in $\mathbb{Z}_7[X]$.

The reductions modulo $7$ are quietly happening at each step. We could have done all the integer arithmetic first and reduced the final coefficients modulo $7$ at the end. Both approaches give the same answer, because reduction commutes with arithmetic (Modular Arithmetic).

A slightly bigger example over $\mathbb{Z}_5$. Compute $(X^2 + 2X + 3)(2X + 1)$ in $\mathbb{Z}_5[X]$.

Multiply each pair:

• $X^2 \cdot 2X = 2X^3$
• $X^2 \cdot 1 = X^2$
• $2X \cdot 2X = 4X^2$
• $2X \cdot 1 = 2X$
• $3 \cdot 2X = 6X = X$ (since $6 \equiv 1 \pmod 5$)
• $3 \cdot 1 = 3$

Group:

• $X^3$ column: $2X^3$.
• $X^2$ column: $X^2 + 4X^2 = 5X^2 = 0$ (since $5 \equiv 0 \pmod 5$).
• $X$ column: $2X + X = 3X$.
• Constant: $3$.

So the answer is $2X^3 + 3X + 3$. The $X^2$ coefficient came out to zero, which is fine, and that slot just disappears from the written form.

Notice the degree of the answer: the first polynomial has degree $2$, the second has degree $1$, and the product has degree $3 = 2 + 1$. That is general. When you multiply a polynomial of degree $a$ by one of degree $b$, the product has degree exactly $a + b$ (assuming the leading coefficients do not happen to multiply to zero, which can happen in $\mathbb{Z}_n$ for non-prime $n$). The growth of degree under multiplication is the inconvenience that the next note will solve.

$\mathbb{Z}_q[X]$ as a ring

Run through the ring axioms for $\mathbb{Z}_q[X]$, using the rules for polynomial addition and multiplication just defined.

The additive group $(\mathbb{Z}_q[X], +)$. Closure: adding polynomial slot-by-slot keeps coefficients in $\mathbb{Z}_q$. Associativity and commutativity: inherited from $\mathbb{Z}_q$. Identity: the zero polynomial (every slot is zero). Inverses: negate every coefficient. In $\mathbb{Z}_q$, the negation of a residue $a$ is $q - a$. So $(\mathbb{Z}_q[X], +)$ is an abelian group.

Multiplication. Closure: schoolbook multiplication produces another polynomial in $\mathbb{Z}_q[X]$. Associativity and commutativity: inherited from $\mathbb{Z}_q$ once you check that the rule $X^i \cdot X^j = X^{i+j}$ is associative and commutative, which it is. Identity: the polynomial $1$ (degree zero, constant coefficient $1$). Distributivity over addition: the way the schoolbook multiplication is defined.

So $\mathbb{Z}_q[X]$ is a commutative ring with identity, for every choice of $q$. It is not a field, even when $q$ is prime, because most polynomials do not have polynomial inverses. The polynomial $X$ does not have a polynomial $p(X)$ with $X \cdot p(X) = 1$, because the product of two non-constant polynomials always has degree at least $1$.

06.The degree problem

We are headed towards a structure $R_q$ that has finitely many elements, because the cryptography needs every key to be a fixed-size object. But $\mathbb{Z}_q[X]$ has infinitely many elements: there is no upper bound on the degree of a polynomial. Multiplying two polynomials almost always grows the degree, so even if you started with two short polynomials, repeated multiplication would produce arbitrarily long ones.

That is the degree problem in plain words. It is the reason we cannot use $\mathbb{Z}_q[X]$ as the home for the cryptographic objects. We need a way to "fold" higher-degree polynomials back down into a fixed range, the same way modular arithmetic folds large integers back into $\{0, 1, \ldots, n-1\}$.

The fix is exactly analogous to what we did with the integers: introduce a modulus and reduce. For integers, the modulus was a positive integer $n$, and reduction kept the answer in $\{0, 1, \ldots, n-1\}$. For polynomials, the modulus is itself a polynomial, traditionally called $f(X)$, and reduction by $f(X)$ keeps the answer's degree strictly below the degree of $f$.

The next note builds that idea up properly. The key new word is quotient ring, the construction $\mathbb{Z}_q[X] / (f(X))$, which is what the slash in $R_q$ is doing. The particular choice of $f(X)$ that ML-KEM and ML-DSA use is $f(X) = X^n + 1$, with $n = 256$. The reduction rule that comes out of that choice is striking: every $X^n$ becomes $-1$. We will see why this is so clean in the next note, and why the resulting ring is the right home for lattice cryptography.

07.A short exercise

Compute the following in $\mathbb{Z}_5[X]$.

1. $(X + 2) + (X + 3)$. Slot-by-slot: $X$ column $2$, constant $5 \equiv 0$. Answer: $2X$.
2. $(2X + 1)(3X + 4)$. Pairs: $6X^2$, $8X$, $3X$, $4$. Reduce: $X^2$, $3X$, $3X$, $4$. Group: $X^2 + 6X + 4 \equiv X^2 + X + 4 \pmod 5$.
3. The degree of $(X^3 + X)(X^2 + 1)$ in $\mathbb{Z}_5[X]$. Both factors are non-zero, leading coefficients are $1$ and $1$, so the leading term of the product is $X^5$. Degree $5$.

Doing a few of these by hand is the cheapest way to make the rules feel routine before the abstraction starts piling up in the next note.