A Probabilistic Approach

We explain in this section a simple probabilistic approach for computing primitive $n$ -roots of unity in ${\mbox{${\mathbb{Z}}$}}/p{\mbox{${\mathbb{Z}}$}}$ . Of course, we assume that $n$ divides $p-1$ . Hence, there exists an integer $q$ such that $p = q n + 1$ holds. According to little Fermat's theorem, for all ${\alpha} \in {\mbox{${\mathbb{K}}$}}$ , with ${\alpha} \neq 0$ and ${\alpha} \neq 1$ , we have

$${\alpha}^{p-1} = 1.$$ (53)

Therefore, we obtain

$${\alpha}^{q n} = 1.$$ (54)

It follows that ${\alpha}^{q}$ is a candidate for being a primitive $n$ -th root of unity. If ${\alpha}^{q}$ is not a primitive $n$ -root root of unity then:

• the sequence of the ${\alpha}^{q k}$ for $k = 0, \ldots, n-1$ is periodic, with a period dividing $n$ , and
• in particular ${\alpha}^{q n /2 } = 1$ holds.

Since ${\alpha}^{q n /2 }$ equals either $1$ or $-1$ , we have the following.

Proposition 5   Let $p > 2$ be a prime number and let $n, q$ be integers such that $n$ is a power of 2 such that we have $p = n q + 1$ . Let ${\alpha} \in {\mbox{${\mathbb{Z}}$}}/p{\mbox{${\mathbb{Z}}$}}$ different from 0 and $1$ . Then, ${\alpha}^{q}$ is a primitive $n$ -th root of unity if and only if ${\alpha}^{q n /2 } = -1$ 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.