Table of Contents
1. Definition
In modular arithmetic, a number $g$ is called a primitive root modulo n if every number coprime to $n$ is congruent to a power of $g$ modulo $n$. Mathematically, $g$ is a primitive root modulo n if and only if for any integer $a$ such that $\gcd(a, n) = 1$, there exists an integer $k$ such that:
$g^k \equiv a \pmod n$.
$k$ is then called the index or discrete logarithm of $a$ to the base $g$ modulo $n$. $g$ is also called the generator of the multiplicative group of integers modulo $n$.
In particular, for the case where $n$ is a prime, the powers of primitive root runs through all numbers from $1$ to $n-1$.
2. Existence
Primitive root modulo $n$ exists if and only if:
- $n$ is 1, 2, 4, or
- $n$ is power of an odd prime number $(n = p^k)$, or
- $n$ is twice power of an odd prime number $(n = 2 \cdot p^k)$.
This theorem was proved by Gauss in 1801.
3. Relation with the Euler function
Let $g$ be a primitive root modulo $n$. Then we can show that the smallest number $k$ for which $g^k \equiv 1 \pmod n$ is equal $\phi (n)$. Moreover, the reverse is also true, and this fact will be used in this article to find a primitive root.
Furthermore, the number of primitive roots modulo $n$, if there are any, is equal to $\phi (\phi (n) )$.
4. Algorithm for finding a primitive root
A naive algorithm is to consider all numbers in range $[1, n-1]$. And then check if each one is a primitive root, by calculating all its power to see if they are all different. This algorithm has complexity $O(g \cdot n)$, which would be too slow. In this section, we propose a faster algorithm using several well-known theorems.
From previous section, we know that if the smallest number $k$ for which $g^k \equiv 1 \pmod n$ is $\phi (n)$, then $g$ is a primitive root. Since for any number $a$ relative prime to $n$, we know from Euler’s theorem that $a ^ { \phi (n) } \equiv 1 \pmod n$, then to check if $g$ is primitive root, it is enough to check that for all $d$ less than $\phi (n)$, $g^d \not \equiv 1 \pmod n$. However, this algorithm is still too slow.
From Lagrange’s theorem, we know that the index of 1 of any number modulo $n$ must be a divisor of $\phi (n)$. Thus, it is sufficient to verify for all proper divisor $d \mid \phi (n)$ that $g^d \not \equiv 1 \pmod n$. This is already a much faster algorithm, but we can still do better.
Factorize $\phi (n) = p_1 ^ {a_1} \cdots p_s ^ {a_s}$. We prove that in the previous algorithm, it is sufficient to consider only the values of $d$ which have the form $\frac { \phi (n) } {p_j}$. Indeed, let $d$ be any proper divisor of $\phi (n)$. Then, obviously, there exists such $j$ that $d \mid \frac { \phi (n) } {p_j}$, i.e. $d \cdot k = \frac { \phi (n) } {p_j}$. However, if $g^d \equiv 1 \pmod n$, we would get:
$g ^ { \frac { \phi (n)} {p_j} } \equiv g ^ {d \cdot k} \equiv (g^d) ^k \equiv 1^k \equiv 1 \pmod n$.
i.e. among the numbers of the form $\frac {\phi (n)} {p_i}$, there would be at least one such that the conditions were not met.
Now we have a complete algorithm for finding the primitive root:
- First, find $\phi (n)$ and factorize it.
- Then iterate through all numbers $g \in [1, n]$, and for each number, to check if it is primitive root, we do the following:
- Calculate all $g ^ { \frac {\phi (n)} {p_i}} \pmod n$.
- If all the calculated values are different from $1$, then $g$ is a primitive root.
Shoup (1990, 1992) proved, assuming the generalized Riemann hypothesis, that $g$ is $O(\log^6 p)$.
5. Implementation
The following code assumes that the modulo p is a prime number. To make it works for any value of p, we must add calculation of $\phi (p)$.
int powmod (int a, int b, int p) { int res = 1; while (b) if (b & 1) res = int (res * 1ll * a % p), --b; else a = int (a * 1ll * a % p), b >>= 1; return res; } int generator (int p) { vector<int> fact; int phi = p-1, n = phi; for (int i=2; i*i<=n; ++i) if (n % i == 0) { fact.push_back (i); while (n % i == 0) n /= i; } if (n > 1) fact.push_back (n); for (int res=2; res<=p; ++res) { bool ok = true; for (size_t i=0; i<fact.size() && ok; ++i) ok &= powmod (res, phi / fact[i], p) != 1; if (ok) return res; } return -1; }