from random import randint

def MillerRabin(n,b=2):
    """Teste de Miller-Rabin para n com base b
    retorna True se o teste for **conclusivo** de que n é composto, False nos outros casos"""
    if n%2 == 0:
        return True

    b %= n
    if b==0:
        return False

    m, k = n-1, 0    
    while m%2 == 0:
        k += 1
        m //= 2
    q = (n-1)//(2**k)

    i = 0
    r = pow(b,q,n)
    while i < k and r != n-1 and r != 1:
        r = pow(r,2,n)
        i += 1

    if i == k:
        return True
    if r == n-1:
        return False
    if r == 1 and i == 0:
        return False
    if r == 1 and i > 0:
        return True

def MillerRabinAleatorio(n,repetições=10):
    """Retorna True se o número é composto, False se é provavelmente primo"""
    bases_usadas = []
    contador = 0
    while contador < repetições:
        contador += 1
        b = randint(1,n-1)
        while b in bases_usadas:
            b = randint(1,n-1)
        if MillerRabin(n,b):
            return True
    return False