The Discrete Logarithm
With a primitive root
g modulo a prime p, every nonzero residue is
g^{x} for some exponent x. Recovering that
exponent is the discrete logarithm — and the belief that it is hard is
what secures a large part of the modern internet.
Definition
Given a primitive root g modulo p and a
residue y, the discrete logarithm of y is the
exponent x with
g^{x} \equiv y \pmod{p}.
It is the modular analogue of an ordinary
logarithm — but
living in a finite, scrambled world. Modulo 7 with
g = 3: since 3^{4} = 81 \equiv 4, the discrete
log of 4 is 4.
A one-way street
Computing g^{x} from x is easy —
square-and-multiply
does it in milliseconds even for thousand-digit primes. But reversing it — finding
x from g^x — has no known efficient
method. Unlike the real logarithm, the residues jump around unpredictably, so there is
nothing to interpolate. The best known classical algorithms still take time exponential in the size
of p.
- Forward (exponentiate) is easy — polynomial time.
- Backward (take the log) is believed hard — no efficient classical algorithm is known.
The payoff: Diffie–Hellman
This asymmetry lets two strangers agree on a shared secret over a public channel. Alice and Bob
publicly fix g and p, secretly pick
a and b, and exchange
g^{a} and g^{b}. Each then forms
(g^{b})^{a} = g^{ab} = (g^{a})^{b} \pmod p,
a key only they share. An eavesdropper sees g,
g^{a} and g^{b} but would need a discrete
logarithm to recover a or b — and cannot. The
same hard problem, transplanted onto elliptic curves, secures most of today's encrypted traffic.