Pollard's Rho algorithm

Pollard's Rho algorithm for factoring a composite integer n works as follows. Use a starting number x_0 (I'm using x_0 == 0) and a polynomial f(x) (I'm using f(x) = x^2 + 1), repeatedly apply the polynomial to the number (eg x_2 = f(f(x_0))), so after i applications you have x_i, and do this arithmetic mod n. For each index k such that you have values for x_k and x_2k, test if gcd(n, |x_2k - x_k|) is greater than 1 and less than n. If so, it will be a factor for n. This is because the graph described by repeatedly applying f(x) mod n looks like a straight path that culminates in a loop, because there are a finite set of numbers less than n and sooner or later you'll see a repeat in the sequence. But actually, since the arithmetic is being done mod n, it is also being done mod p for any prime p that divides n. So even though you are looping with respect to arithmetic mod p, the actual values in the loop may differ because the actual arithmetic is mod n. So two values for the same "node" in a loop may differ, but if so, the difference may be divisible by p. So, given two possible values x_k and x_2k, it is sufficient to test gcd(n, |x_2k - x_k|) to see if anything nontrivial comes up; if so, it is a factor of n.