Modular Exponential and Miller Rabin Algorithms

millerrabin.py

# Please note, this is not my work, but the work of a fellow redditer.
# I am simply placing it here for future use.

def MillerRabin(n,k=5):
'''
Performs the Miller-Rabin primality test on n to an error bound of 4^-k 
(i.e. performs the test k times). True indicates a probable prime while a 
false result indicates a definite composite number.
Inputs:
n - Number to be tested for primality
k - Error bounding parameter
Outputs:
True if n passes k rounds of the Miller-Rabin test, False otherwise
'''
import random
def innerTest(x):
    for r in xrange(2,n-1):
        x = modular_exponent(x,2,n)
        if x == 1:
            return False
        if x == n - 1:
            return True
    return False
ks = []
d = 0
s = n-1
# Write n-1 as 2^d * s
while not s & 1:
    d += 1
    s >>= 1
while len(ks) < k:
    a = random.randint(2,n-2)
    if a in ks:
        continue
    ks.append(a)
    x = modular_exponent(a,s,n)
    if x == 1 or x == n - 1:
        continue
    if innerTest(x):
        continue
    return False
return True

modexponent.py

# Please note, this is not my work, but the work of a fellow redditer.
# I am simply placing it here for future use.

def modular_exponent(base,exponent, mod):
    n = exponent
    x = 1
    power = base % mod
    while n:
        if n & 1:
            x *= power
            x %= mod
            n -= 1
        power = (power ** 2) % mod
        n /= 2
    return x