18.17 Primitive Roots
Primitive roots describe generators of modular multiplication.
18.17 Primitive Roots
Primitive roots describe generators of modular multiplication. Instead of looking at all nonzero residues modulo a prime as unrelated values, a primitive root lets you express every nonzero residue as a power of one number.
This idea is central to discrete logarithms, finite fields, cryptographic protocols, cyclic groups, number-theoretic transforms, and modular algebra. In algorithmic number theory, primitive roots are useful whenever a multiplicative structure needs to be enumerated, indexed, or transformed.
Problem
Given a modulus:
m
find an integer g such that powers of g generate all invertible residues modulo m.
For a prime modulus p, this means:
g^1, g^2, ..., g^(p-1)
produce every nonzero residue modulo p.
Example:
p = 7
Try:
g = 3
Compute powers:
3^1 mod 7 = 3
3^2 mod 7 = 2
3^3 mod 7 = 6
3^4 mod 7 = 4
3^5 mod 7 = 5
3^6 mod 7 = 1
The residues are:
1 2 3 4 5 6
So 3 is a primitive root modulo 7.
Multiplicative Order
The order of a modulo m is the smallest positive integer k such that:
a^k ≡ 1 (mod m)
assuming:
gcd(a,m)=1
Example:
2^1 mod 7 = 2
2^2 mod 7 = 4
2^3 mod 7 = 1
So the order of 2 modulo 7 is:
3
For prime p, Fermat's Little Theorem guarantees:
a^(p-1) ≡ 1 (mod p)
for every nonzero a. Therefore, the order of any nonzero residue modulo p divides:
p - 1
A primitive root modulo p is an element whose order is exactly:
p - 1
Primitive Root Definition
For a prime modulus p, an integer g is a primitive root modulo p if:
order(g) = p - 1
Equivalently, the powers of g generate the full multiplicative group:
1, 2, ..., p-1
modulo p.
Example:
p = 5
Try g = 2:
2^1 mod 5 = 2
2^2 mod 5 = 4
2^3 mod 5 = 3
2^4 mod 5 = 1
The powers generate:
1 2 3 4
So 2 is a primitive root modulo 5.
Non-Example
Modulo 7, try:
g = 2
Powers:
2^1 mod 7 = 2
2^2 mod 7 = 4
2^3 mod 7 = 1
The sequence repeats after length 3:
2, 4, 1, 2, 4, 1, ...
It never reaches:
3, 5, 6
So 2 is not a primitive root modulo 7.
Testing a Primitive Root
A direct test computes all powers and checks whether all nonzero residues appear.
def is_primitive_root_naive(g, p):
seen = set()
value = 1
for _ in range(1, p):
value = value * g % p
seen.add(value)
return len(seen) == p - 1
Example:
print(is_primitive_root_naive(3, 7))
print(is_primitive_root_naive(2, 7))
Output:
True
False
This is easy to understand but inefficient for large primes.
Efficient Criterion
For prime p, g is a primitive root modulo p if and only if:
g^((p-1)/q) mod p != 1
for every distinct prime factor q of:
p - 1
This criterion avoids enumerating all powers.
Why it works: if the order of g is smaller than p - 1, then it divides a proper factor of p - 1. Testing the prime-factor reductions is enough to rule out every proper divisor.
Example
Check whether:
g = 3
is a primitive root modulo:
p = 7
Here:
p - 1 = 6 = 2 × 3
Test prime factors 2 and 3.
For q = 2:
3^((6)/2) = 3^3 = 27 ≡ 6 (mod 7)
not 1.
For q = 3:
3^((6)/3) = 3^2 = 9 ≡ 2 (mod 7)
not 1.
Since neither test gives 1, 3 is a primitive root modulo 7.
Implementation
We need factorization of p - 1.
def distinct_prime_factors(n):
factors = []
d = 2
while d * d <= n:
if n % d == 0:
factors.append(d)
while n % d == 0:
n //= d
d += 1
if n > 1:
factors.append(n)
return factors
Now test a candidate.
def is_primitive_root(g, p):
if g <= 0 or g >= p:
return False
factors = distinct_prime_factors(p - 1)
for q in factors:
if pow(g, (p - 1) // q, p) == 1:
return False
return True
Find the smallest primitive root.
def primitive_root_prime(p):
if p == 2:
return 1
for g in range(2, p):
if is_primitive_root(g, p):
return g
return None
Example:
print(primitive_root_prime(7))
print(primitive_root_prime(17))
Possible output:
3
3
Why Only Prime Factors Matter
Suppose g is not primitive modulo prime p.
Then its order d is a proper divisor of:
p - 1
So:
d < p - 1
Because d divides p - 1, there is at least one prime factor q of p - 1 such that:
d | (p - 1) / q
Then:
g^((p-1)/q) ≡ 1 (mod p)
Thus one of the tests detects failure.
Conversely, if all these tests avoid 1, the order cannot be any proper divisor. Therefore the order must be:
p - 1
and g is primitive.
Building a Log Table
Once a primitive root g is known modulo prime p, every nonzero residue can be represented as:
g^e mod p
for a unique exponent:
0 ≤ e < p - 1
This lets us build a discrete log table for small p.
def log_table(g, p):
table = {}
value = 1
for e in range(p - 1):
table[value] = e
value = value * g % p
return table
Example:
logs = log_table(3, 7)
print(logs)
Output:
{1: 0, 3: 1, 2: 2, 6: 3, 4: 4, 5: 5}
This table maps each nonzero residue to its exponent base 3.
Using Primitive Roots for Multiplication
If:
a ≡ g^x (mod p)
and:
b ≡ g^y (mod p)
then:
ab ≡ g^(x+y) (mod p)
where exponents are taken modulo:
p - 1
Primitive roots turn multiplication of residues into addition of exponents.
This is the modular analogue of logarithms turning multiplication into addition.
Application: Discrete Logarithm
Given:
g^x ≡ h (mod p)
the task of finding x is the discrete logarithm problem.
For small primes, a table works.
For large primes, efficient general solutions are difficult. This difficulty underlies cryptographic systems such as Diffie-Hellman.
Primitive roots provide the generator g used in these systems.
Application: Diffie-Hellman Key Exchange
A simplified Diffie-Hellman setup chooses:
prime p
primitive root g
Alice chooses private value a and sends:
A = g^a mod p
Bob chooses private value b and sends:
B = g^b mod p
Alice computes:
B^a mod p
Bob computes:
A^b mod p
Both obtain:
g^(ab) mod p
The security depends on the difficulty of recovering a or b from the public powers.
Application: Number-Theoretic Transform
The Number-Theoretic Transform uses roots of unity modulo a prime. Primitive roots are used to construct those roots.
For example, if:
p = c · 2^k + 1
and g is a primitive root modulo p, then:
ω = g^c
can be a principal 2^k-th root of unity.
This is why primes such as:
998244353
are popular in fast polynomial multiplication.
Primitive Roots for Composite Moduli
Primitive roots do not exist for every modulus.
They exist exactly for moduli of the form:
1, 2, 4, p^k, 2p^k
where p is an odd prime and k ≥ 1.
For most algorithmic work, the prime modulus case is the most important and the easiest to use.
Common Mistakes
Testing All Powers Unnecessarily
For prime p, factor p - 1 and use the efficient criterion.
Forgetting That g Must Be Coprime to m
For prime p, every 1 ≤ g < p is coprime to p.
For composite moduli, this must be checked.
Confusing Primitive Root with Modular Inverse
A primitive root generates residues by exponentiation.
A modular inverse solves:
ax ≡ 1 (mod m)
These are different concepts.
Assuming Every Modulus Has Primitive Roots
Many composite moduli do not have primitive roots.
Forgetting to Factor p - 1
Testing primitive roots requires the distinct prime factors of p - 1, not of p.
Testing
Basic tests:
def test_primitive_roots():
assert is_primitive_root(3, 7)
assert not is_primitive_root(2, 7)
assert is_primitive_root(2, 5)
assert primitive_root_prime(7) == 3
Check generation:
def test_generation():
p = 17
g = primitive_root_prime(p)
values = set()
x = 1
for _ in range(p - 1):
values.add(x)
x = x * g % p
assert values == set(range(1, p))
This verifies that the selected root generates every nonzero residue.
Takeaway
A primitive root modulo a prime p is a generator of the nonzero residues under multiplication. Its powers produce every value from 1 to p-1, giving a cyclic representation of modular multiplication. Efficient testing relies on factoring p-1 and checking that g^((p-1)/q) is never 1 for any prime factor q. Primitive roots are fundamental in discrete logarithms, Diffie-Hellman key exchange, finite fields, and number-theoretic transforms.