Number-Theoretic Transform — Iterative Butterfly over a Small Prime

NTT = FFT in Z/pZ. Watch bit-reversal → butterfly stages with root ω = g(p-1)/n → pointwise multiply → inverse NTT → n-1 scaling, all exact integers mod a small NTT-friendly prime.

step 0

Working array A

coefficients of a (padded to n)

Working array B

coefficients of b (padded to n)
butterfly lower (u) butterfly upper (v) combined / active

Transform parameters & result

Result C (product coefficients)

filled after the inverse transform
Press Step to begin. We multiply two polynomials mod a small NTT-friendly prime using the iterative NTT: bit-reversal, butterfly stages, pointwise product, inverse, then scaling by n-1.
Self-contained visualization. Counting is exact integer arithmetic mod the chosen prime p = c·2k+1; the root is ω = g(p-1)/n mod p. The butterfly (u + ωjv, u − ωjv) is the same as in 15-divide-and-conquer/05-fft; here every operation is modular. See junior.md, middle.md, and professional.md for the math.