The Negacyclic NTT

Everything is now in place. This note states the transform, computes one completely by hand, and checks that it does what it is supposed to do.

01.The definition

Assume $2n$ divides $q - 1$, and let $\zeta$ be a primitive $2n$th root of unity in $\mathbb{F}_q$.

For $a(X) = a_0 + a_1 X + \cdots + a_{n-1}X^{n-1}$ in $R_q$, the negacyclic NTT is

$$\hat{a}_k \;=\; a\bigl(\zeta^{2k+1}\bigr) \;=\; \sum_{j=0}^{n-1} a_j \, \zeta^{(2k+1)j}, \qquad k = 0, 1, \ldots, n-1 .$$

Read it as what it is: evaluate the polynomial at each of the $n$ odd powers of $\zeta$. Nothing more.

The inverse recovers the coefficients:

$$a_j \;=\; \frac{1}{n} \, \zeta^{-j} \sum_{k=0}^{n-1} \hat{a}_k \, \zeta^{-2jk} .$$

The $\zeta^{-j}$ factor out front is the fingerprint of the negacyclic version. An ordinary inverse DFT has only the $1/n$ and the sum. That extra twist is what undoes the odd-power evaluation grid.

02.A complete worked transform

Take $q = 17$, $n = 4$, $\zeta = 2$, and the evaluation grid $(2, 8, 15, 9)$ from Roots of Unity in a Finite Field.

Transform

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

At $X = 2$. Powers: $2^2 = 4$, $2^3 = 8$.

$$3 + 1 \cdot 2 + 4 \cdot 4 + 2 \cdot 8 \;=\; 3 + 2 + 16 + 16 \;=\; 37 \;\equiv\; 3 \pmod{17},$$

since $37 = 2 \cdot 17 + 3$.

At $X = 8$. Reduce the powers first: $8^2 = 64 \equiv 13$, and $8^3 \equiv 8 \cdot 13 = 104 \equiv 2$, since $104 = 6 \cdot 17 + 2$.

$$3 + 1 \cdot 8 + 4 \cdot 13 + 2 \cdot 2 \;=\; 3 + 8 + 52 + 4 \;=\; 67 \;\equiv\; 16 \pmod{17} .$$

At $X = 15$. Easier as $15 \equiv -2$. Then $15^2 \equiv 4$ and $15^3 \equiv -8 \equiv 9$.

$$3 + 1 \cdot (-2) + 4 \cdot 4 + 2 \cdot 9 \;=\; 3 - 2 + 16 + 18 \;=\; 35 \;\equiv\; 1 \pmod{17} .$$

At $X = 9$. As $9 \equiv -8$: $9^2 \equiv 64 \equiv 13$, and $9^3 \equiv 9 \cdot 13 = 117 \equiv 15 \equiv -2$.

$$3 + 1 \cdot 9 + 4 \cdot 13 + 2 \cdot (-2) \;=\; 3 + 9 + 52 - 4 \;=\; 60 \;\equiv\; 9 \pmod{17} .$$

So

$$\hat{a} \;=\; (3,\; 16,\; 1,\; 9).$$

03.Checking that it multiplies

The claim to verify is that pointwise multiplication in the transformed domain corresponds to negacyclic multiplication in $R_q$.

Take a second polynomial, $b(X) = 1 + X$, so $b = (1, 1, 0, 0)$. Evaluating at the same four points:

$$b(2) = 3, \qquad b(8) = 9, \qquad b(15) = 1 + 15 = 16, \qquad b(9) = 10 .$$

So $\hat{b} = (3, 9, 16, 10)$.

Multiply pointwise modulo $17$:

$$\hat{a} \odot \hat{b} \;=\; (3 \cdot 3,\; 16 \cdot 9,\; 1 \cdot 16,\; 9 \cdot 10) \;=\; (9,\; 144,\; 16,\; 90) \;\equiv\; (9,\; 8,\; 16,\; 5) \pmod{17},$$

using $144 = 8 \cdot 17 + 8$ and $90 = 5 \cdot 17 + 5$.

Now compute the same product the slow way, directly in $R_{17}$:

$$\begin{aligned} a(X) \cdot b(X) &= (3 + X + 4X^2 + 2X^3)(1 + X) \\ &= 3 + 4X + 5X^2 + 6X^3 + 2X^4 . \end{aligned}$$

The $X^4$ term must be reduced. In $R_q$ the rule is $X^4 = -1$, so $2X^4$ becomes $-2$, and it lands on the constant coefficient:

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

So the coefficient list is $(1, 4, 5, 6)$.

Transform that directly and see whether it agrees. Evaluating $1 + 4X + 5X^2 + 6X^3$ at $X = 2$:

$$1 + 8 + 20 + 48 \;=\; 77 \;\equiv\; 9 \pmod{17},$$

since $77 = 4 \cdot 17 + 9$. That matches the first pointwise product. The remaining three match as well, giving $(9, 8, 16, 5)$ both ways.

The transform is multiplicative. Applying the inverse to $(9, 8, 16, 5)$ returns $(1, 4, 5, 6)$, which is the product.

04.The full multiplication procedure

Collecting it into the recipe an implementation follows:

1. Transform $a$. Cost: one NTT.
2. Transform $b$. Cost: one NTT.
3. Multiply the two transforms pointwise. Cost: $n$ multiplications.
4. Inverse-transform the result. Cost: one inverse NTT.

Three transforms and one cheap pointwise step, replacing $n^2$ coefficient multiplications.

There is a detail worth noting because it changes how real code is organised. Many quantities get multiplied repeatedly. In ML-KEM the public matrix $A$ is used in every operation, so it is stored already transformed and steps 1 through 4 shrink to steps 3 and 4 alone. FIPS 203 in fact specifies the public key in the transformed domain, so the transform never has to be applied to it at all. Keeping data in the NTT domain for as long as possible is one of the main structural optimisations in every implementation.

05.What this cost

Being honest about the running example: it saved nothing.

Direct evaluation at four points, with four coefficients each, is $16$ multiplications. Schoolbook multiplication of two length-$4$ polynomials is also $16$. At $n = 4$ the transform is a demonstration, not an improvement.

The saving requires two things that $n = 4$ does not provide. The transform has to be computed by the fast recursive method rather than by direct evaluation, which is the next note. And $n$ has to be large enough for $n \log n$ to beat $n^2$ by a worthwhile margin.

At $n = 256$ it does. Schoolbook is $65{,}536$ multiplications. The three-transform route is about $3{,}300$. That is the factor of twenty, and it only appears once the transform itself stops costing $n^2$.