def euclides_v3(a, b, printa= False):
    dividendo = abs(a)
    divisor = abs(b)
    if printa:
        i = 0
    while True:
        resto = dividendo % divisor
        if printa:
            i += 1
            print(f'{i}. {dividendo = }, {divisor = }, {resto = }')
        if resto == 0:
            return divisor
        # else:
        dividendo = divisor
        divisor = resto

def Fermat (n, base):
    if euclides_v3(n, base) != 1:
        return "inconclusivo"
    res = pow(base, n-1, n)
    if res != 1:
        return f"{n} é composto"
    else:
        return "inconclusivo"


def busca_ingênua(n, x=None):
    """
    Buscando provar que n é composto
    chutando x e vendo se
    x não é ± 1 mod n
    mas x² é 1 mod n
    """
    from random import randrange
    if x is None:
        x = randrange(2, n-2 +1)  # x é um número aleatório de 2 até n-2
    if pow(x, 2, n) == 1:
        return f'{n} é composto! Testemunha: {x}'
    else:
        return "Inconclusivo"

def Miller_Rabin_cima_para_baixo(n, base=None):
    """
    Retorna um par de booleano e string
    O booleano indica se o número pode ser concluído como composto
    e a string é a justificativa
    """
    from random import randrange
    if n%2 == 0:
        if n == 2:
            return False, 'É 2'
        else:
            return True, 'Par maior que 2'
    if base is None:
        base = randrange(2, n-1)
        print(f'{base = }')
    expoente = n-1
    início = pow(base, expoente, n)
    if início != 1:
        return True, 'Composto! PTF'
    while expoente % 2 == 0:
        candidato = pow(base, expoente//2, n)
        if candidato != 1 and candidato != n-1:
            return True, f'Composto! Testemunha: {candidato}'
        if candidato == n-1:
            return False, 'Inconclusivo'
        expoente = expoente//2
    return False, 'Inconclusivo'

def Miller_Rabin_repetido(n, repetições=10):
    for i in range(10):
        resultado, justificativa = Miller_Rabin_cima_para_baixo(n)
        if resultado:
            return True, justificativa
    return False, 'Provavelmente primo!'
