Rabin Miller Primality Theory

from hw3_4_util import mod_exp
from random import randrange

def rabin_miller(n, target=128):
	"""returns True if prob(^n' is prime) <= 2**(-'target')"""
	def calculate_t(n):
		n = n - 1
		t = 0
		while n % 2 == 0:
			n = n / 2
			t += 1
		return t
	if n % 2 == 0:
		return False
	t = calculate_t(n)
	s = (n - 1)/(2 ** t)
	n_tests = target / 2
	tried = set()
	if n_tests > n:
		raise Exception("n i s too small")
	for i in range(n_tests):
		while True:
			a = randrange(1, n)
			if a not in tried:
				break
		tried.add(a)
		if mod_exp(a, s, n) == 1:
			continue
		found = False
		for j in range(0, t):
			if mod_exp(a, 2**j*s, n) == (n - 1):
				found = True
				break
			if not found:
				return False

	return True