test_prime_in_miller_rabin

from typing import Tuple
import random

def is_prime_of_miller_rabin_test(n: int, trials_time: int = 5) -> bool:

    def test_prime_in_100(n: int) -> bool:
        prime_list = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37,
                      41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97]
        for i in prime_list:
            if n % i == 0:
                return True
        else:
            return False

    def convert_n_to_sd(n: int) -> Tuple[int, int]:
        # n-1 convert to (2^s)*d
        s = 0
        d = n - 1
        while True:
            quotient, remainder = divmod(d, 2)
            if remainder == 1:
                return s, d
            s += 1
            d = quotient

    def test_prime_in_miller_rabin(a: int, d: int, n: int, s: int):
        if pow(a, d, n) == 1:
            return False
        for i in range(s):
            if pow(a, 2**i*d, n) == n-1:
                return False
        return True

    if test_prime_in_100(n):
        return False
    s, d = convert_n_to_sd(n)
    for _ in range(trials_time):
        a = random.randint(100, n)
        if test_prime_in_miller_rabin(a, d, n, s):
            return False
    return True


def get_prime(lens: int = 30):
    while True:
        prime = random.randint(10**(lens-1), 10**lens-1)
        if len(str(prime)) != lens:
            continue
        elif prime & 1 == 0:
            prime += 1
        if is_prime_of_miller_rabin_test(prime):
            return prime

if __name__ == '__main__':
    print(get_prime(200))