∑MathAdvanced

Primitive Roots

Key Points

  • •
    A primitive root modulo n is a number g that cycles through all units modulo n when you repeatedly multiply by g, so its multiplicative order equals \((n)\).
  • •
    Primitive roots exist only for n in {1, 2, 4, , 2} where p is an odd prime; otherwise no element generates the full multiplicative group.
  • •
    To test if g is a primitive root modulo n, factor \((n)\) and check that \( 1 \) for every prime divisor q of \((n)\).
  • •
    There are exactly \(((n))\) primitive roots modulo n when they exist.
  • •
    For prime moduli p, finding a primitive root is fast: factor p−1 and test small candidates by fast exponentiation.
  • •
    Primitive roots power modern algorithms like the Number Theoretic Transform (NTT) and enable discrete logarithms via generators.
  • •
    Efficient implementation requires modular exponentiation, greatest common divisor, and usually fast integer factorization (e.g., Pollard–Rho) for larger inputs.
  • •
    In C++, careful use of 128-bit intermediate multiplication and deterministic Miller–Rabin for 64-bit integers makes the implementation robust and fast.

Prerequisites

  • →Euler’s Totient Function — You must compute φ(n) and understand its multiplicativity to size the multiplicative group.
  • →Modular Arithmetic and Modular Exponentiation — Primitive root tests rely on fast modular exponentiation and congruences.
  • →Prime Factorization (Miller–Rabin, Pollard–Rho) — You need to factor n and φ(n) to run the primitive-root test efficiently.
  • →FFT/NTT Basics — Understanding roots of unity and the Cooley–Tukey pattern helps apply primitive roots to NTT.
  • →Basic Group Theory — Concepts like order, cyclic groups, and Lagrange’s theorem underpin primitive roots.

Detailed Explanation

Tap terms for definitions

01Overview

Imagine a clock where you press a button to advance the hand by g hours each time. If after repeating this, you visit every hour mark exactly once before returning to 12, then g is a perfect step size. In modular arithmetic, a primitive root modulo n is exactly such a perfect step size for multiplication: repeatedly multiplying by g cycles through every invertible residue modulo n. Formally, the invertible residues modulo n form a multiplicative group denoted (Z/nZ)* with size (\varphi(n)), Euler’s totient. An element g in this group is a primitive root if its multiplicative order equals (\varphi(n)). Not all moduli admit such a generator; a classic result classifies precisely when the group is cyclic. When primitive roots exist, they serve as building blocks for many number-theoretic algorithms: they let us represent every unit as a power of g, support discrete logs, and produce roots of unity needed for the Number Theoretic Transform (NTT), which is a modular analogue of the FFT used for fast polynomial multiplication. Practically, to find a primitive root you factor (\varphi(n)) and test candidates using fast modular exponentiation. For prime moduli this is particularly straightforward and efficient, which is why competitive programming often uses special primes like 998244353 that come with convenient primitive roots.

02Intuition & Analogies

Think of musical chairs with numbered chairs from 0 to n−1 placed in a circle, but only certain chairs are “active” (the ones coprime to n). You start at chair 1 and keep moving by multiplying the chair number by g and reducing modulo n. If g is a great “step,” you will land on every active chair once before returning to 1. That special step is a primitive root. Another analogy is a combination lock: turning by g ticks each time. If the lock visits all allowed tick marks before repeating, then g is a perfect turn size—again, a primitive root. This cycling behavior is what “order” measures: how many steps it takes to return to the starting position. If order equals the size of the entire group of active chairs ((\varphi(n))), g visits them all and thus generates the whole group. Why don’t all locks have a perfect step? Because some locks are made from multiple disconnected wheels—their movement structure (the multiplicative group) isn’t a single cycle but a product of smaller cycles. Only certain n have a multiplicative group that’s one big loop: 1, 2, 4, powers of an odd prime, and twice those powers. For prime p, life is simple: exactly p−1 chairs are active, and there is always a g that sweeps through all of them. This is why mod primes are super convenient. In coding, you typically factor p−1, try small g like 2, 3, 5, and check via exponentiation that g skips all premature returns to 1; when it passes all checks, you’ve found your generator.

03Formal Definition

Let be an integer and let \((/n)^{}\) denote the multiplicative group of units modulo n. Its order is Euler’s totient \((n)\). For an element g with \((g,n)=1\), the multiplicative order of g modulo n, written \((g)\), is the least positive integer k such that \( 1 \). An element g is a primitive root modulo n if \((g) = (n)\). The group \((/n)^{}\) is cyclic (i.e., has a primitive root) if and only if \(n \{1,2,4,,2\}\) for an odd prime p and . When it is cyclic, the number of primitive roots modulo n equals \(((n))\). A practical characterization: let \(\{,,\}\) be the distinct prime divisors of \((n)\). Then g is a primitive root iff for all i, \( 1 \). For prime p, this reduces to factoring p−1 and testing the same condition. For NTT applications, if p is prime and n divides p−1, then \( = \) is a primitive n-th root of unity modulo p.

04When to Use

Use primitive roots whenever you want to represent every invertible residue as a power of a single base. Typical cases: (1) Number Theoretic Transform (NTT): Fast polynomial multiplication modulo a prime p with p−1 divisible by a large power of two. Starting from a primitive root g modulo p, you create a principal 2^k-th root of unity (\omega = g^{(p-1)/2^k}). (2) Discrete logarithms modulo a prime: If g is a primitive root mod p, every a ∈ (Z/pZ)* equals g^x, so solving a^x ≡ b is manageable via algorithms like Baby-Step Giant-Step. (3) Randomized constructions and hashing: Generators provide uniform cycles, useful in probing sequences or cycle-walking. (4) Cryptographic toy problems and pedagogy: Many classical protocols are clearer in cyclic groups, and prime moduli guarantee them. (5) Lifting to prime powers: For odd p and k ≥ 1, ((\mathbb{Z}/p^k\mathbb{Z})^{\times}) is cyclic, enabling discrete log or root-of-unity style methods at prime powers. Avoid attempting to find primitive roots when n is not in the allowed family; they simply do not exist. In such cases, work in a cyclic subgroup or switch to a prime (or prime-power) modulus.

⚠️Common Mistakes

  • Ignoring the existence criterion: Trying to find a primitive root for arbitrary n is futile if n ∉ {1, 2, 4, p^k, 2p^k}. Always check existence first. - Forgetting to use distinct prime factors of (\varphi(n)): The primitive-root test needs only the distinct primes q dividing (\varphi(n)), not all powers. Using repeated factors wastes time without changing the result. - Miscomputing (\varphi(n)): Totient must be computed from the prime factorization of n; trial subtraction like n−1 only works for primes. - Using slow or overflow-prone modular exponentiation: Always implement binary exponentiation with 128-bit intermediates for 64-bit moduli to avoid overflow. - Assuming a fixed small generator exists for every prime: While many small primes have small generators, some primes require a larger g. Your code should iterate candidates robustly. - Confusing roots of unity with primitive roots: A primitive root modulo p is a generator of all units; an n-th root of unity is an element whose n-th power is 1. The latter is primitive only if its order is exactly n. - Overlooking gcd(g, n) = 1: Candidates not coprime to n can never be primitive roots. - For NTT, picking length n not dividing p−1: You cannot get a principal n-th root of unity unless n | p−1. - For composite moduli, forgetting that the test only makes sense when the group is cyclic: If it is not, no element will pass the full set of exponent checks.

Key Formulas

Totient product formula

Explanation: Euler’s totient equals n times the product over distinct prime divisors p of (1−1/p). This computes how many residues are coprime to n.

Multiplicative order

Explanation: The order of g modulo n is the first exponent that returns g back to 1 under multiplication. Primitive roots have order equal to

Primitive root test

Explanation: Here \(((n))\) is the set of distinct prime divisors of If none of these smaller exponents yields 1, then the order must be

Existence criterion

Explanation: This classical theorem characterizes exactly which moduli admit primitive roots. Outside this set, the multiplicative group is not cyclic.

Count of primitive roots

Explanation: In a cyclic group of size the number of generators equals This counts the elements with full order.

Euler’s theorem

Explanation: For any g coprime to n, raising g to gives 1 modulo n. Hence an order must divide

Order divides group size

Explanation: By Lagrange’s theorem, the order of any element in a finite group divides the group’s size. This underlies the primitive root test.

NTT root construction

Explanation: If p is prime and n divides p−1, raising a primitive root g to (p−1)/n yields an n-th root of unity. It is primitive when n is maximal (e.g., a power of two dividing p−1).

Cyclotomic counting identity

Explanation: The number of elements of each possible order divides n and sums to n. In prime fields, this explains counts of n-th roots of unity.

BSGS complexity

Explanation: The baby-step giant-step method solves discrete logs in time proportional to the square root of the group order, with similar memory usage.

Totient of a prime power

Explanation: For odd prime p and , the group size modulo equals (p−1). This is the target order for primitive roots mod .

Order lifting to p^k

Explanation: Under this condition, a remains a generator when lifted from mod p to mod . This is useful for constructing primitive roots modulo prime powers.

Complexity Analysis

Finding a primitive root relies on two main subroutines: factoring and modular exponentiation. Binary modular exponentiation runs in O(log e) multiplications, where e is the exponent; in our use, exponents are around so each test is O(log n). Testing a single candidate g requires one exponentiation per distinct prime divisor q of so O( log n), where ω counts distinct primes. The dominant cost is factoring For prime p, for composite n in the allowed family, can be computed from the factorization of n, and then itself needs factorization into distinct primes. With Pollard–Rho and Miller–Rabin on 64-bit integers, the expected time to factor a random 64-bit integer is roughly sub-exponential but very fast in practice (well under milliseconds on modern CPUs), with an expected complexity often modeled around O() for the hardest semiprimes. Deterministic Miller–Rabin for 64-bit (fixed bases) ensures correctness of primality checks, while Pollard–Rho probabilistically finds nontrivial factors; recursive splitting yields full factorization. Overall, for 64-bit moduli, the pipeline is: Õ(1) Miller–Rabin calls plus Õ() expected Pollard–Rho operations, then a handful of O(log n) exponentiations per candidate. Typically only a few candidates are needed before finding a primitive root for prime p. Space complexity is small: O(log n) for recursion stacks and O( for factor storage (typically fewer than 10 primes for 64-bit inputs). For NTT, precomputation of roots is O(n) memory and O(n) time per stage, and transforms run in O(n log n) time and O(n) space for in-place iterative implementations.

Code Examples

Primitive root modulo a prime p using Miller–Rabin and Pollard–Rho to factor p−1
1#include <bits/stdc++.h>
2using namespace std;
3using u64 = uint64_t;
4using u128 = __uint128_t;
5
6// 128-bit safe modular multiplication for 64-bit moduli
7static inline u64 mod_mul(u64 a, u64 b, u64 m) {
8    return (u128)a * b % m;
9}
10
11u64 mod_pow(u64 a, u64 e, u64 m) {
12    u64 r = 1 % m;
13    while (e) {
14        if (e & 1) r = mod_mul(r, a, m);
15        a = mod_mul(a, a, m);
16        e >>= 1;
17    }
18    return r;
19}
20
21bool is_prime64(u64 n) {
22    if (n < 2) return false;
23    for (u64 p : {2ULL,3ULL,5ULL,7ULL,11ULL,13ULL,17ULL,19ULL,23ULL,29ULL,31ULL,37ULL}) {
24        if (n % p == 0) return n == p;
25    }
26    u64 d = n - 1, s = 0;
27    while ((d & 1) == 0) { d >>= 1; ++s; }
28    auto trial = [&](u64 a) {
29        if (a % n == 0) return true;
30        u64 x = mod_pow(a, d, n);
31        if (x == 1 || x == n - 1) return true;
32        for (u64 r = 1; r < s; ++r) {
33            x = mod_mul(x, x, n);
34            if (x == n - 1) return true;
35        }
36        return false;
37    };
38    // Deterministic bases for 64-bit (per research results)
39    for (u64 a : {2ULL, 3ULL, 5ULL, 7ULL, 11ULL, 13ULL}) {
40        if (!trial(a)) return false;
41    }
42    return true;
43}
44
45u64 rng64() {
46    static uint64_t x = 88172645463393265ull;
47    x ^= x << 7; x ^= x >> 9; return x;
48}
49
50u64 pollard_rho(u64 n) {
51    if (n % 2ULL == 0ULL) return 2ULL;
52    if (n % 3ULL == 0ULL) return 3ULL;
53    u64 c = (rng64() % (n - 1)) + 1;
54    u64 x = (rng64() % (n - 2)) + 2;
55    u64 y = x;
56    u64 d = 1;
57    auto f = [&](u64 v){ return (mod_mul(v, v, n) + c) % n; };
58    while (d == 1) {
59        x = f(x);
60        y = f(f(y));
61        u64 diff = x > y ? x - y : y - x;
62        d = std::gcd(diff, n);
63        if (d == n) return pollard_rho(n); // retry
64    }
65    return d;
66}
67
68void factor_rec(u64 n, map<u64,int>& mp) {
69    if (n == 1) return;
70    if (is_prime64(n)) { mp[n]++; return; }
71    u64 d = pollard_rho(n);
72    factor_rec(d, mp);
73    factor_rec(n / d, mp);
74}
75
76vector<u64> distinct_prime_factors(u64 n) {
77    map<u64,int> mp;
78    factor_rec(n, mp);
79    vector<u64> res;
80    for (auto &kv : mp) res.push_back(kv.first);
81    return res;
82}
83
84u64 primitive_root_prime(u64 p) {
85    assert(is_prime64(p));
86    if (p == 2) return 1; // only unit is 1
87    u64 phi = p - 1;
88    vector<u64> fac = distinct_prime_factors(phi);
89    for (u64 g = 2; g < p; ++g) {
90        bool ok = true;
91        for (u64 q : fac) {
92            if (mod_pow(g, phi / q, p) == 1) { ok = false; break; }
93        }
94        if (ok) return g;
95    }
96    return 0; // should not happen for prime p
97}
98
99int main() {
100    ios::sync_with_stdio(false);
101    cin.tie(nullptr);
102
103    u64 p; cin >> p;
104    if (!is_prime64(p)) {
105        cout << "Input must be prime.\n";
106        return 0;
107    }
108    u64 g = primitive_root_prime(p);
109    cout << "Primitive root modulo " << p << ": " << g << "\n";
110    // Quick sanity: powers of g should generate p-1 distinct residues
111    // (we won't print them all for big p)
112    return 0;
113}
114

This program finds a primitive root modulo a prime p. It uses deterministic Miller–Rabin (safe for 64-bit) to verify primality and Pollard–Rho to factor p−1 into distinct primes. Then it tests candidates g from 2 upward: if g^{(p−1)/q} ≠ 1 mod p for every distinct prime q | (p−1), g is a primitive root.

Time: Expected O(p^{1/4}) for factoring p−1 with Pollard–Rho plus O(ω(p−1) log p) per tested candidate; typically only a few candidates are needed.Space: O(ω(p−1)) for storing factors plus O(log p) stack/temporaries.
Primitive root modulo n when it exists (n ∈ {1,2,4,p^k,2p^k})
1#include <bits/stdc++.h>
2using namespace std;
3using u64 = uint64_t;
4using u128 = __uint128_t;
5
6static inline u64 mod_mul(u64 a, u64 b, u64 m){ return (u128)a*b % m; }
7
8u64 mod_pow(u64 a, u64 e, u64 m){ u64 r = 1 % m; while(e){ if(e&1) r=mod_mul(r,a,m); a=mod_mul(a,a,m); e>>=1;} return r; }
9
10bool is_prime64(u64 n){
11    if(n<2) return false; for(u64 p:{2ULL,3ULL,5ULL,7ULL,11ULL,13ULL,17ULL,19ULL,23ULL,29ULL,31ULL,37ULL}){ if(n%p==0) return n==p; }
12    u64 d=n-1,s=0; while((d&1)==0){ d>>=1; ++s; }
13    auto trial=[&](u64 a){ if(a%n==0) return true; u64 x=mod_pow(a,d,n); if(x==1||x==n-1) return true; for(u64 r=1;r<s;++r){ x=mod_mul(x,x,n); if(x==n-1) return true; } return false; };
14    for(u64 a:{2ULL,3ULL,5ULL,7ULL,11ULL,13ULL}) if(!trial(a)) return false; return true;
15}
16
17u64 rng64(){ static uint64_t x=88172645463393265ull; x^=x<<7; x^=x>>9; return x; }
18
19u64 pollard_rho(u64 n){ if(n%2ULL==0) return 2ULL; if(n%3ULL==0) return 3ULL; u64 c=(rng64()%(n-1))+1; u64 x=(rng64()%(n-2))+2; u64 y=x; u64 d=1; auto f=[&](u64 v){ return (mod_mul(v,v,n)+c)%n; }; while(d==1){ x=f(x); y=f(f(y)); u64 diff=x>y?x-y:y-x; d=gcd(diff,n); if(d==n) return pollard_rho(n); } return d; }
20
21void factor_rec(u64 n, map<u64,int>& mp){ if(n==1) return; if(is_prime64(n)){ mp[n]++; return; } u64 d=pollard_rho(n); factor_rec(d,mp); factor_rec(n/d,mp); }
22
23map<u64,int> factor(u64 n){ map<u64,int> mp; factor_rec(n,mp); return mp; }
24
25u64 phi_from_factor(const map<u64,int>& mp){ __uint128_t res=1; for(auto &kv:mp){ u64 p=kv.first; int e=kv.second; __uint128_t pk=1; for(int i=0;i<e;i++) pk*=p; res*=pk - pk/p; } return (u64)res; }
26
27bool exists_primitive_root(u64 n){
28    if(n==1||n==2||n==4) return true;
29    // n = p^k or 2*p^k with odd p
30    map<u64,int> mp = factor(n);
31    if(mp.size()==1){ u64 p=mp.begin()->first; return p%2==1; }
32    if(mp.size()==2 && mp.count(2)){
33        // form 2 * p^k where p odd
34        map<u64,int> tmp=mp; tmp.erase(2);
35        return tmp.size()==1 && tmp.begin()->first%2==1 && mp.at(2)==1; // exactly one factor 2
36    }
37    return false;
38}
39
40u64 primitive_root_any(u64 n){
41    if(!exists_primitive_root(n)) return 0; // 0 indicates none
42    if(n==1) return 0; // the only residue is 0 which equals 1 mod 1
43    if(n==2) return 1; // only unit is 1
44    if(n==4) return 3; // 3 generates {1,3}
45    // General case: compute phi(n), factor phi(n), then test candidates with gcd=1
46    map<u64,int> fn = factor(n);
47    u64 phi = phi_from_factor(fn);
48    // distinct prime divisors of phi
49    map<u64,int> fphi = factor(phi);
50    vector<u64> primes; for(auto &kv:fphi) primes.push_back(kv.first);
51    auto coprime=[&](u64 a){ for(auto &kv:fn){ if(a%kv.first==0) return false; } return true; };
52    for(u64 g=2; g<n; ++g){
53        if(!coprime(g)) continue;
54        bool ok=true;
55        for(u64 q:primes){ if(mod_pow(g, phi/q, n) == 1ULL){ ok=false; break; } }
56        if(ok) return g;
57    }
58    return 0; // should not happen when group is cyclic
59}
60
61int main(){
62    ios::sync_with_stdio(false);
63    cin.tie(nullptr);
64
65    u64 n; cin >> n;
66    if(!exists_primitive_root(n)){
67        cout << "No primitive root modulo " << n << " (group not cyclic).\n";
68        return 0;
69    }
70    u64 g = primitive_root_any(n);
71    cout << "Primitive root modulo " << n << ": " << g << "\n";
72    return 0;
73}
74

This program checks whether a primitive root exists for a given n using the exact classification. If it exists, it computes φ(n) from the factorization of n, factors φ(n), and searches for a generator by testing g^{φ(n)/q} ≠ 1 for all distinct prime divisors q of φ(n). Special small cases n ∈ {1,2,4} are handled directly.

Time: Expected O(n^{1/4}) for factoring n and φ(n) with Pollard–Rho, plus O(φ(φ(n)) tests) typically a handful of O(log n) exponentiations per candidate.Space: O(ω(n) + ω(φ(n))) for factor maps and O(log n) for recursion/temporaries.
Using a primitive root to build an NTT (mod 998244353) and convolve two polynomials
1#include <bits/stdc++.h>
2using namespace std;
3using u64 = uint64_t; using u128 = __uint128_t; using i64 = long long;
4
5static inline u64 mod_mul(u64 a, u64 b, u64 m){ return (u128)a*b % m; }
6static inline u64 mod_pow(u64 a, u64 e, u64 m){ u64 r=1%m; while(e){ if(e&1) r=mod_mul(r,a,m); a=mod_mul(a,a,m); e>>=1; } return r; }
7
8// NTT parameters for 998244353 = 119 * 2^23 + 1
9// Known primitive root is 3, but we also compute/check it.
10const u64 MOD = 998244353ULL;
11
12u64 primitive_root_998244353(){
13    // Factor MOD-1 = 2^23 * 7 * 17 * 2? Actually 998244352 = 2^23 * 7 * 17
14    vector<u64> primes = {2, 7, 17};
15    for(u64 g=2; g<MOD; ++g){
16        bool ok=true; for(u64 q:primes){ if(mod_pow(g, (MOD-1)/q, MOD)==1){ ok=false; break; } }
17        if(ok) return g; // minimal primitive root is 3
18    }
19    return 0;
20}
21
22void ntt(vector<u64>& a, bool invert){
23    int n = (int)a.size();
24    // bit-reverse permutation
25    for(int i=1,j=0;i<n;i++){
26        int bit = n>>1; for(; j&bit; bit>>=1) j^=bit; j^=bit; if(i<j) swap(a[i],a[j]);
27    }
28    u64 g = primitive_root_998244353();
29    for(int len=2; len<=n; len<<=1){
30        // wlen is primitive len-th root of unity
31        u64 wlen = mod_pow(g, (MOD-1)/len, MOD);
32        if(invert){
33            // Use inverse root: wlen^{-1} = wlen^{MOD-2}
34            wlen = mod_pow(wlen, MOD-2, MOD);
35        }
36        for(int i=0; i<n; i+=len){
37            u64 w = 1;
38            int half = len>>1;
39            for(int j=0; j<half; ++j){
40                u64 u = a[i+j];
41                u64 v = mod_mul(a[i+j+half], w, MOD);
42                u64 x = u + v; if(x>=MOD) x-=MOD;
43                u64 y = u + MOD - v; if(y>=MOD) y-=MOD;
44                a[i+j] = x;
45                a[i+j+half] = y;
46                w = mod_mul(w, wlen, MOD);
47            }
48        }
49    }
50    if(invert){
51        u64 inv_n = mod_pow(n, MOD-2, MOD);
52        for(u64 &x : a) x = mod_mul(x, inv_n, MOD);
53    }
54}
55
56vector<u64> convolution(const vector<u64>& A, const vector<u64>& B){
57    int n1=A.size(), n2=B.size();
58    int n=1; while(n < n1+n2-1) n<<=1;
59    vector<u64> a(n,0), b(n,0);
60    for(int i=0;i<n1;++i) a[i]=A[i]%MOD;
61    for(int i=0;i<n2;++i) b[i]=B[i]%MOD;
62    ntt(a,false); ntt(b,false);
63    for(int i=0;i<n;++i) a[i] = mod_mul(a[i], b[i], MOD);
64    ntt(a,true);
65    a.resize(n1+n2-1);
66    return a;
67}
68
69int main(){
70    ios::sync_with_stdio(false);
71    cin.tie(nullptr);
72
73    // Example: multiply (1 + 2x + 3x^2) * (4 + 5x)
74    vector<u64> P = {1,2,3};
75    vector<u64> Q = {4,5};
76    vector<u64> R = convolution(P,Q);
77    // Expected coefficients: [4, 13, 22, 15]
78    for(size_t i=0;i<R.size();++i){ if(i) cout << ' '; cout << R[i]; }
79    cout << '\n';
80    return 0;
81}
82

This code constructs an NTT over the prime modulus 998244353. It recovers a primitive root g (which is 3) and then, for each stage of the transform, takes an appropriate power ω = g^{(MOD−1)/len} as a principal len-th root of unity. The NTT and its inverse enable fast polynomial convolution, demonstrated by multiplying two small polynomials.

Time: O(n log n) for the transform and convolution, where n is the padded power-of-two length.Space: O(n) for the arrays, done in-place aside from temporary storage in recursion-free iterative loops.