Efficiently find the generators of a cyclic group

Is there any efficient method to find the generators of a cyclic group?

Edit: The (cyclic)group here refers to a general multiplicative group of prime modulo. Is there any efficient algorithm to find the generators of the (cyclic)group.

Solution 1:

So you are trying to find a primitive root modulo a prime. Wang, On the least primitive root of a prime, Scientia Sinica 10 (1961) 1-14, proved that if the Extended Riemann Hypothesis is true then just trying the numbers 1, 2, 3, etc., in turn will find you a primitive root in polynomial time. There have been improvements in the details of Wang's result but not, I think, in the "big picture".

EDIT: In response to some of the comments above and below, I quote from Victor Shoup's textbook, A Computational Introduction to Number Theory and Algebra, page 268:

Finding a generator for ${\bf Z}_p^*$: There is no efficient algorithm known for this problem, unless the prime factorization of $p-1$ is given, and even then, we must resort to the use of a probabilistic algorithm.

Shoup drives the point home in some notes on page 281, where he discusses Wang's result on the smallest positive primitive root, and related results, and then writes

Of course, just because there exists a small primitive root, there is no known way to efficiently recognize a primitive root modulo $p$ without knowing the prime factorization of $p-1$.

I note also Exercise 11.4:

Suppose there is an efficient algorithm that takes as input a positive integer $n$ and an element $\alpha\in{\bf Z}_n^*$, and computes the multiplicative order of $\alpha$. Show how to use this algorithm to ... build an efficient integer factoring algorithm.