Helpful context:

Fermat’s little theorem tells us that $a^{p-1} \equiv 1 \pmod{p}$ for every $a$ not divisible by the prime $p$. But it says nothing about smaller exponents. Could $a^{(p-1)/2} \equiv 1$ for some $a$? Could the powers of $a$ repeat after only a few steps? The answer is: it depends on $a$. Some elements have the full possible order $p-1$, cycling through all $p-1$ nonzero residues before returning to 1. These elements are called primitive roots, or generators.

The existence of primitive roots is not obvious. It requires a subtle argument about how many solutions polynomial equations can have modulo a prime. Once we know primitive roots exist, a logarithm becomes possible: every nonzero residue is a power of a fixed generator, so we can define the discrete logarithm. And computing that logarithm turns out to be hard - in a way that no one can currently explain theoretically but that everyone observes computationally. The hardness of the discrete logarithm problem is the foundation of Diffie-Hellman key exchange and ElGamal encryption.

The Multiplicative Group Mod $p$

For a prime $p$, the nonzero residues $\{1, 2, \ldots, p-1\}$ form an abelian group under multiplication mod $p$. Call this group $(\mathbb{Z}/p\mathbb{Z})^\times$, or $\mathbb{F}_p^\times$ for short. Its order is $p - 1$.

By Fermat’s little theorem, every element $a$ of this group satisfies $a^{p-1} = 1$. The order of $a$ is the smallest positive integer $k$ such that $a^k \equiv 1 \pmod{p}$. Lagrange’s theorem guarantees that $\text{ord}(a) \mid p-1$.

The possible orders of elements divide $p - 1$. For $p = 7$: $p - 1 = 6$, so element orders are among $\{1, 2, 3, 6\}$.

Element $a$ Powers mod 7 Order
1 $1$ 1
2 $2, 4, 1$ 3
3 $3, 2, 6, 4, 5, 1$ 6
4 $4, 2, 1$ 3
5 $5, 4, 6, 2, 3, 1$ 6
6 $6, 1$ 2

Elements 3 and 5 have order 6 = $p - 1$. Their powers hit every nonzero residue mod 7. These are the primitive roots mod 7.

Primitive Roots

Definition. An integer $g$ is a primitive root (or generator) modulo $p$ if $\text{ord}(g) = p - 1$, i.e., if the sequence $g^1, g^2, g^3, \ldots, g^{p-1}$ is a permutation of $\{1, 2, \ldots, p-1\}$ modulo $p$.

When $g$ is a primitive root mod $p$, every nonzero residue can be written as $g^k$ for some $k \in \{1, \ldots, p-1\}$. In the language of group theory: $g$ generates $(\mathbb{Z}/p\mathbb{Z})^\times$, so this group is cyclic.

Number of primitive roots. There are exactly $\varphi(p-1)$ primitive roots mod $p$, where $\varphi$ is Euler’s totient function. For $p = 7$: $\varphi(6) = \varphi(2)\varphi(3) = 1 \cdot 2 = 2$, which matches (elements 3 and 5).

Existence of Primitive Roots Mod $p$

Theorem. For every prime $p$, there exists a primitive root modulo $p$.

Proof. We show $(\mathbb{Z}/p\mathbb{Z})^\times$ is cyclic. The argument proceeds by counting elements of each order.

Lemma. A polynomial of degree $d$ over $\mathbb{Z}/p\mathbb{Z}$ has at most $d$ roots.

Proof of Lemma. Over a field (and $\mathbb{Z}/p\mathbb{Z}$ is a field since $p$ is prime), a polynomial $f(x)$ of degree $d$ has the factorization property: if $r$ is a root, then $f(x) = (x - r)g(x)$ where $\deg g = d-1$. By induction, at most $d$ roots. $\square$

Now let $G = (\mathbb{Z}/p\mathbb{Z})^\times$ with $|G| = p-1$. For each divisor $d$ of $p - 1$, let $\psi(d)$ denote the number of elements of $G$ of order exactly $d$.

Every element has some order dividing $p-1$. So $\sum_{d \mid p-1} \psi(d) = p - 1$.

Counting elements of each order. If $\psi(d) > 0$, let $a$ have order $d$. Then $1, a, a^2, \ldots, a^{d-1}$ are $d$ distinct elements satisfying $x^d \equiv 1 \pmod{p}$ (since $(a^k)^d = (a^d)^k = 1$). By the lemma, $x^d - 1 \equiv 0 \pmod p$ has at most $d$ roots. So all solutions to $x^d \equiv 1$ are among $\{1, a, \ldots, a^{d-1}\}$.

The elements of order exactly $d$ among $\{1, a, \ldots, a^{d-1}\} = \{a^0, a^1, \ldots, a^{d-1}\}$ are those $a^k$ where $\text{ord}(a^k) = d$. Now $\text{ord}(a^k) = d / \gcd(k, d)$, so $\text{ord}(a^k) = d$ iff $\gcd(k, d) = 1$. There are $\varphi(d)$ such $k$ in $\{0, \ldots, d-1\}$.

So: $\psi(d) = 0$ or $\psi(d) = \varphi(d)$.

Finishing. We know $\sum_{d \mid p-1} \psi(d) = p - 1$ and $\sum_{d \mid p-1} \varphi(d) = p - 1$ (a standard identity). Since $0 \leq \psi(d) \leq \varphi(d)$ for all $d$, and the sums agree, we must have $\psi(d) = \varphi(d)$ for all $d \mid p - 1$.

In particular, $\psi(p-1) = \varphi(p-1) \geq 1$. So elements of order $p-1$ exist. $\square$

Finding Primitive Roots

The proof is nonconstructive. In practice, to find a primitive root mod $p$:

  1. Factor $p - 1 = q_1^{a_1} q_2^{a_2} \cdots q_k^{a_k}$.
  2. For a candidate $g$, check that $g^{(p-1)/q_i} \not\equiv 1 \pmod{p}$ for each prime factor $q_i$.
  3. If all checks pass, $g$ is a primitive root.

Why this works. If $g$ is not a primitive root, then $\text{ord}(g) = d$ for some proper divisor $d \mid p-1$. Then $d \mid (p-1)/q_i$ for at least one prime factor $q_i$ of $p-1$, so $g^{(p-1)/q_i} \equiv 1 \pmod p$.

Example. Is $g = 2$ a primitive root mod $11$? Here $p - 1 = 10 = 2 \cdot 5$. Check $2^{10/2} = 2^5 = 32 \equiv 10 \equiv -1 \not\equiv 1 \pmod{11}$, and $2^{10/5} = 2^2 = 4 \not\equiv 1 \pmod{11}$. Both checks pass, so 2 is a primitive root mod 11.

Discrete Logarithm

Definition. Let $g$ be a primitive root mod $p$. For $y \in \{1, \ldots, p-1\}$, the discrete logarithm of $y$ base $g$ modulo $p$ is the unique integer $x \in \{1, \ldots, p-1\}$ such that

$$g^x \equiv y \pmod{p}.$$

Written $x = \log_g y \pmod{p}$.

Example. With $g = 3$ and $p = 7$: $\log_3 5 \equiv 5 \pmod 6$ (since $3^5 = 243 \equiv 5 \pmod 7$).

Forward direction (easy). Given $g$, $p$, and $x$: compute $y = g^x \bmod p$ in $O(\log x)$ time using fast exponentiation.

Inverse direction (hard). Given $g$, $p$, and $y$: find $x$ such that $g^x \equiv y \pmod p$. No polynomial-time algorithm is known for this. The best general algorithm (baby-step giant-step) runs in $O(\sqrt{p})$ time and space. The Number Field Sieve variant runs in sub-exponential time - like factoring - but still far from polynomial.

The Discrete Logarithm Problem (DLP). Given $(g, p, y)$, find $\log_g y \pmod p$. This is believed hard (no poly-time algorithm known) for appropriately chosen parameters.

Diffie-Hellman Key Exchange

Whitfield Diffie and Martin Hellman (1976) used the DLP to build the first public-key protocol: two parties who have never communicated can agree on a shared secret over a public channel, with no eavesdropper able to learn it.

Protocol. Alice and Bob publicly agree on a prime $p$ and a primitive root $g$.

  1. Alice picks a secret $a \in \{1, \ldots, p-2\}$ and sends $A = g^a \bmod p$ to Bob.
  2. Bob picks a secret $b \in \{1, \ldots, p-2\}$ and sends $B = g^b \bmod p$ to Alice.
  3. Alice computes $B^a = g^{ab} \bmod p$.
  4. Bob computes $A^b = g^{ab} \bmod p$.

Both arrive at the same shared secret $K = g^{ab} \bmod p$.

Why this is secure. An eavesdropper sees $g$, $p$, $A = g^a$, $B = g^b$. To compute $K = g^{ab}$, they need either $a$ or $b$. Getting $a$ from $g^a$ is the DLP. This is the Computational Diffie-Hellman problem (CDH), which is at most as hard as DLP and conjectured equivalent for most practical parameters.

The gap. Multiplying two things together ($g^a \cdot g^b = g^{a+b}$) is easy. Recovering the pieces (finding $a$ from $g^a$) is hard. This asymmetry is what all DH-based cryptography exploits.

Safe Primes and Group Structure

Safe prime. A prime $p = 2q + 1$ where $q$ is also prime. The prime $q$ is called a Sophie Germain prime.

Why safe primes are good for DH. For a safe prime $p$, the order of $(\mathbb{Z}/p\mathbb{Z})^\times$ is $p - 1 = 2q$. The subgroups have orders $1, 2, q, 2q$. The DLP is hardest in the large prime-order subgroup of order $q$.

If $p - 1$ has many small prime factors, the Pohlig-Hellman algorithm can decompose the DLP into easier subproblems and solve it efficiently. A safe prime ensures the only large prime factor of $p - 1$ is $q$, so Pohlig-Hellman provides no advantage.

In practice. Standard DH parameters use safe primes (e.g., RFC 3526 defines primes of this form for use in IKE). The working subgroup is the unique subgroup of order $q$, and elements are checked to belong to this subgroup.

Primitive Roots Mod Composite Moduli

Primitive roots (generators of $(\mathbb{Z}/n\mathbb{Z})^\times$) do not exist for all $n$. The complete characterization:

Theorem. $(\mathbb{Z}/n\mathbb{Z})^\times$ is cyclic (primitive root exists) if and only if $n = 1, 2, 4, p^k$, or $2p^k$ for an odd prime $p$ and $k \geq 1$.

No primitive roots for other $n$. For example:

  • $n = 8$: $(\mathbb{Z}/8\mathbb{Z})^\times = \{1, 3, 5, 7\}$. Every element has order dividing 2, so no element has order $\varphi(8) = 4$. The group is $\mathbb{Z}/2\mathbb{Z} \times \mathbb{Z}/2\mathbb{Z}$, not cyclic.
  • $n = 15$: $\varphi(15) = 8$. The group is $\mathbb{Z}/2\mathbb{Z} \times \mathbb{Z}/4\mathbb{Z}$, not cyclic.
  • $n = pq$ for distinct odd primes: $(\mathbb{Z}/pq\mathbb{Z})^\times \cong (\mathbb{Z}/p\mathbb{Z})^\times \times (\mathbb{Z}/q\mathbb{Z})^\times \cong \mathbb{Z}/(p-1)\mathbb{Z} \times \mathbb{Z}/(q-1)\mathbb{Z}$. This is cyclic only if $\gcd(p-1, q-1) = 1$, which fails for any two odd primes (both $p-1$ and $q-1$ are even).

This is why RSA (which uses $n = pq$) does not use the discrete logarithm directly - the multiplicative group is not cyclic. DH operates mod a prime $p$ precisely because $(\mathbb{Z}/p\mathbb{Z})^\times$ is guaranteed cyclic.

Summary

Concept Definition Key property
Order of $a$ mod $p$ Smallest $k$ with $a^k \equiv 1$ Divides $p-1$ (Fermat/Lagrange)
Primitive root mod $p$ $g$ with $\text{ord}(g) = p-1$ Generates all of $(\mathbb{Z}/p\mathbb{Z})^\times$
Existence Always exists for prime $p$ Follows from poly. root bound over fields
Number of primitive roots $\varphi(p-1)$ Exactly $\varphi(p-1)$ generators
Discrete logarithm $x = \log_g y$ s.t. $g^x \equiv y$ Hard to compute; forward direction easy
Diffie-Hellman Shared secret $g^{ab}$ from $g^a, g^b$ Security = CDH hardness
Safe prime $p = 2q+1$ $p - 1 = 2q$, $q$ prime Resists Pohlig-Hellman attack
Cyclic $(\mathbb{Z}/n\mathbb{Z})^\times$ Exists iff $n = 1,2,4,p^k,2p^k$ Fails for $n = pq$ (RSA setting)

Read next: