## A Probabilistic Approach

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)

Therefore, we obtain (54)

It follows that is a candidate for being a primitive -th root of unity. If is not a primitive -root root of unity then:
• the sequence of the for is periodic, with a period dividing , and
• in particular holds.
Since equals either or , we have the following.

Proposition 5   Let be a prime number and let be integers such that is a power of 2 such that we have . Let different from 0 and . Then, is a primitive -th root of unity if and only if 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.

Marc Moreno Maza
2008-01-07