Primitive Root Calculator
Find primitive roots modulo n, fundamental to number theory and cryptographic protocols like Diffie-Hellman.
Enter n (1 to 10,000) to find its primitive roots
A primitive root modulo n is an integer g whose powers generate all integers coprime to n. Formally, g is a primitive root modulo n if the multiplicative order of g modulo n equals phi(n), where phi is Euler's totient function.
Definition:
g is a primitive root modulo n if and only if:
- gcd(g, n) = 1
- The smallest positive k such that g^k = 1 (mod n) is k = phi(n)
Existence:
Primitive roots exist only for n = 1, 2, 4, p^k, or 2p^k, where p is an odd prime.
Example: For n = 7, we have phi(7) = 6. The number 3 is a primitive root because 3^1 = 3, 3^2 = 2, 3^3 = 6, 3^4 = 4, 3^5 = 5, 3^6 = 1 (mod 7), generating all residues 1-6.
Counting: If n has primitive roots, it has exactly phi(phi(n)) of them. For prime p, this equals phi(p-1).
Applications: Primitive roots are essential in the Diffie-Hellman key exchange, ElGamal encryption, and discrete logarithm-based cryptography. They ensure maximum cycle length in pseudorandom number generators and are used in primality testing algorithms.
What is a primitive root?
A primitive root modulo n is an integer g such that every integer coprime to n is congruent to some power of g modulo n. In other words, g generates all the units in the multiplicative group of integers modulo n. For example, 3 is a primitive root modulo 7 because the powers 3^1, 3^2, 3^3, 3^4, 3^5, 3^6 give all residues 1-6 modulo 7.
Which numbers have primitive roots?
Primitive roots exist only for n = 1, 2, 4, p^k, or 2p^k, where p is an odd prime and k is a positive integer. For example, 7 (prime), 9 (3^2), and 14 (2*7) all have primitive roots, but 8, 12, and 15 do not.
How many primitive roots does a number have?
If n has primitive roots, then it has exactly phi(phi(n)) of them, where phi is Euler's totient function. For a prime p, this equals phi(p-1). For example, 7 has phi(6) = 2 primitive roots (which are 3 and 5).
Why are primitive roots important in cryptography?
Primitive roots are fundamental to the Diffie-Hellman key exchange and the ElGamal encryption system. They ensure that the discrete logarithm problem is hard, which is the basis for the security of these cryptographic protocols. A primitive root guarantees that all possible values can be generated, maximizing the key space.