Primitive Roots
Some elements are so energetic that their powers sweep out every invertible residue
before returning to 1. Such a generator is a primitive
root. When one exists, the tangled multiplicative world modulo
n turns out to be a single, simple cycle.
Definition
A primitive root modulo n is an element
g whose
order
is the maximum possible, \varphi(n). Equivalently, its powers run
through all \varphi(n) residues coprime to
n:
\{\,g^1, g^2, \dots, g^{\varphi(n)}\,\} = \{\text{all units mod } n\}.
Modulo 7, 3 is a primitive root: its powers
3, 2, 6, 4, 5, 1 hit every nonzero residue. But
2 is not — it only ever reaches \{1, 2, 4\}.
When do they exist?
A primitive root modulo n exists exactly when
n is one of
1,\ 2,\ 4,\ p^{k},\ \text{or } 2p^{k} \quad (p \text{ an odd prime}).
Crucially, every prime p has a primitive root — so the units
modulo a prime always form one clean cycle of length p - 1. (For other
n, like 8 or 12, no
single element generates everything.) A prime p has exactly
\varphi(p-1) primitive roots.
Why this is the engine of cryptography
A primitive root g modulo a large prime p
turns the multiplicative group into a number line of exponents: every nonzero residue is
g^{x} for a unique x. Going forwards
(exponent \to residue) is fast by
fast exponentiation;
going backwards is believed to be astronomically hard. That one-way street is the
discrete logarithm problem,
the foundation of Diffie–Hellman and ElGamal.