# 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.

-
How are you given the group? – Qiaochu Yuan Nov 21 '11 at 6:35
@Qiaochu It is a multiplicative group, modulo p. Where p being a prime number. – pkvprakash Nov 21 '11 at 6:42
If the group is given, you may want to add the relevant case to the question, even if you still want to know the general case. (If you do want the general case, you should of course write that as well). – Asaf Karagila Nov 21 '11 at 7:18
@joriki: You can do slightly more than just caching. If you found elements of order $m$ and $n$, you can construct an element of order $\mathrm{lcm}(m, n)$. – j.p. Nov 21 '11 at 8:34
The method that wikipedia describes for your case seems to depend on knowing the prime factorization of $p-1$. That can be used, whenever you know the order of the group (and its factorization). I wonder, what would be the best way of doing this, if you don't know the order of the group, or the prime factorization of the order? – Jyrki Lahtonen Nov 21 '11 at 10:31

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.

-
Interesting. Would the proof hold if you were to start at a number chosen at random? (You can create a pseudo-random number generator based upon primitive roots mod $p$, by simply calculating, for $a$ a primitive root, $a \text{ mod }p$, $a^2 \text{ mod }p$, $a^3 \text{ mod }p$ etc, but clearly taking a small primitive $a$ will not yield a very random number...of course, computers fix their generators, but I still want to know how easy it would be to find a suitable generator...) – user1729 Nov 22 '11 at 10:09
If you don't care about finding the smallest primitive root, you can combine several elements to one that generates the subgroup generated by the given elements. You can then speed up the algorithm by iterating only over the small primes $2, 3, 5, 7, 11, \dots$ (instead of all numbers). – j.p. Nov 22 '11 at 10:25
You write that finding a primitive root takes polynomial time. Do you mean relative to the size of the given prime? (Finding the order of an element of $\mathbb{F}_p^\times$ takes - to my knowledge - as long as factoring $p-1$.) – j.p. Nov 22 '11 at 10:30
@user1729, I suspect you can start anywhere, but as I'm not familiar with the details of the proof I have to refer you back to the paper to see what it says. – Gerry Myerson Nov 22 '11 at 11:32
@jug, you raise a good point. I think in this situation "polynomial" means "polynomial in $\log p$," but perhaps all Wang's result says is that there exists a primitive root less than some small power of $\log p$, and doesn't tell you how to know when you have found one. Again, I'd recommend looking at Wang's paper to see what exactly is there. – Gerry Myerson Nov 22 '11 at 11:36