Math 640:348 Prof. Kontorovich
Spring 2015, 5/6 review session 2

We review factoring by the Pollard rho method

Take a composite integer, say

p=Prime[13];
q=Prime[20];
n=p q

We will iterate a “random” function, like

f[x_]:=Mod[x^2+5, n];

and test when the tortoise has caught the hare by checking if gcd(y_i-x_i , n) > 1. We begin with

i=0; x=1;y=1;

and apply f

i=1;
{x,y}={f[x],f[f[y]]}

What is a “collision” now? It’s when x=y(mod p) (or mod q). But we don’t know what p and q are! So we test whether

GCD[x-y,n]

is non-trivial.

Now iterate

i++;
{x,y}={f[x],f[f[y]]}
GCD[x-y,n]≠1

i++;
{x,y}={f[x],f[f[y]]}
GCD[x-y,n]≠1

i++;
{x,y}={f[x],f[f[y]]}
GCD[x-y,n]≠1

i++;
{x,y}={f[x],f[f[y]]}
GCD[x-y,n]≠1

Aha! We found a collision. It’s not a collision mod n, since x≠y, but it is a collision mod either p or q. Indeed,

GCD[x-y,n]

So 71 is a factor of n, the other one being

n/71

Note that, had we known p, q from the beginning, this really would be a genuine collision:

Mod[{x,y},p]

Not mod p

Mod[{x,y},q]

But yes mod q; that’s the real collision. But since we shouldn’t know p or q to start, the way to test for this collision is as above, namely, by checking whether gcd[x-y,n]>1.

How long did we expect to run the algorithm? Roughly n^1/4 =

n^(1/4)//N

steps, and we halted in

i

steps. Pollard rho wins again.