Given a prime p find a generator of $\mathbb{Z}_p ^{*}$

Question

I found this problem in the introduction of a book on computer complexity and mention that Gauss had an algorithm to solve it but he want a "better taste" algorithm in the book say that finding this algorithm is an open problem.

I took a undergraduate semester on group theory so I know a little bit of cyclic groups so I know that $\mathbb{Z}_p^{*}$ is a cyclic group and that the order of $\mathbb{Z}_p^{*}$ is $p-1$. The problem is not really difficult from a theoretical-point of view but rather a computational problem.

So I want to know exactly what is the algorithm that Gauss made and where to find more on this subject

Answer 1

If we believe in the generalized Riemann hypothesis, for any prime $p$ large enough there is a generator for $\mathbb{Z}/(p\mathbb{Z})^*$ in the first $C\log(p)^2$ elements, so a good strategy to find a generator is to apply the following test:

For every prime divisor $q$ of $(p-1)$, check if $g^{\frac{p-1}{q}}\equiv 1\pmod{p}$. If that happens, discard $g$: it is not a generator. If it survives till the last prime divisor of $p-1$, keep it: it is a generator.

to the elements $g=2,3,5,6,\ldots$ (avoiding perfect powers) till getting a survivor.

Without strong assumptions like GRH, that is not granted to work in $O(\log^k p)$ time, but still is the best approach up to my knowledge, and it gives heuristics for believing in the truth of GRH: it works pretty good for practical purposes, and the existence of a prime $p$ with a too large smallest generator would disprove GRH.