Cryptohack Lab. Extended GCD

Для решения лабы необходимо найти такие u и v, при данных p = 26513 и q = 32321, что выполняется равенство:

p * u + q * v = gcd(p, q)

В качестве ответа используется наименьший из u и v.

Sulution

Алгоритм Евклида мы уже рассматривали. Пришло время расширенного алгоритма Евклида.

Расширенный алгоритм Евклида

Аналогично алгоритму Евклида находит НОД двух чисел p и q, но в дополнение находит коэффициенты x и y для уравнения Безу:

p * u + q * v = gcd(p, q)

Напишу его реализацию на python:

def extended_gcd(p: int, q: int):
    if q == 0:
        return p, 1, 0
    gcd, x1, y1 = extended_gcd(q, p % q)
    return gcd, y1, x1 - (p // q) * y1


p = 26513
q = 32321
g, x, y = extended_gcd(p, q)
print(f"gcd = {g}, x = {x}, y = {y}")

Запущу код:

gcd = 1, x = 10245, y = -8404

Значит ответом будет -8404.