Optimising Pollard's Rho algorithm for large semi-primes 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?
Might as well make this an answer, enough comments. This'll answer your latest questions:


I don't think they have to start at 2, however they need to start at the same value (as per the cycle detection algorithm). So 2 is the simplest choice, and since the function is assumed to trace a pseudorandom sequence, it doesn't really matter where you start.
The function can be any pseudorandom function satisfying the Rho property (gcd is conserved by iterating through it, basically it inherently "remembers" whenever you capture a factor of $n$ without having to store all the numbers, this is the core concept). But $x^2 + c$ is the simplest one, so it's often the best choice as it's fast to calculate and produces a relatively chaotic sequence mod $p$.
$c$ can be negative, because the function is taken modulo $n$, so a negative value is still positive, however it cannot be $0$ or $−2$ (to prevent trivial cycles in $x = 0$ and $x = \pm 1$).
Yes, I said "on the order", this is a probabilistic algorithm so it's usually either a bit less, either a bit more.. it depends on $c$ and on the factor found.  The idea being that it's very fast on small factors (~20 digit prime factor maximum, so I would say a 40-50 digit semiprime is the best you're going to get with Pollard's Rho in reasonable time, which is still pretty good considering its simplicity)