Pollard’s rho algorithm for factoring integers

rho.py

def gcd(a, b):
  while b:
    a, b = b, a%b
  return a

def f(x,n):
  return (x*x-1)%n

def rho(n):
  x = 2
  y = 2
  d = 1
  while d==1:
    print x,y,d
    x = f(x,n)
    y = f(f(y,n),n)
    d = gcd(abs(x-y),n)
  
  if d==n:
    return False
  return d

print rho(455459)

or def f(x,n): return (x*x+1)%n