Lucas Lehmer Primality Test

Lucas Lehmer Primality Test

def lucasLehmerTest(p): #checks if 2^p - 1 is a prime (also called a mersenne prime)
    if p % 2 == 0 and not isPrime(p): return False 
	s = 4
	M = (1 << p) - 1
	for _ in xrange(p - 2):
		s = ((s * s) - 2) % M
	return s == 0

def isPrime(n):
	if n <= 3 or n % 2 == 0 or n % 3 == 0: return n == 2 or n == 3 
	for i in xrange(5, int(n**0.5)+1, 6):
		if n % i == 0 or n % (i + 2) == 0:
			return False
	return True