Computing primitive n mathend000#-th roots of unity

A preliminary step of the FFT-based multiplication is to find primitive n mathend000#-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}$}$ mathend000#.