Primitive root modulo n

Primitive roots modulo n are a concept in number theory. If n is an integer, the numbers coprime to n, taken modulo n, form a group with multiplication as operation; it is written as (Z/nZ)^×. This group is cyclic if and only if n is equal to 2 or 4 or p^k or 2 p^k for an odd prime number p and k ≥ 1. A generator of this cyclic group is called a primitive root modulo n.

Take for example n = 14. The elements of (Z/14Z)^× are the congruence classes of 1, 3, 5, 9, 11 and 13. Then 3 is a primitive root modulo 14, as we have 3² = 9, 3³ = 13, 3⁴ = 11, 3⁵ = 5 and 3⁶ = 1 (modulo 14). The only other primitive root modulo 14 is 5.

No simple general formula to compute primitive roots modulo n is known. There are however methods to locate a primitive root that are faster than simply trying out all candidates: first compute φ(n), the order of (Z/nZ)^×. Then determine the different prime factors of φ(n), say p₁,...,p_k. Now, for every element m of (Z/nZ)^×, compute

$m^{\phi (n)/p_{i}}\mod n\qquad {\mbox{ for }}i=1,\ldots ,k$

using the fast exponentiating by squaring. As soon as you find a number m for which these k results are all different from 1, you stop: m is a primitive root.

If the generalized Riemann hypothesis is true, then for every prime number p, there exists a primitive root modulo p which is less than 70 (ln(p))².