Skip to content

Instantly share code, notes, and snippets.

@silveira
Created April 22, 2014 17:33
Show Gist options
  • Save silveira/11187839 to your computer and use it in GitHub Desktop.
Save silveira/11187839 to your computer and use it in GitHub Desktop.
Pollard’s rho algorithm for factoring integers
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)
@silveira
Copy link
Author

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

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment