Want more features on Pastebin? Sign Up, it's FREE!
Guest

Untitled

By: a guest on May 9th, 2010  |  syntax: Python  |  size: 1.01 KB  |  views: 116  |  expires: Never
download  |  raw  |  embed  |  report abuse  |  print
Text below is selected. Please press Ctrl+C to copy to your clipboard. (⌘+C on Mac)
  1. def split(n):
  2.     """
  3.    Splits n into 2^s * r for an odd r; used in Miller-Rabin test for primality.
  4.    """
  5.     s = 0
  6.     while (n > 0) and (n % 2 == 0):
  7.         s += 1
  8.         n >>= 1
  9.     return (s,n)
  10.  
  11.  
  12. def P(a,r,s,n):
  13.     """
  14.    Condition for primality in Miller-Rabin test.
  15.    """
  16.     if pow(a, r, n) == 1:
  17.         return True
  18.     elif (n - 1) in [pow(a, r*(2**j), n) for j in range(s)]:
  19.         return True
  20.     else:
  21.         return False
  22.  
  23.  
  24. def miller_rabin(n, t):
  25.     """
  26.    Tests n for primality t times.
  27.    """
  28.     (s, r) = split(n - 1)
  29.     for i in range(t):
  30.         a = random.randint(2, n-1)
  31.         if not P(a, r, s, n):
  32.             return False
  33.     return True
  34.  
  35.  
  36. def m_r_prime_gen(n):
  37.     """
  38.    Generates an odd that passes the Miller Rabin primality test for t = 50 in
  39.    the interval [10^n, 10^(n + 1)]
  40.    """
  41.     p = 0
  42.     while (p == 0):
  43.         p = random.randrange(pow(10,n) + 1, pow(10, n + 1), 2)
  44.         if not miller_rabing(p, 50):
  45.             p = 0
  46.     return p
clone this paste RAW Paste Data