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...
Complex Number Fundamentals Representations A complex number $z$ admits three canonical forms: Cartesian: $z = a + bi$, where $i^2 = -1$ Polar: $z = r(\cos\theta + i\sin\theta)$, with $r = |z|$ and $\theta = \arg(z)$ Euler: $z = re^{i\theta}$ via Taylor expansion equivalence De Moivre's Theorem For...
Polynomial Representations A polynomial $A(x) = \sum_{i=0}^{n-1} a_i x^i$ of degree $n-1$ admits two canonical representations. The coefficient representation stores the vector $[a_0, a_1, \ldots, a_{n-1}]$. Alternatively, the point-value representation consists of $n$ distinct evaluation pairs ${(x...