Primitive Root Calculator
Generators of (ℤ/nℤ)* · Order Computation · Cyclic Group Structure
Find all primitive roots (generators) of the multiplicative group (ℤ/nℤ)*. Computes φ(n), φ(φ(n)), the smallest primitive root, and verifies element orders.
Quick Examples
All Primitive Roots mod n
Generating All Roots from Smallest Primitive Root g
Order Table — Elements of (ℤ/nℤ)*
Elements coprime to n, their gcd with n, multiplicative order, and whether they are primitive roots (order = φ(n)).
What Is a Primitive Root?
A primitive root modulo n (also called a generator of the multiplicative group) is an integer g such that the powers g¹, g², g³, ..., g^φ(n) produce every integer from 1 to n that is coprime to n, each exactly once (modulo n). In group theory language, g is a generator of the cyclic group (ℤ/nℤ)*.
The multiplicative order of an element a modulo n is the smallest positive integer k such that aᵏ ≡ 1 (mod n). An element is a primitive root if and only if its order equals φ(n) — the order of the entire group. Primitive roots are the elements that "cycle through" the whole group before returning to 1.
Which Moduli Have Primitive Roots?
Not every n has primitive roots — the Primitive Root Theorem (proved by Gauss) gives a complete characterization. Primitive roots exist for n if and only if:
- n = 1 or n = 2 (trivial cases)
- n = 4
- n = p^k for any odd prime p and k ≥ 1
- n = 2·p^k for any odd prime p and k ≥ 1
Numbers that fail this test — such as n = 8, 12, 15, 16, 20, 24 — have multiplicative groups that are not cyclic, so no single element generates the whole group. For example, (ℤ/8ℤ)* ≅ ℤ&sub2; × ℤ&sub2; (the Klein four-group), where every non-identity element has order 2.
How Many Primitive Roots Are There?
When primitive roots exist for n, the exact count is φ(φ(n)) — the Euler totient of the totient. This follows from the structure of cyclic groups: a cyclic group of order m has exactly φ(m) generators. Since (ℤ/nℤ)* is cyclic of order φ(n), it has φ(φ(n)) generators, i.e., primitive roots.
For instance, for n = 7 (prime), φ(7) = 6 and φ(6) = 2, so exactly 2 primitive roots exist: {3, 5}. For n = 23, φ(23) = 22 and φ(22) = 10, giving 10 primitive roots.
Generating All Primitive Roots from One
If g is a primitive root modulo n, then all other primitive roots are of the form gᵏ (mod n) where gcd(k, φ(n)) = 1, for 1 ≤ k ≤ φ(n). This gives a quick way to enumerate all primitive roots once the smallest one is found.
Reference Table: Common Primitive Roots
| n | Type | φ(n) | φ(φ(n)) | Primitive Roots | Roots Exist? |
|---|---|---|---|---|---|
| 2 | 2 | 1 | 1 | {1} | YES |
| 3 | prime | 2 | 1 | {2} | YES |
| 4 | 4 | 2 | 1 | {3} | YES |
| 5 | prime | 4 | 2 | {2, 3} | YES |
| 7 | prime | 6 | 2 | {3, 5} | YES |
| 8 | 2³ | 4 | — | none | NO |
| 9 | 3² | 6 | 2 | {2, 5} | YES |
| 10 | 2·5 | 4 | 2 | {3, 7} | YES |
| 12 | 4·3 | 4 | — | none | NO |
| 23 | prime | 22 | 10 | {5, 7, 10, 11, 14, 15, 17, 19, 20, 21} | YES |
Applications in Cryptography
Diffie-Hellman Key Exchange: The protocol requires choosing a large prime p and a primitive root g modulo p. Each party raises g to a secret exponent and exchanges the result. The shared secret follows from the fact that gᵃᵇ = (gᵃ)ᵇ = (gᵇ)ᵃ (mod p). Using a primitive root maximizes the security of the construction — a non-primitive-root generator would only generate a proper subgroup, exposing the scheme to small-subgroup attacks.
ElGamal Encryption: Closely related to Diffie-Hellman, ElGamal also relies on a primitive root g of a prime p. Encryption of a message m uses a random exponent k; decryption requires computing the discrete logarithm of the shared secret, which is infeasible for large p.
Discrete Logarithm Problem (DLP): The security of all these systems rests on the DLP: given g and gᵏ mod p, find k. When g is a primitive root modulo a large safe prime p, the DLP is believed to be computationally intractable. The best known algorithms (General Number Field Sieve) require sub-exponential time, which for 2048-bit primes translates to billions of years.
Connection to Fermat's Little Theorem: For prime p, Fermat's Little Theorem states aᵖ⁻¹ ≡ 1 (mod p) for all a not divisible by p. This means every element of (ℤ/pℤ)* has order dividing p-1 = φ(p). A primitive root is precisely an element whose order is exactly p-1, not any proper divisor of it.