Pollard’s ρ Method for factoring

Math 302 Cryptography, March 8, 2017
T. Ratliff, Wheaton College
ratliff_thomas@wheatoncollege.edu

Defining the functions

This is a quick and dirty implementation of the factoring given in Exercise 5.44 of Hoffstein, Pipher, and Silverman

f[x_,n_]:=  Mod[x^2+1 , n]

pollardsRho[n_]:= Module[{x=0,y=0,g=1,i=0},
If[PrimeQ[n]==True, Return[n]];
While[g==1,
x=f[x,n];
y=f[y,n];
y=f[y,n];
g=GCD[Abs[x-y],n]; i++;
];
Print[i, " iterations of Pollard's ρ"];
Return[g];
]

factor[n_]:=Module[{prod=1, tempn=n, g, factorlist={}},
While[prod≠n,
g=pollardsRho[tempn];
Print["     factor found: ",g];
tempn=tempn/g;
prod=prod*g;
AppendTo[factorlist,g];
];
Return[factorlist];
]

Let’s factor some numbers!

factor[351]

Let’s generate a 160-bit odd integer and factor it

bits=160;
n=2*RandomInteger[{2^(bits-2),2^(bits-1)}]+1

factors=factor[n]
Print["Are prime? ",PrimeQ[factors]]
Print["Binary length ",IntegerLength[factors,2]]
Print["Product == n? ", Times@@factors ==n ]

The process isn’t always quick.
This n took over an hour to factor since all of the prime factors are large

n=1243240400068738272601385450801859082641634358209
factors=factor[n]
Print["Are prime? ",PrimeQ[factors]]
Print["Binary length ",IntegerLength[factors,2]]
Print["Product == n? ", Times@@factors ==n ]