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$.

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.

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) )$.

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.

  Running time of this algorithm is $O(Ans \cdot \log \phi (n) \cdot \log n)$ (assume that $\phi (n)$ has $\log \phi (n)$ divisors).

Shoup (1990, 1992) proved, assuming the generalized Riemann hypothesis, that $g$ is $O(\log^6 p)$.

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;
}