We explain in this section a simple probabilistic approach for computing primitive -roots of unity in . Of course, we assume that divides . Hence, there exists an integer such that holds. According to little Fermat's theorem, for all , with and , we have
This proposition is very easy to implement and provides an efficient way to compute primitive roots of unity in practice. It avoids the construction of tables of primitive roots of unity, which was a usual approach as detailed above.
Marc Moreno Maza