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

1. Исходные числа a и b

2. Вычислить r - остаток от деления a на b: a = b * q + r

3. Если r = 0, то b - искомое число (наибольший общий делитель), конец

4. Заменить пару чисел <a, b> парой <b, r>, перейти к пункту 2

При вычислении наибольшего общего делителя с помощью алгоритма Евклида будет выполнено не более 5 * p операций деления с остатком, где p есть количество цифр в десятичной записи меньшего из чисел a и b. На практике алгоритм работает очень быстро.

Решение уравнения a * x + b * y = 1

В 5-м пункте алгоритма RSA предполагается нахождение такого числа e, чтобы e * d = 1 (mod m). Для этого нужно использовать модифицированный алгоритм Евклида, который работает только если числа d и m взаимно просты. Вычисление числа e сводится к решению уравнения m * x + d * e = 1 в натуральных числах. Число x не существенно.

1.2. Алгоритм решения уравнения a * x + b * y = 1

1. Необходимо определить матрицу E =

2. Вычислить r - остаток от деления a на b: a = b * q + r

3. Если r = 0, то второй столбец матрицы дает решение: , конец

4. E = E *

5. Заменить пару чисел <a, b>, парой <b, r>, перейти к пункту 2

В данном алгоритме все вычисления можно производить по модулю большего из чисел a и b. Отрицательное число -q заменяется положительным, полученным путем вычитания числа q из числа, взятого в качестве модуля. Например, если из чисел a и b большим является число b, то все вычисления можно производить по модулю числа b, при этом -q будет представлено как b - q. Скорость работы алгоритма и количество производимых им операций примерно равно соответствующим параметрам алгоритма Евклида, описанного выше.