Kyber (ML-KEM) and Dilithium (ML-DSA) encrypt and sign by repeatedly multiplying polynomials in the ring Rq = ℤq[x] / (xⁿ+1) — coefficients mod a prime q, exponents wrapped so that xⁿ ≡ −1 (a negacyclic ring). Multiplying two such polynomials the schoolbook way costs O(n²) modular multiplications:
c_k = Σ a_i·b_j (i+j=k, mod q) − Σ a_i·b_j (i+j=k+n, mod q)
The Number Theoretic Transform turns multiplication into a modular DFT: evaluate a(x) and b(x) at n roots of a "twisted" 2n-th root of unity ψ (mod q), multiply the evaluations point-by-point in O(n), then transform back:
â_k = NTT(a·ψⁱ) b̂_k = NTT(b·ψⁱ)
ĉ_k = â_k · b̂_k (mod q) ← pointwise, O(n)
c = ψ⁻ⁱ · INTT(ĉ) / n
The forward/inverse transforms themselves use the same Cooley-Tukey butterfly recursion as the FFT, so each costs O(n log n) instead of O(n²). This is exactly why q = 3329 in real Kyber and n = 256: NTT multiplication is the one trick that makes lattice-based key exchange fast enough to replace RSA and ECC at internet scale — the same convolution, computed a smarter way. This simulator uses a small demo ring (q = 97, n up to 16) so every intermediate value is visible, but the algorithm is the real Cooley-Tukey NTT, verified live against the schoolbook result.
- Top lane — polynomial a(x), then its NTT domain â, then a fading twin during the final inverse pass.
- Middle lane — polynomial b(x), then b̂, silent during the inverse pass (b is not needed again).
- Bottom lane — appears once the pointwise product ĉ exists, then becomes the final result c(x) = a(x)·b(x) mod (xⁿ+1, q).