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.
Proof: If
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
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.