Lecture 2: The Number Theoretic Transform (NTT)

The cost problem

Where we stopped

• Our running example in $\mathbb{Z}_{17}[x]/(x^4+1)$: $$a = 1 + 2x + 3x^2 + 4x^3, \qquad b = 5 + 6x + 7x^2 + 8x^3$$ $$a \cdot b = \Out{12 + 15x + 2x^2 + 9x^3}$$
• Schoolbook: multiply every pair, collect, fold back with $x^4 = -1$, reduce mod 17.
• The cost is $n^2$ multiplications:

You have seen this kind of trick before

• Each time, a change of representation makes the expensive step cheap.
• NTT stands for Number Theoretic Transform. It is the FFT, done with integers mod $q$ instead of complex numbers.

Evaluate, multiply, go back

A polynomial is also its values

• Two points fix a line. Three points fix a parabola.
• In general, a polynomial with $n$ coefficients is fixed by its values at $n$ different points.
• So we can store $a$ in two ways:

• Check one: $a(2) = 1 + 2\cdot 2 + 3 \cdot 4 + 4 \cdot 8 = 49 = 2 \cdot 17 + 15$.

Multiplying values is cheap

• If $c = a \cdot b$, then at any point $r$: $c(r) = a(r) \cdot b(r)$.
• One multiplication per point, so $n$ multiplications in total.

• What remains is to make the two conversions cheap: the NTT and its inverse.

The wrap-around needs special points

• The product in $\Rq$ is folded with $x^4 = -1$. A random point $r$ does not know about the fold.
• Unless the point itself satisfies $r^4 = -1$. Then, at that point: $$r^4 = -1, \qquad r^5 = -r, \qquad r^6 = -r^2$$ exactly the fold rule from Lecture 1.

• For $q = 17$, $n = 4$ we need four numbers with $r^4 \equiv 16$. Do they exist?

Powers of 2 mod 17

• $2^4 = 16 = -1$ and $2^8 = 1$, so the powers of $\zeta = 2$ go around a circle of 8.

• $\zeta$ is a primitive $2n$-th root of unity: $\zeta^{2n} = 1$ and $\zeta^{n} = -1$.
• Check one point: $8^4 = 4096 = 240 \cdot 17 + 16 \equiv -1 \pmod{17}$.

The idea, checked on numbers

• Evaluate $a$ and $b$ at the four points, multiply, and compare with $c = 12 + 15x + 2x^2 + 9x^3$:

• Every row matches. Four multiplications gave the values of the product.
• The values $(3, 6, 3, 2)$ fix $c$. Getting the coefficients back from them is the inverse NTT.

Definition of the NTT

• Toy: $\NTT(a) = (a(2), a(8), a(15), a(9)) = (15, 13, 11, 16)$, in some order.
• Done directly, each value costs $n$ multiplications, and there are $n$ values: $n^2$ again.

A fast NTT

Split the problem in half

• Since $4^2 = 16 = -1$: $$x^4 + 1 = (x^2 - 4)(x^2 + 4) \pmod{17}$$
• The four points split into two pairs:
  • $2$ and $15$ are the roots of $x^2 - 4$ ($2^2 = 4$, $15^2 = 225 \equiv 4$)
  • $8$ and $9$ are the roots of $x^2 + 4$ ($8^2 = 64 \equiv 13 = -4$, $9^2 = 81 \equiv 13$)
• Plan: first reduce $a$ mod $x^2 - 4$ and mod $x^2 + 4$. Each half has only 2 coefficients and is responsible for 2 of the points.

Reducing mod $x^2 - c$ is one line

• Write $a = (a_0 + a_1 x) + x^2 (a_2 + a_3 x)$ and replace $x^2$ by $c$ or by $-c$:

• Both results reuse the same products $4 \cdot 3$ and $4 \cdot 4$: two multiplications for the whole step.

The butterfly

• The pattern "$u + w\cdot v$ and $u - w\cdot v$" is called a Cooley-Tukey butterfly. $w$ is the twiddle factor.

• One multiplication, one addition, one subtraction, all mod $q$.

Split again until single numbers remain

• $x^2 - 4 = (x - 2)(x + 2)$ and $x^2 + 4 = (x - 8)(x + 8)$. Reducing $u + vx$ mod $x - r$ gives $u + r\,v$, the value at $r$.

• $13 + x \rightarrow 13 \pm 2 = 15, 11$ $6 + 3x \rightarrow 6 \pm 8\cdot 3 = 30, -18 \equiv 13, 16$

The same steps on an array

• In code, $a$ is one array that is updated in place, one stage at a time. Same colour, same butterfly.

• 4 multiplications in total, against 16 for direct evaluation.

Your turn: $\NTT(b)$

• Compute $\NTT(b)$ for $b = (5, 6, 7, 8)$ with the same stages: $w = 4$, then $w = 2$ and $w = 8$.

Bigger $n$, deeper tree

• $n = 8$: three levels of splits. Each level is one stage of 4 butterflies; the chips are the twiddles.

• Every stage touches every coefficient once: $n/2$ butterflies per stage.

Counting the work

• Each split halves the problem, and 256 halves down to 1 in only 8 steps.

Why the output order looks shuffled

• The fast NTT returned $(a(2), a(15), a(8), a(9))$, which is $(a(\zeta^1), a(\zeta^5), a(\zeta^3), a(\zeta^7))$.
• Output $i$ is the value at $\zeta^{2\,\mathrm{brv}(i) + 1}$, where $\mathrm{brv}$ reverses the bits of $i$:

• The order does not matter. Pointwise multiplication treats every position alike, and the inverse NTT puts things back.

Twiddle factors are a fixed table

• The twiddles depend only on $n$, $q$ and $\zeta$, so they are computed once and stored. Block $k$ uses $\zeta^{\mathrm{brv}(k)}$.

• Software keeps them in a constant array, hardware in a small ROM next to the multiplier.

The whole forward NTT in code

def ntt(a, q, zetas):
    n = len(a)
    k = 1
    length = n // 2
    while length >= 1:
        for start in range(0, n, 2*length):
            w = zetas[k]
            k += 1
            for j in range(start, start+length):
                t = w * a[j+length] 
                a[j+length] = (a[j] - t) 
                a[j] = (a[j] + t) 
        length //= 2
    return a

Going back: the inverse NTT

Undoing one butterfly

• The forward butterfly gave $u' = u + w v$ and $v' = u - w v$. Add and subtract: $$u' + v' = 2u, \qquad u' - v' = 2wv$$
• So $u = (u' + v')/2$ and $v = (u' - v') \cdot w^{-1} / 2$.

• This is the Gentleman-Sande butterfly. The halves pile up, one per stage, so we divide by $n$ once at the end.

The inverse NTT on numbers

• Inverse twiddles mod 17: $2^{-1} = 9$, $8^{-1} = 15$, $4^{-1} = 13$. The stages run in reverse order.

The full pipeline

Is it really faster?

• Count every multiplication: $3 \cdot \frac{n}{2}\log_2 n + 2n$, against $n^2$ for schoolbook.

• Our toy is too small to profit. The win grows with $n$, and $n = 256$ is in the profitable range.

The NTT in ML-DSA and ML-KEM

When does a good $\zeta$ exist?

• ML-KEM picked a small $q$ to keep keys short, and pays for it with a slightly different NTT.

ML-DSA: the full NTT

• $n = 256$, $q = 8380417$, $\zeta = 1753$, with $1753^{256} \equiv -1 \pmod q$.
• 8 stages of 128 butterflies, all the way down to single numbers.
• Pointwise product: 256 multiplications, $\hat c_i = \hat a_i \cdot \hat b_i \bmod q$.

ML-KEM: stop one stage early

• Without a 512th root, the last split cannot happen. ML-KEM runs 7 stages and stops at pieces of degree 1.
• Toy version: stop after stage 1.

• ML-KEM ends with 128 pieces $\hat a_{2i} + \hat a_{2i+1} x$, each reduced mod $x^2 - \gamma_i$.

Multiplying two degree-1 pieces

• One inverse stage on $(3, 0, 4, 13)$ gives $(7, 13, 4, 1)$. Times $2^{-1} = 9$: $\Out{(12, 15, 2, 9)}$ again.
• Cost per piece: 5 multiplications.

ML-KEM in numbers

• $\gamma_i = 17^{2\,\mathrm{brv}(i) + 1} \bmod 3329$, a second fixed table: $17, -17, 2761, -2761, \dots$

• Same total as ML-DSA by coincidence: one stage less, but a more expensive pointwise step.

Stay in the NTT domain

• The schemes avoid converting back and forth:
  • The matrix $\Pub{\mathbf{A}}$ is random anyway, so it is generated directly as NTT values.
  • The secret $\mathbf{s}$ is transformed once and reused in all $k$ rows.
  • Only the final results go through the inverse NTT.

Summary

Summary