Discrete Logarithm

Statement

Let $p$ be prime and $g$ a primitive root mod $p$. The discrete logarithm of $a \in (\mathbb{Z}/p\mathbb{Z})^\times$ base $g$ is the unique integer $k$ with $0 \le k < p-1$ satisfying

Because $g$ generates $(\mathbb{Z}/p\mathbb{Z})^\times$ (by Primitive RootsPrimitive Roots$$g \text{ is a primitive root mod } p \iff \{g^0, g^1, \ldots, g^{p-2}\} = (\mathbb{Z}/p\mathbb{Z})^\times$$A primitive root mod p is a generator of the cyclic group (Z/pZ)*, existing for every prime pRead more →), such $k$ always exists and is unique mod $p-1$. The hardness of computing $k$ from $g$, $a$, and $p$ is the Discrete Logarithm Problem (DLP), the security foundation of Diffie-Hellman and elliptic-curve cryptography.

Visualization

Discrete log table for $g = 2$ in $(\mathbb{Z}/11\mathbb{Z})^\times$:

$k$	$2^k \bmod 11$
0	1
1	2
2	4
3	8
4	5
5	10
6	9
7	7
8	3
9	6

Reading the table backwards: $\log_2 5 = 4$, $\log_2 10 = 5$, $\log_2 7 = 7$. Note that 2 hits all 10 nonzero residues, confirming it is a primitive root mod 11.

Proof Sketch

1. $(\mathbb{Z}/p\mathbb{Z})^\times$ is cyclic of order $p-1$, generated by $g$.
2. The map $k \mapsto g^k$ (for $k \in \mathbb{Z}/(p-1)\mathbb{Z}$) is a group isomorphism from $(\mathbb{Z}/(p-1)\mathbb{Z}, +)$ to $((\mathbb{Z}/p\mathbb{Z})^\times, \times)$.
3. Therefore every element $a$ has a unique preimage $k$ — the discrete logarithm.
4. The discrete log satisfies $\log_g(ab) = \log_g a + \log_g b \pmod{p-1}$, turning multiplication into addition.

Connections

Discrete logarithms exist in any cyclic group; the same concept applies to elliptic curve groups. The existence follows from the Primitive RootsPrimitive Roots$$g \text{ is a primitive root mod } p \iff \{g^0, g^1, \ldots, g^{p-2}\} = (\mathbb{Z}/p\mathbb{Z})^\times$$A primitive root mod p is a generator of the cyclic group (Z/pZ)*, existing for every prime pRead more → theorem. The analogue over $\mathbb{R}$ is the ordinary logarithm from the Fundamental Theorem of CalculusFundamental Theorem of Calculus$$\int_a^b f'(x)\,dx = f(b) - f(a)$$Integration and differentiation are inverse operationsRead more → viewpoint.

/-- If g generates (ZMod p)ˣ, then every element a has a discrete log. -/
theorem dlog_exists {p : ℕ} [Fact p.Prime]
    (g : (ZMod p)ˣ)
    (hg : ∀ x : (ZMod p)ˣ, x ∈ Subgroup.zpowers g)
    (a : (ZMod p)ˣ) : ∃ n : ℤ, g ^ n = a := by
  obtain ⟨n, hn⟩ := hg a
  exact ⟨n, hn⟩