guest@itl:~/home/algebra$
templates/primitive-root.cpp
compilable
$cat templates/primitive-root

Primitive Root

Find the smallest primitive root (generator) modulo a prime p.

[Algebra]|
Jul 9, 2026
|explanatory_notes.md|
#primitive-root#generator#modular#number-theory#group-theory
Log in to track progress, save custom versions, and organize into collections.Log In
$cat source_code/
cpp
#include <bits/stdc++.h>
using namespace std;
using ll = long long;

ll powerMod(ll a, ll b, ll p) {
  ll res = 1;
  a %= p;
  while (b > 0) {
    if (b & 1) {
      res = (__int128)res * a % p;
    }
    a = (__int128)a * a % p;
    b >>= 1;
  }
  return res;
}

ll primitiveRoot(ll p) {
  ll phi = p - 1, n = phi;
  vector<ll> factors;
  for (ll i = 2; i * i <= n; i++) {
    if (n % i == 0) {
      factors.push_back(i);
      while (n % i == 0) {
        n /= i;
      }
    }
  }
  if (n > 1) {
    factors.push_back(n);
  }

  for (ll g = 2; g <= p; g++) {
    bool ok = true;
    for (ll q : factors) {
      if (powerMod(g, phi / q, p) == 1) {
        ok = false;
        break;
      }
    }
    if (ok) {
      return g;
    }
  }
  return -1;
}
46 linesutf-8
$cat explanation_notes.md
notes_viewer --renderedmarkdown (math enabled)

Primitive Root

A primitive root modulo pp is an integer gg such that its powers generate all nonzero residues mod pp:

{g1,g2,…,gp−1}≡{1,2,…,p−1}(modp)\{g^1, g^2, \dots, g^{p-1}\} \equiv \{1, 2, \dots, p-1\} \pmod{p}

Equivalently, gg has multiplicative order φ(p)=p−1\varphi(p) = p - 1.

How It Works

  • Compute φ(p)=p−1\varphi(p) = p - 1 and find all its prime factors q1,q2,…,qkq_1, q_2, \dots, q_k

  • For each candidate g=2,3,…g = 2, 3, \dots, check:

    • g(p−1)/qi≢1(modp)for all ig^{(p-1)/q_i} \not\equiv 1 \pmod{p} \quad \text{for all } i

  • First gg that passes all checks is the smallest primitive root

    • When to Use

  • NTT (Number Theoretic Transform) — need a generator for the multiplicative group mod prime

  • Discrete logarithm problems — converting multiplication to addition

  • Problems that ask "find a generator" or need cyclic group structure mod pp

  • Constructing permutations or sequences with full period mod pp

    • Properties

  • A primitive root exists modulo nn iff nn is 1,2,4,pk1, 2, 4, p^k, or 2pk2p^k for odd prime pp

  • If gg is a primitive root mod pp, then gkg^k is also a primitive root iff gcd⁡(k,p−1)=1\gcd(k, p-1) = 1

  • Total number of primitive roots mod pp is φ(p−1)\varphi(p-1)

  • The smallest primitive root is typically very small (often under 10 for primes used in CP)

    • Complexity

    OperationTimeSpace
    Factor φ(p)\varphi(p)O(p)O(\sqrt{p})O(log⁡p)O(\log p)
    Test one candidateO(klog⁡p)O(k \log p)O(1)O(1)
    Total (worst case)O(g⋅klog⁡p+p)O(g \cdot k \log p + \sqrt{p})O(log⁡p)O(\log p)

    Where kk is the number of distinct prime factors of p−1p - 1 and gg is the smallest primitive root (usually very small).