Check out the Pastebin Gadgets Shop. We have thousands of fun, geeky & affordable gadgets on sale :-)Want more features on Pastebin? Sign Up, it's FREE!

# Untitled

By: a guest on May 9th, 2010  |  syntax: Python  |  size: 1.01 KB  |  views: 125  |  expires: Never
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
Top