In 1971, the American mathematician Daniel Shanks published a method for a problem that had nothing to do with digital money. The idea was simple enough to fit in a paragraph and good enough to last half a century: instead of traversing the entire path from one end, traverse half from each end and meet in the middle.
The problem here is the one from the previous lesson in its favorable version: the public key Q is known, it is known that it equals k times G, and it is known that k is between zero and N. Finding k by brute force would cost N steps. Shanks' method costs about twice the square root of N.
The trick is to write k in a different way. Call m the square root of N, rounded up. Every number between zero and N can be written as i times m plus j, with i and j less than m — it's the same decomposition you do when you say 47 is four tens and seven units, just with m instead of ten.
Substituting in the equation, Q is equal to i times m plus j, all multiplied by G. Move j to the other side: Q minus j times G is equal to i times the point m times G. Notice what happened. On the left side, there are only things that depend on j; on the right side, only things that depend on i. The two sides have been separated.
That's where the name comes from. The baby steps are the m values on the left side: calculate Q minus j times G for each j, and store each result in a table. The giant steps are the m values on the right side: calculate i times the point mG for each i, and for each one, look it up in the table. When a value matches, the corresponding i and j reveal k, because k is i times m plus j.
In bits, the savings are clear. A seventy-bit range has 2^69 candidates, and the square root of that is around 2^34.5 — just over twenty-four billion steps on each side. A machine that performs a few billion operations per second can go through this in minutes, not millennia.
But the calculation above is for time, and the method charges in another currency. The baby step table needs to exist in its entirety before the giant steps begin. There are twenty-four billion entries, and each entry stores at least a piece of the point's coordinate and the value of j — something like thirty bytes per line, being generous. This amounts to nearly seven hundred and fifty gigabytes of memory for a seventy-bit range.
And the memory grows at the same root as time. Eighty bits require about twenty-four terabytes; ninety require almost eight hundred. Storing this on disk instead of memory doesn't solve the problem, because each giant step makes a query to an unpredictable address, and disks don't like random access: the method stops being limited by calculation and starts being limited by search time.
There are versions that reduce the table by storing only part of each point and accepting to check false positives later. They help by a constant factor and do not change the nature of the problem: the baby step and giant step is a method that trades memory for time, and this trade has a physical limit that arrives quickly.
It was to escape exactly this limit that another path was sought — one that costs the same square root in time and practically nothing in memory. It exists, has an animal name, and is the algorithm that has solved the largest challenges ever tackled. In the next lesson, Pollard's kangaroos.