Алгоритм Евклида

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

История

Первое известное описание алгоритма содержится в VII и X книгах «Начал» Евклида. В VII книге алгоритм применяется к целым числам, а в X книге — к длинам отрезков. Евклид не использовал термин «алгоритм» (он появился значительно позже, от имени персидского математика аль-Хорезми); его метод представлял собой геометрическую процедуру «взаимного вычитания» для нахождения общей меры двух отрезков.

Алгоритм был известен и в древнекитайской математике, независимо от греков. В Европе алгоритм активно использовался в эпоху Возрождения. В XIX веке с развитием теории чисел и алгебры алгоритм Евклида был обобщён на многочлены, кольца Гаусса и другие алгебраические структуры.

В XX веке, с появлением вычислительной техники, алгоритм стал одной из базовых операций в компьютерной арифметике. Его эффективность и простота сделали его ключевым элементом в криптографии (например, в алгоритме RSA для генерации ключей и нахождения обратных элементов), теории кодирования и компьютерной алгебре.

Суть и математическая основа

Основой алгоритма Евклида является следующее свойство: наибольший общий делитель двух чисел не изменяется, если большее число заменить на остаток от деления большего на меньшее. Если обозначить два числа как \( a \) и \( b \), при \( a > b \), то:

\[ \text{НОД}(a, b) = \text{НОД}(b, a \bmod b) \]

Процесс повторяется до тех пор, пока одно из чисел не станет равно нулю. Тогда наибольший общий делитель равен ненулевому числу. Математически это записывается как:

\[ \text{НОД}(a, 0) = a \]

Пример вычисления

Найти НОД чисел 252 и 105.

1. 252 ÷ 105 = 2 (остаток 42)
2. 105 ÷ 42 = 2 (остаток 21)
3. 42 ÷ 21 = 2 (остаток 0)

НОД(252, 105) = 21.

Реализации алгоритма

Существует несколько вариантов реализации, различающихся используемой операцией.

Классический вариант с вычитанием

Алгоритм, основанный на последовательном вычитании, наиболее нагляден в геометрической интерпретации. На каждом шаге из большего числа вычитается меньшее. Процесс продолжается до тех пор, пока числа не станут равными или одно не станет нулём.

Пример: НОД(6, 4) = НОД(4, 2) = НОД(2, 2) = 2.

Этот вариант работает медленнее, чем вариант с делением, особенно для чисел с большой разницей (например, для 1 и 10¹⁰⁰).

Вариант с делением (основной)

Наиболее распространённая версия, использующая операцию взятия остатка от деления. Эта реализация значительно быстрее, так как количество итераций логарифмически зависит от размера исходных чисел (теорема Ламе).

Псевдокод: `` function gcd(a, b): while b ≠ 0: t := b b := a mod b a := t return a ``

Бинарный алгоритм (алгоритм Штейна)

В 1967 году Джозеф Штейн предложил вариант, заменяющий деление на более быстрые для компьютера операции: битовые сдвиги (деление на 2) и вычитание. Этот алгоритм особенно эффективен для больших чисел, представленных в двоичном виде.

Правила:

• Если оба числа чётные — вынести двойку и продолжить с их половинками.
• Если одно чётное, другое нечётное — чётное разделить на 2.
• Если оба нечётные — большее заменить разностью.

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

Помимо нахождения НОД, расширенный алгоритм позволяет найти целые коэффициенты \( x \) и \( y \), удовлетворяющие уравнению:

\[ ax + by = \text{НОД}(a, b) \]

Это называется линейным представлением НОД (или тождеством Безу). Расширенный алгоритм рекурсивно находит эти коэффициенты, итерируя процесс деления с остатком.

Значение в криптографии

Расширенный алгоритм Евклида критически важен для вычисления обратного элемента по модулю. Например, для нахождения закрытого ключа \( d \) в алгоритме RSA необходимо решить уравнение:

\[ e \cdot d \equiv 1 \pmod{\varphi(n)} \]

где \( e \) — открытая экспонента, \( \varphi(n) \) — функция Эйлера. Расширенный алгоритм позволяет вычислить \( d \) (мультипликативное обратное к \( e \) по модулю \( \varphi(n) \)).

Применение

• Теория чисел: нахождение НОД, НОК, проверка чисел на взаимную простоту.
• Криптография: генерация ключей (RSA), вычисление обратных элементов, проверка простых чисел.
• Разрешение линейных диофантовых уравнений вида \( ax + by = c \).
• Обработка сигналов: в алгоритме декодирования свёрточных кодов (алгоритм Витерби использует понятие НОД в некоторых версиях).
• Сокращение дробей: деление числителя и знаменателя на НОД для получения несократимой дроби.
• Синтез передаточных функций в теории автоматического управления (нахождение общих делителей полиномов).
• Компьютерная алгебра: нахождение НОД многочленов от одной или нескольких переменных.

Классификация

По типу операндов различают:

1. Алгоритм для целых чисел — классический вариант.
2. Алгоритм для многочленов — обобщение на кольцо многочленов \( K[x] \). Используется для нахождения общего делителя двух многочленов.
3. Алгоритм для целых гауссовых чисел (чисел вида \( a + bi \), где \( a, b \) — целые).
4. Обобщённый алгоритм для евклидовых колец — абстрактная версия, применимая к любому кольцу, в котором определена евклидова норма (например, кольцо целых чисел, кольцо многочленов над полем).

Скорость работы

Количество итераций в алгоритме Евклида (с делением) растёт логарифмически от размера меньшего числа. Для чисел \( a \) и \( b \) (где \( a > b \)) количество шагов не превышает \( \lfloor \log_\varphi(b) \rfloor + 1 \), где \( \varphi \approx 1.618 \) — золотое сечение. Это означает, что для чисел с миллионом десятичных знаков потребуется не более нескольких миллионов итераций, что на практике выполняется за доли секунды.

Наихудшим случаем являются соседние числа Фибоначчи: для чисел \( F_{k+1} \) и \( F_k \) алгоритм потребует ровно \( k \) делений.

Источники:

• «Начала» Евклида (книги VII и X).
• Кнут Д. Э. «Искусство программирования», том 2 «Получисленные алгоритмы» (раздел 4.5.2).
• Штейн Дж. «Binary GCD Algorithm» (1967).
• Кормен Т., Лейзерсон Ч., Ривест Р., Штайн К. «Алгоритмы: построение и анализ» (глава 31).