Never been to DZone Snippets before?

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

About this user

Alexandru Scvortov

« Newer Snippets
Older Snippets »
Showing 1-1 of 1 total  RSS 

Pollard's rho heuristic

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.

   1  
   2  import sys
   3  import random
   4  
   5  def Euclid(a, b):
   6    while b != 0:
   7      r = a % b
   8      a = b
   9      b = r
  10    return a
  11  
  12  def PollardRho(n):
  13    i = 1
  14    x = random.randint(0, n - 1)
  15    y = x
  16    k = 2
  17    tried = set()
  18    tried.add(x)
  19    while True:
  20      i = i + 1
  21      x = (x ** 2 - 1) % n
  22      if x in tried:
  23        return
  24      tried.add(x)
  25      d = Euclid(y - x, n)
  26      if d != 1 and d != n:
  27        print d # d is a factor. Print it.
  28      if i == k:
  29        y = x
  30        k = 2 * k
  31  
  32  def main(argv):
  33    PollardRho(int(argv[0]))
  34  
  35  if __name__ == "__main__":
  36      main(sys.argv[1:])
to python algorithm factorize pollard rho heuristic by scvalex on Jun 24, 2007 3 Comments
« Newer Snippets
Older Snippets »
Showing 1-1 of 1 total  RSS