= Number-theoretic transform
{title2=$\widehat a_j=\sum_{i=0}^{L-1}a_i\omega^{ij}$}
= NTT
{c}
{synonym}
A number-theoretic transform is a <discrete Fourier transform> computed in <modular arithmetic>. In a <finite field> with $p$ elements, choose a <primitive root of unity> $\omega$ of order $L$ dividing $p-1$. The transform above is inverted using $\omega^{-1}$ and $L^{-1}$. With sufficient zero padding, it computes <polynomial> products exactly modulo $p$, avoiding <floating-point arithmetic> rounding.
Back to article page
