Pollard's rho heuristic

scvalex (Alexandru Scvortov) — Sun, 24 Jun 2007 16:52:18 GMT

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:])

DZone Snippets: heuristic code

Pollard's rho heuristic