Primitive Root Calculator

Welcome to the Primitive Root Calculator, a powerful free online tool that finds all primitive roots modulo any positive integer n. This calculator provides step-by-step verification, power tables, and an animated cyclic group visualization to help you understand how primitive roots generate multiplicative groups. Whether you are studying number theory, preparing for cryptography exams, or working with modular arithmetic in competitive programming, this tool delivers instant, accurate results with educational insights.

What is a Primitive Root?

A primitive root modulo n is an integer g whose powers generate all integers that are coprime to n. Formally, g is a primitive root mod n if the multiplicative order of g modulo n equals Euler's totient \(\varphi(n)\). This means the set

contains exactly all \(\varphi(n)\) integers from 1 to n-1 that are coprime to n. A primitive root is essentially a generator of the cyclic group \((\mathbb{Z}/n\mathbb{Z})^*\).

Quick Example

Consider n = 7. Since 7 is prime, \(\varphi(7) = 6\). Let us check if g = 3 is a primitive root:

• 3¹ mod 7 = 3
• 3² mod 7 = 2
• 3³ mod 7 = 6
• 3⁴ mod 7 = 4
• 3⁵ mod 7 = 5
• 3⁶ mod 7 = 1

The powers produce {3, 2, 6, 4, 5, 1} = {1, 2, 3, 4, 5, 6}, which is all integers coprime to 7. So 3 is a primitive root modulo 7.

When Do Primitive Roots Exist?

Primitive roots modulo n exist if and only if n is one of these forms:

• n = 1, 2, or 4
• n = p^k where p is an odd prime and k ≥ 1
• n = 2p^k where p is an odd prime and k ≥ 1

For example, primitive roots exist for 7, 9, 11, 13, 14, 18, 23, 25, 27, 46, but not for 8, 12, 15, 16, 20, 21, 24.

How to Find Primitive Roots

1. Enter the modulus: Type a positive integer n (from 2 to 100,000) into the input field.
2. Calculate: Click "Find Primitive Roots" or press Enter.
3. View all roots: See the complete list of primitive roots, along with Euler's totient and statistics.
4. Study the power table: Examine how the smallest primitive root generates all coprime residues.
5. Visualize the cyclic group: For small moduli, see the animated wheel showing the cyclic structure.

How Many Primitive Roots Does n Have?

If primitive roots exist modulo n, the count equals:

For instance, for n = 13: \(\varphi(13) = 12\) and \(\varphi(12) = 4\), so there are exactly 4 primitive roots modulo 13 (which are 2, 6, 7, 11).

The Verification Algorithm

To check if g is a primitive root modulo n efficiently:

1. Compute \(\varphi(n)\) using the prime factorization of n
2. Find all distinct prime factors \(p_1, p_2, \ldots, p_k\) of \(\varphi(n)\)
3. For each prime factor \(p_i\), check: \(g^{\varphi(n)/p_i} \not\equiv 1 \pmod{n}\)
4. If ALL checks pass, then g is a primitive root

This method is much faster than computing all powers of g, since we only need to test \(k\) exponentiations instead of \(\varphi(n)\) of them.

Primitive Roots in Cryptography

Diffie-Hellman Key Exchange

The Diffie-Hellman protocol uses a large prime p and a primitive root g modulo p. Alice picks secret a, sends \(g^a \bmod p\). Bob picks secret b, sends \(g^b \bmod p\). Both compute the shared secret \(g^{ab} \bmod p\). Security relies on the discrete logarithm problem being computationally hard.

ElGamal Encryption

ElGamal also uses a primitive root as a generator. The public key is \((p, g, g^x \bmod p)\) where x is private. The fact that g generates all elements ensures that every message can be encrypted.

Digital Signatures

DSA (Digital Signature Algorithm) and related schemes use primitive roots in subgroups of \((\mathbb{Z}/p\mathbb{Z})^*\) to create and verify digital signatures.

Reference Table: Smallest Primitive Roots

Frequently Asked Questions

What is a primitive root modulo n?

A primitive root modulo n is an integer g such that the powers \(g^1, g^2, \ldots, g^{\varphi(n)}\) produce all integers coprime to n when taken modulo n. In other words, g generates the entire multiplicative group \((\mathbb{Z}/n\mathbb{Z})^*\). The multiplicative order of g modulo n equals Euler's totient \(\varphi(n)\).

For which values of n do primitive roots exist?

Primitive roots exist modulo n if and only if n is 1, 2, 4, p^k, or 2p^k, where p is an odd prime and k ≥ 1. For example, primitive roots exist for n = 7 (prime), n = 9 (3²), n = 14 (2×7), but NOT for n = 8, 12, 15, or 16.

How many primitive roots does n have?

If primitive roots exist modulo n, the number of primitive roots equals \(\varphi(\varphi(n))\), where \(\varphi\) is Euler's totient function. For example, for n = 13 (prime), \(\varphi(13) = 12\) and \(\varphi(12) = 4\), so there are exactly 4 primitive roots modulo 13.

Why are primitive roots important in cryptography?

Primitive roots are fundamental to the Diffie-Hellman key exchange protocol and the ElGamal encryption system. In these cryptographic protocols, a primitive root g modulo a large prime p is used as a generator. The security relies on the difficulty of the discrete logarithm problem: given \(g^x \bmod p\), it is computationally hard to find x.

How do you verify that g is a primitive root modulo n?

To verify g is a primitive root mod n: (1) Compute \(\varphi(n)\). (2) Find all prime factors \(p_1, p_2, \ldots, p_k\) of \(\varphi(n)\). (3) Check that \(g^{\varphi(n)/p_i} \not\equiv 1 \pmod{n}\) for each prime factor \(p_i\). If all checks pass, g is a primitive root. This is much faster than computing all powers of g.

Related Tools