Miller-Rabin.py

from toolkit import *


def Miller_Rabin_test(n: int) -> bool:
    # sieve out the even number
    if not (n & 1):
        return False

    s, t = 0, n - 1
    while not t & 1:  # stop when end is odd
        t = divmod(t, 2)[0]
        s += 1
    # print(s, t)
    k = 30
    while k:
        b = 2
        while gcd(b, n) != 1:
            b = randint(1)
            # generates b that (b, n) = 1
            b = pow(b, t, n)
            if abs(b) == 1:
                return True
            s -= 1
            canpass = False
            while s > 0:
                # print(k)
                b = pow(b, 2, n)
                if b == n - 1:
                    canpass = True
                    break
                s -= 1
            if not canpass:
                return False
        k -= 1
    return True


def Miller_Rabin_test_by_b(n: int, b: int) -> bool:
    if not (n & 1):
        return False
    # sieve out the even number
    s, t = 0, n - 1
    while not t & 1:  # stop when end is odd
        t = divmod(t, 2)[0]
        s += 1
    # print(s, t)
    b = pow(b, t, n)
    if abs(b) == 1:
        return True
    s -= 1
    while s > 0:
        b = pow(b, 2, n)
        if b == n - 1:
            return True
        s -= 1
    return False


if __name__ == '__main__':
    n = randint(4)
    while len(str(n)) < 10:
        n = randint(4)
    found = Miller_Rabin_test(n)
    while not found:
        n = randint(4)
        while len(str(n)) < 10:
            n = randint(4)
        found = Miller_Rabin_test(n)
    print('Prime number generated by Miller-Rabin test is', n)
    nlst = [17 * 19, 23 * 47]
    for n in nlst:
        blst = [i for i in range(n)]
        # print(blst)
        for b in blst:
            if Miller_Rabin_test_by_b(n, b):
                print(n, 'is a STRONG pseudoprime of base', b)