Quotient Rings and Ideals

The previous note ended with a problem: polynomial multiplication in $\mathbb{Z}_q[X]$ keeps growing the degree, but cryptography needs the elements to live in a fixed-size space. The fix is the same trick we already used for integers, just lifted to polynomials. With integers we picked a modulus $n$ and worked modulo $n$. With polynomials we pick a polynomial modulus $f(X)$ and work modulo $f(X)$. This note builds that construction up, names the pieces formally (ideals, quotient rings), and shows the worked-example version that the next note will turn into the cryptographic ring $R_q$.

01.Polynomial long division

To reduce one polynomial modulo another we need a notion of "remainder" for polynomials. The algorithm is long division, the same idea you saw for integers in school, but with polynomials in $X$ instead of digits.

A worked example over $\mathbb{Z}$ first, before we add the modular twist. Divide $X^3 + 2X + 5$ by $X^2 + 1$.

Step 1. The leading term of the dividend is $X^3$, and the leading term of the divisor is $X^2$. The quotient term needed to kill $X^3$ is $X^3 / X^2 = X$. So the first quotient term is $X$.

Step 2. Multiply the divisor by this quotient term and subtract:

$$(X^3 + 2X + 5) \;-\; X \cdot (X^2 + 1) \;=\; (X^3 + 2X + 5) - (X^3 + X) \;=\; X + 5.$$

Step 3. The remaining polynomial $X + 5$ has degree $1$, which is strictly less than the divisor's degree $2$. The division terminates.

We have written

$$X^3 + 2X + 5 \;=\; X \cdot (X^2 + 1) \;+\; (X + 5).$$

The quotient is $X$ and the remainder is $X + 5$. Just like integer division: $\text{dividend} = \text{quotient} \cdot \text{divisor} + \text{remainder}$, with the remainder strictly smaller (in degree) than the divisor.

This is the polynomial division algorithm in a nutshell. As long as you are dividing in a ring where the leading coefficient of the divisor is invertible (always true if the divisor is monic, meaning its leading coefficient is $1$), the procedure terminates and produces a unique quotient and remainder with $\deg(\text{remainder}) < \deg(\text{divisor})$.

For our cryptographic application we will only ever divide by polynomials of the form $X^n + 1$. The leading coefficient is $1$, so the division always works and the remainder always has degree strictly less than $n$.

02.Reducing modulo a polynomial

Once we have polynomial division, we have the operation "reduce modulo $f(X)$". For a polynomial $g(X)$ and a polynomial modulus $f(X)$, the reduction $g(X) \bmod f(X)$ is the remainder when $g(X)$ is divided by $f(X)$ using the long-division algorithm.

A small worked example over $\mathbb{Z}_5$. Reduce $X^4 + 2X^2 + 1$ modulo $X^2 + 1$.

Step 1. Leading term of dividend $X^4$, leading term of divisor $X^2$. Quotient term: $X^4 / X^2 = X^2$.

Subtract: $(X^4 + 2X^2 + 1) - X^2 \cdot (X^2 + 1) = (X^4 + 2X^2 + 1) - (X^4 + X^2) = X^2 + 1$.

Step 2. Leading term of remaining $X^2$, divisor still $X^2 + 1$. Quotient term: $X^2 / X^2 = 1$.

Subtract: $(X^2 + 1) - 1 \cdot (X^2 + 1) = 0$.

The remainder is $0$. So $X^4 + 2X^2 + 1 \equiv 0 \pmod{X^2 + 1}$ in $\mathbb{Z}_5[X]$. (You can check this by noting that $X^4 + 2X^2 + 1 = (X^2 + 1)^2$, which is divisible by $X^2 + 1$.)

A second example, where the remainder is non-zero. Reduce $X^3 + X$ modulo $X^2 + 1$ in $\mathbb{Z}_5[X]$.

Quotient term: $X$. Subtract: $(X^3 + X) - X \cdot (X^2 + 1) = (X^3 + X) - (X^3 + X) = 0$.

So the remainder is $0$ here too. Try one more: reduce $X^3 + X^2 + X + 1$ modulo $X^2 + 1$ in $\mathbb{Z}_5[X]$.

Quotient term: $X$. Subtract: $(X^3 + X^2 + X + 1) - X(X^2 + 1) = X^3 + X^2 + X + 1 - X^3 - X = X^2 + 1$.

Now the remaining polynomial is $X^2 + 1$, same degree as the divisor. Quotient term: $1$. Subtract: $(X^2 + 1) - 1(X^2 + 1) = 0$.

So $X^3 + X^2 + X + 1 \equiv 0 \pmod{X^2 + 1}$ as well. (Why? Because $X^3 + X^2 + X + 1 = (X^2 + 1)(X + 1)$, and the divisor cleanly divides it.)

For an example with a non-zero remainder, reduce $2X^3 + 3$ modulo $X^2 + 1$ in $\mathbb{Z}_5[X]$.

Quotient term: $2X$. Subtract: $(2X^3 + 3) - 2X(X^2 + 1) = 2X^3 + 3 - 2X^3 - 2X = -2X + 3 \equiv 3X + 3 \pmod 5$.

The remainder is $3X + 3$, of degree $1$, strictly less than the divisor's degree $2$. Done.

The point of these examples is to show that no matter how big the dividend's degree is, the remainder always has degree strictly less than the divisor's. So if our divisor is $X^n + 1$, every remainder has degree at most $n - 1$, and the polynomial fits in $n$ coefficient slots.

A faster way to reduce modulo $X^n + 1$

Doing long division by hand every time is tedious. There is a much cleaner shortcut for the specific divisor $X^n + 1$.

The equation $X^n + 1 \equiv 0$ rearranges to $X^n \equiv -1$. So when reducing modulo $X^n + 1$, every occurrence of $X^n$ can be replaced by $-1$. Higher powers follow the same rule: $X^{n+1} = X \cdot X^n \equiv -X$, $X^{n+2} \equiv -X^2$, and so on. In general,

$$X^{n+k} \;\equiv\; -X^k \pmod{X^n + 1}, \qquad X^{2n + k} \;\equiv\; X^k \pmod{X^n + 1}.$$

The pattern is "every multiple of $n$ flips sign and starts over." This is called a negacyclic reduction rule, because the wrap-around is accompanied by a sign flip.

Re-do the example $2X^3 + 3$ modulo $X^2 + 1$ using the rule $X^2 \equiv -1$.

$2X^3 = 2X \cdot X^2 \equiv 2X \cdot (-1) = -2X$. So $2X^3 + 3 \equiv -2X + 3 = 3X + 3 \pmod 5$. Same answer as long division gave us, in two lines instead of three.

A second example, with $n = 4$. Reduce $X^5 + X^4 + X + 1$ modulo $X^4 + 1$.

$X^4 \equiv -1$, so $X^5 = X \cdot X^4 \equiv -X$, and $X^4 \equiv -1$. The polynomial becomes $-X + (-1) + X + 1 = 0$. So $X^5 + X^4 + X + 1 \equiv 0 \pmod{X^4 + 1}$.

The negacyclic rule turns the reduction into pure book-keeping: collect every term whose exponent is at least $n$, subtract $n$ from the exponent, flip the sign. This is the rule that the cryptographic NTT hardware will eventually implement.

04.Equivalence classes of polynomials

Two polynomials $g(X)$ and $h(X)$ in $\mathbb{Z}_q[X]$ are congruent modulo $f(X)$, written

$$g(X) \;\equiv\; h(X) \pmod{f(X)},$$

if their difference $g(X) - h(X)$ is divisible by $f(X)$. The set of all polynomials congruent to a fixed $g(X)$ is called the equivalence class of $g(X)$ modulo $f(X)$. Each class has many polynomial representatives, but exactly one of degree strictly less than $\deg f$, namely the remainder $g(X) \bmod f(X)$.

This mirrors the integer case. In $\mathbb{Z}$, two integers are congruent modulo $n$ if their difference is divisible by $n$. In $\mathbb{Z}_q[X]$, two polynomials are congruent modulo $f(X)$ if their difference is divisible by $f(X)$. The residue classes modulo $n$ each had a unique representative in $\{0, 1, \ldots, n - 1\}$. The residue classes modulo $f(X)$ each have a unique representative of degree strictly less than $\deg f$.

The set of equivalence classes, with the natural addition and multiplication inherited from $\mathbb{Z}_q[X]$, is a ring in its own right. That ring is what we are about to give a formal name to.

05.Ideals: the kernel of "divisible by"

The mathematical machinery that makes this construction precise is called an ideal. Defining ideals is short. An ideal of a ring $R$ is a non-empty subset $I \subseteq R$ such that

1. If $a, b \in I$, then $a + b \in I$.
2. If $a \in I$ and $r \in R$, then $r \cdot a \in I$.

The first rule says $I$ is closed under addition. The second is the strong condition: $I$ absorbs multiplication by anything in $R$, not just by elements of $I$.

The key example for us is the principal ideal generated by $f(X)$, written $(f(X))$, which is the set of all multiples of $f(X)$:

$$(f(X)) \;=\; \{\, p(X) \cdot f(X) \,:\, p(X) \in \mathbb{Z}_q[X] \,\}.$$

Closure under addition is clear: $p_1 f + p_2 f = (p_1 + p_2) f$, still a multiple of $f$. Absorption: $r \cdot (p f) = (r p) f$, still a multiple of $f$. So $(f(X))$ is an ideal of $\mathbb{Z}_q[X]$.

Why does this matter? Because the equivalence relation "$g(X) \equiv h(X) \pmod{f(X)}$" is exactly "$g(X) - h(X) \in (f(X))$." The ideal is the set of polynomials we are deciding to call "zero." Two polynomials are equivalent if their difference is in the ideal.

The quotient ring $R / I$

For any ring $R$ and ideal $I$, the quotient ring $R / I$ is the set of equivalence classes of $R$ under the relation "$a \equiv b$ if $a - b \in I$." Addition and multiplication of classes are defined by picking a representative from each class, doing the operation in $R$, and taking the class of the result.

The two ideal axioms are exactly what is needed to make this well-defined. Closure under addition makes "the sum of two classes is the class of their sum" well-defined. Absorption under multiplication does the same for multiplication. Without those properties, you could pick different representatives and get different answers, and the construction would not produce a ring.

Specialised to our case: $\mathbb{Z}_q[X] / (f(X))$ is the ring of equivalence classes of polynomials modulo $f(X)$. Its elements are best represented by their unique low-degree representative: the polynomial of degree strictly less than $\deg f$. Addition and multiplication are computed by doing the operation in $\mathbb{Z}_q[X]$ and then reducing the result modulo $f(X)$.

For the choice $f(X) = X^n + 1$, every element is represented by a polynomial of degree at most $n - 1$. There are exactly $q^n$ such polynomials (each of the $n$ coefficient slots is a residue in $\{0, 1, \ldots, q-1\}$). So $\mathbb{Z}_q[X] / (X^n + 1)$ is a finite ring, with exactly $q^n$ elements. That is the final win: a ring large enough to be cryptographically useful, but small enough that every element fits in a fixed-size object.

Putting it together: the recipe for $R_q$

The construction in three sentences. Start with $\mathbb{Z}_q$, the ring of integers modulo $q$. Lift it to $\mathbb{Z}_q[X]$, the polynomial ring in one variable $X$. Quotient by the ideal $(X^n + 1)$, which means working modulo $X^n + 1$ on every product. The resulting ring is

$$R_q \;=\; \mathbb{Z}_q[X] \,/\, (X^n + 1).$$

The next note unpacks $R_q$ in detail: how to add and multiply inside it, what the negacyclic reduction rule looks like in practice, and what specific values of $n$ and $q$ Kyber and Dilithium use.

08.A short exercise

Compute the following modulo $X^3 + 1$ in $\mathbb{Z}_5[X]$, using the negacyclic shortcut $X^3 \equiv -1$.

1. $X^4 + X + 1$. Replace $X^4 = X \cdot X^3 \equiv -X$. So the polynomial reduces to $-X + X + 1 = 1$.
2. $X^5 + 2X^2$. Replace $X^5 = X^2 \cdot X^3 \equiv -X^2$. So the polynomial reduces to $-X^2 + 2X^2 = X^2$.
3. $X^6 + X^3$. Replace $X^6 = X^3 \cdot X^3 \equiv (-1)(-1) = 1$. And $X^3 \equiv -1$. So $X^6 + X^3 \equiv 1 + (-1) = 0$. The polynomial is divisible by $X^3 + 1$.

The negacyclic rule is the engine that the cryptographic NTT will run inside hardware. Doing a few of these by hand is the right preparation for understanding why the hardware looks the way it does.