I have programmed an implementation of Pollard's Rho factoring algorithm using C++ and the GMP library.
It is reasonably fast with large numbers, however I haven't implemented any form of cycle detection (I just try and avoid the problem, see below), and it struggles with small numbers.
Here is the pseudo code of my implementation:
input n x = 2 y = 2 d = 1 c = 1 z = 1 failed = 0 temp = 0 while d == 1 or d == n z = 1 failed = failed + 1 if failed = sqrt(n) c = c + 1 failed = 0 repeat 100 times: x = x^2 + c mod n repeat twice: y = y^2 + c mod n temp = abs(x - y) z = z * temp d = gcd(z, n)
I was wondering how I could improve the efficiency of this algorithm? If I'm using large semiprimes, do I need to worry about cycle detection?