NTT: Fast Polynomial Multiplication for Lattice Crypto (2D)

Ring size n

Run

Animation speed 1.0×

Current Stage

Ready.

Live Readouts

Modular ops so far

0 / 0

Modulus q

NTT result vs. naive O(n²) convolution

—

How it works

Kyber (ML-KEM) and Dilithium (ML-DSA) encrypt and sign by repeatedly multiplying polynomials in the ring R_q = ℤ_q[x] / (xⁿ+1) — coefficients mod a prime q, exponents wrapped so xⁿ ≡ −1 (a negacyclic ring). The naive way costs O(n²) modular multiplications — every coefficient of a against every coefficient of b. The Number Theoretic Transform turns that convolution into three O(n)/O(n log n) steps: 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 with the inverse NTT:

â = NTT(a·ψⁱ)     b̂ = NTT(b·ψⁱ)
ĉ = â · b̂  (mod q)      ← pointwise, O(n)
c = ψ⁻ⁱ · INTT(ĉ) / n

The forward/inverse transforms use the Cooley-Tukey butterfly recursion — a bit-reversal permutation followed by log₂(n) passes, each combining pairs of values with a twiddle factor w. That is exactly what the diagram on the right draws: one column per pass, nodes are coefficients, crossing lines are butterflies. This page implements the NTT completely from scratch (real modular exponentiation, real butterfly loops, no BigInt/FFT library) and cross-checks every result against a direct O(n²) convolution computed independently.

Node color/height — the coefficient's value mod q.
Highlighted column — the current butterfly pass.
Right strip — a(x)/b(x) inputs, â/b̂ transform domain, ĉ pointwise product, c(x) final result.

Real timing benchmark

Runs the same from-scratch NTT and a direct O(n²) negacyclic convolution at increasing polynomial degree n, timed with performance.now() in this browser. Uses a second NTT-friendly prime (q = 12289, the modulus from the original NTRU/Kyber-round-1 proposals) so n can grow past 16.

Status

Idle

Modulus q

12289

Results

n will appear here after running.

Op counts are exact (schoolbook = n², NTT counted per modular multiply/add in the butterfly loops). Times are wall-clock milliseconds for one run at each n — small-n numbers are noisy (sub-millisecond), the crossover and the growing gap at large n are the real signal.

⚠ Couldn't drawCanvas 2D context unavailable in this browser.

NTT: Fast Polynomial Multiplication for Lattice Cryptography (2D Butterfly View)