Модульное возведение в степень

Модульное возведение в степень — это возведение в степень, выполняемое по модулю . Оно полезно в информатике , особенно в области криптографии с открытым ключом , где оно используется как в обмене ключами Диффи–Хеллмана, так и в обмене открытыми/закрытыми ключами RSA .

Модульное возведение в степень — это остаток от возведения целого числа $b$ (основание) в степень $e$ (показатель степени) и деления его на положительное целое число $m$ (модуль); то есть $c = b e mod m$ . Из определения деления следует, что $0 \leq c < m$ .

Например, если $b = 5$ , $e = 3$ и $m = 13$ , то деление $5 \cdot 3 = 125$ на $13$ дает остаток $c = 8$ .

Модульное возведение в степень можно выполнить с отрицательным показателем степени $e,$ найдя модульное мультипликативное обратное число $d$ для $b$ по модулю $m,$ используя расширенный алгоритм Евклида . То есть:

c = b e mod m = d - e mod m

, где

e < 0

b \cdot d \equiv 1 (mod m)

Модульное возведение в степень эффективно для вычислений, даже для очень больших целых чисел. С другой стороны, вычисление модульного дискретного логарифма – то есть нахождение показателя степени $e$ при заданных $b$ , $c$ и $m$ – считается сложным. Это одностороннее поведение функции делает модульное возведение в степень кандидатом на использование в криптографических алгоритмах.

Прямой метод

Самый прямой метод вычисления модульной экспоненты — это вычислить $b e$ напрямую, а затем взять это число по модулю $m$ . Попробуйте вычислить $c$ , если $b = 4$ , $e = 13$ и $m = 497$ :

с \equiv 4 13 (мод 497)

Можно использовать калькулятор для вычисления 4 ¹³ ; это дает 67 108 864. Взяв это значение по модулю 497, ответ $c$ определяется как 445.

Обратите внимание, что $b$ имеет длину всего одну цифру, а $e$ — длину всего две цифры, но значение $b\cdot e$ имеет длину 8 цифр.

В сильной криптографии $b$ часто составляет не менее 1024 бит . ^[1] Рассмотрим $b = 5 \times 10 76$ и $e = 17$ , оба из которых являются вполне разумными значениями. В этом примере $b$ имеет длину 77 цифр, а $e$ — 2 цифры, но значение $b e$ имеет длину 1304 десятичных знака. Такие вычисления возможны на современных компьютерах, но огромная величина таких чисел значительно замедляет скорость вычислений. По мере того как $b$ и $e$ увеличиваются еще больше, чтобы обеспечить лучшую безопасность, значение $b e$ становится громоздким.

Время, необходимое для выполнения возведения в степень, зависит от операционной среды и процессора. Описанный выше метод требует $O (e)$ умножений для завершения.

Метод, эффективный с точки зрения памяти

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

Этот алгоритм использует идентичность

(а \cdot b) mod m = [(а mod m) \cdot (b mod m)] mod m

Модифицированный алгоритм:

Входные данные: целое число $b$ (основание), целое число $e$ (экспонента) и положительное целое число $m$ (модуль).

Выходные данные Модульная экспонента $c$ , где

c = b e mod m

Инициализируем $c = 1$ и переменную цикла $e' = 0$
Пока e′ < e делать
1. Увеличить $e'$ на 1
2. Рассчитайте $c = (b \cdot c) mod m$
Выход $c$

Обратите внимание, что в конце каждой итерации цикла справедливо уравнение $c \equiv b e' (mod m)$ . Алгоритм завершается, когда цикл выполняется $e$ раз. В этой точке $c$ содержит результат $b e mod m$ .

Подводя итог, этот алгоритм увеличивает $e'$ на единицу, пока он не станет равен $e$ . На каждом шаге результат предыдущей итерации $c$ умножается на $b$ и выполняется операция по модулю над полученным произведением, тем самым сохраняя результирующее $c$ как небольшое целое число.

Снова представлен пример $b = 4$ , $e = 13$ и $m = 497.$ Алгоритм выполняет итерацию тринадцать раз:

(e' = 1) c = (4 \cdot 1) mod 497 = 4 mod 497 = 4

(e' = 2) c = (4 \cdot 4) mod 497 = 16 mod 497 = 16

(e' = 3) c = (4 \cdot 16) mod 497 = 64 mod 497 = 64

(e' = 4) c = (4 \cdot 64) mod 497 = 256 mod 497 = 256

(e' = 5) c = (4 \cdot 256) mod 497 = 1024 mod 497 = 30

(e' = 6) c = (4 \cdot 30) mod 497 = 120 mod 497 = 120

(e' = 7) c = (4 \cdot 120) mod 497 = 480 mod 497 = 480

(e' = 8) c = (4 \cdot 480) mod 497 = 1920 mod 497 = 429

(e' = 9) c = (4 \cdot 429) mod 497 = 1716 mod 497 = 225

(e' = 10) c = (4 \cdot 225) mod 497 = 900 mod 497 = 403

(e' = 11) c = (4 \cdot 403) mod 497 = 1612 mod 497 = 121

(e' = 12) c = (4 \cdot 121) mod 497 = 484 mod 497 = 484

(e' = 13) c = (4 \cdot 484) mod 497 = 1936 mod 497 = 445

Окончательный ответ для $c$ , таким образом, равен 445, как и в прямом методе.

Как и первый метод, для завершения требуется $O(e)$ умножений. Однако, поскольку числа, используемые в этих вычислениях, намного меньше чисел, используемых в вычислениях первого алгоритма, время вычислений уменьшается по крайней мере в $O(e)$ раз в этом методе.

В псевдокоде этот метод можно реализовать следующим образом:

Функция modular_pow(основание, показатель степени, модуль) —  если модуль = 1 , то  возвращается 0 с := 1 для e_prime = 0 в exponent-1 do c := (c * base) mod modulus return c

Двоичный метод справа налево

Третий метод радикально сокращает количество операций для выполнения модульного возведения в степень, сохраняя при этом тот же объем памяти, что и в предыдущем методе. Это комбинация предыдущего метода и более общего принципа, называемого возведением в степень путем возведения в квадрат (также известного как бинарное возведение в степень ).

Во-первых, требуется, чтобы показатель степени $e$ был преобразован в двоичную запись . То есть, $e$ можно записать как:

e=\sum _{i=0}^{n-1}a_{i}2^{i}

В такой записи длина e составляет $n$ $бит$ . $a$ $i$ может принимать значение 0 или 1 для любого $i$ такого, что $0 \leq$ $i$ $<$ $n$ . По определению, $a$ $n$ $- 1$ $= 1$ .

Тогда значение $b e$ можно записать как:

b^{e}=b^{\left(\sum _{i=0}^{n-1}a_{i}2^{i}\right)}=\prod _{i=0}^{n-1}b^{a_{i}2^{i}}

Следовательно, решение $c$ имеет вид:

c\equiv \prod _{i=0}^{n-1}b^{a_{i}2^{i}}{\pmod {m}}

Псевдокод

Ниже приведен пример в псевдокоде, основанном на Прикладной криптографии Брюса Шнайера . ^[2] Входные данные base , exponent и modulus соответствуют $b$ , $e$ и $m$ в приведенных выше уравнениях.

Функция modular_pow(base, exponent, modulus) —  если modulus = 1 , то  возвращает 0. Утверждает  :: (modulus - 1) * (modulus - 1) не переполняет base. результат := 1 основание := основание mod модуль пока показатель степени > 0 сделать  если (показатель степени mod 2 == 1) тогда результат := (результат * основание) mod модуль показатель степени := показатель степени >> 1 база := (база * база) mod модуль возврат результата

Обратите внимание, что при первом входе в цикл переменная base кода эквивалентна $b$ . Однако повторное возведение в квадрат в третьей строке кода гарантирует, что при завершении каждого цикла переменная base эквивалентна $b 2 i mod m$ , где $i$ — количество итераций цикла. (Это делает $i$ следующим рабочим битом двоичной экспоненты exponent , где наименее значимый бит — exponent ₀ ).

Первая строка кода просто выполняет умножение в . Если $a$ равно нулю, код не выполняется, поскольку это фактически умножает текущий итог на единицу. Если $a$ вместо этого равно единице, переменная base (содержащая значение $b$ $2$ $i$ $mod$ $m$ исходного base) просто умножается на. $\prod _{i=0}^{n-1}b^{a_{i}2^{i}}{\pmod {m}}$

В этом примере основание $b$ возводится в степень $e = 13.$ Степень в двоичной системе счисления равна 1101. Имеется четыре двоичные цифры, поэтому цикл выполняется четыре раза со значениями $a 0 = 1, a 1 = 0, a 2 = 1$ и $a 3 = 1$ .

Сначала инициализируем результат значением 1 и сохраним значение $b$ в переменной $x$ : $R$

R\leftarrow 1\,(=b^{0}){\text{ and }}x\leftarrow b

Шаг 1) бит 1 равен 1, поэтому устанавливаем ;

R\leftarrow R\cdot x{\text{ }}(=b^{1})

набор .

x\leftarrow x^{2}{\text{ }}(=b^{2})

Шаг 2) бит 2 равен 0, поэтому не сбрасывайте

R

;

набор .

x\leftarrow x^{2}{\text{ }}(=b^{4})

Шаг 3) бит 3 равен 1, поэтому устанавливаем ;

R\leftarrow R\cdot x{\text{ }}(=b^{5})

набор .

x\leftarrow x^{2}{\text{ }}(=b^{8})

Шаг 4) бит 4 равен 1, поэтому устанавливаем ;

R\leftarrow R\cdot x{\text{ }}(=b^{13})

Это последний шаг, поэтому нам не нужно возводить

x

в квадрат .

Готово: теперь $R$ — . $b^{13}$

Вот приведенный выше расчет, где мы вычисляем $b = 4$ в степени $e = 13$ , выполненный по модулю 497.

Инициализировать:

R\leftarrow 1\,(=b^{0})

и .

x\leftarrow b=4

Шаг 1) бит 1 равен 1, поэтому устанавливаем ;

R\leftarrow R\cdot 4\equiv 4{\pmod {497}}

набор .

x\leftarrow x^{2}{\text{ }}(=b^{2})\equiv 4^{2}\equiv 16{\pmod {497}}

Шаг 2) бит 2 равен 0, поэтому не сбрасывайте

R

;

набор .

x\leftarrow x^{2}{\text{ }}(=b^{4})\equiv 16^{2}\equiv 256{\pmod {497}}

Шаг 3) бит 3 равен 1, поэтому устанавливаем ;

R\leftarrow R\cdot x{\text{ }}(=b^{5})\equiv 4\cdot 256\equiv 30{\pmod {497}}

набор .

x\leftarrow x^{2}{\text{ }}(=b^{8})\equiv 256^{2}\equiv 429{\pmod {497}}

Шаг 4) бит 4 равен 1, поэтому устанавливаем ;

R\leftarrow R\cdot x{\text{ }}(=b^{13})\equiv 30\cdot 429\equiv 445{\pmod {497}}

Готово: теперь $R$ равно , тот же результат, что и в предыдущих алгоритмах. $4^{13}\equiv 445{\pmod {497}}$

Время выполнения этого алгоритма составляет $O(log$ exponent $)$ . При работе с большими значениями exponent , это обеспечивает существенное преимущество в скорости по сравнению с предыдущими двумя алгоритмами, время выполнения которых составляет $O($ exponent $)$ . Например, если бы exponent был 2 ²⁰ = 1048576, этот алгоритм имел бы 20 шагов вместо 1048576 шагов.

Реализация вЛуа

функция modPow(b, e, m) если m == 1 , то  вернуть 0 конец  локального r = 1 б = б % м пока e > 0 делать  если e % 2 == 1 тогда г = (г*б) % м конец б = (б*б) % м e = e >> 1 --используйте 'e = math.floor(e / 2)' в Lua 5.2 или старше конец  возврат r конец

Двоичный метод слева направо

Мы также можем использовать биты экспоненты в порядке слева направо. На практике мы обычно хотим получить результат по модулю некоторого модуля $m$ . В этом случае мы бы сократили каждый результат умножения $(mod m)$ перед тем, как продолжить. Для простоты вычисление модуля здесь опущено. Этот пример показывает, как вычислять с использованием двоичного возведения в степень слева направо. Экспонента равна 1101 в двоичном виде; есть 4 бита, поэтому есть 4 итерации. $b^{13}$

Инициализируем результат значением 1: . $r\leftarrow 1\,(=b^{0})$

Шаг 1) ; бит 1 = 1, поэтому вычисляем ;

r\leftarrow r^{2}\,(=b^{0})

r\leftarrow r\cdot b\,(=b^{1})

Шаг 2) ; бит 2 = 1, поэтому вычисляем ;

r\leftarrow r^{2}\,(=b^{2})

r\leftarrow r\cdot b\,(=b^{3})

Шаг 3) ; бит 3 = 0, поэтому мы завершили этот шаг;

r\leftarrow r^{2}\,(=b^{6})

Шаг 4) ; бит 4 = 1, поэтому вычисляем .

r\leftarrow r^{2}\,(=b^{12})

r\leftarrow r\cdot b\,(=b^{13})

Минимальное количество умножений

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

Обобщения

Матрицы

Член $m$ любой константно-рекурсивной последовательности (такой как числа Фибоначчи или числа Перрина ), где каждый член является линейной функцией $k$ предыдущих членов, может быть эффективно вычислен по модулю $n$ путем вычисления $A m mod n$ , где $A$ — соответствующая сопутствующая матрица $k \times k$ . Вышеуказанные методы легко адаптируются к этому приложению. Это можно использовать , например, для проверки простоты больших чисел $n .$

Псевдокод

Рекурсивный алгоритм для ModExp(A, b, c)= $A b mod c$ , где $A$ — квадратная матрица.

функция Matrix_ModExp(Matrix A, int b, int c) если b == 0 , то возвращает I // Единичная матрица , если (b mod 2 == 1) , то возвращает (A * Matrix_ModExp ( A, b - 1, c)) mod c   Матрица D := Matrix_ModExp(A, b / 2, c) возврат (D * D) mod c

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

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

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

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

Реализации программного обеспечения

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

Встроенная функция Pythonpow() (возведения в степень) [1] принимает необязательный третий аргумент — модуль
Класс .NET FrameworkBigInteger имеет ModPow()метод для выполнения модульного возведения в степень
Класс Javajava.math.BigInteger имеет modPow()метод для выполнения модульного возведения в степень
Функция MATLAB изpowermod Symbolic Math Toolbox
В языке Wolfram Language есть функция PowerMod
Модуль Perl имеетMath::BigInt метод bmodpow()[2] для выполнения модульного возведения в степень
У Раку есть встроенная рутина expmod.
Тип Gobig.Int содержит Exp()метод (возведения в степень) [3], третий параметр которого, если он не равен нулю, является модулем
Библиотека BC Math в PHPbcpowmod() имеет функцию [4] для выполнения модульного возведения в степень
Библиотека GNU Multiple Precision Arithmetic Library (GMP) содержит mpz_powm()функцию [5] для выполнения модульного возведения в степень
Пользовательская функция @PowerMod()для FileMaker Pro (с примером 1024-битного шифрования RSA )
В пакете Rubyopenssl имеется OpenSSL::BN#mod_expметод [6] для выполнения модульного возведения в степень.
Калькулятор HP Prime Calculator имеет функцию CAS.powmod() [7] ^{[ permanent dead link ]} для выполнения модульного возведения в степень. Для a^b mod c, a не может быть больше 1 EE 12. Это максимальная точность большинства калькуляторов HP, включая Prime.

Смотрите также

Редукция Монтгомери для вычисления остатка, когда модуль очень большой.
Умножение Коханского , сериализуемый метод вычисления остатка, когда модуль очень большой
Редукция Барретта , алгоритм вычисления остатка, когда модуль очень большой.

Ссылки

^ "Слабый алгоритм Диффи–Хеллмана и атака Logjam". weakdh.org . Получено 03.05.2019 .
^ Шнайер 1996, стр. 244.
^ IL Markov, M. Saeedi (2012). «Константно-оптимизированные квантовые схемы для модульного умножения и возведения в степень». Quantum Information and Computation . 12 (5–6): 0361–0394. arXiv : 1202.6614 . Bibcode :2012arXiv1202.6614M. doi :10.26421/QIC12.5-6-1. S2CID 16595181.

Внешние ссылки

В Wikibook Algorithm Implementation есть страница по теме: Модульное возведение в степень

Шнайер, Брюс (1996). Прикладная криптография: протоколы, алгоритмы и исходный код на языке C, второе издание (2-е изд.). Wiley. ISBN 978-0-471-11709-4.
Пол Гарретт, Java-апплет быстрого модульного возведения в степень
Гордон, Дэниел М. (1998). «Обзор методов быстрого возведения в степень» (PDF) . Журнал алгоритмов . 27 (1). Elsevier BV: 129–146. doi :10.1006/jagm.1997.0913. ISSN 0196-6774.