# 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). 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. 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). Dec 25, 2023 at 21:51