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
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.