Primitive roots

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

$$a^x\equivb\hbox{ (mod }p)$$

has a solution for any $b\not\equiv0$. Such an $a$ is called a primitive root of $p$, and $x$is called the discrete logarithm of $b$.

We showed in the beginning of section 2 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.

Lemma 10   Let $b,d$ be as in Lemma 9. If $d=p-1$, then $b$ is a primitive root. 

Proof: If $1\le K<L\le p-1$ and $b^K\equiv b^L$, then $b^{L-K} \equiv1$. Since this can't happen by assumption, the first $p-1$ powers of $b$ must all be different, hence must include all numbers between 1 and $p-1$. height 8pt width 4pt

It is often possible to find a primitive root if $p-1$ has a small number of prime divisors. We will use $p=1223$ as an example. $p-1=2\cdot13\cdot47$. By Lemmas  10 and 9, if $a$ is not a primitive root, then we will either have $a^{26}$, $a^{94}$, or $a^{611}\equiv1\hbox{ (mod }1223)$. $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. Why?)

It is easy to show that, if $a$ is a primitive root, $a^x$ is a primitive root if and only if $(x,p-1)=1$. In this example, this means the number of primitive roots is

$$1222\left(\frac12\right)\left(\frac {12}{13}\right)\left(\frac{46}{47}\right)=552$$

Thus, if we had just chosen $a$ at random, the probability that it would be a primitive root is $\approx.45$. 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.