4
$\begingroup$

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

  • 0
    If $p$ is of the form $2^\alpha + 1$ then the primitive elements are precisely the quadratic non-residues2012-05-22

1 Answers 1

3

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.