Computing Primitive Roots

Theorem 2.5.8 does not suggest an efficient algorithm for finding primitive roots. To actually find a primitive root mod $ p$ in practice, we try $ a=2$ , then $ a=3$ , etc., until we find an $ a$ that has order $ p-1$ . Computing the order of an element of $ (\mathbb{Z}/p\mathbb{Z}{})^*$ requires factoring $ p-1$ , which we do not know how to do quickly in general, so finding a primitive root modulo $ p$ for large $ p$ seems to be a difficult problem.

Algorithm 2.5 (Primitive Root)   Given a prime $ p$ this algorithm computes the smallest positive integer $ a$ that generates $ (\mathbb{Z}/p\mathbb{Z}{})^*$ .
  1. [$ p=2$ ?] If $ p=2$ output $ 1$ and terminate. Otherwise set $ a=2$ .
  2. [Prime Divisors] Compute the prime divisors $ p_1, \ldots, p_r$ of $ p-1$ .
  3. [Generator?] If for every $ p_i$ , we have $ a^{(p-1)/p_i} \not\equiv 1\pmod{p}$ , then $ a$ is a generator of $ (\mathbb{Z}/p\mathbb{Z}{})^*$ , so output $ a$ and terminate.
  4. [Try next] Set $ a=a+1$ and go to step 3.

Proof. Let $ a\in (\mathbb{Z}/p\mathbb{Z}{})^*$ . The order of $ a$ is a divisor $ d$ of the order $ p-1$ of the group $ (\mathbb{Z}/p\mathbb{Z}{})^*$ . Write $ d =(p-1)/n$ , for some divisor $ n$ of $ p-1$ . If $ a$ is not a generator of $ (\mathbb{Z}/p\mathbb{Z}{})^*$ , then since $ n\mid (p-1)$ , there is a prime divisor $ p_i$ of $ p-1$ such that $ p_i\mid n$ . Then

$\displaystyle a^{(p-1)/p_i} = (a^{(p-1)/n})^{n/p_i} \equiv 1\pmod{p}.$

Conversely, if $ a$ is a generator, then $ a^{(p-1)/p_i} \not\equiv 1\pmod{p}$ for any $ p_i$ . Thus the algorithm terminates with step 3 if and only if the $ a$ under consideration is a primitive root. By Theorem 2.5.8 there is at least one primitive root, so the algorithm terminates. $ \qedsymbol$

William 2007-06-01