Введение

Модульная экспоненциация — это возведение в степень, выполняемое по модулю. Она полезна в информатике, особенно в области криптографии с открытым ключом, где используется как в обмене ключами Диффи — Хеллмана, так и в алгоритмах RSA с открытым и закрытым ключами. Модульная экспоненциация — это остаток от деления целого числа b (основания) в степени e (показателя степени) на положительное целое число m (модуля); то есть, из определения деления следует, что 0 ≤ c < m. Например, если b = 5, e = 3 и m = 13, то деление на 13 дает остаток c = 8. Модульную экспоненциацию можно выполнить с отрицательным показателем степени e, найдя модульное мультипликативное обратное d к b по модулю m, используя расширенный алгоритм Евклида. То есть: , где e < 0 и b ⋅ d ≡ 1 (mod m). Модульная экспоненциация эффективно вычисляется даже для очень больших целых чисел. С другой стороны, вычисление модульного дискретного логарифма — то есть нахождение показателя степени e при заданных b, c и m — считается сложной задачей. Такое поведение, свойственное односторонним функциям, делает модульную экспоненциацию подходящей для использования в криптографических алгоритмах.

Прямой метод

Самый прямой метод вычисления модульного показателя степени – вычислить b^e непосредственно, а затем взять остаток от деления этого числа на m. Рассмотрим задачу вычисления c, при заданных b, e и m:

Можно использовать калькулятор для вычисления 413^e; это даст 67 108 864. Взяв остаток от деления этого значения на 497, получим ответ c = 445. Обратите внимание, что b состоит только из одной цифры, а e – только из двух, но значение b^e имеет 8 цифр. В надежной криптографии b часто составляет не менее 1024 бит. Рассмотрим, например, b и e, оба из которых являются вполне разумными значениями. В этом примере b состоит из 77 цифр, а e – из 2 цифр, но значение b^e имеет 1304 десятичных цифры. Такие вычисления возможны на современных компьютерах, но огромный размер этих чисел значительно замедляет скорость вычислений. По мере увеличения b и e для повышения безопасности, значение b^e становится неудобным для работы. Время, необходимое для возведения в степень, зависит от вычислительной среды и процессора. Описанный выше метод требует Big O умножений для завершения.

Минимальные умножения

В книге "Искусство компьютерного программирования", том 2, "Получисленные алгоритмы", страница 463, Дональд Кнут отмечает, что вопреки некоторым утверждениям, данный метод не всегда обеспечивает минимально возможное число умножений. Наименьший контрпример – это степень 15, для которой двоичный метод требует шести умножений. Вместо этого можно вычислить x³ за два умножения, затем x⁶, возведя x³ в квадрат, затем x¹², возведя x⁶ в квадрат, и, наконец, x¹⁵, умножив x¹² на x³. Таким образом, желаемый результат достигается всего за пять умножений. Однако последующие страницы посвящены описанию способов построения подобных последовательностей в общем случае.

Конечные циклические группы

Обмен ключами Диффи — Хеллмана использует возведение в степень в конечных циклических группах. Описанные выше методы модульного возведения матрицы в степень очевидно применимы и в этом контексте. Модульное умножение матриц C ≡ AB (mod n) повсюду просто заменяется групповым умножением 1=c = ab.

Обратная и квантовая модульная экспоненциализация

В квантовых вычислениях модульное возведение в степень является узким местом алгоритма Шора, где оно должно вычисляться цепью, состоящей из обратимых логических элементов, которые, в свою очередь, могут быть разложены на квантовые логические элементы, подходящие для конкретного физического устройства. Более того, в алгоритме Шора основание и модуль возведения в степень известны при каждом вызове, что позволяет применять различные оптимизации схемы.