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

Расширенный алгоритм Евклида позволяет не только найти наибольший общий делитель (НОД) двух целых чисел \(a\) и \(b\), но и определить коэффициенты \(\text{x}\) и \(\text{y}\) (коэффициенты Безу), такие что: $\(ax + by = \text{gcd}(a, b)\)$

Применение

Этот алгоритм критически важен в криптографии (например, для поиска обратного элемента по модулю в алгоритме RSA).

Реализации

Python

Итеративный подход:

def bezout(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) # Возвращает x, y и gcd(a, b)

Рекурсивный подход:

def bezout_recursive(a, b):
    if not b:
        return (1, 0, a)
    y, x, g = bezout_recursive(b, a % b)
    return (x, y - (a // b) * x, g)

Go

func ExtendedGCD(a, b int) (int, int, int) {
    if a == 0 {
        return 0, 1, b
    }
    x1, y1, gcd := ExtendedGCD(b%a, a)
    x := y1 - (b/a)*x1
    y := x1
    return x, y, gcd
}

C

#include <stdio.h>

void extended_gcd(int a, int b, int *x, int *y, int *gcd) {
    if (a == 0) {
        *x = 0; *y = 1; *gcd = b;
        return;
    }
    int x1, y1;
    extended_gcd(b % a, a, &x1, &y1, gcd);
    *x = y1 - (b / a) * x1;
    *y = x1;
}

int main() {
    int a = 30, b = 20, x, y, gcd;
    extended_gcd(a, b, &x, &y, &gcd);
    printf("gcd(%d, %d) = %d, x = %d, y = %d\\n", a, b, gcd, x, y);
    return 0;
}

---

Источник: Wikibooks