Instantly share code, notes, and snippets.

# 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.
Pollard's rho algorithm in Python
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters. Learn more about bidirectional Unicode characters
 #!/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 commented May 29, 2017

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

### TheJonny commented Jul 1, 2017 • edited Loading

``````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 commented Dec 21, 2017

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 cofactor`25` and `pollard_rho(125, f=lambda x: x**2 - 1)` returns `5`.

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