Pollard’s ρ Method for factoring
Math 302 Advanced Cryptography
March 18, 2019

T. Ratliff, Wheaton College
ratliff_thomas@wheatoncollege.edu

Define the functions - This is a quick and dirty implementation of Exercise 5.44

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

pollardsRho[n_]:= Module[{x=0,y=0,g=1,i=0},
If[PrimeQ[n]==True, Print[n," is prime"]; 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];
]

mrWitness[a_,n_]:=Module[{temp=n-1,k=0,q,aq,i},
While[Mod[temp,2]==0,temp=temp/2;k++];
q=(n-1)/2^k;
aq=PowerMod[a,q,n];

If[Mod[aq,n]==1,Return[False]];

i=0;
While[i<k,If[Mod[aq+1,n]==0,Return[False]];
aq=Mod[aq^2,n];
i++];
Return[True]
]

mrPrimeTest[n_,r_]:=Module[{a,i},
If[n==2,Return[True]];
If[EvenQ[n],Return[False]];

For[i=1,i≤r,i++,
a=RandomInteger[{1,n-1}];

If[GCD[a,n]>1,Return[False]];

If[mrWitness[a,n]==True,Return[False]]
];

Return[True]];

Factoring n=372011

First check that n is composite

n=372011
mrWitness[2,n]

Now let’s call pollardsRho[ ] on n, n/g_1, n/g_2, . . . . and check if each g_i is prime or if we need to factor them

pollardsRho[n]

mrPrimeTest[ ]

Let’s try a bigger value

n=RandomInteger[{2^159, 2^160}]

Check that n is composite

mrWitness[2,n]