# How does Pollard's rho algorithm work?

I am trying to understand how does Pollard's rho algorithm actually work, but I just can not wrap my head around it. I already read its section in the CLRS book and also on internet but still can not understand its structure or analysis. This is a java implementation of the pseudocode from the CLRS book along with euclid gcd algorithm:

public static void pollardRho(int n) {
Random rand = new Random();
int i = 1;
int x0 = rand.nextInt(n);
int y = x0;
int k = 2;
while (true) {
i++;
int x = (x0 * x0 - 1) % n;
int d = gcd(y - x, n);
if (d != 1 && d != n) {
System.out.println(d);
}
if (i == k) {
y = x;
k *= 2;
}
x0 = x;
}
}

public static int gcd(int a, int b) {
// fixes the issue with java modulo operator % returning negative
// results based on the fact that gcd(a, b) = gcd(|a|, |b|)
if (a < 0) a = -a;
if (b < 0) b = -b;

while (b != 0) {
int tmp = b;
b = (a % b);
a = tmp;
}
return a;
}
• Why does it choose $$x = (x_0^2 - 1) \mod n$$?
• What does $$y$$ actually represent and why is it chosen to be equal to $$\{x_1,x_2,x_4,x_8,x_{16},...\}$$?
• Why does it compute $$\text{GCD}(y-x,n)$$ and how does $$d$$ turns out to be a factor of $$n$$?
• And why is the expected running time is $$O(n^{1/4})$$ arithmetic operations and $$O(2^{\beta/4} \beta^2)$$ bit operations assuming that $$n$$ is $$\beta$$ bits long?

I understand that if there exists a non-trivial square-root of $$x^2 \equiv 1 \pmod{n}$$ then $$n$$ is a composite and $$x$$ is a factor, but $$y - x$$ is not a square root of $$n$$ is it?

• en.wikipedia.org/wiki/Pollard%27s_rho_algorithm
– D.W.
Commented Feb 26, 2020 at 23:36
• @D.W. I already read that but still don't understand it, also they seem to be explaining a different variant of the algorithm. Commented Feb 26, 2020 at 23:41

The idea behind Pollard $$\rho$$ is that if you take any function $$f : [0, n - 1] \to [0, n - 1]$$, the iteration $$x_{k + 1} = f(x_k)$$ must fall into a cycle eventually. Take now $$f$$ as a polynomial, and consider it modulo $$n = p_1 p_2 \dotsm p_r$$, where the $$p_i$$ are primes:

$$\begin{equation*} x_{k + 1} = f(x_k) \bmod n = f(x_k) \bmod p_1 p_2 \dotsm p_r \end{equation*}$$

Thus it repeats the same iteration structure modulo each of the primes into which $$n$$ factors.

We don't know anything about the cycles, but it is easy to see that if you go with $$x_0 = x'_0$$ and:

\begin{align*} x_{k + 1} &= f(x_k) \\ x'_{k + 1} &= f(f(x'_k)) \end{align*}

(i.e., $$x'$$ advances twice as fast) eventually $$x'_k$$ and $$x_k$$ will span one (or more) cycles (see Floyd's cycle detection algorithm for details), thus in our case, $$x'_k \equiv x_k \mod{p_i}$$, and $$\gcd(x'_k, x_k)$$ will be a factor of $$n$$, hopefully a non-trivial one.

Any polynomial works, but we want irreducible ones (no non-trivial factors, detecting those is not the point of the exercise). Linear polynomials don't give factors, next simplest to compute is a quadratic one, but just $$x^2$$ doesn't work either (reducible), so take $$x^2 + 1$$ for simplicity. Remember the idea here is to work with very large numbers, few and simple arithmetic operations are a distinct bonus. The analysis of the algorithm (e.g. in Knuth's "Seminumerical algorithms") models $$f(x) \bmod p$$ as a random function, which is close enough to explain the overall characteristics of the algorithm.

• The trick is that if n has a factor p, then xk modulo p has only p different values and will run into a cycle after about sqrt(p) steps (birthday paradox). And you can check whether xi modulo p and xj modulo are one cycle apart by checking whether gcd(xi, xj) ≠ 1. So you can check for cycles for all possible primes p simultaneously, without knowing p. So the smallest prime factor is found in O(n^(1/4)), because the smallest prime factor is less than sqrt(n). Commented Oct 31, 2022 at 9:34
• Except if n is prime - in that case pollard-rho would take O(n^(1/2)). So if you did say 5 n^(1/4) rounds then this was either very bad luck, or n is prime. So you try proving that n is a prime. Commented Oct 31, 2022 at 9:35

Just one part of the answer: You calculate a sequence and look for cycles. There are two well-known algorithms for cycle detections, Brent's and Floyd's. One calculates $$x_{2k}$$ and $$x_k$$ in parallel which will find cycles, the other tries to detect cycles of length ≤ 2, then length ≤ 4, then length ≤ 8, then length ≤ 16 etc. by calculating 2^k values from some starting point with k growing if no cycle is found. For example, if it takes 25 steps to enter a cycle of length 39, then when k = 32, y is set to a point in the cycle. When k = 64, x hasn't quite gone through the cycle since step 32, so y is set to a different point in the cycle (note that the algorithm doesn't know that it is inside the cycle). Then the algorithm would progress x until k = 128, but after 39 steps at k = 103 the cycle is found.

And another part: If p is a factor, then the sequence $$x_k \mod p$$ will run into a cycle after about $$p^{1/2}$$ iterations (at most p iterations, but the birthday paradox reduces it to the square root). But you can detect cycles for all primes simultaneously by checking whether n and $$x_i - x_j$$ have a common factor > 1. That common factor divides n.

An interesting thing is that pollard-rho will find for example a factor p = 127 always at exactly the same number of iterations (specific to the number 127, and the specific implementation), no matter which n that is a multiple of 127 you would examine.

Warning: The algorithm that you found is incomplete. First, it is very slow if n is not composite. It takes $$O(n^{1/2})$$ if n is a prime and will tell you "n is divisible by n", so you know nothing that you didn't know before. So after say $$5 n^{1/4}$$ iterations you start suspecting that n is prime and try to prove it. Second, pollard-rho can find two or more factors simultaneously. Worst case, if say n = p x q x r, it is possible that pollard-rho tells you "n is divisible by p x q", so you need to check if the factors you get are indeed primes. Worse, it is possible that pollard-rho tells you "n is divisible by n" if it found the factors p, q and r at the same time. Which is 100% true and 100% useless, so you have to run the algorithm again with say x^2 + 2, x^2 + 3 etc. instead of x^2 + 1. This is rare.

When you implemented your algorithm, you can make a table telling you which prime factor p is found after how many iterations. If you find multiple primes that take the same number of iterations, then their products will cause you trouble. Note that this is a property of the algorithm and the prime, not a property of n.

PS. Why not x^2 - 1? One reason is that if you get x = 1 at some point, you are stuck. And you have to be careful if you get x = 0. But I'd suggest that if you have the algorithm implemented with x^2 + 1, then you just check what happens if you replace it with x^2 and x^2 - 1. Will it still work?

PS. Only just noticed: If n is a prime, your algorithm will run forever. If pollard-rho finds n as a factor, then it's very likely that you have a prime, so you would check that.