next up previous contents
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 $p$ is a prime, there is an $a$ such that the equation

\begin{displaymath}{a^x}\equiv{b}\hbox{ (mod }{p})\end{displaymath}

has a solution for any $b\not{\equiv}0$. 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}
{\equiv}1$. 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}}\equiv{1}\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

\begin{displaymath}1222\left(\frac{1}{2}\right)\left(\frac{12}{13}\right)\left(\frac{46}{47}\right)=552\end{displaymath}

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.


next up previous contents
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