The guide
Split the exponent in two and a hidden number gives itself up in the square root of the time
How baby steps and giant steps turn one search of a million guesses into two searches of a thousand, why a small prime is no protection, and why the same trick cannot touch a real key.
- 1,766 against 765,433 steps used against brute force, worked example
- m = 1,001 table size: ceiling of the square root of 1,000,002
- x = 765,432 found at giant step 764 and baby index 668
- 1,000,000 entries the largest table the page will build
- 1.797 x 10^308 table entries a 2048-bit group order would need
Read the full guide Fold the guide
Somebody picks a prime, a base and a target, and asks for the exponent that links them. In symbols: find x so that g to the power x leaves the remainder h when divided by p. Going from x to h is quick, even for huge numbers, because modular exponentiation is efficient. Going back is believed to be hard, and that gap is what a good deal of public-key cryptography stands on.
The obvious way back is to try every exponent in turn: g, g squared, g cubed, until the answer shows up. This is called trial multiplication, and it takes time proportional to the size of the group. For a group of a million elements that is a million multiplications. The American mathematician Daniel Shanks published a better method in 1971, and a later paper credits the idea to Gelfond in 1962. It does not beat the problem. It splits it.
Cutting one search into two
Pick a number m and write the unknown exponent as x = i m + j, where i and j both run from 0 up to m minus 1. The equation g^x = h then rearranges into g^j = h times (g^(-m))^i. The left side depends only on j. The right side depends only on i. Neither side needs the other to be computed, and that is the whole trick.
So compute the left side for every j once and keep the results in a table: these are the baby steps, each one a single multiplication by g. Then walk the right side: start at h and multiply by g^(-m) over and over, the giant steps, each one skipping m exponents at a time. After each giant step, look the value up in the table. A hit at position j after i giant steps means x = i m + j.
For this to cover every possible exponent in a group of order n, the two ranges together must reach n. That needs m times m to be at least n, so m is the ceiling of the square root of n: the integer square root, plus one unless n is a perfect square. Python’s math module has the integer square root as isqrt. The ceiling matters. With the floor, m times m can fall short of n, and the top few exponents are never searched.
Here is the case that shows it. For p = 1,000,003 the group of nonzero remainders has order 1,000,002. The floor of the square root is 1,000, and 1,000 squared is 1,000,000, two short of the order. The exponent 1,000,001 is therefore invisible to a table of 1,000 entries, and a search for it finds nothing. The ceiling is 1,001, and 1,001 squared is 1,002,001, which covers everything.
The other easy slip is the sign of the giant step. The recipe multiplies by g^(-m), the modular inverse of g^m, not by g^m itself. Multiplying by g^m walks the wrong way and can still land on a table entry, which returns a confident wrong answer. The page therefore computes g^x at the end and compares it with h. The check costs one modular power and rules out that whole class of wrong answers.
A worked example you can reproduce
Take p = 1,000,003, a prime, with base g = 2 and target h = 95,715. The order is 1,000,002, so m = 1,001. The inverse of 2^1001 modulo p, found with the extended Euclid algorithm, is 432,760. That inverse exists because g and p share no factor, which is the condition for any residue to be invertible.
The table holds the 1,001 values 2^0 up to 2^1000. The giant loop starts at gamma = 95,715 and multiplies by 432,760 at each step. Giant steps 0 to 763 all miss. At step 764 the value lands in the table at j = 668, so x = 764 times 1,001 plus 668 = 765,432. A direct check confirms that 2^765432 leaves the remainder 95,715.
The count is the point. The method used 1,001 baby steps and 765 giant steps, which is 1,766 steps in all. Trial multiplication would have tested 765,433 values: 1,766 against 765,433. The worst case for the split method is about 2m, here 2,002, because the giant loop can never run past m steps.
Numbers of 13 digits are too big for ordinary arithmetic in a browser, whose plain numbers hold integers exactly only up to 9,007,199,254,740,991. The page therefore multiplies with BigInt, which has no such limit, and keeps the table values, which are all below 10^13, as ordinary numbers. A separate Python script with exact integers gave the same inverse, the same meeting point and the same answer, and so did sympy’s discrete logarithm routine.
What the table costs, and what it buys
Nothing is free. The method spends memory to save time, a space-time tradeoff in the usual sense: the table holds about the square root of n entries, and the running time is also about the square root of n. Brute force needs almost no memory but time proportional to n.
The table is only useful if a lookup is cheap. In a well-dimensioned hash table the average cost of a lookup does not depend on how many entries it holds, which is why the loop does not slow down as m grows. A JavaScript Map is specified to give access times that are sublinear on average, and this page uses it as a table keyed by the value.
A smaller table is allowed. Choosing m below the square root saves memory, and the running time then grows in proportion to n divided by m. The method does not even need the exact order: any upper bound on it is enough, which is why the page has an optional bound n. With p = 101 and base 4, whose order is 50, a bound of 50 gives a table of 8 entries instead of 10. Storing one half and computing the other also drives the meet-in-the-middle attack, the main reason Double DES is not used. Here it is applied to a discrete logarithm.
When there is no answer
A discrete logarithm need not exist. Raising g to every power only ever produces the subgroup generated by g, and a target outside that subgroup has no logarithm at all. If g is a primitive root, a generator of the whole group, every target has one. If not, only some do.
With p = 101 and g = 4, the order of g is 50, so only half of the 100 nonzero residues are ever reached. The target 70 equals 4^17 and is found. The target 2 lies outside the subgroup, the giant loop runs through all of its steps without a hit, and the page reports that there is no answer rather than inventing one.
Even when an answer exists, it is only fixed up to a multiple of the order of g. The page reports the smallest exponent. Trial multiplication stops at that same exponent, so the number of values it tests is one more than the exponent.
Why a real key is out of reach
All of this works because the numbers are small. The page accepts primes of up to 13 digits, which makes m at most 1,000,000, and builds a table of that size in a second or two. Each extra two bits of group order doubles the table.
Now scale up. A group whose order is near 2^64 needs a table of about 4.3 billion entries. One near 2^128 needs about 1.8 x 10^19. A 2048-bit prime with a generator needs a table of about 1.797 x 10^308 entries. No computer will ever hold that, which is why real systems use groups of that size and why this method is no threat to them.
Attacks on real parameters use other ideas, such as the index calculus family, and key sizes are chosen against those. The Logjam attack exploited servers that still allowed 512-bit export-grade primes, and its authors estimated that the precomputation for one widely reused 1024-bit prime would be within the budget of a large national agency. Both rest on number field sieve precomputation shared across targets, not on a table of baby steps.
A small prime is another matter. When the modulus is a prime that is not too large, an eavesdropper can recover a Diffie-Hellman private exponent from public values with exactly this method. Small primes give no protection, because the work grows with the square root of the order and not with its length in digits.
What the method does not do
It does not handle a composite modulus well. When the group order has many small factors, the Pohlig-Hellman algorithm breaks the logarithm into small pieces by those factors and is far faster, which is why baby-step giant-step is usually used for groups of prime order. This page names that method and does not build it.
It does not cover other groups such as elliptic curves, where the arithmetic changes. And it does not replace Pollard’s rho for logarithms, which has about the same running time with only a small memory requirement. Rho trades the table for a random walk, and it is what you reach for when the table no longer fits.
The takeaway is a pattern more than a program. When a search has the shape of a product, two small searches that must agree beat one large one, provided you can afford to remember one of them. Here the pattern turns a million guesses into about two thousand, and the arithmetic of the table tells you at once where it stops paying.
Sources
Every source consulted for this guide. Links checked November 15, 2026.
- Baby-step giant-step Wikipedia (CC BY-SA)
- Discrete logarithm Wikipedia (CC BY-SA)
- Modular arithmetic Wikipedia (CC BY-SA)
- Modular exponentiation Wikipedia (CC BY-SA)
- Primitive root modulo n Wikipedia (CC BY-SA)
- Cyclic group Wikipedia (CC BY-SA)
- Pohlig-Hellman algorithm Wikipedia (CC BY-SA)
- Pollard's rho algorithm for logarithms Wikipedia (CC BY-SA)
- Index calculus algorithm Wikipedia (CC BY-SA)
- Diffie-Hellman key exchange Wikipedia (CC BY-SA)
- Space-time tradeoff Wikipedia (CC BY-SA)
- Hash table Wikipedia (CC BY-SA)
- Meet-in-the-middle attack Wikipedia (CC BY-SA)
- Daniel Shanks Wikipedia (CC BY-SA)
- BigInt - JavaScript MDN Web Docs (Creative Commons licence)
- Map - JavaScript MDN Web Docs (Creative Commons licence)
- math - Mathematical functions Python Software Foundation (PSF licence)