Over a million developers have joined DZone.
{{announcement.body}}
{{announcement.title}}

DZone's Guide to

# Pollard's Rho Heuristic

·
Free Resource

Comment (0)

Save
{{ articles[0].views | formatCount}} Views
```Pollard's rho heuristic is a method used to find a number's factors. This is faster than the classic brute-force, try every number until sqrt(n) method, but it's results are highly unpredictable.

This just prints the factors.

```
import sys
import random

def Euclid(a, b):
while b != 0:
r = a % b
a = b
b = r
return a

def PollardRho(n):
i = 1
x = random.randint(0, n - 1)
y = x
k = 2
tried = set()
while True:
i = i + 1
x = (x ** 2 - 1) % n
if x in tried:
return
d = Euclid(y - x, n)
if d != 1 and d != n:
print d # d is a factor. Print it.
if i == k:
y = x
k = 2 * k

def main(argv):
PollardRho(int(argv[0]))

if __name__ == "__main__":
main(sys.argv[1:])
``````
Topics:

Comment (0)

Save
{{ articles[0].views | formatCount}} Views

Opinions expressed by DZone contributors are their own.