Next: Proof of Theorem 5 Up: Introduction to Number Theory Previous: Powers modulo a prime   Contents

Primitive roots

Recall that theorem 5 says that if is a prime, there is an such that the equation

has a solution for any . Such an is called a primitive root of , and is called the discrete logarithm of .

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.

Lemma 10   Let be as in Lemma 9. If , then is a primitive root.

Proof: If and , then . Since this can't happen by assumption, the first powers of must all be different, hence must include all numbers between 1 and . height 8pt width 4pt

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.

Next: Proof of Theorem 5 Up: Introduction to Number Theory Previous: Powers modulo a prime   Contents
Translated from LaTeX by Scott Sutherland
2002-12-14