0
$\begingroup$

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?

$\endgroup$
3
  • $\begingroup$ 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). $\endgroup$
    – SEJPM
    Commented Apr 17, 2016 at 13:05
  • $\begingroup$ 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. $\endgroup$
    – gnasher729
    Commented Dec 25, 2023 at 21:48
  • $\begingroup$ 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). $\endgroup$
    – gnasher729
    Commented Dec 25, 2023 at 21:51

1 Answer 1

1
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.