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

Этот алгоритм используется для отыскания наибольшего общего делителя (н.о.д.) двух целых чисел, x₁ и x₂. Если обозначить н.о.д. через h, то этот алгоритм можно также использовать для нахождения таких целых чисел m и n, что

m x₁ - n x₂=h,

которые используются в системе зашифрования/расшифрования RSA.

Алгоритм Евклида формулируется следующим образом.

Можем предположить, что оба числа x₁ и x₂ положительны, и что x₁ больше x₂ (если это не так, поменяем их местами).

Разделим x₁ на x₂; пусть в остатке получается число x₃:

x₁ = a₁x₂+x₃, где a₁ - целое число, а 0 x₃< x₂.

Если x₃0, то разделим x₂ на x₃; пусть в остатке получается x₄:

x₂ = a₂x₃+x₄, где a₂ - целое число, а 0 x₄< x₃.

Продолжаем таким образом до тех пор, пока в остатке не получится ноль, то есть, пока мы не получим

x_(n-1) = a_(n-1)x_n.

Тогда наибольший общий делитель чисел x₁ и x₂ (h) будет равен x_n. Если h=1, то целые числа x₁ и x₂ называются взаимно-простыми.

Пример

Найти н.о.д. чисел 1001 и 221.

Решение

1001=4221+117,

221=1117+104,

117=1104+13,

104=813+0.

Таким образом, н.о.д. чисел 1001 и 221 равен 13. (Проверка: 1001=1391, 221=1317; числа 91 и 17 взаимно-простые.)

В математической литературе принято обозначать н.о.д. пары целых чисел m и n через (m,n). Так, (1001,221)=13, а (91,17)=1.

Следующий пример иллюстрирует использование алгоритма Евклида в рамках метода RSA, как описано в главе 13.

Пример

Найти целые числа m и n, такие что 91m-17n=1.

Решение

Имеем:

91=517+6,

17=26+5,

6=15+1,

5=51,

что подтверждает взаимную простоту чисел 91 и 17 (если это было бы не так, то у нашего уравнения не существовало бы решения). Возвращаемся по шагам алгоритма в обратном порядке, начиная с предпоследней строки:

1=6-15 и 5=17-26,

поэтому

1=6-1(17-26)=36-17,

но

6=91-517,

следовательно,

1=3(91-517)-17=391-1617.

Итак,

m=3 и n=16.

(Проверка: 391=273 и 1617=272.)

Альтернативный метод

Значения m и n можно также найти с помощью непрерывных дробей (см. [6.7]). При этом метод отыскания остается тем же самым, что и в алгоритме Евклида, хотя все это и выглядит по-другому.

В качестве иллюстрации метода снова вычислим значения m и n, такие что

91m-17n=1.

,

,

.

Таким образом, для данной непрерывной дроби частичные отношения будут равны (5, 2, 1, 5), а последовательные приближения, соответственно

, , и .

Числа m и n совпадают с числителем и знаменателем предпоследнего приближения: они, как и ранее, оказываются равны 16 и 3.