PDF Run this chapter's code LaTeX source Comments

Chapter 6Number Theoretic Transform (NTT)

6.1Purpose and scope#

The NTT is a finite-field analogue of a discrete Fourier transform. It changes representation so that structured polynomial multiplication becomes much cheaper. It is an integral part of ML-KEM’s specified arithmetic, not merely an optional optimization [1].

This chapter distinguishes three settings that are often conflated:

1. a cyclic NTT for \(\mathbb{F}_q[x]/(x^n-1)\);

2. a full scalar negacyclic transform for \(\mathbb{F}_q[x]/(x^n+1)\), when a primitive \(2n\)-th root exists; and

3. ML-KEM’s partial NTT, whose output consists of 128 degree-one residues modulo quadratic polynomials.

6.2Roots of unity and the cyclic transform#

If \(\omega\in\mathbb{F}_q\) has multiplicative order \(n\), then evaluation at \[1,\omega,\omega^2,\ldots,\omega^{n-1}\] identifies multiplication modulo \(x^n-1\) with \(n\) scalar products. This requires \(n\mid(q-1)\). The standard radix-2 butterfly network implements this map in \(O(n\log n)\) operations when \(n\) is a power of two.

For the negacyclic quotient \(x^n+1\), scalar evaluation points must be roots of \(x^n+1\), so a primitive \(2n\)-th root is required. The difference is structural, not cosmetic: an algorithm written only for an \(n\)-th root and cyclic convolution is not automatically an ML-KEM algorithm.

6.2.1Finding a root in a toy field#

The nonzero elements of \(\mathbb{F}_{17}\) form a group of order \(16\). If \(g\) is a generator, then \(g^2\) has order \(8\) and can serve as \(\omega\) for an 8-point cyclic NTT. SageMath can check that condition directly:

F = GF(17)
g = F.multiplicative_generator()
omega = g^2
print(omega.multiplicative_order())  # 8

The important test is the multiplicative order, not merely that an element happens to satisfy an isolated power equation. For a coefficient vector \((a_0,\ldots,a_{n-1})\), the cyclic transform records \[\widehat a_i=a(\omega^i)=\sum_{j=0}^{n-1}a_j\omega^{ij},\qquad 0\le i<n.\] The inverse uses \(\omega^{-1}\) and multiplies by \(n^{-1}\), so an NTT is a reversible change of representation, not a lossy sampling operation.

6.3A complete toy cyclic NTT#

The following SageMath program performs a complete forward transform, pointwise product, and inverse transform in the cyclic ring \(\mathbb{F}_{17}[x]/(x^8-1)\). It is intentionally a toy model, not ML-KEM.

q = 17
F = GF(q)
n = 8
g = F.multiplicative_generator()
omega = g^((q - 1)//n)
assert omega.multiplicative_order() == n

def ntt(a):
    return [sum(a[j] * omega^(i*j) for j in range(n)) for i in range(n)]

def intt(A):
    n_inv = F(n)^(-1)
    return [n_inv * sum(A[i] * omega^(-i*j) for i in range(n))
            for j in range(n)]

a = vector(F, [1, 2, 3, 0, 0, 0, 0, 0])
b = vector(F, [4, 5, 0, 0, 0, 0, 0, 0])
A, B = ntt(a), ntt(b)
c = vector(F, intt([A[i]*B[i] for i in range(n)]))
print(c)                 # (4, 13, 5, 15, 0, 0, 0, 0)  (22 = 5 in GF(17))
print(intt(ntt(a)) == list(a))  # True

The code evaluates at powers of the actual primitive root omega, uses an inverse transform, and checks reconstruction. It therefore demonstrates an NTT, unlike evaluation at the unrelated points \(0,1,\ldots,n-1\).

6.3.1Following one product through the transform#

For the input polynomials \(a(x)=1+2x+3x^2\) and \(b(x)=4+5x\), direct multiplication gives \(4+13x+22x^2+15x^3\). The program computes the same result in four conceptual steps:

1. evaluate \(a\) at \(1,\omega,\ldots,\omega^7\);

2. evaluate \(b\) at the same points;

3. multiply the eight pairs of values; and

4. apply the inverse transform to obtain \((4,13,22,15,0,0,0,0)\).

Because the toy ring is modulo \(x^8-1\) and the product has degree below eight, no visible wrap-around occurs. Higher-degree terms would wrap cyclically, not negacyclically.

6.4Butterflies and complexity#

The direct code is intentionally transparent, but it evaluates every output from every input and therefore takes \(O(n^2)\) field operations. A practical radix-2 NTT uses butterflies to reuse work, by the same divide-and-conquer recursion Cooley and Tukey published for the DFT [2]. A butterfly combines two values \(u\) and \(v\) using a twiddle factor \(\omega^k\): \[(u,v)\longmapsto(u+\omega^k v,\;u-\omega^k v).\] There are \(\log_2n\) stages and \(O(n)\) work per stage, giving \(O(n\log n)\) operations.

6.5Why ML-KEM is different#

ML-KEM uses \(q=3329\) and \(n=256\). Since \[q-1=3328=2^8\cdot13,\] there are primitive \(256\)-th roots in \(\mathbb{Z}_{3329}\), but no primitive \(512\)-th roots. In particular, \(x^{256}+1\) does not split into 256 linear factors. With \(\zeta=17\), a primitive 256-th root, FIPS 203 gives the factorization \[x^{256}+1=\prod_{i=0}^{127}\left(x^2-\zeta^{2\operatorname{BitRev}_7(i)+1}\right).\] Consequently, the ML-KEM NTT is an isomorphism from \[R_q=\mathbb{Z}_{3329}[x]/(x^{256}+1)\] to a product of 128 quadratic residue rings, not to 256 scalar evaluation values [1, sec. 4.3].

6.5.1The three-level mental model#

6.6Multiplication in the ML-KEM NTT domain#

Each NTT-domain coordinate is represented by two coefficients, \(a_0+a_1X\), reduced modulo \(X^2-\gamma\). For two such residues, multiplication is \[(a_0+a_1X)(b_0+b_1X)\bmod(X^2-\gamma) = (a_0b_0+a_1b_1\gamma)+(a_0b_1+a_1b_0)X.\] FIPS 203’s MultiplyNTTs applies this base-case multiplication to each of the 128 coordinate pairs. Thus “pointwise multiplication” is accurate only if each point is understood as a quadratic component; it is not 256 independent scalar multiplications.

The forward and inverse transforms themselves use butterfly networks and precomputed twiddle factors, as specified by FIPS 203. Their implementation details are deliberately not reconstructed here from a generic radix-2 routine: a conforming implementation must follow the standard’s algorithms, bounds, and test vectors.

6.7Practical implementation checklist#

Before treating an NTT implementation as an ML-KEM implementation, verify all of the following.

• The coefficient ring is \(\mathbb{Z}_{3329}[x]/(x^{256}+1)\), not a cyclic substitute.

• The forward and inverse transforms follow the specified ordering and twiddle factors.

• NTT-domain multiplication operates on 128 pairs with the appropriate quadratic modulus.

• Modular reduction, serialization, sampling, and bounds follow FIPS 203 in addition to the transform itself.

• The implementation is checked against official known-answer tests and is engineered for its required side-channel model.

This checklist explains why a short classroom transform is valuable for intuition but must not be described as a complete implementation of ML-KEM.

6.8Summary#

An NTT is not simply “evaluate a polynomial at several integers.” It is a structured transform at roots of unity, together with its inverse. A cyclic transform uses \(x^n-1\); a full scalar negacyclic transform needs a primitive \(2n\)-th root. ML-KEM uses neither simplified picture directly: its partial NTT maps \(R_q\) to 128 quadratic components and multiplies them with base-case quadratic products.

References