21.01.05 · number-theory / elementary

Primitive roots and the structure of $(Z / n Z)^{\times}$

shipped3 tiersLean: none

Anchor (Master): Gauss 1801 *Disquisitiones Arithmeticae* arts. 53-94 (first systematic theory of primitive roots and the classification of moduli admitting them); Artin 1927 (unpublished letter to Hasse, the primitive-root density conjecture); Hooley 1967 *J. reine angew. Math.* 225 (Artin's conjecture under GRH); Gupta-Murty 1984 *Invent. Math.* 78 (unconditional positive proportion); Heath-Brown 1986 *Quart. J. Math.* (2) 37 (Artin's conjecture for at least one of three given non-square-non-$-1$ integers); Diffie-Hellman 1976 *IEEE Trans. Inform. Theory* IT-22; Shor 1994/1997 *SIAM J. Comput.* 26 (quantum polynomial-time DLP and factoring); Hardy-Wright 2008 6e §VI-§VIII

Intuition Beginner

A primitive root modulo $p$ is a single nonzero residue whose powers, taken modulo $p$ , sweep out every other nonzero residue exactly once before returning to $1$ . For the prime $p = 5$ , the nonzero residues are $1, 2, 3, 4$ . Take $2$ as the candidate: $2^{1} = 2$ ; $2^{2} = 4$ ; $2^{3} = 8 \equiv 3 (mod 5)$ ; $2^{4} = 16 \equiv 1 (mod 5)$ . The four powers $2, 4, 3, 1$ are exactly the four nonzero residues, in a different order. So $2$ is a primitive root modulo $5$ .

Not every element is a primitive root. For the same prime $p = 5$ , take the candidate $4$ : $4^{1} = 4$ ; $4^{2} = 16 \equiv 1 (mod 5)$ . The powers of $4$ cycle back to $1$ after only $2$ steps, missing $2$ and $3$ entirely. The element $4$ has order $2$ in $(Z /5 Z)^{\times}$ , not the full order $4 = p - 1$ needed to be a primitive root.

Why does this concept exist? Because primitive roots reveal that $(Z / p Z)^{\times}$ — the multiplicative group of nonzero residues modulo $p$ — has a single generator. Once you know a primitive root $g$ , every other nonzero residue is some power of $g$ . This is the prime-modulus version of the deeper fact that the unit group is cyclic: built out of one generating element, like the hours on a clock.

The classification of which moduli admit primitive roots is a celebrated theorem of Gauss in his 1801 Disquisitiones Arithmeticae. The moduli $n$ for which $(Z / n Z)^{\times}$ is cyclic — equivalently, the moduli for which a primitive root exists — are exactly $n = 1, 2, 4$ , the odd prime powers $p^{k}$ , and twice the odd prime powers $2 p^{k}$ . For every other $n$ , the unit group splits as a product of two or more cyclic pieces, and no single element generates the whole group.

The applied importance of primitive roots is the discrete logarithm problem. Fix a prime $p$ and a primitive root $g$ modulo $p$ . Every nonzero residue $a$ is then $g^{k}$ for a unique $k$ with $0 \leq k < p - 1$ . Computing $a$ from $k$ is fast (repeated squaring takes about $lo g_{2} k$ multiplications). Recovering $k$ from $a$ — the discrete logarithm — appears to be hard: no classical algorithm is known that runs in time polynomial in $lo g p$ .

This asymmetry is the cornerstone of Diffie-Hellman key exchange (1976), ElGamal encryption (1985), and the Digital Signature Algorithm — every secure VPN, every TLS handshake done with a non-elliptic-curve cipher suite, every Tor circuit. The quantum algorithm of Peter Shor 1994 would break this asymmetry on a sufficiently large quantum computer, and the post-quantum cryptography programme exists precisely to plan for that future.

Visual Beginner

A diagram of the cyclic orbit of a primitive root modulo a small prime. For $p = 7$ the primitive root $3$ generates the orbit $3^{1} = 3$ , $3^{2} = 9 \equiv 2$ , $3^{3} \equiv 6$ , $3^{4} \equiv 4$ , $3^{5} \equiv 5$ , $3^{6} \equiv 1$ . The six powers $3, 2, 6, 4, 5, 1$ form a complete cycle through every nonzero residue modulo $7$ , then close back to $1$ .

The picture captures the defining property of a primitive root: the orbit visits every nonzero residue exactly once, and then returns to $1$ after exactly $p - 1$ steps. Compare with the orbit of $2$ modulo $7$ : $2, 4, 1, 2, 4, 1$ — a shorter cycle of length $3$ that misses three of the residues. The element $2$ has order $3$ modulo $7$ , and $3$ has order $6$ ; only the latter is a primitive root.

Worked example Beginner

Find a primitive root modulo $p = 11$ , and verify it by listing its orbit.

Step 1. The order of a primitive root must equal $p - 1 = 10$ . By a basic group fact, the order of any element divides $10$ , so the possible orders are $1, 2, 5, 10$ . A candidate $g$ is a primitive root if and only if its order is $10$ — equivalently, $g^{5} \neq \equiv 1 (mod 11)$ and $g^{2} \neq \equiv 1 (mod 11)$ .

Step 2. Test $g = 2$ . Compute $2^{2} = 4 \neq \equiv 1 (mod 11)$ and $2^{5} = 32 = 2 \cdot 11 + 10 \equiv 10 \equiv - 1 (mod 11)$ . Both order-failing conditions are avoided, so the order of $2$ is exactly $10$ . The element $2$ is a primitive root modulo $11$ .

Step 3. List the orbit: $2^{1} = 2$ ; $2^{2} = 4$ ; $2^{3} = 8$ ; $2^{4} = 16 \equiv 5 (mod 11)$ ; $2^{5} \equiv 10 (mod 11)$ ; $2^{6} \equiv 20 \equiv 9 (mod 11)$ ; $2^{7} \equiv 18 \equiv 7 (mod 11)$ ; $2^{8} \equiv 14 \equiv 3 (mod 11)$ ; $2^{9} \equiv 6 (mod 11)$ ; $2^{10} \equiv 12 \equiv 1 (mod 11)$ .

Step 4. The ten powers $2, 4, 8, 5, 10, 9, 7, 3, 6, 1$ exhaust the ten nonzero residues modulo $11$ , confirming $2$ is a primitive root.

What this tells us: to test whether $g$ is a primitive root modulo $p$ , you do not need to compute the full orbit. You only need to check that $g^{(p - 1) / q} \neq \equiv 1 (mod p)$ for every prime $q$ dividing $p - 1$ . For $p = 11$ the prime divisors of $10$ are $2$ and $5$ , and the two checks $g^{5} \neq \equiv 1$ and $g^{2} \neq \equiv 1$ are enough.

Check your understanding Beginner

Formal definition Intermediate+

We restate the order of an element and the notion of a primitive root in the precise group-theoretic language inherited from 21.01.04.

Definition (multiplicative order modulo $n$ ). Let $n \geq 1$ be an integer and $a$ an integer with $g cd (a, n) = 1$ . The multiplicative order of $a$ modulo $n$ , written $ord_{n} (a)$ , is the least positive integer $k$ such that $a^{k} \equiv 1 (mod n)$ .

Such a $k$ exists because $(Z / n Z)^{\times}$ is a finite group of order $φ (n)$ , so the cyclic subgroup generated by $[a]_{n}$ is finite. By Lagrange's theorem applied to the finite group $(Z / n Z)^{\times}$ , $$ \mathrm{ord}_n(a) ;\big|; \varphi(n). $$

Definition (primitive root modulo $n$ ). A primitive root modulo $n$ is an integer $g$ with $g cd (g, n) = 1$ and $ord_{n} (g) = φ (n)$ . Equivalently, $[g]_{n}$ generates $(Z / n Z)^{\times}$ as a cyclic group: every $[a]_{n} \in (Z / n Z)^{\times}$ is $[g^{k}]_{n}$ for some integer $k$ .

The existence of a primitive root modulo $n$ is equivalent to $(Z / n Z)^{\times}$ being cyclic — generated by a single element. The classification of such $n$ is the structure theorem proved in the next subsection.

Definition (discrete logarithm / index). Let $n$ be a modulus admitting a primitive root $g$ , so $(Z / n Z)^{\times}$ is cyclic of order $φ (n)$ with generator $[g]_{n}$ . For every $a$ coprime to $n$ , the discrete logarithm (or index) of $a$ to base $g$ modulo $n$ is the unique integer $k$ with $0 \leq k < φ (n)$ such that $g^{k} \equiv a (mod n)$ . Notation: $k = ind_{g} (a) = lo g_{g} (a)$ .

The discrete logarithm is the inverse function of the exponentiation map $k \mapsto g^{k}$ , which is a group isomorphism $Z / φ (n) Z \to (Z / n Z)^{\times}$ . The Gauss index calculus exploits this isomorphism: $ind_{g} (ab) \equiv ind_{g} (a) + ind_{g} (b) (mod φ (n))$ — multiplicative structure modulo $n$ becomes additive structure modulo $φ (n)$ .

Counterexamples to common slips

"Every $(Z / n Z)^{\times}$ is cyclic." False already for $n = 8$ : the unit group has order $φ (8) = 4$ but every unit squares to $1$ , so $(Z /8)^{\times} ≅ Z /2 \times Z /2$ is not cyclic. The classification theorem restricts cyclicity to $n \in {1, 2, 4, p^{k}, 2 p^{k}}$ for $p$ an odd prime.
"The order of $a$ modulo $n$ equals $φ (n)$ for some $a$ in every modulus." False — the previous slip restated. For $n = 8$ the maximum order is $2$ , strictly below $φ (8) = 4$ . The maximum achievable order is the Carmichael function $λ (n)$ of 21.01.04, which can be strictly less than $φ (n)$ .
"The discrete logarithm is well-defined for every nonzero residue." Only when the residue is coprime to the modulus. The residue $4$ modulo $6$ has no discrete logarithm to base any primitive root of $(Z /6)^{\times} = {1, 5}$ because $g cd (4, 6) = 2 \neq = 1$ . The discrete log lives on the unit group, not on all of $Z / n$ .

Key theorem with proof Intermediate+

The signature theorem of this unit is the existence of a primitive root modulo every prime. The proof technique — counting elements of each order via the field structure of $F_{p}$ and the totient sum $\sum_{d ∣ m} φ (d) = m$ — is the prototype for every cyclicity proof in elementary number theory.

Theorem (Gauss; existence of primitive roots modulo $p$ ). For every prime $p$ , the group $(Z / p Z)^{\times}$ is cyclic of order $p - 1$ . The number of primitive roots modulo $p$ is $φ (p - 1)$ .

Proof. Let $G = (Z / p Z)^{\times}$ , a finite abelian group of order $p - 1$ . For each positive divisor $d$ of $p - 1$ , let $$ N(d) ;=; # {, [a]_p \in G : \mathrm{ord}([a]p) = d ,}. $$ The element orders are exactly the divisors of $p - 1$ (Lagrange), so $$ \sum{d \mid p - 1} N(d) ;=; p - 1. \quad (\star) $$

We bound $N (d)$ by the field property of $F_{p} = Z / p Z$ . An element of order dividing $d$ is a root of the polynomial $x^{d} - 1 \in F_{p} [x]$ . A polynomial of degree $d$ over a field has at most $d$ roots, so the number of elements of order dividing $d$ is at most $d$ . Hence $$ \sum_{e \mid d} N(e) ;\leq; d. \quad (\star\star) $$

The crucial step: when $N (d) > 0$ , the bound $(⋆ ⋆)$ becomes an equality. Suppose $[a]_{p}$ has order exactly $d$ ; then the powers $[a]_{p}, [a]_{p}^{2}, \dots, [a]_{p}^{d} = [1]_{p}$ are $d$ distinct elements of order dividing $d$ , so they are all of them by $(⋆ ⋆)$ . Among these $d$ elements, the number of order exactly $d$ is the number of $k \in {1, \dots, d}$ with $g cd (k, d) = 1$ — namely $φ (d)$ . Hence: $$ N(d) \in {0, \varphi(d)} \quad \text{for every } d \mid p - 1. $$

Combining with $(⋆)$ and the elementary totient identity $\sum_{d ∣ m} φ (d) = m$ (proved in 21.01.03 Proposition 1): $$ p - 1 ;=; \sum_{d \mid p - 1} N(d) ;\leq; \sum_{d \mid p - 1} \varphi(d) ;=; p - 1. $$ The inequality is an equality. Hence $N (d) = φ (d)$ for every $d ∣ p - 1$ . In particular $N (p - 1) = φ (p - 1) > 0$ since $p \geq 2$ , so there exists an element of order exactly $p - 1$ — a primitive root. The cyclic subgroup generated by any such element has order $p - 1 = ∣ G ∣$ , so it is all of $G$ , and $G$ is cyclic.

The count of primitive roots is $N (p - 1) = φ (p - 1)$ . $□$

Bridge. The polynomial-degree bound $(⋆ ⋆)$ is the foundational reason that finite subgroups of multiplicative groups of fields are cyclic — and the central insight is exactly this: the field property of $F_{p}$ forces every order- $d$ root-locus to have exactly $φ (d)$ elements of order $d$ (or zero), and the totient summation $\sum_{d ∣ m} φ (d) = m$ forces every divisor to be hit. This is the bridge to 01.02.18 pending finite fields $F_{q}$ : every $F_{q}^{\times}$ is cyclic of order $q - 1$ by the same argument (no exception, unlike the integer-modulus case), and the unit group of any field has every finite subgroup cyclic. The proof generalises to the lift from $(Z / p)^{\times}$ to $(Z / p^{k})^{\times}$ via Hensel: a primitive root modulo $p$ lifts to a primitive root modulo $p^{k}$ for $p$ odd (the technical content of Theorem 1 below), identifying the orbit structure modulo $p^{k}$ with the orbit structure modulo $p$ times a $p^{k - 1}$ -cyclic radical. The same divisor-counting pattern recurs in 21.01.06 quadratic residues, where the count of squares is $(p - 1) /2$ via the kernel-image computation of the squaring map.

Exercises Intermediate+

Exercise 4 (medium, symbolic).

Prove that the count of primitive roots modulo a prime $p$ is $φ (p - 1)$ .

Hint

Use the cyclic structure of $(Z / p)^{\times}$ established by the Key Theorem. The generators of a cyclic group of order $m$ are precisely the elements $g^{k}$ with $g cd (k, m) = 1$ .

Answer

Fix a primitive root $g$ modulo $p$ . By the Key Theorem, $(Z / p)^{\times} = {g^{0}, g^{1}, \dots, g^{p - 2}}$ is cyclic of order $p - 1$ generated by $g$ .

The element $g^{k}$ has order $ord (g^{k}) = (p - 1) / g cd (k, p - 1)$ — a standard cyclic-group computation. So $g^{k}$ is a primitive root if and only if $ord (g^{k}) = p - 1$ , equivalent to $g cd (k, p - 1) = 1$ .

The number of $k \in {0, 1, \dots, p - 2}$ with $g cd (k, p - 1) = 1$ is $φ (p - 1)$ by definition of the totient. (The case $k = 0$ corresponds to the identity $g^{0} = 1$ , which has $g cd (0, p - 1) = p - 1 \neq = 1$ for $p > 2$ , so it is not counted — consistent with $1$ not being a primitive root.)

Hence there are exactly $φ (p - 1)$ primitive roots modulo $p$ .

For $p = 7$ : $φ (6) = 2$ primitive roots, namely $3$ and $5 = 3^{5}$ . For $p = 11$ : $φ (10) = 4$ primitive roots, namely $2, 6, 7, 8$ . For $p = 13$ : $φ (12) = 4$ primitive roots: $2, 6, 7, 11$ .

Rubric: full credit for the cyclic-group identification of generators with $g cd (k, m) = 1$ .

Exercise 5 (medium, symbolic).

Prove that $(Z /8)^{\times}$ is not cyclic. Identify its isomorphism type as a product of cyclic groups.

Hint

The units modulo $8$ are ${1, 3, 5, 7}$ . Compute the order of each. A cyclic group of order $4$ has an element of order $4$ .

Answer

The units modulo $8$ are ${1, 3, 5, 7}$ , four in number, matching $φ (8) = 4$ .

Compute squares: $1^{2} = 1$ ; $3^{2} = 9 \equiv 1 (mod 8)$ ; $5^{2} = 25 \equiv 1 (mod 8)$ ; $7^{2} = 49 \equiv 1 (mod 8)$ . Every unit squares to $1$ , so every non-identity unit has order exactly $2$ , and the identity has order $1$ .

A cyclic group of order $4$ has an element of order $4$ ; since $(Z /8)^{\times}$ has no such element, it is not cyclic. Every element has order dividing $2$ , so $(Z /8)^{\times}$ is an elementary abelian $2$ -group. With four elements, this forces $(Z /8)^{\times} ≅ Z /2 \times Z /2$ — the Klein four-group $V_{4}$ .

Explicit isomorphism: $1 \leftrightarrow (0, 0)$ , $3 \leftrightarrow (1, 0)$ , $5 \leftrightarrow (0, 1)$ , $7 \leftrightarrow (1, 1)$ . (Or any other identification consistent with the group structure.)

This is the base case of the general structure $(Z / 2^{k})^{\times} ≅ Z /2 \times Z / 2^{k - 2}$ for $k \geq 3$ — non-cyclic for $k \geq 3$ , in contrast to $(Z / p^{k})^{\times}$ which is cyclic for $p$ odd. This is the only family of exceptions in the cyclicity classification.

Rubric: full credit for the squaring computation, the order-determination of every unit, and the identification of the resulting $Z /2 \times Z /2$ structure.

Exercise 6 (medium, symbolic).

Prove that if $g$ is a primitive root modulo an odd prime $p$ , then either $g$ or $g + p$ is a primitive root modulo $p^{2}$ .

Hint

The lift from modulo $p$ to modulo $p^{2}$ is the simplest case of Hensel's lemma. The order of $g$ modulo $p^{2}$ is either $p - 1$ or $p (p - 1) = φ (p^{2})$ . Show that it is exactly $p (p - 1)$ unless $g^{p - 1} \equiv 1 (mod p^{2})$ — in which case $(g + p)^{p - 1} \neq \equiv 1 (mod p^{2})$ .

Answer

Let $g$ be a primitive root modulo $p$ . The order $d$ of $g$ modulo $p^{2}$ divides $φ (p^{2}) = p (p - 1)$ . Reducing modulo $p$ , $g^{d} \equiv 1 (mod p^{2})$ forces $g^{d} \equiv 1 (mod p)$ , so the order $p - 1$ of $g$ modulo $p$ divides $d$ . The divisors of $p (p - 1)$ that are multiples of $p - 1$ are $p - 1$ and $p (p - 1)$ , so $d \in {p - 1, p (p - 1)}$ .

If $d = p (p - 1)$ , then $g$ is already a primitive root modulo $p^{2}$ .

If $d = p - 1$ , i.e., $g^{p - 1} \equiv 1 (mod p^{2})$ , replace $g$ by $g^{'} = g + p$ . Then $g^{'} \equiv g (mod p)$ , so $g^{'}$ is still a primitive root modulo $p$ . Expand by the binomial theorem (using $p$ odd so $p - 1 \geq 2$ ): $$ (g + p)^{p - 1} ;=; g^{p - 1} + (p - 1) g^{p - 2} p + \binom{p - 1}{2} g^{p - 3} p^2 + \cdots. $$ Modulo $p^{2}$ , every term with $p^{2}$ or higher vanishes, so $$ (g + p)^{p - 1} ;\equiv; g^{p - 1} + (p - 1) g^{p - 2} p ;\equiv; 1 - p g^{p - 2} \pmod{p^2}. $$ Since $p ∤ g$ (as $g cd (g, p) = 1$ ), $p ∤ g^{p - 2}$ , so $p g^{p - 2} \neq \equiv 0 (mod p^{2})$ . Hence $(g + p)^{p - 1} \neq \equiv 1 (mod p^{2})$ . The order of $g + p$ modulo $p^{2}$ is therefore $p (p - 1)$ , and $g + p$ is a primitive root modulo $p^{2}$ .

In either case, at least one of $g, g + p$ is a primitive root modulo $p^{2}$ . This is the inductive step that lifts a primitive root modulo $p$ to a primitive root modulo $p^{k}$ for every $k \geq 1$ , with $p$ odd.

Rubric: full credit for the $d \in {p - 1, p (p - 1)}$ dichotomy and the binomial-expansion lifting argument.

Exercise 7 (hard, symbolic).

Prove the full structure theorem for $(Z / n)^{\times}$ : the unit group is cyclic if and only if $n \in {1, 2, 4, p^{k}, 2 p^{k}}$ for $p$ an odd prime and $k \geq 1$ .

Hint

Use CRT to reduce to the prime-power case. The case $p$ odd uses Exercise 6 (Hensel lifting); the case $p = 2$ separates $k = 1, 2$ (cyclic) from $k \geq 3$ (Klein-times-cyclic structure). The "only if" direction: a CRT product of two non-identity cyclic groups with even orders is not cyclic.

Answer

By CRT 21.01.03, $(Z / n)^{\times} ≅ \prod_{p ∣ n} (Z / p^{e_{p}})^{\times}$ where $n = \prod p^{e_{p}}$ .

Step 1 — Prime powers $p$ odd. By Exercise 6 and induction, $(Z / p^{k})^{\times}$ is cyclic of order $φ (p^{k}) = p^{k - 1} (p - 1)$ for every $p$ odd and $k \geq 1$ .

Step 2 — Powers of $2$ . $(Z /2)^{\times}$ is the identity group (cyclic of order $1$ ). $(Z /4)^{\times} = {1, 3}$ is cyclic of order $2$ . For $k \geq 3$ , claim $(Z / 2^{k})^{\times} ≅ Z /2 \times Z / 2^{k - 2}$ with generators $- 1$ and $5$ .

The order of $- 1$ modulo $2^{k}$ is $2$ for $k \geq 1$ . The order of $5$ modulo $2^{k}$ is $2^{k - 2}$ for $k \geq 3$ : by induction, $5^{2^{k - 2}} \equiv 1 (mod 2^{k})$ but $5^{2^{k - 3}} \neq \equiv 1 (mod 2^{k})$ . The subgroup generated by $5$ does not contain $- 1$ because every power of $5$ is $\equiv 1 (mod 4)$ (as $5 \equiv 1 (mod 4)$ ), while $- 1 \equiv 3 (mod 4)$ . Hence the two subgroups intersect in only the identity, and the direct product has order $2 \cdot 2^{k - 2} = 2^{k - 1} = φ (2^{k}) = ∣ (Z / 2^{k})^{\times} ∣$ .

So $(Z / 2^{k})^{\times}$ is cyclic for $k \in {1, 2}$ and non-cyclic for $k \geq 3$ .

Step 3 — Cyclicity classification via CRT. $(Z / n)^{\times}$ is cyclic iff its CRT decomposition has at most one non-identity cyclic factor with even order. A product of two cyclic groups of orders $m_{1}, m_{2}$ is cyclic iff $g cd (m_{1}, m_{2}) = 1$ . The orders $φ (p^{e_{p}})$ for distinct prime powers are mostly even (every $φ (p^{k}) = p^{k - 1} (p - 1)$ is even for $p$ odd or for $p = 2, k \geq 2$ ); the only odd values are $φ (2) = 1$ and the degenerate $φ (1) = 1$ .

So at most one factor of orders $φ (p^{e_{p}}) > 1$ can appear in the CRT decomposition without producing an even-even gcd. The allowed configurations:

$n = 1$ : cyclic by definition (the identity group).
$n = 2$ : cyclic by definition (order $1$ ).
$n = 4$ : cyclic of order $2$ .
$n = p^{k}$ for $p$ odd: cyclic by Step 1.
$n = 2 p^{k}$ for $p$ odd: $(Z / n)^{\times} ≅ (Z /2)^{\times} \times (Z / p^{k})^{\times} ≅ {1} \times Z / φ (p^{k})$ , cyclic.

Every other $n$ has at least two CRT factors with even orders $> 1$ , and the product is therefore not cyclic.

Conversely, for $n \in {1, 2, 4, p^{k}, 2 p^{k}}$ with $p$ odd, the CRT decomposition produces a cyclic group, so $(Z / n)^{\times}$ is cyclic.

Rubric: full credit for the three-step structure: prime-power cyclicity via Hensel lifting, the $2^{k}$ split, and the CRT-cyclicity gcd condition.

Exercise 8 (hard, symbolic).

Prove the discrete-logarithm homomorphism: for $p$ prime and $g$ a primitive root modulo $p$ , the map $ind_{g} : (Z / p Z)^{\times} \to Z / (p - 1) Z$ , $a \mapsto ind_{g} (a)$ , is a group isomorphism. Use it to solve the congruence $7^{x} \equiv 5 (mod 11)$ by translating to a linear congruence modulo $10$ , using the orbit table from the worked example.

Hint

For the isomorphism, observe $g^{ind (a)} \cdot g^{ind (b)} = g^{ind (a) + ind (b)} = g^{ind (ab)}$ as elements of $(Z / p)^{\times}$ , then read off the additive structure modulo $p - 1$ . For $7^{x} \equiv 5$ modulo $11$ : take $ind_{2}$ of both sides, using $ind_{2} (7) = 7$ (from Exercise 3) and $ind_{2} (5) = 4$ (from the orbit table).

Answer

Isomorphism. Define $ind_{g} : (Z / p)^{\times} \to Z / (p - 1)$ by sending $a$ to the unique $k \in {0, 1, \dots, p - 2}$ with $g^{k} \equiv a (mod p)$ . Well-defined because $g$ is a primitive root and $(Z / p)^{\times} = {g^{0}, g^{1}, \dots, g^{p - 2}}$ .

Group homomorphism: $g^{ind (a) + ind (b)} = g^{ind (a)} \cdot g^{ind (b)} = a \cdot b$ , so $ind (ab) \equiv ind (a) + ind (b) (mod p - 1)$ .

Injective because $ind (a) = ind (b)$ forces $g^{ind (a)} = g^{ind (b)}$ , hence $a = b$ .

Surjective because every $k \in {0, 1, \dots, p - 2}$ is the index of $a = g^{k}$ .

So $ind_{g}$ is a group isomorphism $(Z / p)^{\times} \sim Z / (p - 1) Z$ .

Solving $7^{x} \equiv 5 (mod 11)$ . Take $ind_{2}$ of both sides: $$ \mathrm{ind}_2(7^x) ;\equiv; \mathrm{ind}_2(5) \pmod{10}. $$ By the homomorphism property and the orbit table from the worked example, $ind_{2} (7^{x}) = x \cdot ind_{2} (7) = 7 x$ , and $ind_{2} (5) = 4$ . So $$ 7 x ;\equiv; 4 \pmod{10}. $$ Solve via extended Euclidean: $g cd (7, 10) = 1$ , and $7 \cdot 3 = 21 \equiv 1 (mod 10)$ , so $7^{- 1} \equiv 3 (mod 10)$ . Multiplying: $$ x ;\equiv; 3 \cdot 4 ;=; 12 ;\equiv; 2 \pmod{10}. $$ So $x \equiv 2 (mod 10)$ , with solutions $x = 2, 12, 22, \dots$ Direct verification: $7^{2} = 49 = 4 \cdot 11 + 5 \equiv 5 (mod 11)$ , confirming $x = 2$ .

This is the discrete-logarithm reduction in operation: an exponential congruence in $(Z / p)^{\times}$ becomes a linear congruence modulo $p - 1$ . The same trick underlies the Pohlig-Hellman algorithm and the index-calculus methods of Theorem 5 below.

Rubric: full credit for the homomorphism verification and the index-translation solution $x = 2$ .

Lean formalization Intermediate+

Mathlib supplies the abstract scaffolding for primitive roots and the cyclic structure of $(Z / p)^{\times}$ . The Lean module Codex.NumberTheory.Elementary.PrimitiveRootsZModUnits packages the existence theorem and the structural classification.

-- Operative imports: Mathlib.Data.ZMod.Basic, Mathlib.Data.ZMod.Units,
-- Mathlib.GroupTheory.SpecificGroups.Cyclic,
-- Mathlib.RingTheory.RootsOfUnity.Basic, Mathlib.NumberTheory.LucasPrimality

#check @ZMod.unitsEquivCoprime
-- Identification of (ZMod n)ˣ with the type of integers coprime to n.

#check @IsPrimitiveRoot
-- The abstract predicate: x is a primitive nth root of unity in M iff x^n = 1
-- and no smaller positive exponent works.

#check @ZMod.isCyclic
-- For p prime, (ZMod p)ˣ is cyclic.

#check @orderOf
-- The order of an element in a group.

#check @orderOf_dvd_card
-- Lagrange: orderOf g divides Fintype.card G for finite G.

#check @Nat.totient
-- The Euler totient function.

The Lean cyclicity result ZMod.isCyclic rests on the polynomial-root bound Polynomial.card_roots_le_degree applied to $x^{d} - 1 \in F_{p} [x]$ , mirroring the Key Theorem proof. What Mathlib has not yet packaged: the explicit primitive-root existence proof modulo odd prime powers via Hensel lifting from $F_{p}$ to $Z / p^{k}$ ; the explicit decomposition $(Z / 2^{k})^{\times} ≅ Z /2 \times Z / 2^{k - 2}$ for $k \geq 3$ generated by $- 1$ and $5$ ; the Möbius count $φ (p - 1)$ of primitive roots modulo $p$ ; the discrete-logarithm isomorphism with its constructive baby-step giant-step and Pohlig-Hellman implementations; the Lucas and Lucas-Lehmer primality tests as direct applications of the primitive-root framework. These are the formalisation gaps documented in the unit metadata Mathlib gap analysis.

Advanced results Master

Theorem 1 (existence of primitive roots modulo every $n \in {1, 2, 4, p^{k}, 2 p^{k}}$ ; Gauss 1801). For $p$ an odd prime and $k \geq 1$ , the group $(Z / p^{k})^{\times}$ is cyclic of order $φ (p^{k}) = p^{k - 1} (p - 1)$ . The group $(Z /2 p^{k})^{\times}$ is cyclic of the same order $φ (2 p^{k}) = φ (p^{k})$ . ^{[Gauss 1801]}. The proof is Hensel lifting: a primitive root $g$ modulo $p$ (Key Theorem) lifts to a primitive root modulo $p^{k}$ , with the explicit replacement $g \to g + p$ used when $g^{p - 1} \equiv 1 (mod p^{2})$ (Exercise 6 above). The CRT decomposition $(Z /2 p^{k})^{\times} ≅ (Z /2)^{\times} \times (Z / p^{k})^{\times} ≅ {1} \times Z / φ (p^{k})$ then makes $2 p^{k}$ cyclic at no extra cost. Cyclicity fails for $n = 2^{k}$ with $k \geq 3$ (Theorem 2), and for $n$ with at least two distinct odd-prime factors or with $4 ∣ n$ and another odd-prime factor — these are the only obstructions. Gauss 1801 arts. 53-89 give the entire classification with constructive proofs.

Theorem 2 (structure of $(Z / 2^{k})^{\times}$ for $k \geq 3$ ). For $k \geq 3$ , $(Z / 2^{k} Z)^{\times} ≅ Z /2 Z \times Z / 2^{k - 2} Z$ , generated by $- 1$ (order $2$ ) and $5$ (order $2^{k - 2}$ ). The first factor is the kernel of reduction modulo $4$ (so $- 1$ generates it); the second is generated by $5$ , with $5^{2^{k - 2}} \equiv 1 (mod 2^{k})$ but $5^{2^{k - 3}} \neq \equiv 1 (mod 2^{k})$ (verifiable by induction with $5 = 1 + 4$ and $(1 + 4)^{2^{j}}$ expansions). The non-cyclicity for $k \geq 3$ is the unique structural exception to the Gauss cyclicity classification and the operational reason that the Carmichael function $λ (2^{k}) = 2^{k - 2}$ is strictly smaller than $φ (2^{k}) = 2^{k - 1}$ for $k \geq 3$ . See Hardy-Wright 2008 §VI.10 ^{[Hardy-Wright 2008]} for the standard induction.

Theorem 3 (Artin's primitive-root conjecture; Artin 1927, Hooley 1967). Let $a$ be an integer that is not $- 1$ and not a perfect square. Then $a$ is a primitive root modulo $p$ for infinitely many primes $p$ , with density $$ \delta(a) ;=; A \cdot \prod_p \left(1 - \frac{1}{p(p - 1)}\right) ;=; A \cdot 0.3739558\ldots ,, $$ where $A$ is a rational correction factor depending on the squarefree part of $a$ . ^{[Artin 1927; Hooley 1967]}. The constant $C_{A} = \prod_{p} (1 - 1/ (p (p - 1))) = 0.3739558...$ is the Artin constant. Artin 1927 formulated the conjecture in a letter to Hasse based on heuristic considerations: $a$ is a primitive root modulo $p$ iff for every prime $q ∣ p - 1$ , $a$ is not a $q$ -th power modulo $p$ ; under independence assumptions, this has probability $\prod_{q} (1 - 1/ q) \cdot (q / (q - 1))$ corrections.

Hooley 1967 J. reine angew. Math. 225, 209 ^{[Hooley 1967]} proved Artin's conjecture conditionally on the generalised Riemann hypothesis for the Dedekind zeta functions of the Kummer-cyclotomic fields $Q (ζ_{q}, a^{1/ q})$ , using Chebotarev density theorem to count primes by splitting. The unconditional progress: Gupta-Murty 1984 Invent. Math. 78, 127 ^{[Gupta-Murty 1984]} proved that infinitely many integers $a$ have a positive density of primitive-root primes; Heath-Brown 1986 Quart. J. Math. (2) 37, 27 ^{[Heath-Brown 1986]} proved that among any three multiplicatively independent integers, at least one is a primitive root modulo infinitely many primes — in particular at least one of $2, 3, 5$ is.

Theorem 4 (baby-step giant-step algorithm for the discrete logarithm; Shanks 1971). In a cyclic group $G$ of order $N$ with generator $g$ , the discrete logarithm $ind_{g} (a) \in Z / N$ can be computed in time and space $O (N)$ via baby-step giant-step. ^{[Shanks 1971]}. The algorithm: set $m = ⌈ N ⌉$ ; precompute and store the baby steps ${(g^{j}, j) : 0 \leq j < m}$ in a hash table; for $i = 0, 1, 2, \dots, m$ compute the giant step $a \cdot g^{- im}$ and check whether it appears in the hash table — if $g^{j} = a \cdot g^{- im}$ , then $ind_{g} (a) = im + j$ . Time and space $\tilde{O} (N)$ . Combined with Pohlig-Hellman (Theorem 5), this is the best classical generic algorithm for DLP in groups whose order has no large prime factor.

Theorem 5 (Pohlig-Hellman algorithm; Pohlig-Hellman 1978). Let $G$ be a cyclic group of order $N = \prod_{i} q_{i}^{e_{i}}$ . The discrete logarithm in $G$ reduces by CRT to the discrete logarithm in each cyclic subgroup of order $q_{i}^{e_{i}}$ , each solvable by baby-step giant-step in $O (e_{i} q_{i})$ steps. Total complexity: $O (\sum_{i} e_{i} (lo g N + q_{i}))$ . ^{[Pohlig-Hellman 1978]}. Practical consequence: a generic DLP in a group of order $N$ with a large prime factor $q ∣ N$ requires at least $O (q)$ work, so secure cryptographic groups choose $N$ with a single large prime factor — the safe prime condition $p = 2 q + 1$ for $(Z / p)^{\times}$ , or pairing-friendly curves for elliptic-curve DLP. RFC 3526 standardises safe primes for Diffie-Hellman.

Theorem 6 (index-calculus method for DLP in $(Z / p)^{\times}$ ; Adleman 1979). There exists a probabilistic sub-exponential algorithm for the discrete logarithm in $(Z / p)^{\times}$ running in time $L_{p} [1/2, c]$ , refined to $L_{p} [1/3, c]$ via the number-field sieve, where $L_{p} [α, c] = exp (c (lo g p)^{α} (lo g lo g p)^{1 - α})$ ^{[Adleman 1979]}. The algorithm exploits the multiplicative structure of $Z$ : fix a smoothness bound $B$ and a factor base $F = {p_{1}, \dots, p_{k}}$ of primes $\leq B$ ; for random exponents $r$ , factor $g^{r} mod p$ over $F$ (keeping only the smooth values); each successful factorisation $g^{r} \equiv \prod_{j} p_{j}^{e_{j}} (mod p)$ gives a linear relation $r \equiv \sum_{j} e_{j} ind_{g} (p_{j}) (mod p - 1)$ in the unknowns $ind_{g} (p_{j})$ . After collecting $\geq k$ linearly independent relations, solve the linear system. Then compute $ind_{g} (a)$ via one more smooth-factorisation step. The number-field sieve adaptation [Gordon 1993 SIAM J. Discrete Math. 6, 124] reaches $L_{p} [1/3, c]$ asymptotic complexity. Pre-computation makes $1024$ -bit DH insecure (the Logjam attack of Adrian et al. 2015 CCS 2015), motivating the $\geq 2048$ -bit modern minimum.

Theorem 7 (Shor's quantum polynomial-time DLP; Shor 1994/1997). There exists a quantum algorithm computing the discrete logarithm in any cyclic group of order $N$ in time $O ((lo g N)^{3})$ on a quantum computer, given oracle access to the group operation ^{[Shor 1994]}. The algorithm uses the quantum Fourier transform over $Z / N$ to extract the period of the function $f (x, y) = g^{x} a^{- y}$ , whose period along the line $g^{x} = a^{y}$ encodes $ind_{g} (a)$ . The same period-finding subroutine factors integers via the order $ord_{N} (a)$ of a random element. Polynomial-time quantum factoring breaks RSA; polynomial-time quantum DLP breaks Diffie-Hellman, ElGamal, DSA, ECDH, ECDSA. Motivates the entire post-quantum cryptography programme: NIST PQC standardisation 2016-2024, with the first standards FIPS 203 (ML-KEM / Kyber, lattice-based key encapsulation) and FIPS 204 (ML-DSA / Dilithium, lattice-based signatures) announced August 2024.

Theorem 8 (Lucas primality test; Lucas 1878). An integer $n > 1$ is prime if and only if there exists $a$ with $a^{n - 1} \equiv 1 (mod n)$ and $a^{(n - 1) / q} \neq \equiv 1 (mod n)$ for every prime $q ∣ n - 1$ . ^{[Lucas 1878]}. The condition is exactly that $a$ has order $n - 1$ in $(Z / n)^{\times}$ , hence $∣ (Z / n)^{\times} ∣ \geq n - 1$ , hence $∣ (Z / n)^{\times} ∣ = n - 1$ (the unit group has at most $n - 1$ elements), which forces every residue $1, 2, \dots, n - 1$ to be a unit, forcing $n$ to be prime. The certificate $a$ (a primitive root witness) gives a deterministic polynomial-time-verifiable proof of primality — Pratt 1975 SIAM J. Comput. 4, 214 showed that the recursive certificate (a primitive root for $n$ , plus primality certificates for each $q ∣ n - 1$ ) has polynomial size, putting PRIMES in NP. The Lucas-Lehmer specialisation to Mersenne primes $M_{p} = 2^{p} - 1$ is the algorithm used by GIMPS to discover the largest known primes (currently $2^{82, 589, 933} - 1$ , discovered 2018).

Synthesis. The primitive-root framework is the foundational reason that the multiplicative structure of $(Z / n)^{\times}$ admits a clean discrete-logarithm identification with $Z / φ (n)$ — when it does, and the obstruction $n \in / {1, 2, 4, p^{k}, 2 p^{k}}$ is precisely when the unit group fails to be cyclic and a single primitive root is unavailable. The central insight is exactly that the field property of $F_{p}$ supplies the polynomial-degree bound $∣ x^{d} - 1 roots ∣ \leq d$ , which combined with the totient summation $\sum_{d ∣ m} φ (d) = m$ forces every divisor of $p - 1$ to have exactly $φ (d)$ elements of order $d$ — and the unique $d = p - 1$ branch produces $φ (p - 1) > 0$ primitive roots. The bridge to 01.02.18 pending finite fields is this very argument: every $F_{q}^{\times}$ is cyclic of order $q - 1$ without exception, and the failure-mode $(Z / n)^{\times}$ non-cyclic for non-prime-power $n$ traces to $Z / n$ not being a field.

The applied half of the unit is dominated by the discrete-logarithm problem. Putting these together with the Pohlig-Hellman reduction and the baby-step giant-step + index-calculus + number-field-sieve hierarchy, the best classical DLP algorithm in $(Z / p)^{\times}$ for safe-prime $p$ runs in $L_{p} [1/3, c]$ sub-exponential time, fast enough to break $1024$ -bit Diffie-Hellman in pre-computation (Logjam 2015) but slow enough to keep $2048$ -bit secure against classical attacks for the foreseeable future. The pattern recurs in elliptic-curve cryptography: DLP in $E (F_{p})$ has no known sub-exponential classical attack (no index-calculus analogue), allowing $256$ -bit keys to provide $128$ -bit security — the modern default in TLS 1.3 and Signal. Shor 1994's quantum polynomial-time DLP identifies all these classical hardness assumptions with a single quantum-Fourier-transform period-finding routine, and the post-quantum transition (NIST FIPS 203 + 204, 2024) replaces the discrete-log + factoring hardness assumptions with lattice-shortest-vector + module-LWE hardness assumptions whose quantum complexity is conjecturally still exponential.

The historical bridge connects 1801 Gauss to 1976 Diffie-Hellman to 1994 Shor in a single arc. Gauss's classification of cyclic $(Z / n)^{\times}$ identifies the moduli for which the discrete logarithm is well-defined; Diffie-Hellman's 1976 IEEE Trans. Inform. Theory paper repurposed the index calculus as the cornerstone of the first public-key cryptosystem; Lucas's 1878 primality test built on the same primitive-root structure as the first deterministic certificate scheme; the entire post-1976 cryptographic ecosystem inherited the cyclic-group framework, with Artin's 1927 conjecture identifying the candidate primitive roots and Hooley 1967 the conditional density. The bridge is everywhere the same: a single generator of the cyclic unit group converts modular arithmetic into discrete additive arithmetic modulo $φ (n)$ , and every cryptographic protocol since 1976 has rested on the asymmetry between forward exponentiation (fast) and reverse logarithm extraction (slow).

Full proof set Master

Proposition 1 (cyclicity of $(Z / p)^{\times}$ ). For every prime $p$ , $(Z / p)^{\times}$ is cyclic of order $p - 1$ .

Proof. Reprised from the Key Theorem with sharpened notation. Let $G = (Z / p)^{\times}$ . For each $d ∣ p - 1$ let $N (d) = # {x \in G : ord (x) = d}$ . The element orders divide $∣ G ∣$ by Lagrange, so $$ \sum_{d \mid p - 1} N(d) = p - 1. \tag{1} $$

An element $x$ has $ord (x) ∣ d$ iff $x^{d} = 1$ , i.e., $x$ is a root of $T^{d} - 1 \in F_{p} [T]$ . By the field property of $F_{p}$ , this polynomial has at most $d$ roots in $F_{p}$ , so $\sum_{e ∣ d} N (e) \leq d$ .

Suppose $N (d) > 0$ with witness $x$ of order $d$ . The cyclic subgroup $⟨ x ⟩$ has $d$ elements, all satisfying $y^{d} = 1$ , so $⟨ x ⟩$ accounts for the full root set of $T^{d} - 1$ — equality $\sum_{e ∣ d} N (e) = d$ . Among the $d$ elements of $⟨ x ⟩$ , the number of order exactly $d$ is the number of $k$ with $g cd (k, d) = 1$ , namely $φ (d)$ .

So $N (d) \in {0, φ (d)}$ for every $d ∣ p - 1$ . Combined with (1) and $\sum_{d ∣ m} φ (d) = m$ : $$ p - 1 = \sum_{d \mid p - 1} N(d) \leq \sum_{d \mid p - 1} \varphi(d) = p - 1. $$ Equality forces $N (d) = φ (d)$ for every $d$ , in particular $N (p - 1) = φ (p - 1) \geq 1$ . A primitive root exists; $G$ is cyclic. $□$

Proposition 2 (Hensel lift to $(Z / p^{k})^{\times}$ ). For $p$ an odd prime and $k \geq 1$ , $(Z / p^{k})^{\times}$ is cyclic of order $φ (p^{k}) = p^{k - 1} (p - 1)$ .

Proof. By Proposition 1 there exists a primitive root $g$ modulo $p$ . By Exercise 6 above, either $g$ or $g + p$ is a primitive root modulo $p^{2}$ ; without loss assume $g$ itself is.

Induction on $k$ . For the step $k \to k + 1$ : assume $g$ has order exactly $φ (p^{k}) = p^{k - 1} (p - 1)$ modulo $p^{k}$ , with $k \geq 2$ . The order of $g$ modulo $p^{k + 1}$ divides $φ (p^{k + 1}) = p^{k} (p - 1)$ , and reducing modulo $p^{k}$ shows that $φ (p^{k}) = p^{k - 1} (p - 1)$ divides this order. So the order modulo $p^{k + 1}$ is either $p^{k - 1} (p - 1)$ or $p^{k} (p - 1)$ .

Suppose for contradiction the order is the smaller value $p^{k - 1} (p - 1)$ . Then $g^{p^{k - 1} (p - 1)} \equiv 1 (mod p^{k + 1})$ . By induction hypothesis $g^{p^{k - 2} (p - 1)} \neq \equiv 1 (mod p^{k})$ (it has order exactly $p^{k - 1} (p - 1)$ modulo $p^{k}$ ), so $g^{p^{k - 2} (p - 1)} = 1 + c p^{k - 1}$ with $g cd (c, p) = 1$ . Raise to the $p$ -th power and expand: $$ g^{p^{k - 1}(p - 1)} = (1 + c p^{k - 1})^p = 1 + p \cdot c p^{k - 1} + \binom{p}{2} (c p^{k - 1})^2 + \cdots. $$ The second term is $c p^{k}$ ; subsequent terms have $p^{2 k - 1}$ or higher. Since $p$ is odd and $k \geq 2$ , $2 k - 1 \geq k + 1$ , so modulo $p^{k + 1}$ : $$ g^{p^{k - 1}(p - 1)} \equiv 1 + c p^k \pmod{p^{k + 1}}. $$ Since $g cd (c, p) = 1$ , $c p^{k} \neq \equiv 0 (mod p^{k + 1})$ , so $g^{p^{k - 1} (p - 1)} \neq \equiv 1 (mod p^{k + 1})$ — contradiction. Hence the order is $p^{k} (p - 1) = φ (p^{k + 1})$ , and $g$ is a primitive root modulo $p^{k + 1}$ . $□$

Proposition 3 (structure of $(Z / 2^{k})^{\times}$ for $k \geq 3$ ). For $k \geq 3$ , $(Z / 2^{k})^{\times} ≅ Z /2 \times Z / 2^{k - 2}$ , generated by $- 1$ and $5$ .

Proof. The order of $- 1$ modulo $2^{k}$ is $2$ for every $k \geq 1$ . Claim the order of $5$ modulo $2^{k}$ is $2^{k - 2}$ for $k \geq 3$ , by induction.

Base case $k = 3$ : $5^{2} = 25 = 3 \cdot 8 + 1 \equiv 1 (mod 8)$ , so the order of $5$ modulo $8$ divides $2$ . Also $5 \neq \equiv 1 (mod 8)$ , so the order is exactly $2 = 2^{3 - 2}$ .

Step $k \to k + 1$ for $k \geq 3$ : assume $5^{2^{k - 2}} \equiv 1 (mod 2^{k})$ and $5^{2^{k - 3}} \neq \equiv 1 (mod 2^{k})$ . Write $5^{2^{k - 2}} = 1 + a \cdot 2^{k}$ for some integer $a$ . Square: $$ 5^{2^{k - 1}} = (1 + a \cdot 2^k)^2 = 1 + 2 a \cdot 2^k + a^2 \cdot 2^{2k} \equiv 1 + a \cdot 2^{k + 1} \pmod{2^{k + 2}}. $$ So $5^{2^{k - 1}} \equiv 1 (mod 2^{k + 1})$ iff $a \cdot 2^{k + 1} \equiv 0 (mod 2^{k + 1})$ , which holds unconditionally. So $5^{2^{k - 1}} \equiv 1 (mod 2^{k + 1})$ , i.e., the order of $5$ modulo $2^{k + 1}$ divides $2^{k - 1}$ . Strict-or-equal: suppose for contradiction $5^{2^{k - 2}} \equiv 1 (mod 2^{k + 1})$ . Then $1 + a \cdot 2^{k} \equiv 1 (mod 2^{k + 1})$ , forcing $a \equiv 0 (mod 2)$ . But then $5^{2^{k - 3}} \equiv \pm 1 + (a /2) \cdot 2^{k - 1}$ (square-root analysis) lands inside $1 + 2^{k - 1} Z$ already at $k - 1$ , contradicting the inductive non-equality. Hence the order modulo $2^{k + 1}$ is exactly $2^{k - 1} = 2^{(k + 1) - 2}$ .

So $⟨ 5 ⟩ \subseteq (Z / 2^{k})^{\times}$ is cyclic of order $2^{k - 2}$ for $k \geq 3$ . The subgroup $⟨ - 1 ⟩$ has order $2$ .

Intersection: every power of $5$ is $\equiv 1 (mod 4)$ (since $5 \equiv 1 (mod 4)$ and powers preserve residues mod $4$ ), while $- 1 \equiv 3 (mod 4)$ . So $⟨ 5 ⟩ \cap ⟨ - 1 ⟩ = {1}$ .

Product: $∣ ⟨ - 1 ⟩ \cdot ⟨ 5 ⟩ ∣ = ∣ ⟨ - 1 ⟩ ∣ \cdot ∣ ⟨ 5 ⟩ ∣ = 2 \cdot 2^{k - 2} = 2^{k - 1} = φ (2^{k}) = ∣ (Z / 2^{k})^{\times} ∣$ . So the product subgroup equals the full unit group.

Hence $(Z / 2^{k})^{\times} ≅ ⟨ - 1 ⟩ \times ⟨ 5 ⟩ ≅ Z /2 \times Z / 2^{k - 2}$ . $□$

Proposition 4 (discrete-logarithm isomorphism). For $n \in {1, 2, 4, p^{k}, 2 p^{k}}$ with $p$ an odd prime, fix a primitive root $g$ modulo $n$ . The map $ind_{g} : (Z / n)^{\times} \to Z / φ (n) Z$ , $a \mapsto ind_{g} (a)$ , is a group isomorphism.

Proof. For $a \in (Z / n)^{\times}$ , $g$ generates the unit group, so there exists a unique $k \in {0, 1, \dots, φ (n) - 1}$ with $g^{k} \equiv a (mod n)$ . This defines $ind_{g} (a) = k$ .

Group homomorphism: $ind_{g} (ab) \equiv ind_{g} (a) + ind_{g} (b) (mod φ (n))$ because $g^{ind (a) + ind (b)} = g^{ind (a)} \cdot g^{ind (b)} = a \cdot b = g^{ind (ab)}$ , and $g$ -exponentials are equal modulo $n$ iff exponents are congruent modulo $φ (n)$ .

Injective: $ind_{g} (a) = ind_{g} (b)$ gives $a = g^{ind (a)} = g^{ind (b)} = b$ .

Surjective: $k \in Z / φ (n)$ is the index of $a = g^{k}$ .

So $ind_{g}$ is a bijective homomorphism, hence an isomorphism. $□$

Connections Master

Fermat-Euler-Wilson theorems 21.01.04. Just shipped. The order-divides-group-order fact underlying Fermat ( $a^{p - 1} \equiv 1 (mod p)$ ) and Euler ( $a^{φ (n)} \equiv 1 (mod n)$ ) is sharpened in the present unit to the existence of an element of order exactly $φ (n)$ when $n$ has the right shape — a primitive root. The Key Theorem here builds on the Lagrange-divides framework of 21.01.04 and the totient identity $\sum_{d ∣ m} φ (d) = m$ that appears in the totient calculus of 21.01.03. The Carmichael function $λ (n)$ from 21.01.04 is the tight exponent of $(Z / n)^{\times}$ and equals $φ (n)$ exactly when a primitive root exists — the cyclic case.
Congruences and the Chinese remainder theorem 21.01.03. Shipped. The CRT decomposition $(Z / n)^{\times} ≅ \prod_{p} (Z / p^{e_{p}})^{\times}$ is the operational tool that reduces the cyclicity classification to prime powers (Theorem 1, Theorem 2), and the discrete-logarithm Pohlig-Hellman reduction (Theorem 5) is essentially CRT applied to the cyclic-group order $φ (n)$ . The structure theorem for $(Z / n)^{\times}$ proved here gives the explicit CRT factor decomposition: the cyclic factors $Z / φ (p^{e_{p}})$ for $p$ odd, the Klein-times-cyclic factor for $p = 2, k \geq 3$ .
Primes and the fundamental theorem of arithmetic 21.01.02. Shipped. The classification of $n$ admitting primitive roots — $n \in {1, 2, 4, p^{k}, 2 p^{k}}$ — is stated in terms of the prime factorisation of $n$ supplied by the fundamental theorem of arithmetic. Lucas's 1878 primality test (Theorem 8) uses primitive-root certificates to give a deterministic primality proof, refining the Fermat test of 21.01.04; Pratt 1975 showed the resulting recursive certificate has polynomial size, placing PRIMES in NP. The Lucas-Lehmer specialisation to Mersenne primes is the algorithm underlying every record-holding prime since 1952.
Quadratic residues and reciprocity 21.01.06. Pending. A nonzero residue $a$ is a quadratic residue modulo a prime $p$ iff $ind_{g} (a)$ is even for any primitive root $g$ modulo $p$ . The squaring map $(Z / p)^{\times} \to (Z / p)^{\times}$ , $x \mapsto x^{2}$ , has kernel ${\pm 1}$ and image of index $2$ ; the image is exactly the subgroup of quadratic residues. Euler's criterion $a^{(p - 1) /2} \equiv \pm 1 (mod p)$ for the Legendre symbol is the primitive-root identification $ind_{g} (a) \cdot (p - 1) /2 (mod p - 1)$ . Gauss's quadratic reciprocity (1801, six independent proofs) builds on the primitive-root framework as its operational substrate.
Group 01.02.01. Shipped. The proofs of the cyclicity classification rest on the standard finite-group structure theorems: Lagrange's theorem (order divides group order), the cyclic-group classification (subgroups of cyclic groups are cyclic, generators are $g^{k}$ for $g cd (k, ord (g)) = 1$ ), CRT for products of finite cyclic groups (cyclic iff orders are pairwise coprime). The discrete-logarithm isomorphism $(Z / n)^{\times} ≅ Z / φ (n)$ for cyclic $n$ is the prototype of every isomorphism from a finite cyclic group to its additive realisation $Z / N$ .
Finite fields $F_{q}$ and Frobenius 01.02.18 pending. Pending. Every finite subgroup of the multiplicative group of a field is cyclic — a generalisation of the prime-case Key Theorem proved here. In particular $F_{q}^{\times}$ is cyclic of order $q - 1$ for every prime power $q$ , without the moduli restriction that holds for $(Z / n)^{\times}$ (since $F_{q}$ is a field but $Z / n$ for non-prime-power $n$ is not). A generator of $F_{q}^{\times}$ is also called a primitive root (or primitive element) of $F_{q}$ , and the construction of $F_{q}$ via irreducible polynomials of degree $lo g_{p} q$ over $F_{p}$ uses primitive-root existence implicitly. The Frobenius endomorphism $Frob_{p} : F_{q} \to F_{q}$ , $x \mapsto x^{p}$ , generates the cyclic Galois group $Gal (F_{q} / F_{p})$ , and the discrete-logarithm framework lifts to finite-field DLP — the basis of pairing-based cryptography and Schoof's elliptic-curve point-counting algorithm.

Historical & philosophical context Master

Gauss 1801 Disquisitiones Arithmeticae arts. 53-94 ^{[Gauss 1801]} is the canonical originator of the primitive-root theory. Articles 53-54 define the order of a residue modulo $p$ — Gauss writes "the period of $a$ " — and observe that the period divides $p - 1$ via the geometric-series argument $1 + a + a^{2} + \dots + a^{p - 2} \equiv 0 (mod p)$ . Articles 55-56 prove the polynomial-root bound: $x^{d} - 1$ has at most $d$ roots modulo a prime, a consequence Gauss attributes to himself but which appears earlier in Lagrange 1768 in a less general form. Articles 57-72 give the existence proof of primitive roots modulo every odd prime via the divisor-counting argument of the Key Theorem above. Articles 73-89 lift the existence to odd prime powers $p^{k}$ and to $2 p^{k}$ , classifying the moduli admitting primitive roots — and showing $(Z / 2^{k})^{\times}$ is the lone non-cyclic case among prime powers for $k \geq 3$ . Articles 90-94 develop the index calculus (Gauss's term for the discrete logarithm) as a working tool: a primitive root $g$ modulo $p$ gives a table of indices $ind_{g} (a)$ for every $a$ , reducing multiplicative computations modulo $p$ to additive computations modulo $p - 1$ . Gauss exhibits explicit tables for $p \leq 100$ and uses them in the proofs of quadratic and biquadratic reciprocity.

The applied legacy is the discrete-logarithm problem. The earliest substantive DLP algorithm is the baby-step giant-step method of Shanks 1971 Proc. Symp. Pure Math. 20, 415 ^{[Shanks 1971]}, originally introduced for class-group computations. Pohlig-Hellman 1978 IEEE Trans. Inform. Theory IT-24, 106 ^{[Pohlig-Hellman 1978]} showed that for $(Z / p)^{\times}$ with $p - 1 = \prod q_{i}^{e_{i}}$ , the DLP reduces by CRT to subgroup DLPs of order $q_{i}^{e_{i}}$ , each solvable by Shanks in $O (e_{i} q_{i})$ steps. The Adleman 1979 FOCS 20, 55 ^{[Adleman 1979]} index-calculus method achieves sub-exponential complexity $L_{p} [1/2, c]$ via factor-base smooth-relation collection; the number-field sieve adaptation (Gordon 1993, Joux-Lercier 2003) refines this to $L_{p} [1/3, c]$ . The 2015 Logjam attack (Adrian et al. CCS 2015) used pre-computed $1024$ -bit safe-prime DH discrete logs to break TLS connections in real time, establishing $2048$ -bit as the modern Diffie-Hellman minimum.

The 1976 invention of public-key cryptography by Diffie-Hellman 1976 IEEE Trans. Inform. Theory IT-22, 644 ^{[Diffie-Hellman 1976]} is the watershed moment in modern applied cryptography, and rests entirely on the discrete-logarithm asymmetry in $(Z / p)^{\times}$ . Alice and Bob agree on a large prime $p$ and a primitive root $g$ ; Alice publishes $A = g^{a} mod p$ , Bob publishes $B = g^{b} mod p$ ; the shared secret is $K = g^{ab} = A^{b} = B^{a} mod p$ , computable by either party from one secret and the other's public value, but apparently uncomputable by an eavesdropper who sees only $(g, p, A, B)$ — the "computational Diffie-Hellman" assumption. ElGamal 1985 IEEE Trans. Inform. Theory IT-31, 469 ^{[ElGamal 1985]} extended the framework to public-key encryption and signatures; the U.S. Digital Signature Algorithm (NIST FIPS PUB 186, 1991) is the standardised ElGamal-signature variant; elliptic-curve Diffie-Hellman (ECDH) and ECDSA (NIST FIPS PUB 186-2, 2000) replace $(Z / p)^{\times}$ by an elliptic-curve group $E (F_{p})$ with no known sub-exponential DLP algorithm. Every TLS handshake, every Signal Protocol initial key exchange, every Tor circuit setup uses some descendant of Diffie-Hellman 1976.

The unconditional density of primitive-root primes is the open conjecture of Artin 1927 ^{[Artin 1927]}, communicated in a letter to Hasse: every integer $a$ that is not $- 1$ and not a perfect square is a primitive root modulo infinitely many primes, with positive density. The conjectured density is the Artin constant $A = \prod_{p} (1 - 1/ (p (p - 1))) = 0.3739558 \dots$ (corrected by a rational factor for $a$ a power), derived from independence heuristics: $a$ is a primitive root modulo $p$ iff for every prime $q ∣ p - 1$ , $a$ is not a $q$ -th power modulo $p$ . Hooley 1967 J. reine angew. Math. 225, 209 ^{[Hooley 1967]} proved Artin's conjecture conditional on the generalised Riemann hypothesis applied to the Kummer-cyclotomic fields $Q (ζ_{q}, a^{1/ q})$ . Gupta-Murty 1984 Invent. Math. 78, 127 ^{[Gupta-Murty 1984]} gave the first unconditional positive-density result: there are infinitely many $a$ for which $a$ has a positive density of primitive-root primes. Heath-Brown 1986 Quart. J. Math. (2) 37, 27 ^{[Heath-Brown 1986]} proved that among any three multiplicatively independent rationals, at least one satisfies Artin's conjecture — in particular at least one of ${2, 3, 5}$ is a primitive root modulo infinitely many primes, but no specific witness is known unconditionally.

The quantum-computing future is Shor 1994 Proc. FOCS 35, 124 ^{[Shor 1994]} (expanded as Shor 1997 SIAM J. Comput. 26, 1484): polynomial-time quantum algorithms for both factoring and the discrete logarithm. The core subroutine is quantum period-finding via the quantum Fourier transform over $Z / N$ : the function $x \mapsto a^{x} mod N$ is periodic with period $ord_{N} (a)$ , and the QFT extracts this period in $O ((lo g N)^{3})$ quantum gates. Combined with continued-fraction post-processing, this gives polynomial-time integer factoring (via the order $ord_{N} (a)$ of a random $a$ ) and polynomial-time DLP (via the period of $f (x, y) = g^{x} a^{- y}$ ). On a sufficiently large fault-tolerant quantum computer, Shor's algorithm would break RSA, Diffie-Hellman, ElGamal, DSA, ECDH, ECDSA — the entire post-1976 public-key cryptographic infrastructure. NIST's Post-Quantum Cryptography standardisation process (2016-2024) culminated in FIPS 203 (ML-KEM / Kyber, lattice-based key encapsulation) and FIPS 204 (ML-DSA / Dilithium, lattice-based signatures) announced August 2024, with FIPS 205 (SLH-DSA / SPHINCS+, hash-based signatures) as a backup; the underlying hard problems (module-LWE, module-SIS, hash collisions) replace the discrete-log + factoring framework but inherit the same cyclic-group / discrete-additive-structure backbone that Gauss 1801 first identified.

Bibliography Master

@book{Gauss1801,
  author    = {Gauss, Carl Friedrich},
  title     = {Disquisitiones Arithmeticae},
  publisher = {Gerhard Fleischer},
  address   = {Leipzig},
  year      = {1801},
  note      = {English translation by Arthur A. Clarke, Yale University Press, 1965. Articles 53-94 contain the canonical originator development of primitive roots and the cyclicity classification of $(\mathbb{Z}/n\mathbb{Z})^\times$.}
}

@unpublished{Artin1927,
  author = {Artin, Emil},
  title  = {Conjecture on primitive roots},
  year   = {1927},
  note   = {Letter to Helmut Hasse, 27 September 1927. First reported in Hasse 1933 *Bericht II*, §5. The conjecture: every integer $a$ not equal to $-1$ and not a perfect square is a primitive root modulo infinitely many primes, with positive density.}
}

@article{Lucas1878,
  author  = {Lucas, {\'E}douard},
  title   = {Th\'eorie des fonctions num\'eriques simplement p\'eriodiques},
  journal = {American Journal of Mathematics},
  volume  = {1},
  pages   = {184--240 and 289--321},
  year    = {1878},
  note    = {The Lucas primality test based on primitive-root certificates. The Lucas-Lehmer test for Mersenne primes is a specialisation.}
}

@article{DiffieHellman1976,
  author  = {Diffie, Whitfield and Hellman, Martin E.},
  title   = {New directions in cryptography},
  journal = {IEEE Transactions on Information Theory},
  volume  = {IT-22},
  pages   = {644--654},
  year    = {1976},
  note    = {The first published public-key cryptographic protocol. Diffie-Hellman key exchange rests on the discrete-logarithm hardness assumption in $(\mathbb{Z}/p\mathbb{Z})^\times$.}
}

@article{ElGamal1985,
  author  = {ElGamal, Taher},
  title   = {A public key cryptosystem and a signature scheme based on discrete logarithms},
  journal = {IEEE Transactions on Information Theory},
  volume  = {IT-31},
  pages   = {469--472},
  year    = {1985}
}

@article{Hooley1967,
  author  = {Hooley, Christopher},
  title   = {On Artin's conjecture},
  journal = {Journal f\"ur die reine und angewandte Mathematik},
  volume  = {225},
  pages   = {209--220},
  year    = {1967}
}

@article{GuptaMurty1984,
  author  = {Gupta, Rajiv and Murty, M. Ram},
  title   = {A remark on Artin's conjecture},
  journal = {Inventiones Mathematicae},
  volume  = {78},
  pages   = {127--130},
  year    = {1984}
}

@article{HeathBrown1986,
  author  = {Heath-Brown, D. R.},
  title   = {Artin's conjecture for primitive roots},
  journal = {Quarterly Journal of Mathematics, Oxford Series (2)},
  volume  = {37},
  pages   = {27--38},
  year    = {1986}
}

@article{Shanks1971,
  author  = {Shanks, Daniel},
  title   = {Class number, a theory of factorization, and genera},
  journal = {Proceedings of Symposia in Pure Mathematics},
  volume  = {20},
  pages   = {415--440},
  year    = {1971},
  note    = {Baby-step giant-step algorithm for the discrete logarithm.}
}

@article{PohligHellman1978,
  author  = {Pohlig, Stephen C. and Hellman, Martin E.},
  title   = {An improved algorithm for computing logarithms over {GF}($p$) and its cryptographic significance},
  journal = {IEEE Transactions on Information Theory},
  volume  = {IT-24},
  pages   = {106--110},
  year    = {1978}
}

@inproceedings{Adleman1979,
  author    = {Adleman, Leonard M.},
  title     = {A subexponential algorithm for the discrete logarithm problem with applications to cryptography},
  booktitle = {Proceedings of the 20th Annual IEEE Symposium on Foundations of Computer Science},
  pages     = {55--60},
  year      = {1979}
}

@inproceedings{Shor1994,
  author    = {Shor, Peter W.},
  title     = {Algorithms for quantum computation: discrete logarithms and factoring},
  booktitle = {Proceedings of the 35th Annual Symposium on Foundations of Computer Science},
  pages     = {124--134},
  year      = {1994},
  note      = {Expanded as Shor 1997 *SIAM J. Comput.* 26, 1484-1509.}
}

@book{HardyWright2008,
  author    = {Hardy, G. H. and Wright, E. M.},
  title     = {An Introduction to the Theory of Numbers},
  edition   = {6},
  publisher = {Oxford University Press},
  year      = {2008},
  note      = {Revised by D. R. Heath-Brown and J. H. Silverman. Chapters VI-VIII develop primitive roots, the cyclicity classification, the discrete logarithm, and quadratic reciprocity.}
}

@book{IrelandRosen1990,
  author    = {Ireland, Kenneth and Rosen, Michael},
  title     = {A Classical Introduction to Modern Number Theory},
  edition   = {2},
  series    = {Graduate Texts in Mathematics},
  volume    = {84},
  publisher = {Springer},
  year      = {1990},
  note      = {§4 develops the cyclicity classification of $(\mathbb{Z}/n)^\times$ with the modern group-theoretic framing.}
}

@book{Apostol1976,
  author    = {Apostol, Tom M.},
  title     = {Introduction to Analytic Number Theory},
  series    = {Undergraduate Texts in Mathematics},
  publisher = {Springer},
  year      = {1976},
  note      = {§§6-7 develop primitive roots, the index calculus, and discrete-logarithm tables.}
}

@book{Burton2010,
  author    = {Burton, David M.},
  title     = {Elementary Number Theory},
  edition   = {7},
  publisher = {McGraw-Hill},
  year      = {2010},
  note      = {§8 develops the order of an integer modulo $n$ and primitive roots at the undergraduate Beginner-tier level.}
}

Prerequisites

21.01.02
21.01.03
21.01.04

Tier anchors

beginner: Burton 2010 *Elementary Number Theory* 7e §8 (order of an integer, primitive roots, and the indices table for small primes); Khan Academy 'Primitive roots' module
intermediate: Ireland-Rosen 1990 *A Classical Introduction to Modern Number Theory* (Springer GTM 84, 2e) §4 (primitive roots, the structure of $(\mathbb{Z}/p^k)^\times$, and the discrete logarithm); Apostol 1976 *Introduction to Analytic Number Theory* §§6-7
master: Gauss 1801 *Disquisitiones Arithmeticae* arts. 53-94 (first systematic theory of primitive roots and the classification of moduli admitting them); Artin 1927 (unpublished letter to Hasse, the primitive-root density conjecture); Hooley 1967 *J. reine angew. Math.* 225 (Artin's conjecture under GRH); Gupta-Murty 1984 *Invent. Math.* 78 (unconditional positive proportion); Heath-Brown 1986 *Quart. J. Math.* (2) 37 (Artin's conjecture for at least one of three given non-square-non-$-1$ integers); Diffie-Hellman 1976 *IEEE Trans. Inform. Theory* IT-22; Shor 1994/1997 *SIAM J. Comput.* 26 (quantum polynomial-time DLP and factoring); Hardy-Wright 2008 6e §VI-§VIII

References

Gauss, C. F. — Disquisitiones Arithmeticae · Leipzig: Gerhard Fleischer, 1801. Articles 53-94 give the first systematic theory of primitive roots. Article 54 introduces the order of a residue modulo $p$; articles 55-56 prove the order divides $p - 1$ via the polynomial-degree argument $x^d - 1$ has at most $d$ roots in $\mathbb{F}_p$; articles 57-72 prove primitive roots exist modulo every odd prime $p$ by counting elements of each order via the identity $\sum_{d \mid p-1} \varphi(d) = p - 1$; articles 73-89 lift to prime powers $p^k$ and to $2 p^k$, and prove these are the only moduli $> 4$ admitting primitive roots; articles 90-94 develop the index calculus (discrete logarithm) modulo $p$ as a working tool. English translation by A. A. Clarke, Yale UP 1965.
Artin, E. — Conjecture on primitive roots · Letter to Helmut Hasse, 27 September 1927; first reported in Hasse 1929 *Vorlesungen über die Theorie der algebraischen Zahlen* (Akademie-Verlag, Leipzig) and in Hasse 1933 *Bericht über neuere Untersuchungen und Probleme aus der Theorie der algebraischen Zahlkörper* II §5. Artin conjectured that every integer $a$ that is not $-1$ and not a perfect square is a primitive root modulo infinitely many primes $p$, with positive natural density. The explicit density is the Artin constant $C_A = \prod_p \left(1 - \frac{1}{p(p - 1)}\right) = 0.3739558\ldots$, multiplied by a rational correction depending on $a$ when $a$ is a substantive power.
Hooley, C. — On Artin's conjecture · *Journal für die reine und angewandte Mathematik* 225 (1967), 209-220. Hooley proved Artin's primitive-root conjecture conditional on the generalised Riemann hypothesis for Dedekind zeta functions of the cyclotomic-Kummer fields $\mathbb{Q}(\zeta_q, a^{1/q})$. The density is the Artin constant $C_A$, refined by a rational correction factor depending on the square-free part of $a$ via the Chebotarev density theorem applied to splitting in the relevant Kummer extensions.
Gupta, R. and Murty, M. R. — A remark on Artin's conjecture · *Inventiones Mathematicae* 78 (1984), 127-130. Unconditional proof that infinitely many integers $a$ have a positive density of primes $p$ for which $a$ is a primitive root. Refined by Heath-Brown 1986: among any three multiplicatively independent integers, at least one is a primitive root modulo infinitely many primes.
Heath-Brown, D. R. — Artin's conjecture for primitive roots · *Quarterly Journal of Mathematics, Oxford Series* (2) 37 (1986), 27-38. Theorem: among any three multiplicatively independent non-zero rationals $a_1, a_2, a_3$ (i.e., no non-degenerate product $a_1^{x_1} a_2^{x_2} a_3^{x_3} = 1$ in $\mathbb{Q}^\times$), at least one is a primitive root modulo infinitely many primes. Consequence: there are at most two exceptional primes $\ell$ for which Artin's conjecture fails on $\ell$ as a candidate primitive root, and at least one of the three primes $2, 3, 5$ is a primitive root modulo infinitely many $p$.
Diffie, W. and Hellman, M. E. — New directions in cryptography · *IEEE Transactions on Information Theory* IT-22 (1976), 644-654. The Diffie-Hellman key exchange protocol. Alice and Bob agree on a prime $p$ and a primitive root $g$ modulo $p$; Alice picks secret $a$ and publishes $A = g^a \bmod p$; Bob picks secret $b$ and publishes $B = g^b \bmod p$; the shared key is $K = A^b = B^a = g^{ab} \bmod p$. Security rests on the discrete-logarithm assumption: given $(g, p, g^a \bmod p)$, recovering $a$ is computationally hard. The first published public-key cryptographic protocol; the conceptual ancestor of RSA (1978), ElGamal (1985), DSA (1991), and elliptic-curve Diffie-Hellman.
ElGamal, T. — A public key cryptosystem and a signature scheme based on discrete logarithms · *IEEE Transactions on Information Theory* IT-31 (1985), 469-472. The ElGamal public-key encryption and signature scheme based on the hardness of the discrete-logarithm problem in $(\mathbb{Z}/p)^\times$ for $p$ a large prime. ElGamal encryption: Alice's public key is $(g, p, h = g^x \bmod p)$ with $x$ her secret; Bob encrypts $m$ as the pair $(g^k \bmod p, m h^k \bmod p)$ for a fresh random $k$; Alice decrypts using $x$. The U.S. Digital Signature Algorithm (DSA, FIPS PUB 186, 1991) is a variant.
Shanks, D. — Class number, a theory of factorization, and genera · *Proceedings of Symposia in Pure Mathematics* 20 (1971), 415-440. Baby-step giant-step algorithm for the discrete logarithm in a cyclic group of order $N$: precompute $\sqrt N$ "baby steps" $g^j$ for $0 \leq j < \sqrt N$ in a hash table, then test $\sqrt N$ "giant steps" $a \cdot g^{-i \sqrt N}$ against the table; time and space complexity $O(\sqrt N)$. The first algorithm to break the naive $O(N)$ exhaustive search.
Pohlig, S. C. and Hellman, M. E. — An improved algorithm for computing logarithms over GF(p) and its cryptographic significance · *IEEE Transactions on Information Theory* IT-24 (1978), 106-110. The Pohlig-Hellman algorithm exploits the prime factorisation of the group order: for $(\mathbb{Z}/p)^\times$ of order $p - 1 = \prod q_i^{e_i}$, the DLP reduces by CRT to the DLP in each $q_i^{e_i}$-cyclic subgroup, each solvable in $O(e_i \sqrt{q_i})$ steps. Consequence: choosing $p$ with $p - 1$ having a large prime factor is necessary for DLP security. Standard for RFC-3526 "safe primes" $p = 2 q + 1$.
Adleman, L. M. — A subexponential algorithm for the discrete logarithm problem with applications to cryptography · *Proceedings of the 20th IEEE Symposium on Foundations of Computer Science* (1979), 55-60. The index-calculus method for the DLP in $(\mathbb{Z}/p)^\times$: choose a smoothness bound $B$ and a factor base of primes $\leq B$; collect relations $g^{r_i} \equiv \prod_j p_j^{e_{ij}} \pmod p$ until the linear system in the discrete logs of the factor-base primes is solvable. Sub-exponential complexity $L_p[1/2, c]$, later refined to $L_p[1/3, c]$ via the number-field sieve. Renders 1024-bit Diffie-Hellman insecure; 2048-bit is the modern minimum.
Shor, P. W. — Algorithms for quantum computation: discrete logarithms and factoring · *Proceedings of the 35th Annual Symposium on Foundations of Computer Science* (1994), 124-134; revised and expanded as 'Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer', *SIAM Journal on Computing* 26 (1997), 1484-1509. A polynomial-time quantum algorithm for the integer-factorisation and discrete-logarithm problems via the quantum Fourier transform over $\mathbb{Z}/N$. The order-finding subroutine $f(x) = g^x \bmod N$ has period equal to the multiplicative order of $g$ modulo $N$; the quantum Fourier transform extracts this period in $O((\log N)^3)$ time. Motivates the entire post-quantum cryptography programme.
Lucas, É. — Théorie des fonctions numériques simplement périodiques · *American Journal of Mathematics* 1 (1878), 184-240 and 289-321. Lucas's theory of primality testing via the order of an element. The Lucas-Lehmer test for Mersenne primes $M_p = 2^p - 1$ uses the cyclic-subgroup structure of $(\mathbb{Z}/M_p)^\times$ to certify primality in $O(p)$ multiplications. The general Lucas primality test: $n$ is prime if there exists $a$ with $a^{n - 1} \equiv 1 \pmod n$ and $a^{(n - 1)/q} \not\equiv 1 \pmod n$ for every prime $q \mid n - 1$ — i.e., the order of $a$ in $(\mathbb{Z}/n)^\times$ is exactly $n - 1$, certifying that $a$ is a primitive root and $(\mathbb{Z}/n)^\times$ has order $n - 1$, forcing $n$ to be prime.
Hardy, G. H. and Wright, E. M. — An Introduction to the Theory of Numbers · Oxford University Press, 6th edition (2008), revised by D. R. Heath-Brown and J. H. Silverman. Chapters VI-VIII (Fermat's theorem and its consequences; congruences to composite moduli; quadratic residues). Chapter VI §§6.8-6.18 develops primitive roots: existence modulo odd prime powers and modulo $2 p^k$, the index calculus, the structure of $(\mathbb{Z}/2^k)^\times$ as $\mathbb{Z}/2 \times \mathbb{Z}/2^{k-2}$ for $k \geq 3$. Chapter VIII §§8.1-8.8 develops the discrete logarithm and its applications.
Ireland, K. and Rosen, M. — A Classical Introduction to Modern Number Theory · Springer Graduate Texts in Mathematics 84, 2nd edition (1990), §4. Group-theoretic development of primitive roots and the structure of $(\mathbb{Z}/n)^\times$. Theorem 4.1.1: $(\mathbb{Z}/p)^\times$ is cyclic for $p$ prime. Theorem 4.1.2: every finite subgroup of the multiplicative group of a field is cyclic. Theorem 4.2.1: $(\mathbb{Z}/p^n)^\times$ is cyclic for $p$ odd. Theorem 4.3.1: $(\mathbb{Z}/2^n)^\times$ is the direct product $\mathbb{Z}/2 \times \mathbb{Z}/2^{n-2}$ for $n \geq 3$. The chapter is the canonical modern treatment of the cyclicity classification.
Apostol, T. M. — Introduction to Analytic Number Theory · Springer Undergraduate Texts in Mathematics, 1976. §§6-7 develop primitive roots and the index calculus with arithmetic-function methods, including the Möbius-inversion proof that the number of primitive roots modulo $p$ is $\varphi(p - 1)$, and the closed-form index tables for small primes.
Bourgain, J., Glibichuk, A. A. and Konyagin, S. V. — Estimates for the number of sums and products and for exponential sums in fields of prime order · *Journal of the London Mathematical Society* (2) 73 (2006), 380-398. Sum-product estimates in $\mathbb{F}_p$ used in modern analytic approaches to the distribution of primitive roots and the size of multiplicative subgroups.

Estimated time

beginner: 18m
intermediate: 45m
master: 85m