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 / smallprimes.py < prev    next >
Encoding:
Python Source  |  1992-12-09  |  1.3 KB  |  83 lines
  1. # smallprimes.py Module for generating small primes
  2. # Copyright (c) 1992 by Jan-Hein B\"uhrman & Niels T. Ferguson
  3.  
  4. from math import sqrt
  5. import sys
  6.  
  7. initial_primes_bound = 1
  8.  
  9. def minbound( k ):
  10.     global bound, primes
  11.     if k <= bound:
  12.         return primes
  13.     if k > 2*bound:
  14.         # just a quick heuristic
  15.         bound = k
  16.         primes = None
  17.         primes = eratosthenes(k)
  18.     else:
  19.         for i in range(bound | 1, k, 2):
  20.             for d in primes:
  21.                 q, r = divmod(i, d)
  22.                 if q < d:
  23.                     primes.append(i)
  24.                     break
  25.                 if not r:
  26.                     break
  27.     return primes
  28.  
  29. def ge_find(lwb, upb, n):
  30.     if lwb == upb - 1:
  31.         return lwb
  32.     h = (upb + lwb) / 2
  33.     if primes[h] <= n:
  34.         return ge_find(h, upb, n)
  35.     else:
  36.         return ge_find(lwb, h, n)
  37.     
  38. def ge_index(n):
  39.     return ge_find(0, len(primes), n)
  40.     
  41. def eratosthenes(upb):
  42.     # list is from 0 to max (inclusive)
  43.     # in list, i maps to real number 2i+1
  44.     print 'Generating small primes list...',
  45.     sys.stdout.flush()
  46.     max = (upb-1) / 2
  47.     rootlimit = int(sqrt(float(max / 2)))
  48.     r = range(max+1)
  49.     r[0] = None
  50.     #print r
  51.     
  52.     for pi in r:
  53.         if pi:
  54.             #print  2*pi+1
  55.             if pi > rootlimit:
  56.                 break
  57.             i = 2 * (pi*pi + pi)
  58.             p = pi + pi + 1
  59.             while i <= max:
  60.                 r[i]= None
  61.                 i = i + p
  62.             #print r
  63.     res = [2]
  64.     for pi in r:
  65.         if pi:
  66.             res.append(pi + pi + 1)
  67.     print
  68.     return res
  69.     
  70.  
  71. primes = [2] #eratosthenes(initial_primes_bound)
  72. bound =  3    #initial_primes_bound
  73.  
  74.  
  75.         
  76.     
  77.  
  78.     
  79.     
  80.             
  81.                 
  82.         
  83.