Factoring with Pollard's algorithm

The Pollard-rho method. Here is a primitive version without improvements by Brent. One reason for the success of the method is the Bursday paradox. The method produces "randomly" numbers modulo the unknown prime number p and will eventually find two numbers x,y, which are congruent modulo p. With GCD[n,x-y], the factor p is recovered.


FactorWithPollard[n_] := Module[{a=3, x=17, y=17, q=1},
   While[Less[q,2],
     Do[x=Mod[x*x-a,n];
        y=Mod[y*y-a,n];
        y=Mod[y*y-a,n];
        q=Mod[q*(x-y),n],{i,20}];
     q=Mod[GCD[n,x-y],n] ];q];

Here are some tests. The Pollard method got famous, with the factorisation of the 8'th Fermat number. With the above primitive program and not too much patience, one can factor the 6'th Fermat number.


FermatNumber[n_]:=2^(2^n)+1;

FactorWithPollard[FermatNumber[5]];
FactorWithPollard[FermatNumber[6]];