stc/exp/raphus/primes.py

   1 """
   2 From http://www.4dsolutions.net/cgi-bin/py2html.cgi?script=/ocn/python/primes.py
   3 """
   4
   5 import random
   6
   7 def bigppr(bits=256):
   8     """
   9     Randomly generate a probable prime with a given
  10     number of hex digits
  11     """
  12
  13     candidate = random.getrandbits(bits)
  14
  15     if candidate&1==0:
  16         candidate += 1
  17     prob = 0
  18     while 1:
  19         prob=pptest(candidate)
  20         if prob>0: break
  21         else: candidate += 2
  22     return candidate
  23
  24 def pptest(n):
  25     """
  26     Simple implementation of Miller-Rabin test for
  27     determining probable primehood.
  28     """
  29     bases  = [random.randrange(2,50000) for x in range(90)]
  30
  31     # if any of the primes is a factor, we're done
  32
  33     if n<=1: return 0
  34
  35     for b in bases:
  36         if n%b==0: return 0
  37
  38     tests,s  = 0L,0
  39     m        = n-1
  40
  41     # turning (n-1) into (2**s) * m
  42
  43     while not m&1:  # while m is even
  44
  45         m >>= 1
  46         s += 1
  47     for b in bases:
  48         tests += 1
  49         isprob = algP(m,s,b,n)
  50         if not isprob: break
  51
  52     if isprob: return (1-(1./(4**tests)))
  53     else:      return 0
  54
  55 def algP(m,s,b,n):
  56     """
  57     based on Algorithm P in Donald Knuth's 'Art of
  58     Computer Programming' v.2 pg. 395
  59     """
  60     result = 0
  61     y = pow(b,m,n)
  62     for j in range(s):
  63        if (y==1 and j==0) or (y==n-1):
  64           result = 1
  65           break
  66        y = pow(y,2,n)
  67     return result