Computing primitive $n$ -th roots of unity

A preliminary step of the FFT-based multiplication is to find primitive $n$ -th roots of unity. We explain in this section how to compute such numbers in ${\mbox{${\mathbb{K}}$}} = {\mbox{${\mathbb{Z}}$}}/p{\mbox{${\mathbb{Z}}$}}$ .