Primitive Roots

Generators of the multiplicative group (ℤ/nℤ)* — the discrete logarithm problem underpins modern cryptography

Select modulus and base to explore
13
2
5
g is a primitive root mod n ⟺ ord_n(g) = φ(n) ⟺ {g^k mod n | k=0..φ(n)-1} = (ℤ/nℤ)*

Primitive roots exist iff n ∈ {1, 2, 4, p^k, 2p^k} for odd prime p (Gauss). The number of primitive roots mod p is φ(p-1). The Diffie-Hellman key exchange and ElGamal encryption rely on the hardness of the discrete logarithm: given g^x mod p, find x.