The Target Ring $R_q$

We have arrived at the construction the chapter has been pointing at. This note assembles all the pieces into a single object, computes a fully worked product inside it, lists the few properties that will matter downstream, and writes down the specific values of $n$ and $q$ that Kyber and Dilithium use.

01.Definition

For a positive integer $n$ and a positive integer $q \ge 2$, the ring $R_q$ is

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

Read this from left to right. Start with the integers modulo $q$, namely $\mathbb{Z}_q = \{0, 1, \ldots, q-1\}$. Form polynomials with coefficients in $\mathbb{Z}_q$, namely $\mathbb{Z}_q[X]$. Quotient by the ideal generated by $X^n + 1$, which means replacing every $X^n$ by $-1$ during arithmetic.

Every element of $R_q$ is represented uniquely by a polynomial of degree strictly less than $n$:

$$a(X) \;=\; a_0 + a_1 X + a_2 X^2 + \cdots + a_{n-1} X^{n-1},$$

where each coefficient $a_i$ lives in $\mathbb{Z}_q$. So an element of $R_q$ is a list of $n$ coefficients, each one a residue in $\{0, 1, \ldots, q-1\}$. The ring $R_q$ has exactly $q^n$ elements.

Two elements are added by adding their coefficient lists slot by slot, with sums reduced modulo $q$. Two elements are multiplied by doing schoolbook polynomial multiplication and then reducing the result modulo $X^n + 1$ using the rule $X^n \equiv -1$.

A small worked product in $R_{17}$ with $n = 4$

Let $n = 4$ and $q = 17$. Elements of $R_{17}$ are polynomials of degree at most $3$ with coefficients in $\{0, 1, \ldots, 16\}$. The reduction rule is $X^4 \equiv -1 \equiv 16 \pmod{17}$.

Take

$$a(X) \;=\; 3 + X + 4 X^2 + 2 X^3, \qquad b(X) \;=\; 1 + X.$$

Step 1. Schoolbook multiplication, ignoring the reduction by $X^n + 1$ for now.

$$a(X) \cdot b(X) \;=\; (3 + X + 4X^2 + 2X^3)(1 + X).$$

Expand each term:

• $3 \cdot 1 = 3$
• $3 \cdot X = 3X$
• $X \cdot 1 = X$
• $X \cdot X = X^2$
• $4X^2 \cdot 1 = 4X^2$
• $4X^2 \cdot X = 4X^3$
• $2X^3 \cdot 1 = 2X^3$
• $2X^3 \cdot X = 2X^4$

Group by power of $X$:

• $X^4$: $2$
• $X^3$: $4 + 2 = 6$
• $X^2$: $1 + 4 = 5$
• $X^1$: $3 + 1 = 4$
• $X^0$: $3$

So before reduction, $a(X) \cdot b(X) = 2X^4 + 6X^3 + 5X^2 + 4X + 3$.

Step 2. Reduce modulo $X^4 + 1$, that is, replace every $X^4$ by $-1$.

$2X^4 = 2 \cdot X^4 \equiv 2 \cdot (-1) = -2$. The rest of the polynomial has degree at most $3$, so it is left alone.

$$a(X) \cdot b(X) \;\equiv\; -2 + 6X^3 + 5X^2 + 4X + 3 \;=\; 6X^3 + 5X^2 + 4X + 1 \pmod{X^4 + 1}.$$

Step 3. Reduce coefficients modulo $17$. None of $6, 5, 4, 1$ exceed $16$, so the answer is already in canonical form:

$$a(X) \cdot b(X) \;=\; 6X^3 + 5X^2 + 4X + 1 \quad \text{in } R_{17}.$$

That is one full multiplication in $R_q$ done by hand. Both reductions (by $X^n + 1$ and by $q$) happen at the end, and you could equally well reduce intermediate values as you go, since reduction commutes with arithmetic. In hardware, reducing as you go keeps the data path narrow.

03.A second worked product, illustrating the negacyclic flip

Stay with $n = 4$, $q = 17$. Take

$$a(X) \;=\; X^3, \qquad b(X) \;=\; X^2.$$

Schoolbook product: $a(X) \cdot b(X) = X^5$.

Reduce modulo $X^4 + 1$: $X^5 = X \cdot X^4 \equiv X \cdot (-1) = -X$. In $\mathbb{Z}_{17}$, the coefficient $-1$ becomes $16$. So the answer is $16 X$, or equivalently $-X$ if you prefer the centred representation $\{-8, \ldots, 8\}$ instead of $\{0, \ldots, 16\}$.

The minus sign is the negacyclic part of the negacyclic ring. If we had quotiented by $X^4 - 1$ instead of $X^4 + 1$, the rule would be $X^4 \equiv +1$, and there would be no sign flip (that is the cyclic case). The choice of $X^n + 1$ over $X^n - 1$ is what makes this ring negacyclic, and it has consequences for the cryptanalysis. The schemes in this book all use $X^n + 1$.

Properties of $R_q$ in the cryptographic sizes

A few properties of $R_q$ are worth stating, since they are what makes the cryptography possible.

$R_q$ is a commutative ring with identity. It inherits its ring structure from $\mathbb{Z}_q[X]$ via the quotient construction. The additive identity is the zero polynomial, and the multiplicative identity is the constant polynomial $1$.

$R_q$ is finite. It has $q^n$ elements. For Kyber's parameters ($n = 256$, $q = 3329$), this is roughly $3329^{256} \approx 2^{2980}$ elements. Each element fits in $n \cdot \lceil \log_2 q \rceil$ bits, which for Kyber is $256 \cdot 12 = 3072$ bits = $384$ bytes. A single $R_q$ element is the natural unit of bandwidth in this cryptography.

$R_q$ is not always a field. Even when $q$ is prime, the polynomial $X^n + 1$ can be reducible (factor non-trivially) over $\mathbb{Z}_q$, in which case $R_q$ is a proper ring, not a field. Whether this is a feature or a bug depends on the use. For Kyber and Dilithium, $X^n + 1$ over $\mathbb{Z}_q$ factors fully into linear factors thanks to a careful choice of $q$, and the factorisation is exactly what makes the Number Theoretic Transform fast.

Multiplication in $R_q$ has structure that hardware can exploit. A naive schoolbook multiplication of two degree-$(n-1)$ polynomials takes $\Theta(n^2)$ coefficient multiplications. The Number Theoretic Transform reduces this to $\Theta(n \log n)$, which for $n = 256$ is the difference between roughly $65{,}000$ and roughly $3{,}300$ coefficient multiplications per product. The NTT is the subject of Chapter 4 and is the central data path of the hardware.

05.NIST parameter sets

The post-quantum standards fix specific values of $n$ and $q$.

Both schemes use $n = 256$. That is a deliberate design choice: a single hardware NTT of length $256$ is enough to serve both schemes, and is the basis of every "unified accelerator" paper in the post-quantum literature. The two values of $q$ differ. Kyber's $q = 3329$ is small enough that a coefficient fits in $12$ bits, which is friendly to small-FPGA deployment. Dilithium's $q = 8\,380\,417$ is larger, requiring $23$ bits per coefficient, but it is still less than a $32$-bit word.

Both moduli are prime, and both satisfy

$$q \;\equiv\; 1 \pmod{n}, \qquad n = 256,$$

since $3329 = 13 \cdot 256 + 1$ and $8\,380\,417 = 32{,}736 \cdot 256 + 1$.

Only one of them satisfies the stronger congruence modulo $2n = 512$, and the difference matters more than anything else on this page. Working it out:

$$8\,380\,417 \;\equiv\; 1 \pmod{512}, \qquad \text{but} \qquad 3329 \;\equiv\; 257 \pmod{512}.$$

The condition $q \equiv 1 \pmod{2n}$ is exactly what a primitive $2n$-th root of unity needs in order to exist in $\mathbb{Z}_q$, and that root is what the fast transform runs on. So ML-DSA gets the complete transform and ML-KEM does not.

That is not a defect in ML-KEM. It is a deliberate trade, and the NTT chapter explains both the workaround and why a modulus small enough to fit a coefficient in twelve bits was judged worth it.

06.Why this ring, not some other

Three properties make $R_q = \mathbb{Z}_q[X] / (X^n + 1)$ the right home for module-lattice cryptography.

The first is compactness. Each $R_q$ element packs $n$ coefficients into a single algebraic object. A vector of $k$ such elements (the secret key in Kyber is such a vector) shrinks key sizes by a factor of $n$ compared to a flat vector of $kn$ scalars. That compactness is what makes lattice cryptography practical at all. RSA keys are around $2{,}000$ to $4{,}000$ bits. Kyber keys are around $10{,}000$ to $25{,}000$ bits. Larger, but not impossibly larger, and that is the difference between deployable and not.

The second is fast multiplication. The NTT exploits the structure of $X^n + 1$ to multiply two $R_q$ elements in $\Theta(n \log n)$ time instead of $\Theta(n^2)$. Without this speedup, the cryptography would be slow enough to be unusable. The NTT lives inside this ring. It does not work for arbitrary polynomial moduli.

The third is security reduction. Deciding whether a given pair $(a, b) \in R_q \times R_q$ has the form $(a, a \cdot s + e)$ for some short secret $s$ and small noise $e$ is conjectured to be as hard as the worst-case Shortest Vector Problem on lattices. This is the Ring-LWE problem, and it is the assumption on which Kyber's security rests. The structure of $R_q$ gives the proof. Switching to a different ring would invalidate the security argument.

These three properties are what the chapter has been building towards. Now that the ring is in hand, the cryptography itself, and the question of why lattices, can be tackled. That is the subject of the remaining chapters.

07.Chapter summary, in three lines

A ring is a set with two compatible operations. The integers modulo a prime form a finite field. Polynomials with coefficients in that field, quotiented by $X^n + 1$, form the ring $R_q$ where Kyber and Dilithium do their work.

If the symbol $R_q = \mathbb{Z}_q[X] / (X^n + 1)$ at the top of this chapter feels different now from how it looked at the start, the chapter has done its job. Chapter 2 explains why lattice-based cryptography exists in the first place: what the public-key cryptography of the last fifty years looked like, what Shor's algorithm broke, and how the NIST competition arrived at module-lattice schemes as the replacement.