Date: Thu, 13 Apr 95 10:46:26 CDT
From: rusin (Dave Rusin)
To: uhl@wst.edvz.sbg.ac.at
Subject: Re: algorithm for primitive roots 
Newsgroups: sci.math

In article <D6yvM3.AD6@wst.edvz.sbg.ac.at> you write:
>
>Hi !
>
>I'm looking for an algorithm for calculating primitive roots
>(actually I know that there aren't really fast ones, I'm looking
>for algorithms that are not TOO slow).

Statistically speaking you should do fine by guessing! Assuming that
you meant primitive roots in  Z_p  (p=prime) you're just looking for
generators of the cyclic group  Z_p^* = Z_(p-1). If you select an
element of this group at random it's a generator with probability
Prod(1-1/q)  (the product over all primes  q  dividing  p-1). Moreover,
you can test any guess  a  by simply computing  a^((p-1)/q) for each
prime  q  dividing  p-1:  a  is a primitive root iff each of these is
distinct from  1.

Roughly speaking, the prime number theorem asserts that your probability
of success is at least  1/log(p), so for large  p  you should succeed
in finding a primitive root after  N*log(p)  iterations with probability
about  1-(1/e^N); thus your expected run time is linear in  log(p).

I would be surprised (and pleased to hear about) an algorithm which
runs faster.

(Of course this assumes you have a factorization of  p-1, which I know is
_not_ yet known to be possible in such a short time. On the other hand, 
the values of  p  for which a factorization of  p-1  is hard are precisely
the values of  p  for which a random selection of  a  is likely to 
produce a primitive root. So if it's OK simply to create an integer  a
which is _very likely_ to be a primitive root, you're in luck.)

dave