Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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

share|cite|improve this question
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

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.

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.