9
$\begingroup$

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.

  • 3
    How are you given the group?2011-11-21
  • 2
    @Qiaochu It is a multiplicative group, modulo p. Where p being a prime number.2011-11-21
  • 1
    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).2011-11-21
  • 1
    @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)$.2011-11-21
  • 0
    @jug: You're right. That's actually more than just "slightly more" than caching. I've deleted my comment.2011-11-21
  • 0
    @joriki: No need to delete your comment just because you missed something. Now my comment is dangling in the air without reference. Shall I remove it, too? I think the upvoting of comments serves well for compacting a too long list of comments.2011-11-21
  • 0
    @jug: I agree in general and I usually don't delete comments that were wrong. However, in the present case it was rather long and I wanted to spare people from reading through it just to find that it was wrong -- also it was visible because of the upvotes and your correction wasn't, but I just realized I could have solved that by upvoting yours :-) Also I thought that your comment still makes enough sense without mine.2011-11-21
  • 0
    @joriki: it doesn't make *that* much sense. We readers are still wondering what caching is...have we roamed into the world of computers?!?2011-11-21
  • 0
    I have wondered about this question for a while. I know that you can speed up checking to see if a number is a generator using the theorem of quadratic reciprocity, but other than that...(assuming we are, of course, looking at the multaplicative group mod $p$)2011-11-21
  • 1
    The method that [wikipedia](http://en.wikipedia.org/wiki/Primitive_root_modulo_n#Finding_primitive_roots) 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?2011-11-21

1 Answers 1

15

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.

  • 0
    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...)2011-11-22
  • 0
    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).2011-11-22
  • 0
    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$.)2011-11-22
  • 0
    @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.2011-11-22
  • 0
    @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.2011-11-22