Primitive Roots and Discrete Logarithm
Work inside cyclic multiplicative groups by finding generators and solving exponent equations with baby-step giant-step.
Primitive Roots and Discrete Logarithm
The main note is rendered from the TeX source. Code lives in a separate C++ file so the write-up stays readable.
Overview
Primitive roots and discrete logarithms are two sides of the same idea: if a multiplicative modular group is cyclic, then every non-zero element can be represented as a power of one generator. That turns multiplication into addition on exponents.
When to Use It
Use these ideas when:
the problem has equations like \(a^x \equiv b \pmod m\),
you need to enumerate powers by generator order,
a multiplicative subgroup needs to be indexed explicitly.
Core Idea
For a prime modulus \(p\), the non-zero residues form a cyclic group of size \(p-1\). If \(g\) is a primitive root modulo \(p\), then every non-zero residue is \(g^k\) for some \(k\).
The discrete logarithm problem asks to recover \(k\) from \[ g^k \equiv h \pmod p. \] The standard contest algorithm is baby-step giant-step.
Key Insight
Once a generator exists, multiplicative equations become additive equations on exponents modulo the group order. The hard part shifts from algebra to fast lookup of powers.
Worked Problem
Problem.
For a prime \(p\), given \(g\) and \(h\), find the smallest non-negative \(x\) such that \[ g^x \equiv h \pmod p, \] or report that no such \(x\) exists.
Why these tools fit.
If \(g\) generates the relevant subgroup, the problem is exactly a discrete logarithm. Baby-step giant-step rewrites \(x = iq + j\) and matches \[ g^{iq} \equiv h g^{-j}. \]
Correctness Intuition
Baby-step giant-step covers every exponent by splitting it into a large-block index \(i\) and a small offset \(j\). A hash table over one side and a linear scan over the other finds the match in \(O(\sqrt{m})\) time.
Complexity Analysis
primitive root modulo prime \(p\): factor \(p-1\), then test candidates in roughly \(O(\tau(p-1)\log p)\),
baby-step giant-step: \(O(\sqrt{m}\log m)\) time and \(O(\sqrt{m})\) memory.
Implementation
The code includes:
primitive_root_prime(p)for prime moduli,discrete_log_prime(g, h, p)with baby-step giant-step.
Common Pitfalls
Forgetting the primitive-root existence conditions for general composite moduli.
Calling BSGS when \(g\) and \(p\) are not coprime in the implemented variant.
Ignoring subgroup issues; not every \(h\) is reachable from every \(g\).
Variants / Extensions
General discrete log with gcd handling.
Using exponent indices to solve multiplicative congruences.
Primitive roots for NTT-friendly moduli and subgroup generators.
Practice Problems
Solve \(a^x \equiv b \pmod p\).
Find a generator of \((\mathbb{Z}/p\mathbb{Z})^\times\).
Transform multiplicative constraints into additive ones over exponents.
References
Code
Contest-ready reference implementation for the idea explained above.
long long mod_pow(long long a, long long e, long long mod) {
long long result = 1 % mod;
while (e > 0) {
if (e & 1) result = (__int128)result * a % mod;
a = (__int128)a * a % mod;
e >>= 1;
}
return result;
}
vector<long long> distinct_prime_factors(long long n) {
vector<long long> factors;
for (long long p = 2; p * p <= n; ++p) {
if (n % p == 0) {
factors.push_back(p);
while (n % p == 0) n /= p;
}
}
if (n > 1) factors.push_back(n);
return factors;
}
long long primitive_root_prime(long long p) {
vector<long long> factors = distinct_prime_factors(p - 1);
for (long long g = 2; g < p; ++g) {
bool ok = true;
for (long long q : factors) {
if (mod_pow(g, (p - 1) / q, p) == 1) {
ok = false;
break;
}
}
if (ok) return g;
}
return -1;
}
long long discrete_log_prime(long long g, long long h, long long p) {
long long n = (long long)sqrt((long double)p) + 1;
unordered_map<long long, long long> baby;
long long value = 1;
for (long long j = 0; j < n; ++j) {
if (!baby.count(value)) baby[value] = j;
value = (__int128)value * g % p;
}
long long factor = mod_pow(mod_pow(g, p - 2, p), n, p);
value = h % p;
for (long long i = 0; i <= n; ++i) {
auto it = baby.find(value);
if (it != baby.end()) {
return i * n + it->second;
}
value = (__int128)value * factor % p;
}
return -1;
}
Source Files and Assets
Raw files are still available here when you want the original TeX, C++, or statement assets.