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.
|show 5 more comments|
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:
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
I note also Exercise 11.4: