Miller-Rabin primality test (deterministic version) in Python

prime_test.py

''' partly stolen from http://en.literateprograms.org/Miller-Rabin_primality_test_(Python) '''

def miller_rabin_pass(a, s, d, n):
    a_to_power = pow(a, d, n)
    if a_to_power == 1:
        return True
    for i in xrange(s-1):
        if a_to_power == n - 1:
            return True
        a_to_power = (a_to_power * a_to_power) % n
    return a_to_power == n - 1

def miller_rabin(n):
    '''if n < 1,373,653, it is enough to test a = 2 and 3;
    if n < 9,080,191, it is enough to test a = 31 and 73;
    if n < 4,759,123,141, it is enough to test a = 2, 7, and 61;
    if n < 2,152,302,898,747, it is enough to test a = 2, 3, 5, 7, and 11;'''
    if n < 2: return False
    if n in {2, 7, 61}: return True
    d = n - 1
    s = 0
    while d % 2 == 0:
        d >>= 1
        s += 1
    for a in {2,7,61}:
        if not miller_rabin_pass(a, s, d, n):
            return False
    return True

no se como lo hicistes, lo vistes o descubistes, pero funciona estupendo