"""
Нахождение обратного по модулю
"""
def egcd(a, b):
    if a == 0:
        return (b, 0, 1)
    else:
        g, y, x = egcd(b % a, a)
        return (g, x - (b // a) * y, y)
def modinv(a, m):
    g, x, y = egcd(a, m)
    if g != 1:
        raise Exception('modular inverse does not exist')
    else:
        return x % m

"""
Генерирования сообщение
"""
def id_generator(size=6, chars=string.ascii_lowercase):
    return ''.join(random.choice(chars) for _ in range(size))

"""
Конвертирование int <---> bytes
"""
def int_to_bytes(x):
    return x.to_bytes((x.bit_length() + 7) // 8, 'big')

def int_from_bytes(xbytes):
    return int.from_bytes(xbytes, 'big')

'''
Euclidean algorithm.
Returns  x, y, gcd(a, b):
ax + by = gcd(a, b).
'''
def euclidean(a, b):
    x, xx, y, yy = 1, 0, 0, 1
    while b:
        q = a // b
        a, b = b, a % b
        x, xx = xx, x - xx*q
        y, yy = yy, y - yy*q
    return (x, y, a)



"""
Вычисление квадратного корня
"""
def isqrt(x):
    """
    Вычисляет квадратный корень любого сколь угожно большего целого числа

    Функция возвращает кортеж (a, r), где a **  2 + r = x
    a - наибольшее целое такое, что a**2 <= x, а r - это остаток
    Если x - идельный квадрат, то остаток равен нулю
    """

    N = 0   # Исходные данные на текущей итерации
    a = 0   # Решение на текущей итерации

    # Число будет обработано начиная с MSB, 2 бита за раз
    # MSB - Most significant bit, старший бит, наиболее значимый бит
    L = x.bit_length()
    L += (L % 2)          # Округление до следующего четного

    for i in range(L, -1, -1):

        # Следующие два бита
        n = (x >> (2*i)) & 0b11

        # Проверка на то, можем ли мы уменьшить остаток
        if ((N - a*a) << 2) + n >= (a << 2) + 1:
            b = 1
        else:
            b = 0

        a = (a << 1) | b   # Добавляем следующий бит решения
        N = (N << 2) | n   # Добавляем следующий бит исходных данных

    return a, N-a*a