The Discrete Logarithm

With a primitive root g modulo a prime p, every nonzero residue is g^{x} for some exponent x. Given g and x, computing y \equiv g^{x} \pmod p is quick, even for enormous numbers, using fast modular exponentiation. But run the question backwards — given g and y, what was x? — and everything grinds to a halt. That reversed question is the discrete logarithm problem, and the belief that it has no fast answer 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 (base g) is the exponent x with

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

It is the modular analogue of an ordinary logarithm — "what power do I raise the base to?" — but living in a finite, scrambled world where there's no smooth curve to read values off, only a jumble of residues that must be checked one by one.

It behaves like a logarithm in a second way too: it turns multiplication into addition. Modulo 7 with g = 3, the discrete log of 2 is 2 (since 3^2 \equiv 2) and the discrete log of 6 is 3 (since 3^3 \equiv 6). Multiply the residues: 2 \times 6 = 12 \equiv 5 \pmod 7. Add their discrete logs instead: 2 + 3 = 5 — exactly the discrete log of 5 (since 3^5 \equiv 5, from the worked example below). In symbols, \operatorname{dlog}(xy) \equiv \operatorname{dlog}(x) + \operatorname{dlog}(y) \pmod{p-1} — precisely the rule \log(xy) = \log x + \log y you already know, just wearing a modular disguise.

Does the base have to be a primitive root?

Not strictly — but it has to be able to reach the target. If g is a primitive root, its powers cover every nonzero residue, so a discrete log of y always exists for any y. If g is not a primitive root — recall 2 modulo 7, whose powers only ever reach \{2, 4, 1\} — then a discrete log of 2 with base 2 still makes sense (it's 1), but a discrete log of, say, 3 with base 2 modulo 7 simply doesn't exist — no power of 2 is ever congruent to 3. Using a primitive root as the base is what guarantees the discrete logarithm is defined for every nonzero residue, which is exactly why cryptographic schemes insist on one.

Worked example: brute-forcing a small discrete log

Why call it "discrete"? An ordinary logarithm lives on a smooth number line — you could sketch y = \log_g(x) as a continuous curve and read off an approximate answer for any x, or use calculus to close in on it. Residues modulo p have no such curve: they're a finite, scattered set of whole numbers with no "in between," and no notion of one candidate exponent being close to the right one. There's nothing to zero in on gradually — you either land on the exact residue, or you don't. That absence of any smooth structure to exploit is a big part of why the problem resists every clever shortcut that works for ordinary logarithms.

Solve 3^{x} \equiv 5 \pmod 7 for x. With such a small modulus, the only honest approach is also the simplest one: list every power of 3 until 5 turns up.

3^1 \equiv 3,\quad 3^2 \equiv 2,\quad 3^3 \equiv 6,\quad 3^4 \equiv 4,\quad 3^5 \equiv 5 \pmod 7.

There it is at the fifth step: 3^5 \equiv 5 \pmod 7, so x = 5. Five multiplications and a lookup — trivial for a modulus this tiny.

Try a second one modulo 11, using the primitive root g = 2: solve 2^{x} \equiv 9 \pmod{11}.

2^1 \equiv 2,\ 2^2 \equiv 4,\ 2^3 \equiv 8,\ 2^4 \equiv 5,\ 2^5 \equiv 10,\ 2^6 \equiv 9 \pmod{11}.

Six steps this time: x = 6. Notice the pattern — there is no shortcut, no formula to jump straight to the answer. You simply climb the list of powers, one rung at a time, until you spot the target.

Smarter than brute force — but still not fast

Nobody actually solves discrete logs by listing every power one at a time; there are cleverer methods. The simplest is baby-step giant-step: instead of trudging through all p - 1 exponents in order, split the search into two halves and meet in the middle, so it only needs roughly \sqrt{p} steps instead of p of them. That sounds like a huge win — and it is, mathematically — but it's nowhere near enough to make large discrete logs practical. If p has 300 digits, \sqrt{p} still has roughly 150 digits' worth of steps to check — a number so large that even this "smarter" algorithm would still outlast the sun.

Real cryptographic attacks use even more sophisticated methods still (with names like the number field sieve), which shave the exponent down further without ever making it polynomial. That's the crucial detail: every known classical improvement makes the climb a little gentler, but none of them turn the mountain into a hill.

Forward (compute g^x \bmod p from x) is easy — polynomial time, via repeated squaring.
Backward (recover x from g^x \bmod p) is believed hard — no efficient classical algorithm is known for large p.

This lopsidedness — trivial one way, brutal the other — is exactly the kind of "one-way function" cryptography is built from: something anyone can compute, but that (almost) nobody can undo.

It's easy to slip into saying the discrete logarithm problem is proven impossible to solve quickly. It isn't — nobody has ever proved that a fast classical algorithm can't exist. All anyone can honestly say is that decades of trying, by very smart, very motivated people, haven't found one. That's strong evidence, not a mathematical guarantee. The entire security of Diffie–Hellman and its relatives rests on this unproven — if extensively battle-tested — assumption.

There's a sharper reason to stay humble about it, too: a large-scale quantum computer running Shor's algorithm could solve the discrete logarithm problem efficiently, collapsing the "hard" direction back down to easy. Such machines don't exist yet at the size needed to threaten real cryptographic primes, but the possibility is exactly why researchers are already building "post-quantum" alternatives that don't lean on this one assumption.

So how big a prime is actually safe? Researchers occasionally attack smaller discrete logs on purpose, just to measure how far the "hard" side has really been pushed. In 2019, a team of cryptographers solved a discrete logarithm modulo a carefully chosen 795-bit prime (about 240 decimal digits) — a new record at the time. It took the equivalent of roughly thousands of years of computing time on a single computer, spread across a cluster of machines running for months.

That sounds terrifying until you compare it with what's actually used in practice: modern systems favour primes of 2048 bits or more — not merely twice as big as the record, but astronomically harder, because the difficulty grows exponentially with the number of digits. The record-breaking effort is exactly the kind of evidence behind the word "believed" in "believed hard" — nobody has proven it, but the gap between what's crackable and what's actually deployed keeps getting checked, and it keeps holding.

The payoff: Diffie–Hellman

This asymmetry lets two strangers agree on a shared secret over a public channel, in full view of anyone listening. 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, for a large enough prime, cannot.

Whitfield Diffie and Martin Hellman published this idea in 1976, in a paper called "New Directions in Cryptography" — with an important contribution from Ralph Merkle, whose earlier work on secure communication over insecure channels helped inspire it. At the time it felt like magic: for the entire history of cryptography, both sides of a conversation had needed to secretly share a key before they could talk. Diffie, Hellman and Merkle showed that strangers could build a shared secret live, in public, with no prior meeting at all.

Decades later, it emerged that British intelligence had gotten there first — and told no one. Between 1969 and 1974, mathematicians James Ellis, Clifford Cocks and Malcolm Williamson at GCHQ had independently worked out essentially the same idea (Cocks's version even anticipated what we now call RSA), but it was classified as a state secret and only declassified in 1997. The public world of cryptography had to reinvent it from scratch — a reminder that a beautiful piece of mathematics has a way of getting discovered more than once.

Every time your browser shows a little padlock icon, there's a good chance this exact hard problem is quietly at work behind the scenes. Diffie–Hellman key exchange (and its modern cousin, elliptic-curve Diffie–Hellman) is one of the handshakes that sets up an encrypted HTTPS connection, letting your laptop and a bank's server that have never met before agree on a secret key while an attacker watches every byte fly past.

Move the same idea onto elliptic curves instead of ordinary modular arithmetic, and you get the elliptic-curve discrete logarithm problem — believed even harder, for a given key size, than the version here. That's why elliptic-curve cryptography can use much shorter keys than classic Diffie–Hellman while staying just as hard to break. One unproven assumption, sitting quietly underneath nearly every secure connection on the internet today.