# Is it possible for the Rho method against an Elliptic Curve to take more than the sqrt of the total state space?

Is it possible for the Rho method against an Elliptic Curve to take more than the sqrt of the total state space? It the reason why this is not generally done because of a meet-in-the-middle attack?

• IIRC this is an estimate based on the birthday paradox. It is possible to take siginifcantly longer but this is also highly unlikely (but I'm not fit enough in Pollard-Rho to give a real answer). Commented Apr 17, 2016 at 13:05
• Assume n = p * q, and we don’t find either in 5 * n^(1/4) steps. Then p, q are not found in c1 sqrt(p) and c2 sqrt(q) steps with c1 * c2 >= 25, so one is a bit larger and one a bit smaller than 5. One such prime is rare, two are very rare. Not impossible. And I think this behaviour is random. So at some point you think “maybe n is prime” and run a primality test, but if it is composite then you might as well continue with pollard-rho. Commented Dec 25, 2023 at 21:48
• Floyd’s cycle finding takes more iterations, but each calculates only one new value instead of two (or three if you don’t store calculated values). Commented Dec 25, 2023 at 21:51

## 1 Answer

The Rho method is probabilistic, so it's possible you could find the solution within the first few iterations, or after you've generated almost the entire space.

The probability starts getting in your favor around the square root of the order, because that's when the probability reaches approximately 50%. Since the probability increases quadratically, it's very likely to find a solution shortly after passing that point.