What is the reason behind calculating GCD in Pollard rho integer factorisation?

Question

This is the pseudo code for calculating integer factorisation took from CLRS. But what is the point in calculating GCD involved in Line 8 and the need for doubling k when i == k in Line 13.? Help please.

Answer 1

That pseudocode is not Pollard-rho factorization despite the label. It is one trial of the related Brent's factorization method. In Pollard-rho factorization, in the ith step you compute x_i and x_(2i), and check the GCD of x_(2i)-x_i with n. In Brent's factorization method, you compute GCD(x_(2^a)-x_(2^a+b),n) for b=1,2, ..., 2^a. (I used the indices starting with 1 to agree with the pseudocode, but elsewhere the sequence is initialized with x_0.) In the code, k=2^a and i=2^a+b. When you detect that i has reached the next power of 2, you increase k to 2^(a+1).

GCDs can be computed very rapidly by Euclid's algorithm without knowing the factorizations of the numbers. Any time you find a nontrivial GCD with n, this helps you to factor n. In both Pollard-rho factorization and Brent's algorithm, one idea is that if you iterate a polynomial such as x^2-c, the differences between the values of the iterates mod n tend to be good candidates for numbers that share nontrivial factors with n. This is because (by the Chinese Remainder Theorem) iterating the polynomial mod n is the same as simultaneously iterating the polynomial mod each prime power in the prime factorization of n. If x_i=x_j mod p1^e1 but not mod p2^e2, then GCD(xi-xj,n) will have p1^e1 as a factor but not p2^e2, so it will be a nontrivial factor.

This is one trial because x_1 is initialized once. If you get unlucky, the value you choose for x_1 starts a preperiodic sequence that repeats at the same time mod each prime power in the prime factorization of n, even though n is not prime. For example, suppose n=1711=29*59, and x_1 = 4, x_2=15, x_3=224, x_4=556, x_5=1155, x_6=1155, ... This sequence does not help you to find a nontrivial factorization, since all of the GCDs of differences between distinct elements and 1711 are 1. If you start with x_1=5, then x_2=24, x_3=575, x_4=401, x_5=1677, x_6=1155, x_7=1155, ... In either factorization method, you would find that GCD(x_4-x_2,1711)=GCD(377,1711)=29, a nontrivial factor of 1711. Not only are some sequences not helpful, others might work, but it might be faster to give up and start with another initial value. So, normally you don't keep increasing i forever, normally there is a termination threshold where you might try a different initial value.