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

 

ВХОД: Положительные целые числа a,b, ab.

ВЫХОД: Наибольший общий делитель gcd(a, b).

1. WHILE b0 DO

2. ra mod b, ab, br.

3. RETURN a.

Пример 3.11. Покажем, как с помощью алгоритма Евклида

вычисляется gcd(28,8):

a: 28 8 4

b: 8 4 0

r: 4 0

Здесь каждый столбец представляет собой очередную итерацию алгоритма. Процесс продолжается до тех пор, пока b не станет равным нулю. Тогда в значении переменной а содержится ответ (4).

Рассмотрим одно важное применение обобщенного алгоритма Евклида. Во многих задачах криптографии для заданных чисел с, m требуется находить такое число d < т, что

cd mod т=1. (3.14)

Отметим, что такое d существует тогда и только тогда, когда числа с и m взаимно простые.

Определение 3.6.Число d, удовлетворяющее (3.14), называется инверсией с по модулю m и часто обозначается c-1 mod m.

Данное обозначение для инверсии довольно естественно, так как мы можем теперь переписать (3.14) в виде

cc-1 mod m=1.'

Умножение на с-1 соответствует делению на с при вычислениях по модулю m. По аналогии можно ввести произвольные отрицательные степени при вычислениях по модулю m:

c-e=(се)-1=(c-1)е (mod m).

Покажем, как можно вычислить инверсию с помощью обобщенного алгоритма Евклида. Равенство (2.14) означает, что для некоторого целого k

cd-km=1. (3.15)

Учитывая, что с и m взаимно просты, перепишем (2.15) в виде

m(-k)+cd=gcd(m,c), (3.16)

что полностью соответствует (3.13), здесь только по-другому обозначены переменные. Поэтому, чтобы вычислить с-1 mod m, т.е. найти число d, нужно просто использовать обобщенный алгоритма Евклида для решения уравнения (3.16). Заметим, что значение переменной k нас не интересует, поэтому можно не вычислять вторые элементы строк U, V, Т. Кроме того, если число d получается отрицательным, то нужно прибавить к нему т, так как по определению число a mod m берется из множества {0, 1, ..., m-1}.

Одной из важнейших операций в криптографии с открытыми ключами является операция возведения в степень по модулю. Идея построения эффективного алгоритма возведения степень была ранее проиллюстрирована с помощью (3.5) и (3.6). Рассмотренный алгоритм можно реализовать и без хранения в памяти ряда чисел (3.5). Дадим описание этого алгоритма в форме, пригодной для непосредственной программной реализации. В названии алгоритма отражен тот факт, что биты показателя степени просматриваются справа-налево, т.е. от младшего к старшему.