Number-theoretic transform (${\hat{a}}_j={\sum }_{i=0}^{L-1}{a}_i{\omega }^{ij}$)

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.