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 / rabin_miller.py < prev    next >
Text File  |  1992-12-09  |  831b  |  34 lines
  1. # Implementation of the Rabin-Miller test
  2. # Copyright (c) 1992 by Jan-Hein B\"uhrman & Niels T. Ferguson
  3.  
  4.  
  5. from assert import assert
  6. from mpz import *
  7. from qualify import log2_pprime_prob
  8.  
  9. def miller_test(base, n):
  10.     # first we check that we have an odd number larger then 10
  11.     # print 'Rabin-Miller test, n = ' + `n` + ', base = ' + `base`
  12.     assert( (n & 1 and n > 10) )
  13.     k, q = 0, n-1
  14.     while (q & 1) == 0:
  15.         k, q = k+1, q >> 1
  16.     # print `k`, `q`
  17.     # print `base`, `q`, `n`
  18.     t, pt = powm(base, q, n), 0
  19.     if t == 1:
  20.         # test to this base return 'probably prime'
  21.         return []
  22.     nm1 = n-1
  23.     while k > 0 and t != nm1:
  24.         tp, t, k = t, (t*t) % n, k-1
  25.     if k > 0 and t == nm1:
  26.         return []
  27.     f = gcd((t - pt) % n, n)
  28.     if 1 < f < n:
  29.         print 'MILLER TEST FOUND FACTOR: n = ' + `n` + \
  30.               '; base = ' + `base` 
  31.         return [f, n/f]
  32.     else:
  33.         return [n]
  34.