Some number theory (calculation of a^p % n and primality testing)

number_theory.py

from random import randrange

fermat_test = lambda p: pow(randrange(2,p-1), p-1, p) ==  1
euclid_gcd = lambda a,b : max([a,b]) if min([a,b]) == 0 else euclid_gcd(min([a,b]), max([a,b]) % min([a,b]))

def miller_rabin(p, k =20):
	r = 0
	d = p-1
	while d % 2 == 0:
		d //= 2
		r += 1

	for j in range (k):	
		a = randrange(2,p-2)	
		x = pow(a, d, p)
	
		if x in [1, p-1]:
			continue
			
		for i in range(r-1):
			x = pow (x, 2, p)
			if x == 1:
				return False
			elif x == p-1:
				continue
		return False	
		
	return True
	
def fastmodpower(a,n,p):
	N = n
	r = 1
	while N>0:
		if N% 2 == 1:
			r = r * a % p
		N //= 2
		a = a*a%p
	print r
	
fastmodpower(2,3, 5)		
			
def fastpower(a,n):
	
	if n == 0:
		return 1
	elif n == 1:
		return a
	else:
		x = fastpower(a, n//2)
		if n % 2 == 0:
			return x*x
		else:
			return a*x*x			

print fastpower(5,4)

def fastmodpower2(a,n,p):
	
	if n == 0:
		return 1
	elif n == 1:
		return a
	else:
		x = fastpower(a, n//2) % p
		if n % 2 == 0:
			return x*x % p
		else:
			return a*x*x % p
			
print fastmodpower2(5,4,624)