import math

def bachet_bezout(a, b):
    """Does the Bachet-Bezout algorithm on a of b

    Args:
        a (uint): the number
        b (uint): the modulo

    Returns:
        uint: An array with the pgdc and the coefficients of bachet_bezout, [pgdc, u, v]
    """
    
    if (a == 0):
        return 0
    if (b == 0):
        return -1
    
    u = [1, 0]
    v = [0, 1]
    q = 1
    r = 1
    i = 2
    while (r > 0):
        q = a // b
        r = a % b
        
        u.append(u[i-2] - q * u[i-1])
        v.append(v[i-2] - q * v[i-1])
        
        a = b
        b = r
        i += 1 
    
    return a, u[i-2], v[i-2]

def inverse_modulaire(a, n):
    """Does the inverse modular of a by n, using Bachet-Bezout

    Args:
        a (uint): the number
        n (uint): the modulo

    Returns:
        uint: the inverse modular
    """
    
    return bachet_bezout(a, n)[1]

def exponentiation_rapide(a, exp, n):
    """Does the quick explanation of a pow x modulo n

    Args:
        a (uint): the number
        exp (uint): the exponent of the number
        n (uint): the modulo

    Returns:
        uint: The result of of the quick explanation
    """
    
    if (a == 0):
        return 0
    if (exp == 0):
        return 1
    
    r = 1
    b = a % n
    while (exp > 0):
        y = exp % 2
        r = (r * b**y) % n
        b = (b**2) % n
        exp = exp // 2
    
    return int(r)

def is_square(a):
    """Check if a number is a perfect square, using the Newton methode
    from : https://stackoverflow.com/questions/2489435/check-if-a-number-is-a-perfect-square 
        
    Args:
        a (uint): number checked

    Returns:
        bool: true if the number is a perfect square, otherwise flase
    """
    
    x = a // 2 # start value
    seen = set([x])
    
    while x * x != a:
        x = (x + (a // x)) // 2
        
        if x in seen: 
            return False
        
        seen.add(x)
        
    return True

def fermat_factorization(n):
    """Does the Fermat's factorization on n,
    n = a² - b² = (a + b) * (a - b) = p * q <=> b² = a² - n

    Args:
        n (uint): number used

    Returns:
        tuple of uint: the two coeficient a and b
    """
    
    a = math.ceil(math.sqrt(n))
    # a = 26262277040 - 10
    b = 0
    while(a <= n): # a cannot be greater than n, because : n = (a + b) * q > 0 => a <= n
        b2 = a**2 - n
        
        if (is_square(b2)):
            b = int(math.sqrt(b2))
            break
        
        a += 1
        
    if(a > n): print("The Fermat's factorization didn't work on n")
    
    return (a, b)

def decode_msg(M):
    """Decode a code UTF-8 in characters
    from : Niklaus Eggenberg

    Args:
        M (uint): code UTF-8

    Returns:
        strings: a strings containing characters UTF-8
    """
    
    return M.to_bytes((M.bit_length() + 7) // 8, "little").decode("utf-8")