Skip to content

Instantly share code, notes, and snippets.

@thomdixon
Last active March 27, 2021 22:05
Show Gist options
  • Save thomdixon/dd1e280681f16535fbf1 to your computer and use it in GitHub Desktop.
Save thomdixon/dd1e280681f16535fbf1 to your computer and use it in GitHub Desktop.
Pollard's rho algorithm in Python
#!/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
@Motherboard
Copy link

This fails for some numbers... e.g. pollard_rho(125) returns None

@TheJonny
Copy link

TheJonny commented Jul 1, 2017

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

@thomdixon
Copy link
Author

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.

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