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

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

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

1. WHILE b 0 DO

2. r a mod b, a b, b r.

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). Дадим описание этого алгоритма в форме, пригодной для непосредственной программной реализации. В названии алгоритма отражен тот факт, что биты показателя степени просматриваются справа-налево, т.е. от младшего к старшему.

Дата добавления: 2014-01-11