home *** CD-ROM | disk | FTP | other *** search
/ OS/2 Shareware BBS: 10 Tools / 10-Tools.zip / pyth_os2.zip / python-1.0.2 / Demo / rsa / pollardrho.py < prev    next >
Text File  |  1992-12-09  |  871b  |  36 lines
  1. # Implementation of pollard-rho factorization method
  2. # Copyright (c) 1992 by Jan-Hein B\"uhrman & Niels T. Ferguson
  3. #
  4.  
  5. from mpz import *
  6.  
  7. def one_pollard_rho(n, start, c, maxiterations):
  8.     # print 'Pollard-Rho: n = ' + `n` + ', f(x) = x^2 + ' + `c`
  9.     x1, x2, r, prod, terms = start, (start*start + c) % n, 1, 1, 0
  10.     while terms < maxiterations:
  11.         for j in range(r):
  12.             x2, prod, terms = \
  13.                   (x2 * x2 + c) % n, \
  14.                   prod * ((x1 + n - x2) % n) % n, \
  15.                   terms + 1
  16.             if not (terms & 0x0f) :
  17.                 g = gcd(n, prod)
  18.                 if g > 1 :
  19.                     return [g]
  20.                 if g == 0 :
  21.                     return []
  22.                 prod = 1
  23.                 # print terms
  24.         x1, r = x2, r+r
  25.         for j in range(r):
  26.             x2 = (x2*x2 + c) % n
  27.     return []
  28.         
  29. def try_pollard_rho(n, maxiters, maxpolys, rf):
  30.     for i in range(maxpolys):
  31.         c = 1 + rf(n - 3)
  32.         r = one_pollard_rho(n, 1 + rf(n - 1), c, maxiters)
  33.         if len(r) > 0:
  34.             break
  35.     return r
  36.