Pollard’s rho algorithm for fast factorization in Python

Algorithms to factor numbers are useful in many areas but especially encryption.

The most obvious method of factoring a number (by repeated division) is a very slow process (indeed the security of modern encryption depends on this process being slow)

Pollard’s Rho is a very fast, probabilistic method that can be used to find factors much faster than the standard method.

My implementation, based on the psudocode of page 976 in “Introduction to Algorithms, third edition” is as follows:



from random import randint
from fractions import gcd
from math import *

def PollardRho(n):
    i=0;
    xi=randint(0,n-1);
    k=2
    y=xi
    while i< n:
        i=i+1
        xi=((xi^2)-1)%n
        d=gcd(y-xi,n)
        if d!=1 and d!=n:
            print d;
        if i==k:
            y=xi
            k=2*k

PollardRho(1200)

The first two lines initialize i to 1 and x1 to a random integer between 0 and n-1

The code xi=((xi^2)-1)%n is the recurrence:   x_i=(x^2_{i-1} -1) mod n which produces the x_i value of the infinite sequence.

Most psudocode has this running forever with a while(true) so I modified it to only try n times. This is probably overkill because if n is composite we can expect this method to discover enough divisors to factor n completely after about n^(1/4) updates.