Primitive Root Modulo n - Finding Primitive Roots

Finding Primitive Roots

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.

If the multiplicative order of a number m modulo n is equal to (the order of Z_n×), then it is a primitive root. In fact the converse is true: If m is a primitive root modulo n, then the multiplicative order of m is . We can use this to test for primitive roots.

First, compute . Then determine the different prime factors of, say p₁, ..., p_k. Now, for every element m of Z_n*, compute

using a fast algorithm for modular exponentiation such as exponentiation by squaring. A number m for which these k results are all different from 1 is a primitive root.

The number of primitive roots modulo n, if there are any, is equal to

since, in general, a cyclic group with r elements has generators.

If g is a primitive root modulo p, then g is a primitive root modulo all powers pk unless g p – 1 ≡ 1 (mod p2); in that case, g + p is.

If g is a primitive root modulo pk, then g or g + pk (whichever one is odd) is a primitive root modulo 2pk.

Finding primitive roots modulo p is also equivalent to finding the roots of the (p-1)th cyclotomic polynomial modulo p.