NTT and modular arithmetic (statement)

Definition. The NTT computes the discrete Fourier transform over $\mathbb{Z}/p\mathbb{Z}$: $\hat a_k=\sum_j a_j\omega^{jk}$, where $\omega$ is an $n$-th primitive root of unity mod $p$.

Existence of $\omega$. By the structure of $\mathbb{F}_p^*$ (cyclic of order $p-1$), $\mathbb{F}_p^*$ contains an element of order $n$ iff $n\mid p-1$.

Application. Fast polynomial multiplication over $\mathbb{Z}/p\mathbb{Z}$ via NTT with $O(n\log n)$ complexity, used in computer algebra and cryptography.

Conclusion. The NTT requires $p\equiv1\pmod n$; typical choices use $p=k\cdot 2^m+1$.