Theorem 5 showed that if p is a prime, there is an a such that the equation
has a solution for any 
.
Such an a is called a primitive root of p, and x
is called the discrete logarithm of b.
We showed in subsection 4.2.3 that it is easy to obtain b given a and x. Finding x given a and b is much harder. Many modern encryption systems are based on the fact that no efficient way of computing discrete logarithms is known.
Neither an efficient method for always finding primitive roots is
known. However, it is often possible to find one in special cases.
We will use p=1223 as an example. 
. By
Lemma 9, if a is not a primitive root, then we will either
have 
, 
, or 
. a=2 and 3 fail,
but a=5 satisfies all three conditions, so it is a primitive
root. We could tell that a=4 would not be a primitive root without
testing.
It is easy to show that, if a is a primitive root, 
is a
primitive root if and only if (x,p-1)=1. In this example, this means
the number of primitive roots is
Thus, if we had just chosen
a at random, the probability that it would be a primitive root is
. Choosing a 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.