On this page
1. The problem in one line
Ordinary logarithms answer "what power turns 2 into 8?" — and the answer, 3, can be found by steady approximation. Bigger exponents give bigger results, so you can close in.
Now do it inside modular arithmetic. Given a base g, a prime p, and a result y, find the exponent x:
Forwards is fast. Backwards, for a well-chosen prime, is believed to be infeasible. That is the discrete logarithm problem.
2. Why it is hard
The wrap destroys order. In ordinary arithmetic the outputs climb steadily, so you can guess intelligently. Modulo a prime, consecutive exponents scatter across the whole range with no pattern to exploit.
34 mod 17 = 13 35 mod 17 = 5 36 mod 17 = 15
Knowing 3⁵ = 5 tells you nothing useful about 3⁶. With a 2048-bit prime there is nothing to do but search a space larger than the number of atoms in the universe.
3. Diffie–Hellman key exchange
In 1976 Whitfield Diffie and Martin Hellman used this asymmetry to solve a problem that had looked impossible: two people who have never met agreeing on a secret key over a line everyone can hear.
Agree publicly
Alice and Bob agree on a prime p and base g. Eavesdroppers see both.
Choose secrets
Alice picks a, Bob picks b. Neither is ever transmitted.
Exchange
Alice sends ga mod p; Bob sends gb mod p. Both values travel in the clear.
Combine
Alice computes (gb)a, Bob computes (ga)b. Both equal gab mod p — the shared secret.
An eavesdropper has ga and gb but needs gab, and getting there means solving a discrete logarithm.
Note what this does not provide: authentication. Diffie–Hellman alone cannot tell you who is on the other end, which is why an active attacker can sit in the middle and why real systems bolt on signatures. Protocols handle that.
4. How it gets attacked
Brute force means trying every exponent — hopeless at real sizes. Better algorithms exist:
Baby-step giant-step trades memory for time, solving in about √p steps instead of p. That is a huge speed-up and still nowhere near enough: the square root of a 2048-bit number is a 1024-bit number.
Pollard's rho reaches similar √p time with almost no memory. Index calculus does better still against ordinary prime fields, which is why those moduli must be so large.
Index calculus does not transfer to elliptic curve groups — which is why ECC gets equivalent security from 256-bit keys instead of 3072-bit ones.
5. Where it stands today
Classical attacks are held off by size. Shor's algorithm, however, solves discrete logarithms efficiently on a large quantum computer — the same blow that lands on RSA. Both rest on problems quantum computers are unusually good at.
That is why NIST standardised lattice-based replacements, and why anything that must stay secret for decades should already be moving.
Solve one by hand
The discrete log calculator shows every step of a baby-step giant-step search at readable scale.
Open the calculator →Frequently asked questions
- What is the discrete logarithm problem?
- Given g, a prime p and a result y, find the exponent x such that g^x is congruent to y modulo p. Computing the power is fast; recovering the exponent is believed to be infeasible for large primes.
- Why is the discrete logarithm hard?
- Because modular reduction destroys the ordering of outputs. Consecutive exponents scatter unpredictably, so there is no way to narrow the search by comparing sizes.
- How does Diffie-Hellman use it?
- Two parties exchange g^a and g^b publicly and each raises the other's value to their own secret, both arriving at g^ab. An eavesdropper would need to solve a discrete logarithm to match them.
- Is the discrete logarithm problem quantum-safe?
- No. Shor's algorithm solves it efficiently on a sufficiently large quantum computer, which is why lattice-based replacements are being standardised.