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

this pseudo code calculating integer factorisation took clrs. point in calculating gcd involved in line 8 , need doubling k when i == k in line 13.? please.

that pseudocode not pollard-rho factorization despite label. 1 trial of related brent's factorization method. in pollard-rho factorization, in ith step compute x_i , x_(2i), , check gcd of x_(2i)-x_i n. in brent's factorization method, compute gcd(x_(2^a)-x_(2^a+b),n) b=1,2, ..., 2^a. (i used indices starting 1 agree pseudocode, elsewhere sequence initialized x_0.) in code, k=2^a , i=2^a+b. when detect has reached next power of 2, increase k 2^(a+1).

gcds can computed rapidly euclid's algorithm without knowing factorizations of numbers. time find nontrivial gcd n, helps factor n. in both pollard-rho factorization , brent's algorithm, 1 idea if iterate polynomial such x^2-c, differences between values of iterates mod n tend candidates numbers share nontrivial factors n. because (by chinese remainder theorem) iterating polynomial mod n same simultaneously iterating polynomial mod each prime power in prime factorization of n. if x_i=x_j mod p1^e1 not mod p2^e2, gcd(xi-xj,n) have p1^e1 factor not p2^e2, nontrivial factor.

this 1 trial because x_1 initialized once. if unlucky, value choose x_1 starts preperiodic sequence repeats @ same time mod each prime power in prime factorization of n, though n not prime. example, suppose n=1711=29*59, , x_1 = 4, x_2=15, x_3=224, x_4=556, x_5=1155, x_6=1155, ... sequence not find nontrivial factorization, since of gcds of differences between distinct elements , 1711 1. if start x_1=5, x_2=24, x_3=575, x_4=401, x_5=1677, x_6=1155, x_7=1155, ... in either factorization method, find gcd(x_4-x_2,1711)=gcd(377,1711)=29, nontrivial factor of 1711. not sequences not helpful, others might work, might faster give , start initial value. so, don't keep increasing forever, there termination threshold might try different initial value.