Number Theoretic Transform: Fast Polynomial Multiplication over Finite Fields
In a finite field modulo a prime $p$, a primitive root of unity of order $n$ exists if $n$ divides $p-1$. Let $g$ be a primitive root modulo $p$. The $n$-th root of unity $\zeta_n$ is defined as: $$\zeta_n = g^{(p-1)/n} \mod p$$ Key properties analogous to complex roots of unity: $\zeta_{2n}^2 = \ze...