DZone Snippets is a public source code repository. Easily build up your personal collection of code snippets, categorize them with tags / keywords, and share them with the world

Snippets has posted 5883 posts at DZone. View Full User Profile

Pollard's Rho Heuristic

06.24.2007
| 6069 views |
  • submit to reddit
        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()
  tried.add(x)
  while True:
    i = i + 1
    x = (x ** 2 - 1) % n
    if x in tried:
      return
    tried.add(x)
    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:])
    

Comments

Snippets Manager replied on Wed, 2007/05/02 - 1:34pm

Actually, it'd be better if you used n = input("Enter a number: ") This would also parse the input into an integer. Anyway, I used parameter passing to specifiy n.

Snippets Manager replied on Wed, 2007/08/08 - 7:02am

OK, I've figured it out. I just needed an input statement to collect a value for n, like: n = raw_input("Enter a number: ")

Snippets Manager replied on Wed, 2007/08/08 - 7:02am

I'm completely new to Python. Would like to run this code, but I get this error: Traceback (most recent call last): File "C:/Python25/rho1.py", line 35, in main(sys.argv[1:]) File "C:/Python25/rho1.py", line 32, in main PollardRho(int(argv[0])) IndexError: list index out of range