Why Multiplication Is the Bottleneck

Before building a fast algorithm it is worth being precise about what is slow and by how much. This note counts.

01.Counting schoolbook multiplication

Multiply two polynomials of degree less than $n$ the way Chapter 1 did it. Every coefficient of the first must meet every coefficient of the second, so the number of coefficient multiplications is

$$n \times n \;=\; n^2 .$$

There are additions too, and a reduction step afterwards to fold degrees $n$ and above back down using $X^n = -1$, but those are cheap by comparison. The $n^2$ multiplications are the cost.

Put the deployed number in. With $n = 256$,

$$256^2 \;=\; 65{,}536$$

coefficient multiplications, for one product of two polynomials.

02.How often that happens

One product would not matter. The trouble is how many there are.

From Module-LWE, generating the public key means computing $A\mathbf{s}$, where $A$ is $k \times k$ and $\mathbf{s}$ has $k$ entries. That is $k^2$ ring multiplications. For ML-KEM-768, with $k = 3$, that is nine.

Encapsulation and decapsulation each perform a similar number. So a single ML-KEM operation involves on the order of ten to twenty ring multiplications, each of them $65{,}536$ coefficient multiplications by the schoolbook method. That is around a million multiplications per operation, every one of them followed by a reduction modulo $q$.

A web server completing thousands of handshakes per second cannot afford that, and a small embedded device cannot afford it at all. Elliptic-curve key exchange, the thing being replaced, costs far less. If lattice schemes were to be adopted at all, this number had to come down.

03.What has to be beaten

Restating the target precisely. We want to compute

$$c(X) \;=\; a(X) \cdot b(X) \bmod (X^n + 1)$$

in substantially fewer than $n^2$ coefficient multiplications.

The answer is about $n \log_2 n$, which at $n = 256$ means roughly $2{,}000$ rather than $65{,}536$. Accounting honestly for the two forward transforms and one inverse transform that the method actually needs, the real figure is around $3{,}300$, still a factor of about twenty.

A factor of twenty is the difference between these schemes being deployable and not.

04.Where the idea comes from

The method is not new mathematics. It is the Fast Fourier Transform, discovered by Gauss around 1805, forgotten, and rediscovered by Cooley and Tukey in 1965. It is the algorithm behind digital audio, image compression, and radio.

The classical FFT works with complex numbers, specifically with the complex roots of unity $e^{2\pi i / n}$. Those are unavailable here. Everything in $R_q$ lives in $\mathbb{Z}_q$, where there is no $i$, no exponential function, and no continuum.

The Number Theoretic Transform is what you get when you carry out the same construction using roots of unity that exist inside $\mathbb{Z}_q$. The structure of the algorithm is identical. Only the arithmetic changes, and it changes in a direction that suits hardware, since integer multiplication modulo a small prime is far cheaper to build than floating-point complex multiplication.

The next two notes build the idea in the order it needs to be built. First the observation that makes fast multiplication possible at all, which has nothing to do with roots of unity. Then the question of where to find suitable evaluation points inside a finite field.