Алгоритм степеней

Ввод: целые числа а, е и n, где а, n > 0 и е ≥ 0.

Вывод: вычет степени а^е по модулю n.

Шаг 1. А = а, Р = 1, Е = е.

Шаг 2. Если Е = 0, то выводим сообщение: «а^е º Р (mod n)»; в противном случае переходим к шагу 3.

Шаг 3. Если Е нечетно, то присваиваем переменной Р вычет произведения А ·Р по модулю n, а Е — значение (Е - 1)/2, после чего переходим к шагу 5; в противном случае идем к шагу 4.

Шаг 4. Если Е четно, то присваиваем Е значение Е/2 и идем к шагу 5.

Шаг 5. Заменяем текущее значение переменной А на вычет А² по модулю n и переходим к шагу 2.

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

Алгоритм Евклида предназначен для вычисления наибольшего общего делителя двух натуральных чисел. Наибольший общий делитель чисел a и b – наибольшее целое число d, на которое и а, и b делятся: d = НОД(a,b). Если НОД(а, b) = 1, то числа а и b взаимно простые.

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

Ввод: натуральные числа а и b, а≥ b.

Вывод: наибольший общий делитель чисел а и b.

Шаг 1. Положить А = а иВ = b.

Шаг 2. Заменить значение R остатком от деления А на В и перейти к шагу 3.

Шаг 3. Если R = 0, то сообщить: наибольший общий дели­тель чисел a u b равен В», и остановиться; в противном случае перейти к шагу 4.

Шаг 4. Заменить значение А на значение B, значение В на значение R и возвратиться к шагу 2.

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

Пусть a и b – два целых положительных числа. Тогда существуют целые (не обязательно положительные) числа x и y, такие, что

ax + by = НОД(a, b). (1)

Расширенный алгоритм Евклида служит для отыскания НОД(a, b), x и y, удовлетворяющих данному равенству.

Введем три вектора U = (u₁, u₂, u₃), V = (v₁, v₂, v₃), T = (t₁, t₂, t₃).

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

ВЫХОД: НОД(a, b), x, y, ax + by = НОД (a, b).

1. U ß (a, 1, 0), V ß (b, 0, 1).
2. WHILE v₁ <> 0 DO
3. q ß u₁ div v₁;
4. T ß (u₁ mod v₁, u₂ - qv₂, u₃ – qv₃);
5. U ß V, V ß T.
6. RETURN U=(НОД(a, b), x, y).

Во многих задачах криптографии для заданных чисел c, m требуется найти такое число d < m, что

cd mod m = 1. (2)

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

Число d называется инверсией c по модулю m и часто обозначается c^-1 mod m.

Естественно будет выглядеть запись

cс^-1 mod m = 1.

Умножение на c^-1 соответствует делению на с при вычислениях по модулю m.

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

cd - km = 1. (3)

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

m(-k) + cd = НОД(m, c). (4)

Если число d получится отрицательным, то к нему надо прибавить m.

Пример. Найдем 3^-1 mod 11.

a = 11, b = 3,

U 11 1 0

V U 3 0 1

T V U 2 1 -3 q = 3

T V U 1 -1 4 q = 1

T V 0 3 -11 q = 2

Получается: 3^-1 mod 11 = 4

Литература

1. ГОСТ Р 34.10-94. Государственный стандарт Российской Федерации. Криптографи­ческая защита информации. Процедуры выработки и проверки электронной цифровой подписи на базе асимметричного криптографического алгоритма.

2. Коутинхо С. Введение в теорию чисел. Алгоритм RSA. М.: Постмаркет, 2001. - 328 с.

3. Программирование алгоритмов защиты информации. Учебное пособие // Домашев А.В., Грунтович М.М., Попов В.О., Правиков Д.И., Прокофьев И.В., Щербаков А.Ю. - М.: Издатель Молгачева С.В., Издательство «Нолидж», 2002.- 416 с.

4. Петров А. А. Компьютерная безопасность. Криптографические методы защиты. – М.: ДМК, 2000. - 448 с.

5. Виноградов И. М. Основы теории чисел. М.: Наука, 1982.

6. Кнут Д. Искусство программирования на ЭВМ. Т. 2. Получисленные алгоритмы. М.: Мир, 1977.

7. Прахар К. Распределение простых чисел. М.: Мир 1967.

8. Ахо А., Хопкрофт Дж., Ульман Дж. Построение и анализ вычислительных алгоритмов. М.: Мир, 1979.

9. Акритас А. Основы компьютерной алгебры с приложениями. Пер. с англ.- М.: Мир, 1994. – 544 с.

10. Саломаа А. Криптография с открытым ключом. М.: Мир, 1996. - 318 с.

11. Лебедев А. Н. Криптография с открытым ключом и возможности ее практического применения // Защита информации. 1992. Вып. 2. С. 129-147.

12. Уильямс Х. Проверка чисел на простоту с помощью вычислительных машин // Кибернетический сборник. 1986. Вып. 23. С. 51-99.

13. Menezes A., van Oorschot P., Vanstone S. Handbook of applied cryptography. CRC Press, 1996. 661 p. (http://www.cacr.math.uwaterloo.ca/ hac/).