Discrete logarithm calculator

Base g

Target h

Prime p

Solve for xLoad an example

Answer

Nothing you enter here leaves your browser. It uses exact big-integer arithmetic, so there is no rounding.

This discrete logarithm calculator finds the exponent x in gx ≡ h (mod p) for primes up to about 10¹³, using Shanks's baby-step giant-step method, and shows how much work it took. It's the problem behind Diffie–Hellman, and the page makes the point that a small prime falls in a flash while a 2,048-bit one never will. It runs in your browser.

What a discrete logarithm is

Ordinary logarithms undo exponentiation. If 2x = 1024 then x = 10. A discrete logarithm does the same thing in modular arithmetic, where numbers wrap around after reaching a prime p. Given a base g, a target h and the prime, find the exponent x with gx ≡ h (mod p).

Going the other way is easy. Computing gx mod p takes only about log₂(x) multiplications by the square-and-multiply method. But nobody knows a fast way back. The exponent hides in a scrambled sequence. 5, 25, 125, 625, … reduced modulo 999,983 jumps around with no pattern, and finding which position holds a given value seems to need a search. That asymmetry, easy forwards and hard backwards, is the foundation of Diffie–Hellman key exchange, ElGamal encryption and DSA signatures. Diffie and Hellman's 1976 paper that started public-key cryptography proposed exactly this.

Baby-step giant-step

The obvious attack is brute force. Try x = 0, 1, 2, … until gx = h, which takes up to p − 1 steps. Daniel Shanks's baby-step giant-step method (1971) does much better by trading memory for time. Write the unknown as x = i·m + j with m = ⌈√p⌉. Then gi·m + j = h rearranges to gj = h · (g−m)i, and the search splits in two:

1. Baby steps. Compute gj for every j from 0 to m − 1 and store them in a table, remembering which j gave which value.
2. Giant steps. Start at h and repeatedly multiply by g−m, looking each result up in the table. The first hit gives i and j, and so x = i·m + j.

Each phase takes about √p steps, so a 6-digit prime needs about a thousand of each instead of a million. The tool prints the sizes after each solve. The price is memory for the table, which is why the method stops being practical at around 10¹³, and why the tool refuses larger primes. (There are cousins that use almost no memory, such as Pollard's rho, which still take about √p time.)

Why a 2,048-bit prime is safe

The method's cost is the square root of the size of the group, and that's where the numbers get out of hand. This table assumes a billion steps a second, which is generous, and ignores the memory entirely:

Taking the square root halves the number of bits, so a 2,048-bit prime needs about 2¹⁰²⁴ steps, around 10³⁰⁸, which is unimaginable. Your browser computes the table's last row when the page loads. One caveat belongs here. Baby-step giant-step is a generic attack that works in any group, and for ordinary integers modulo a prime there are faster, sub-exponential methods, the number field sieve and its relatives. That's why real Diffie–Hellman primes are 2,048 bits or more and not 256. NIST rates a 2,048-bit prime as about 112 bits of security, not the 1,024 bits a generic attack would suggest. Elliptic-curve groups have no such shortcut, which is why 256-bit curves compare with 3,072-bit primes. In every group the principle is the same, and the attacker's work grows far faster than the user's.

Try it on the puzzle

Public-key systems rest on this problem being hard. See how long guessing takes for the same idea applied to passwords. This is the tool you need for level 4 of the treasure-chest puzzle. Eve recorded a protocol run that used a 6-digit prime, so the answer falls out in a thousand steps. Press "Load an example" and Solve to see the method work, then use it on Eve's numbers. The same weakness is why the protocol fails with a small prime, and the article explains it.

Common questions