def split(n):
"""
Splits n into 2^s * r for an odd r; used in Miller-Rabin test for primality.
"""
s = 0
while (n > 0) and (n % 2 == 0):
s += 1
n >>= 1
return (s,n)
def P(a,r,s,n):
"""
Condition for primality in Miller-Rabin test.
"""
if pow(a, r, n) == 1:
return True
elif (n - 1) in [pow(a, r*(2**j), n) for j in range(s)]:
return True
else:
return False
def miller_rabin(n, t):
"""
Tests n for primality t times.
"""
(s, r) = split(n - 1)
for i in range(t):
a = random.randint(2, n-1)
if not P(a, r, s, n):
return False
return True
def m_r_prime_gen(n):
"""
Generates an odd that passes the Miller Rabin primality test for t = 50 in
the interval [10^n, 10^(n + 1)]
"""
p = 0
while (p == 0):
p = random.randrange(pow(10,n) + 1, pow(10, n + 1), 2)
if not miller_rabing(p, 50):
p = 0
return p