primes

def miller_rabin_prime(n):
    """Implementation of the Miller-Rabin probalistic primality
    test. http://en.wikipedia.org/wiki/Miller-Rabin_primality_test"""
    if n % 2 and n > 3:
        # Odd number greater than 3
        k = 3 # Decide accuracy of our test

        #write n - 1 as 2s*d with d odd by factoring powers of 2 from n - 1
        n1, s, d = n - 1, 0, 0
        while True:
            if not n1 % 2:
                s += 1
                n1 //= 2
            else:
                d = n1
                break

        for _ in range(k):
            a = randint(2, n - 1)
            x = pow(a, d, n)

            if x not in (1, n - 1):
                for _ in range(s):
                    x = pow(x, 2, n)
                    if x == 1:
                        return False
                    elif x == n -1:
                        break
                else:
                    return False

        # n is probably prime
        return True
    else:
        # 2 or 3 are the only prime numbers that will fall in here.
        return n in (2, 3)