FediPrimes/millerrabin.py

import random
import psimp as p



def MillerRabinRandom(n, k):
    """Carry out a Miller-Rabin test on n with k iterations, choosing random
    values for a.
    """
    r, d = p.trd(n-1)
    for iter in range(k):
        a = random.randint(2, n - 2)
        x = pow(a, d, n)
        if x == 1 or x == n - 1:
            continue
        compo = True
        for iterb in range(r - 1):
            x = pow(x, 2, n)
            if x == n - 1:
                compo = False
                break
        if compo:
            return True
    return False


def MillerRabin(n, base):
    """Carry out a Miller-Rabin test on n with a specified base.
    """
    r, d = p.trd(n-1)
    a = base
    x = pow(a, d, n)
    if x == 1 or x == n - 1:
        return False
    for iterb in range(r - 1):
        x = pow(x, 2, n)
        if x == n - 1:
            return False
    return True