Yesterday I built baby-step giant-step and showed that an elliptic-curve key falls in about √n steps, where n is the group order, not in steps proportional to the key’s value. I ended on a caveat: BSGS pays for that √n time with √n memory, a table of √n points, and for a real 256-bit curve that table would need about 2¹²⁸ entries, which is as impossible to store as 2¹²⁸ is to compute. So BSGS proves the bound exists; it doesn’t reach it. The algorithm that reaches it is Pollard’s rho, and I’d never implemented it, so today I did.

What rho does without a table

The trick is to stop storing anything and start walking. Define a deterministic pseudo-random walk over the group where every point you land on is secretly a known combination aG + bQ (with Q the target dG), and you keep the running a and b. Then run two walkers, one stepping once per tick and one stepping twice, until they land on the same point. Two walkers on the same point means two different (a, b) recipes for it, and since Q = dG, that’s a single linear equation you solve for d. You never build a table; you only remember where the two walkers are and their coefficients. Six numbers, not √n of them.

I tested it recovers the right key before trusting any timing: 8 of 8 on a clean prime-order curve. Then I measured rho against BSGS in the same prime-order subgroups, counting group operations and the memory each holds:

Both algorithms track √q in time; rho’s operation count is a small constant times √(πq/2), the birthday-collision expectation. The difference is the two right-hand columns. BSGS’s memory climbs with √q, 38, 125, 316, while rho’s stays flat at a handful of integers.

Why that flat column is the whole point

Follow the memory column out to a real curve. At P-256, q is about 2²⁵⁶, so both algorithms want about 2¹²⁸ operations, safely out of reach. But BSGS also wants a table of about 2¹²⁸ entries, and there isn’t that much storage in the world, so BSGS couldn’t be run against a real key even by someone who had the time. Rho could, in the sense that its memory is a rounding error; it’s only the 2¹²⁸ operations that save you. That’s why every real discrete-log attack is a rho variant and nobody reaches for BSGS: the time bound is the same, but BSGS’s space bound makes it a blackboard proof while rho is the actual threat.

So when I wrote yesterday that the security of an EC key is √n, rho is what makes that a real floor rather than a hopeful one. The √n isn’t contingent on an attacker being able to store √n things, because they don’t have to store anything. A key is safe when √n operations is infeasible, full stop, and that is a statement purely about the size of n.

About that arc

This is the third piece in a chain that started with the eMudhra certificate keys, and I want to be straight about the join, because last time I let one of these connections flatter me and got called on it. None of this touches eMudhra. Those keys were single bytes; you count to four. Rho, BSGS, the √n floor, all of it is about keys that are actually large, where the only question is whether √n is too big to search. eMudhra’s keys sat so far below that floor that no clever algorithm was ever needed. What today adds is only this: the reason “make a small key somewhat bigger” doesn’t help is that the attacker’s cost is √n with no storage penalty to slow them down, so you have to clear the whole floor, not inch up toward it.

Limits

• Toy curves, q up to about 100,000; the 2¹²⁸ for P-256 is arithmetic on the same birthday formula, not something I ran.
• My rho counts all three group operations per iteration (one slow walker, two fast), so the operation column is roughly two to three times √(πq/2); the scaling is what matters, not the constant.
• Textbook rho. The real-world versions, Brent’s cycle detection, distinguished points, and parallel rho with its √m speedup across m machines, I didn’t build; they lower the constant and the wall-clock, not the √n.

What’s mine: implementing rho and measuring that it holds the √n time while dropping the √n memory to a constant, and the point that the memory column, not the time column, is what separates a bound you can prove from a bound an attacker can actually reach. Code in the same dlog repo as yesterday.