March 9, 2023
Math 302 Cryptography
Spring 2023

T. Ratliff, Wheaton College
ratliff_thomas@wheatoncollege.edu

Pollard’s ρ  for factoring

This function will apply the algorithm discussed in class to find one factor of n. 
I hope it’s fairly self-explanatory.

pFactor[n_]:=Module[{x=1,y=1,g=1,i=1, f},
f[x_]:=Mod[x^2+1,n];

While[g==1, 
x=f[x];
y=f[f[y]];
g=GCD[Abs[x-y],n];
(*Print[i," ", x," ", y, " ", g];  You can uncomment this to see each stage in the sequences*)
i++
];
Print["Collision at i = ",i-1,", x = ",x,", y = ",y,", g = ", g]
]

pFactor[2465]