has a solution for any . Such an is called a

We showed in
the beginning of section 2 that it is easy to obtain given
and . Finding given and is much harder. Many modern
encryption systems are based on the fact that no efficient way of
computing discrete logarithms is known.

It is often possible to find a primitive root if has a small number of
prime divisors.
We will use as an example.
. By Lemmas 10 and 9, if is not a primitive root,
then we will either have
, , or
. and 3 fail, but
satisfies all three conditions, so it is a primitive root. (we
could tell that would not be a primitive root without testing. Why?)

It is easy to show that, if is a primitive root, is a
primitive root if and only if . In this example, this means
the number of primitive roots is

Thus, if we had just chosen at random, the probability that it would be a primitive root is . Choosing at random and testing until we found a primitive root would not be expected to take too long.

This is an example of a *probabilistic algorithm*. It is possible
for it to take a long time, but the amount of time needed on average is
reasonably small. We will see many other probabilistic algorithms later.

2002-12-14