negacyclic-ntt.md

negacyclic NTT: fast ring multiplication multiplication in R_q = F_p[x]/(x^n+1) is the critical bottleneck in lattice cryptography. naive polynomial multiplication is O(n^2). the negacyclic NTT reduces this to O(n log n) — and more importantly, to exactly 3n field multiplications for a full ring…