Primitive Root
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 \(n1\).
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, n1]\). 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 wellknown 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 = p1, 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;
}