Алгоритм Евклида: код, которому две тысячи лет

Этому алгоритму больше двух тысяч лет, и он по-прежнему быстрее, чем всё, что вы придумаете для НОД с ходу.

Евклид записал его около 300 года до н. э. в «Началах» — и с тех пор почти ничего не пришлось менять.

Зачем вообще нужен НОД

Наибольший общий делитель двух чисел — это самое большое число, на которое делятся оба без остатка. НОД(12, 18) = 6. Звучит как школьная скука, но именно через НОД сокращают дроби, раскладывают задачи на «несводимые» части и — внезапно — проверяют, можно ли обратить число в модульной арифметике, на которой стоит вся современная криптография.

Наивный способ и почему он плох

В лоб: перебрать все числа от меньшего вниз и найти первое, что делит оба. Для чисел вроде 1000-значных (а в криптографии именно такие) этот перебор не закончится никогда — на него не хватит возраста Вселенной. Евклид предложил совершенно другой ход.

Гениальное наблюдение

Ключевая идея: НОД двух чисел не меняется, если из большего вычесть меньшее. Если число $d$ делит и $a$, и $b$, то оно делит и их разность $a - b$. Значит, можно бесконечно уменьшать числа вычитанием, а НОД останется прежним. Современная версия заменяет череду вычитаний одним делением с остатком:

$$\gcd(a, b) = \gcd(b, a \bmod b)$$

Мы заменяем пару $(a, b)$ на пару $(b, \text{остаток от } a/b)$ и повторяем, пока второе число не станет нулём. Тогда первое — искомый НОД.

def gcd(a, b):
    while b:
        a, b = b, a % b   # сдвигаем пару, остаток заменяет большее
    return a

print(gcd(48, 18))      # 6
print(gcd(1071, 462))   # 21
print(gcd(17, 5))       # 1 — взаимно простые

# древняя «вычитательная» версия — та же логика, медленнее
def gcd_sub(a, b):
    while a != b:
        if a > b:
            a -= b
        else:
            b -= a
    return a

print(gcd_sub(48, 18))  # тоже 6

Почему он невероятно быстр

Кажется, что вычитание будет тянуться вечно для пары вроде (1000000, 1). Так и есть — поэтому версия с остатком важна: один % делает работу тысяч вычитаний разом. Доказано, что число шагов алгоритма Евклида растёт лишь как логарифм от величины чисел. Худший случай — соседние числа Фибоначчи (об этой связи в XIX веке написал Габриэль Ламе, и это считается одной из первых оценок сложности алгоритма в истории). Даже для тысячезначных чисел хватает нескольких сотен шагов.

Расширенная версия и криптография

Есть «расширенный» Евклид: он не только находит НОД, но и выражает его в виде $\gcd(a,b) = a\cdot x + b\cdot y$ с целыми $x, y$. Эти коэффициенты — ключ к нахождению обратного элемента по модулю: числа, на которое нужно умножить, чтобы получить единицу в модульной арифметике. Без этого не сгенерировать ключи RSA — того самого шифрования, что защищает HTTPS-соединение, по которому вы читаете эту статью. Получается, древнегреческий алгоритм буквально работает каждый раз, когда вы заходите на сайт по защищённому протоколу.

Мораль

Алгоритм Евклида — доказательство, что хорошая идея не устаревает. Он пережил падение античных цивилизаций, изобретение нуля, появление компьютеров и до сих пор лежит в фундаменте технологий, которые греки не могли вообразить. Когда говорят «думай как программист», на самом деле имеют в виду — думай как Евклид: ищи преобразование, которое уменьшает задачу, сохраняя то, что тебе важно.