Is there a method for finding a primitive element (generator) of $(\mathbb Z/p\mathbb{Z})^*$, where $p$ is a prime number?
Finding a generator of $(\mathbb Z/p\mathbb{Z})^*$
4
$\begingroup$
number-theory
group-theory
finite-groups
-
0If $p$ is of the form $2^\alpha + 1$ then the primitive elements are precisely the quadratic non-residues – 2012-05-22
1 Answers
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.