Primitive Root Calculator

Find all primitive roots of a given modulus n — generators of the multiplicative group (Z/nZ)*. Enter any positive integer to get primitive roots, Euler's totient, cyclic group visualization, and a step-by-step verification with power tables.

Embed Primitive Root Calculator Widget

About Primitive Root Calculator

The Primitive Root Calculator finds all primitive roots of a given modulus n — integers g whose powers \(g^1, g^2, \ldots, g^{\varphi(n)}\) generate every element of the multiplicative group \((\mathbb{Z}/n\mathbb{Z})^*\). Enter any positive integer to instantly see all primitive roots, Euler's totient \(\varphi(n)\), an interactive cyclic group visualization, a power table, and a step-by-step verification of the smallest primitive root.

Applications of Primitive Roots

🔐

Diffie-Hellman

Key exchange protocol uses primitive roots as generators

🔏

ElGamal Encryption

Public-key cryptosystem based on discrete logarithms

✍

Digital Signatures

DSA and Schnorr signatures rely on cyclic group generators

🎲

Pseudorandom Numbers

Linear congruential generators use primitive root properties

📡

Error-Correcting Codes

Reed-Solomon and BCH codes use generators of finite fields

🧮

Number Theory

Index calculus, quadratic residues, and discrete logarithm problems

Key Concepts and Formulas

Concept	Formula / Definition	Description
Primitive Root	\(\text{ord}_n(g) = \varphi(n)\)	An integer g whose order mod n equals Euler's totient
Euler's Totient	\(\varphi(n) = n \prod_{p\|n}\left(1 - \frac{1}{p}\right)\)	Count of integers in [1, n] coprime to n
Existence Criterion	\(n \in \{1, 2, 4, p^k, 2p^k\}\)	Primitive roots exist only for these forms (p odd prime)
Number of Roots	\(\varphi(\varphi(n))\)	Count of primitive roots when they exist
Primitive Root Test	\(g^{\varphi(n)/p} \not\equiv 1 \pmod{n}\) for all primes \(p \| \varphi(n)\)	Sufficient condition: check only for prime factors of φ(n)
Generating All Roots	\(g^k \bmod n\) where \(\gcd(k, \varphi(n)) = 1\)	Once one root g is found, all others follow

Understanding Primitive Roots

A primitive root modulo n is an integer g such that \(\{g^1 \bmod n, g^2 \bmod n, \ldots, g^{\varphi(n)} \bmod n\}\) equals the set of all integers from 1 to n−1 that are coprime to n. In group-theoretic terms, g is a generator of the cyclic multiplicative group \((\mathbb{Z}/n\mathbb{Z})^*\). For example, 3 is a primitive root mod 7 because the powers 3¹=3, 3²=2, 3³=6, 3⁴=4, 3⁵=5, 3⁶=1 (mod 7) produce every element of {1, 2, 3, 4, 5, 6}.

When Do Primitive Roots Exist?

A classic result in number theory (proved by Gauss) states that primitive roots modulo n exist if and only if n is one of: 1, 2, 4, p^k, or 2p^k, where p is an odd prime and k ≥ 1. For other values of n, the group \((\mathbb{Z}/n\mathbb{Z})^*\) is not cyclic — it decomposes as a direct product of cyclic groups by the Chinese Remainder Theorem — so no single element can generate the entire group. For instance, \((\mathbb{Z}/8\mathbb{Z})^* \cong \mathbb{Z}/2 \times \mathbb{Z}/2\) has no primitive root.

How to Find Primitive Roots Efficiently

The standard algorithm works in two phases. Phase 1: find the smallest primitive root by trial. For each candidate g starting from 2, compute \(g^{\varphi(n)/p} \bmod n\) for every prime factor p of \(\varphi(n)\). If none of these equals 1, then g is a primitive root. In practice, the smallest primitive root is typically small — it is conjectured to be \(O(n^\epsilon)\) for any \(\epsilon > 0\). Phase 2: once a primitive root g is known, all other primitive roots are \(g^k \bmod n\) where \(\gcd(k, \varphi(n)) = 1\), giving exactly \(\varphi(\varphi(n))\) primitive roots in total.

How to Use the Primitive Root Calculator

Enter the modulus n: Type a positive integer in the input field, or click one of the quick example buttons to auto-fill a value.
Click Find Primitive Roots: Press the button to compute all primitive roots modulo n.
Review the results: See the count, the complete list of primitive roots, Euler's totient, group order, and whether primitive roots exist for your n.
Explore the visualization: For n ≤ 100, the interactive cyclic group wheel shows how each primitive root generates the entire group through its powers. Click on any root chip to see its cycle animated on the wheel.
Study the power table: The grid shows g^k mod n for k = 1, 2, …, φ(n), with primitive roots and the identity element highlighted in distinct colors.

Primitive Roots in Cryptography

Primitive roots play a central role in modern cryptography. In the Diffie-Hellman key exchange, two parties agree on a large prime p and a primitive root g mod p, then exchange public keys g^a mod p and g^b mod p. The shared secret g^ab mod p is computationally infeasible for an eavesdropper to determine, because computing discrete logarithms in large cyclic groups is believed to be hard. Similarly, ElGamal encryption and the Digital Signature Algorithm (DSA) both rely on the difficulty of the discrete logarithm problem in groups generated by primitive roots.

FAQ

What is a primitive root modulo n?

A primitive root modulo n is an integer g such that the powers g¹, g², …, g^φ(n) modulo n produce every integer coprime to n exactly once. Equivalently, g has multiplicative order equal to φ(n), meaning g generates the entire multiplicative group (Z/nZ)*.

For which values of n do primitive roots exist?

Primitive roots exist if and only if n is 1, 2, 4, p^k, or 2p^k, where p is an odd prime and k is a positive integer. For example, n = 7 (prime), n = 9 (3²), and n = 14 (2 × 7) all have primitive roots, but n = 8, n = 12, and n = 15 do not.

How many primitive roots does n have?

If n has primitive roots, then the number of primitive roots modulo n equals φ(φ(n)), where φ is Euler's totient function. For example, n = 7 has φ(φ(7)) = φ(6) = 2 primitive roots, which are 3 and 5.

How do you find primitive roots?

To find primitive roots of n: first compute φ(n) and factorize it. Then for each candidate g coprime to n, check if g^(φ(n)/p) is not congruent to 1 mod n for every prime factor p of φ(n). If all checks pass, g is a primitive root. All other roots can be found as g^k mod n where gcd(k, φ(n)) = 1.

Why are primitive roots important in cryptography?

Primitive roots are fundamental to the Diffie-Hellman key exchange, ElGamal encryption, and digital signature algorithms. They ensure that the discrete logarithm problem is hard, which is the basis of security for these cryptographic protocols. A primitive root generates all elements of the group, maximizing the search space for attackers.

Reference this content, page, or tool as:

"Primitive Root Calculator" at https://MiniWebtool.com/primitive-root-calculator/ from MiniWebtool, https://MiniWebtool.com/

by miniwebtool team. Updated: 2026-04-16

You can also try our AI Math Solver GPT to solve your math problems through natural language question and answer.

Related MiniWebtools:

Collatz Conjecture Calculator

Cube and Cube Root Calculator

Cube Root Calculator

Digital Root CalculatorNew

Euler's Totient Function Calculator

Möbius Function CalculatorNew

Modular Exponentiation CalculatorNew

n-th Root Calculator

Number of Digits CalculatorFeatured

Prime Factorization Calculator

Primitive Root Calculator

About Primitive Root Calculator

Applications of Primitive Roots

Key Concepts and Formulas

Understanding Primitive Roots

When Do Primitive Roots Exist?

How to Find Primitive Roots Efficiently

How to Use the Primitive Root Calculator

Primitive Roots in Cryptography

FAQ

Related MiniWebtools:

Advanced Math Operations:

Top & Updated: