Chapter 4: Ring-LWE, Module-LWE, and the Number Theoretic Transform

01.What this chapter is for

Chapter 3 ended by saying that plain Learning With Errors needs megabyte keys, that replacing vectors with elements of $R_q$ fixes that, and that multiplication in $R_q$ has a fast algorithm. It then declined to give any of the details.

This chapter gives them. It defines Ring-LWE and Module-LWE properly, and then spends most of its length on the fast multiplication algorithm, which is called the Number Theoretic Transform.

The NTT deserves that space for a reason that has nothing to do with elegance. It is where implementations spend most of their time. A profile of ML-KEM shows the transform and its inverse dominating everything else, which makes it the thing worth optimising in software and the thing worth building in silicon. Every hardware accelerator for these schemes is, at its core, an NTT engine with support circuitry around it.

By the end you should be able to compute a small NTT by hand, multiply two polynomials through it, and explain why ML-KEM cannot use the full version of the algorithm.

02.Who this is written for

The same reader as the earlier chapters, with one addition. This is the first chapter where the pace of the arithmetic picks up, because there is genuinely more of it. Nothing beyond Chapter 1 is assumed, and in particular no signal processing, no Fourier analysis, and no complex numbers are needed. The Fast Fourier Transform is mentioned as a relative of the NTT, and the chapter does not depend on you having met it.

What is assumed is comfort with polynomial multiplication in $R_q$, which was built in The Target Ring. If the rule $X^n = -1$ and the sign flip it causes are not yet automatic, reread that note first. Everything here rests on it.

03.Reading order

1. Ring-LWE. The definition, and a worked demonstration that one ring sample carries as much as $n$ plain samples.
2. Module-LWE. The middle setting the standards actually use, and the parameter sets.
3. Why Multiplication Is the Bottleneck. Counting the cost of schoolbook multiplication and seeing what needs to be beaten.
4. Evaluation and Interpolation. The one idea the whole transform rests on: multiplying polynomials is cheap if you store them the right way.
5. Roots of Unity in a Finite Field. Where the evaluation points come from when there are no complex numbers available, and the divisibility condition that decides whether a given $q$ can support the transform at all.
6. The Negacyclic NTT. The definition, and a complete length-4 transform over $\mathbb{F}_{17}$ computed by hand, including the multiplication cross-check.
7. The Butterfly and Bit Reversal. How the $n^2$ evaluation becomes an $n \log n$ network, with all four butterflies of the length-4 example written out.
8. The Parameters the Standards Actually Use. The actual roots used by ML-KEM and ML-DSA, and why one of them cannot run the algorithm this chapter just built.
9. Implementation Axes, and the Chapter Summary. What an implementer or a hardware designer decides after all of the above, and the chapter summary.

04.A note on the worked example

One example runs through the whole chapter: $q = 17$, $n = 4$, transforming the polynomial $a(X) = 3 + X + 4X^2 + 2X^3$. It is small enough that every step can be checked with a pencil, and it reappears in later chapters.

It is worth knowing in advance that this example demonstrates the algorithm and not its benefit. At $n = 4$, going through the transform costs about the same as schoolbook multiplication, so the fast method saves nothing. The crossover happens well above $4$. At the deployed $n = 256$ the schoolbook route costs about $65{,}000$ coefficient multiplications and the transform route about $3{,}300$, which is where the factor of twenty that makes these schemes practical actually comes from.