**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
**

(53) |

(54) |

- the sequence of the for is periodic, with a period dividing , and
- in particular holds.

**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.
**

*
*

2008-01-07