Skip to content

Instantly share code, notes, and snippets.

@thomdixon

thomdixon/PollardRho.py

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.
Download ZIP
Pollard's rho algorithm in Python
Raw
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
@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