Pollard's rho algorithm in Python

PollardRho.py

#!/usr/bin/env python

from fractions import gcd

def pollard_rho(n, seed=2, f=lambda x: x**2 + 1):
   x, y, d = seed, seed, 1
   while d == 1:
     x = f(x) % n
     y = f(f(y)) % n
     d = gcd((x - y) % n, n)
   if d != n:
      return d

def pollard_rho(n):
    if n%2 == 0: return 2
    if is_prime(n): return n # define it somehow, e.g. return False, then it infinite loops on primes
    while True:
        c = random.randint(2, n-1)
        f = lambda x: x**2 + c 
        x = y = 2 
        d = 1 
        while d == 1:
            x = f(x) % n 
            y = f(f(y)) % n 
            d = gcd((x - y) % n, n)
        if d != n: return d

It is well known that Pollard's rho algorithm can fail for some inputs. Simply change the f or seed values if it fails. e.g., pollard_rho(125, seed=3) returns the cofactor25 and pollard_rho(125, f=lambda x: x**2 - 1) returns 5.