2
$\begingroup$

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?

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

2 Answers 2

5
$\begingroup$

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.

$\endgroup$
2
  • 1
    $\begingroup$ 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). $\endgroup$
    – gnasher729
    Commented Oct 31, 2022 at 9:34
  • $\begingroup$ 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. $\endgroup$
    – gnasher729
    Commented Oct 31, 2022 at 9:35
1
$\begingroup$

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.

$\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.