# Finding a generator of $(\mathbb Z/p\mathbb{Z})^*$

Is there a method for finding a primitive element (generator) of $(\mathbb Z/p\mathbb{Z})^*$, where $p$ is a prime number?

-
No I mean Zp in respect of multiplication modulo p. –  gosom Jan 14 '12 at 17:16
That is, the group of nonzero integers mod p, under multiplication mod p. Then you are asking for primitive roots of unity mod p! –  Dustan Levenstein Jan 14 '12 at 17:18
The same link you have provided contains a detailed answer you are looking for, see this @gosom –  Iyengar Jan 14 '12 at 17:38
The references provided in that article should provide further methods. I've that Cohen's book is pretty good, for example. –  Dylan Moreland Jan 14 '12 at 17:43

## 1 Answer

William Stein has a webpage on the problem of finding generators for $(\mathbb{Z}/p\mathbb{Z})^*$.

There are some probabilistic polytime algorithms for finding primitive roots. Also assuming the Extended Riemann Hypothesis, there are polytime algorithms.

However in general no efficient (fast) algorithm is known.

-