Primitive Root

$g$ is a primitive root modulo $n$ if its powers generate every residue coprime to $n$ — that is, ${\mathrm{ord}}_n(g)=\phi (n)$.

Existence

A primitive root modulo $n$ exists iff $n\in \{1,2,4,p^k,2p^k\}$ for an odd prime $p$.

In particular, every prime modulus has $\phi (p-1)$ primitive roots — a substantial fraction, which is why random search finds one quickly.

Finding one

long long primitiveRoot(long long p) {            // p prime
    long long phi = p - 1;
    vector<long long> fac = primeFactors(phi);    // distinct prime factors
    for (long long g = 2; g < p; g++) {
        bool ok = true;
        for (long long q : fac)
            if (powmod(g, phi / q, p) == 1) { ok = false; break; }
        if (ok) return g;
    }
    return -1;
}

Why the test works: $\mathrm{ord}(g)$ divides $\phi$. If $g^{\phi /q}\ne 1$ for every prime $q\mid \phi$, then no proper divisor of $\phi$ can be the order, so it must be $\phi$ itself.

The search terminates fast: the smallest primitive root is $O(p^{1/4+\epsilon })$ under GRH, and in practice is a tiny number — for $p<10^9$ it is almost always below 100.

Cost: dominated by factoring $\phi (n)$.

Useful primitive roots

Modulus	Primitive root	Note
$998244353=119\cdot 2^{23}+1$	3	the standard NTT prime
$1004535809=479\cdot 2^{21}+1$	3
$469762049=7\cdot 2^{26}+1$	3
$10^9+7$	5	not NTT-friendly ($2^1\Vert p-1$ only)
$2^{61}-1$	37

An NTT-friendly prime has $p=c\cdot 2^k+1$ with $k$ large, so that $g^{(p-1)/2^j}$ is a $2^j$-th root of unity for every $j\le k$ — exactly what the transform needs.

Discrete logarithm

Once $g$ is known, every non-zero residue is $g^k$ for a unique $k\in [0,\phi )$, and multiplication becomes addition of exponents. That turns:

Multiplicative problem	Into
$ab\mathrm{mod}p$	$\mathrm{ind}(a)+\mathrm{ind}(b)\mathrm{mod}(p-1)$
$a^k\equiv b$ (discrete root)	$kx\equiv \mathrm{ind}(b)(\mathrm{mod}p-1)$ — a linear congruence
$a^x\equiv b$ (discrete log)	$x\mathrm{ind}(a)\equiv \mathrm{ind}(b)$
Order of $a$	$\frac{p-1}{\gcd (\mathrm{ind}(a),p-1)}$

This is the number-theoretic analogue of logarithms turning multiplication into addition, and it is the reason primitive roots matter.

Multiplicative order

${\mathrm{ord}}_n(a)$ = the smallest $k>0$ with $a^k\equiv 1$. It always divides $\phi (n)$.

long long order(long long a, long long n) {
    long long phi = eulerPhi(n), ord = phi;
    for (long long q : primeFactors(phi))
        while (ord % q == 0 && powmod(a, ord / q, n) == 1) ord /= q;
    return ord;
}

Start from $\phi (n)$ and divide out prime factors while the power still gives 1.

Where it appears

Problem	Use
NTT	need a $2^k$-th root of unity: $g^{(p-1)/2^k}$
Solving $x^k\equiv a(\mathrm{mod}p)$	reduce to a linear congruence in the exponent
Length of the decimal period of $1/n$	${\mathrm{ord}}_n(10)$
Cyclic group structure	${\mathbb{Z}}_p^{\ast }\cong {\mathbb{Z}}_{p-1}$
Diffie-Hellman, ElGamal	the security rests on the discrete log being hard
Rader’s FFT	re-indexes by a primitive root
Counting solutions of $x^k=a$	$\gcd (k,p-1)$ solutions if $a$ is a $k$-th power residue, else 0

Counting $k$-th power residues

The $k$-th powers modulo $p$ form a subgroup of index $\gcd (k,p-1)$, so there are exactly $\frac{p-1}{\gcd (k,p-1)}$ of them, and $a$ is a $k$-th power iff

$a^{\frac{p-1}{\gcd (k,p-1)}}\equiv 1(\mathrm{mod}p).$

For $k=2$ this is the Euler criterion for quadratic residues.

See also: Discrete Logarithm · Discrete Root · Euler Totient