#1. Miller-Rabin algorithm. It will work for numbers of arbitrary size.

import random

def miller_rabin(n, k=5) -> bool:
    if n % 2 == 0 or n <= 2:
        return False
    s, t = step1(n)
    for _ in range(k):
        a: int = random.randint(2, n - 2) 
        x: int = pow(a, t, n)
        if x == 1:
            continue
        for _ in range(s):
            y: int = pow(x, 2, n)
            if y == 1 and x != 1 and x != n - 1:
                return False
            x = y
        if y != 1:
            return False
    return True



def step1(n) -> tuple[int, int]:
    t: int = n - 1
    s = 0
    while t % 2 == 0:
        t //= 2
        s += 1
    return s, t

def main():
    print(miller_rabin(13))
    print(miller_rabin(15))
    print(miller_rabin(2**1279 - 1))
        
if __name__ == '__main__':
    main()