← Back to Chapter 9, The number theoretic transform

Negacyclic-NTT butterfly, end to end

Step the negacyclic number theoretic transform at the chapter's (n, q, ψ) = (4, 17, 2). Pre-twist by powers of ψ, run the radix-2 Cooley-Tukey butterflies, multiply the spectra pointwise, and invert. The product lands on the chapter's verified schoolbook result [15, 16, 10, 4].