Что такое алгоритм Евклида?

Алгоритм Евклида (Euclidean algorithm) — это эффективный метод вычисления наибольшего общего делителя (НОД) двух натуральных (или целых) чисел. Описанный около 300 г. до н.э. древнегреческим математиком Евклидом в книге VII его математического трактата «Начала» (Elements), он широко известен как один из «древнейших алгоритмов человечества».

Самый простой способ найти НОД — это найти разложение на простые множители обоих чисел и перемножить общие простые множители. Однако по мере роста чисел вычислительная сложность самого разложения на простые множители становится огромной, что затрудняет решение этой задачи в реальные сроки. С другой стороны, используя алгоритм Евклида, можно вычислить НОД чрезвычайно быстро, даже для гигантских чисел, состоящих из тысяч цифр.

Основная теорема и механика

Пусть $\gcd(a, b)$ — наибольший общий делитель двух натуральных чисел $a$ и $b$ (где $a \ge b$). Алгоритм Евклида основан на следующей простой теореме:

$$ a = bq + r \implies \gcd(a, b) = \gcd(b, r) $$

Другими словами, он использует свойство: «Когда $a$ делится на $b$ с частным $q$ и остатком $r$ , НОД чисел $a$ и $b$ равен НОД чисел $b$ и $r$ ».

Доказательство теоремы

Почему выполняется $\gcd(a, b) = \gcd(b, r)$ ? Давайте кратко докажем это.

Пусть $d$ — любой общий делитель чисел $a$ и $b$ . Тогда мы можем выразить $a = md$ и $b = nd$ (где $m, n$ — целые числа).
Из $a = bq + r$ мы получаем $r = a - bq$ .
Подстановка выражений в это дает $r = md - (nd)q = d(m - nq)$ .
Поскольку $m - nq$ — целое число, $d$ также является делителем числа $r$ . Следовательно, любой общий делитель $d$ чисел $a$ и $b$ также является общим делителем чисел $b$ и $r$ .
И наоборот, пусть $e$ — общий делитель чисел $b$ и $r$ , который можно записать как $b = k e$ и $r = l e$ .
$a = bq + r = (k e)q + l e = e(kq + l)$ , что делает $e$ делителем числа $a$ . Таким образом, любой общий делитель $e$ чисел $b$ и $r$ также является общим делителем чисел $a$ и $b$ .
Следовательно, множество общих делителей $\{a, b\}$ полностью совпадает с множеством общих делителей $\{b, r\}$ , и их максимальные значения (наибольшие общие делители) также равны. $\blacksquare$

Блок-схема алгоритма

Используя это свойство, алгоритм Евклида многократно выполняет деление до тех пор, пока остаток не станет равным $0$ .

  flowchart TD
    Start["Начало: Ввод a, b"] --> Check{"b == 0 ?"}
    Check -- "Yes" --> End["НОД равен a"]
    Check -- "No" --> Calc["r = a % b"]
    Calc --> Update["a = b, b = r"]
    Update --> Check

Пример пошагового вычисления

В качестве примера найдем наибольший общий делитель чисел $a = 1071$ и $b = 1029$ .

$1071 \div 1029 = 1 \cdots 42$ (обновление до $a=1029, b=42$)
$1029 \div 42 = 24 \cdots 21$ (обновление до $a=42, b=21$)
$42 \div 21 = 2 \cdots 0$ (завершение, так как остаток равен $0$)

Последний оставшийся делитель, $21$ , и есть наибольший общий делитель чисел $1071$ и $1029$ .

Программная реализация

Реализация на Python

В Python есть методы, использующие рекурсивные функции, и методы, использующие циклы while . Метод цикла быстрее, поскольку в нем нет накладных расходов на вызовы функций.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
def gcd_loop(a: int, b: int) -> int:
    """
    Реализация алгоритма Евклида с использованием цикла
    """
    while b != 0:
        a, b = b, a % b
    return a

def gcd_recursive(a: int, b: int) -> int:
    """
    Реализация алгоритма Евклида с использованием рекурсии
    """
    if b == 0:
        return a
    return gcd_recursive(b, a % b)

print(gcd_loop(1071, 1029))  # Вывод: 21

Реализация на C++

В C++17 и более поздних версиях функция std::gcd стандартизирована в заголовке <numeric> , но если бы вы реализовывали ее сами, она выглядела бы так:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
#include <iostream>

// Функция для вычисления наибольшего общего делителя (рекурсивная версия)
int gcd(int a, int b) {
    if (b == 0) {
        return a;
    }
    return gcd(b, a % b);
}

int main() {
    std::cout << "GCD: " << gcd(1071, 1029) << std::endl; // Вывод: 21
    return 0;
}

Временная сложность и теорема Ламе

Насколько быстр алгоритм Евклида? Что касается его вычислительной сложности, широко известна теорема Ламе (Lamé’s theorem), доказанная французским математиком Габриэлем Ламе в 1844 году.

Теорема Ламе Количество шагов деления, необходимых для применения алгоритма Евклида к двум натуральным числам $a, b$ ($a > b$), не превышает $5$ -кратного количества цифр в десятичном представлении числа $b$ .

В результате временная сложность алгоритма составляет $O(\log(\min(a, b)))$ .

Худший сценарий (при котором количество делений максимально) возникает, когда заданы два последовательных числа Фибоначчи. Например, в процессе нахождения НОД чисел $F_{n+2}$ и $F_{n+1}$ частное всегда равно $1$ , непрерывно переходя к меньшим числам Фибоначчи.

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

Расширение алгоритма для нахождения целых чисел $x, y$ , которые удовлетворяют следующему соотношению Безу (Bézout’s identity) в дополнение к нахождению наибольшего общего делителя, называется расширенным алгоритмом Евклида (Extended Euclidean algorithm).

$$ ax + by = \gcd(a, b) $$

Реализация расширенного алгоритма Евклида

В процессе возврата из рекурсивных вызовов мы выполняем обратные вычисления для расчета коэффициентов $x$ и $y$ .

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
def ext_gcd(a: int, b: int) -> tuple[int, int, int]:
    """
    Функция, возвращающая (gcd, x, y), удовлетворяющие ax + by = gcd(a, b)
    """
    if b == 0:
        return a, 1, 0
    
    g, x1, y1 = ext_gcd(b, a % b)
    x = y1
    y = x1 - (a // b) * y1
    
    return g, x, y

g, x, y = ext_gcd(111, 30)
print(f"gcd: {g}, x: {x}, y: {y}")
# Вывод: gcd: 3, x: 3, y: -11
# Проверка: 111 * 3 + 30 * (-11) = 333 - 330 = 3

Применение в современном обществе (Криптография RSA и др.)

Расширенный алгоритм Евклида — это не просто математическая головоломка, а важнейшая технология, поддерживающая современное интернет-общество. Ярким примером является криптография RSA . В процессе генерации ключей шифрования RSA необходимо найти закрытый ключ $d$ (модульное обратное), который удовлетворяет условию $e d \equiv 1 \pmod{\phi(N)}$ для заданного числа $e$ и функции Эйлера $\phi(N)$ . Поскольку это можно преобразовать к виду $ed + k\phi(N) = 1$ , мы можем использовать расширенный алгоритм Евклида для вычисления $d$ с чрезвычайно высокой скоростью.

Заключение

Несмотря на то, что алгоритм Евклида был открыт в далеком прошлом в эпоху до нашей эры, он продолжает оставаться основой современной информатики благодаря своей оптимизированной логике и высокой вычислительной эффективности. Хотя это часто первая тема, с которой сталкиваются при изучении алгоритмов, за ней скрывается огромное богатство математической красоты и практической пользы.