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

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

\[ a \cdot x + b \cdot y = \gcd(a, b) \]

где \(a\) и \(b\) — целые числа, не равные одновременно нулю. Данное представление НОД в виде линейной комбинации исходных чисел называется соотношением Безу, а коэффициенты \(x\) и \(y\) — коэффициентами Безу. Расширенный алгоритм лежит в основе многих криптографических систем, в частности, при вычислении обратного элемента по модулю в алгоритме RSA и при решении модульных уравнений.

История

Алгоритм Евклида, описанный в «Началах» Евклида (около 300 г. до н. э.), изначально был геометрическим методом нахождения общей меры двух отрезков. Его числовая версия для целых чисел была формализована значительно позже. Расширенная версия алгоритма, позволяющая находить коэффициенты Безу, впервые была явно сформулирована в работах французского математика Этьена Безу в XVIII веке, хотя отдельные случаи её применения встречались и ранее. В современной вычислительной математике расширенный алгоритм Евклида стал стандартным инструментом после развития теории чисел и криптографии в XX веке.

Математическая основа

Соотношение Безу

Для любых целых чисел \(a\) и \(b\) существуют такие целые числа \(x\) и \(y\), что:

\[ a \cdot x + b \cdot y = \gcd(a, b) \]

Это утверждение является следствием того, что множество всех линейных комбинаций \(a\) и \(b\) совпадает с множеством чисел, кратных их НОД. Расширенный алгоритм Евклида не только доказывает существование такого представления, но и конструктивно находит \(x\) и \(y\).

Рекуррентная природа

Классический алгоритм Евклида основан на последовательном делении с остатком:

\[ \begin{aligned} a &= b \cdot q_1 + r_1 \\ b &= r_1 \cdot q_2 + r_2 \\ r_1 &= r_2 \cdot q_3 + r_3 \\ &\vdots \\ r_{n-1} &= r_n \cdot q_{n+1} + 0 \end{aligned} \]

где \(r_n = \gcd(a, b)\). Расширенный алгоритм использует те же шаги, но на каждом этапе выражает текущий остаток через исходные \(a\) и \(b\). На последнем шаге, когда остаток становится равен НОД, получается искомое линейное представление.

Описание алгоритма

Итеративная версия

Алгоритм можно реализовать итеративно, сохраняя на каждом шаге коэффициенты для двух последних остатков. Пусть на вход подаются числа \(a\) и \(b\). Вводятся переменные:

• \(x_1 = 1, y_1 = 0\) — коэффициенты для \(a\);
• \(x_2 = 0, y_2 = 1\) — коэффициенты для \(b\).

На каждом шаге, пока \(b \neq 0\):

1. Вычисляется частное \(q = \lfloor a / b \rfloor\).
2. Вычисляется остаток \(r = a - q \cdot b\).
3. Обновляются коэффициенты:

\[ \begin{aligned} x &= x_1 - q \cdot x_2 \\ y &= y_1 - q \cdot y_2 \end{aligned} \]

1. Производится сдвиг:

\[ \begin{aligned} a &= b, \quad b = r \\ x_1 &= x_2, \quad y_1 = y_2 \\ x_2 &= x, \quad y_2 = y \end{aligned} \]

После завершения цикла \(a\) содержит НОД, а \(x_1\) и \(y_1\) — искомые коэффициенты Безу.

Рекурсивная версия

Рекурсивная реализация более компактна. Если \(b = 0\), то \(\gcd(a, b) = a\), и коэффициенты равны \(x = 1, y = 0\). Иначе рекурсивно вызывается алгоритм для пары \((b, a \bmod b)\), который возвращает \(\gcd\) и коэффициенты \(x', y'\) для этой пары. Затем текущие коэффициенты вычисляются по формулам:

\[ \begin{aligned} x &= y' \\ y &= x' - \lfloor a / b \rfloor \cdot y' \end{aligned} \]

Пример работы

Найти НОД(30, 18) и коэффициенты Безу.

Шаги итеративного алгоритма:

Результат: НОД = 6, \(x = -1\), \(y = 2\). Проверка:

\[ 30 \cdot (-1) + 18 \cdot 2 = -30 + 36 = 6 \]

Применение

Вычисление обратного элемента по модулю

Расширенный алгоритм Евклида используется для нахождения мультипликативного обратного числа \(a\) по модулю \(m\), если \(\gcd(a, m) = 1\). В этом случае уравнение \(a \cdot x + m \cdot y = 1\) даёт \(x\), которое является обратным элементом: \(a \cdot x \equiv 1 \pmod{m}\). Это критически важно для криптосистемы RSA, где требуется вычислять секретный ключ \(d\) как обратный к открытому ключу \(e\) по модулю \(\varphi(n)\).

Решение диофантовых уравнений

Линейные диофантовы уравнения вида \(a \cdot x + b \cdot y = c\) имеют целые решения тогда и только тогда, когда \(c\) делится на \(\gcd(a, b)\). Расширенный алгоритм позволяет найти частное решение, а затем построить общее решение, добавляя кратные \(b / \gcd\) к \(x\) и вычитая кратные \(a / \gcd\) из \(y\).

Китайская теорема об остатках

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

Криптография на эллиптических кривых

В алгоритмах, использующих эллиптические кривые (ECDSA, EdDSA), расширенный алгоритм Евклида применяется для деления многочленов в конечных полях и для вычисления обратных элементов.

Сложность

Временная сложность расширенного алгоритма Евклида совпадает со сложностью классического алгоритма и составляет \(O(\log \min(|a|, |b|))\) арифметических операций. В худшем случае (когда входные числа являются последовательными числами Фибоначчи) количество шагов пропорционально логарифму чисел. Алгоритм эффективно работает даже для очень больших чисел (тысячи бит), что делает его пригодным для криптографических приложений.

Модификации

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

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

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

Аналогичный алгоритм существует для многочленов над полем. Он позволяет находить НОД двух многочленов и представлять его в виде линейной комбинации исходных многочленов. Это применяется в теории кодирования (коды БЧХ, Рида — Соломона) и в символьных вычислениях.

Ограничения

Расширенный алгоритм Евклида определён только для целых чисел и многочленов над полем. Для чисел с плавающей запятой или других алгебраических структур понятие НОД не определено в классическом смысле. Кроме того, алгоритм не даёт единственного решения — коэффициенты Безу определены с точностью до прибавления кратных \(b / \gcd\) к \(x\) и \(a / \gcd\) к \(y\). На практике часто выбирают решение, в котором \(x\) минимально по модулю.

Источники

• Кнут Д. Э. Искусство программирования. Том 2. Получисленные алгоритмы. — 3-е изд. — М.: Вильямс, 2007.
• Кормен Т., Лейзерсон Ч., Ривест Р., Штайн К. Алгоритмы: построение и анализ. — 3-е изд. — М.: Вильямс, 2013.
• Виноградов И. М. Основы теории чисел. — 9-е изд. — М.: Наука, 1981.
• Боревич З. И., Шафаревич И. Р. Теория чисел. — 3-е изд. — М.: Наука, 1985.