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

Операция в модульной арифметике

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

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

Например, учитывая b = 5 , e = 3 и m = 13 , при делении 5 ³ = 125 на 13 остается остаток c = 8 .

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

c знак равно б ^е mod м знак равно d ^{- е} mod м , где е < 0 и б ⋅ d ≡ 1 (мод м ) .

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

Прямой метод

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

с ≡ 4 ¹³ (мод. 497)

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

Обратите внимание, что длина b составляет только одну цифру, а длина e — только две цифры, но длина значения b ^{e составляет 8 цифр.}

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

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

Метод эффективного использования памяти

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

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

( а ⋅ б ) mod m = [( a mod m ) ⋅ ( b mod m )] mod m

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

1. Установите c = 1 , e′ = 0 .
2. Увеличьте e' на 1.
3. Установите c = (b ⋅ c) mod m .
4. Если e′ < e , перейдите к шагу 2. В противном случае c содержит правильное решение c ≡ b ^e (mod m ) .

Обратите внимание, что при каждом переходе к шагу 3 уравнение c ≡ b ^e′ (mod m ) выполняется. Когда шаг 3 был выполнен e раз, c содержит искомый ответ. Таким образом, этот алгоритм в основном подсчитывает e' по единицам, пока e' не достигнет e , выполняя умножение на b и операцию по модулю каждый раз, когда он добавляет единицу (чтобы гарантировать, что результаты остаются небольшими).

Пример b = 4 , e = 13 и m = 497 представлен снова. Алгоритм проходит шаг 3 тринадцать раз:

• e′ = 1. c = (1 ⋅ 4) mod 497 = 4 mod 497 = 4 .
• е′ = 2. c = (4 ⋅ 4) mod 497 = 16 mod 497 = 16 .
• е′ = 3. c = (16 ⋅ 4) mod 497 = 64 mod 497 = 64 .
• е′ = 4. c = (64 ⋅ 4) mod 497 = 256 mod 497 = 256 .
• е′ = 5. c = (256 ⋅ 4) mod 497 = 1024 mod 497 = 30 .
• е′ = 6. c = (30 ⋅ 4) mod 497 = 120 mod 497 = 120 .
• е′ = 7. c = (120 ⋅ 4) mod 497 = 480 mod 497 = 480 .
• e′ = 8. c = (480 ⋅ 4) mod 497 = 1920 mod 497 = 429 .
• е′ = 9. c = (429 ⋅ 4) mod 497 = 1716 mod 497 = 225 .
• е′ = 10. c = (225 ⋅ 4) mod 497 = 900 mod 497 = 403 .
• е′ = 11. c = (403 ⋅ 4) mod 497 = 1612 mod 497 = 121 .
• е′ = 12. c = (121 ⋅ 4) mod 497 = 484 mod 497 = 484 .
• е′ = 13. c = (484 ⋅ 4) mod 497 = 1936 mod 497 = 445 .

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

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

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

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

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

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

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

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

В таких обозначениях длина e равна n битам. a _i может принимать значение 0 или 1 для любого i такого, что 0 ≤ i < n . По определению, _n − ₁ = 1 .

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

${\displaystyle 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 :

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

Псевдокод

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

функцияmodular_pow (база, показатель, модуль) -  если модуль = 1 , то  возвращает 0. Assert  :: (модуль - 1) * (модуль - 1) не переполняет базу результат := 1 базовый := базовый модуль модуля , пока показатель степени > 0, выполните  if (показатель степени 2 == 1), затем результат := (результат * базовый) модуль модуля показатель степени := показатель >> 1base : = (base * base) модуль возвращаемый результат

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

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

В этом примере основание b возводится в степень e = 13 . Показатель степени равен 1101 в двоичном формате. Имеется четыре двоичных цифры, поэтому цикл выполняется четыре раза со значениями a ₀ = 1, a ₁ = 0, a ₂ = 1 и a ₃ = 1 .

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

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

Шаг 1) бит 1 равен 1, поэтому установите ; ${\displaystyle R\leftarrow R\cdot x{\text{ }}(=b^{1})}$

набор . ${\displaystyle x\leftarrow x^{2}{\text{ }}(=b^{2})}$

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

набор . ${\displaystyle x\leftarrow x^{2}{\text{ }}(=b^{4})}$

Шаг 3) бит 3 равен 1, поэтому установите ; ${\displaystyle R\leftarrow R\cdot x{\text{ }}(=b^{5})}$

набор . ${\displaystyle x\leftarrow x^{2}{\text{ }}(=b^{8})}$

Шаг 4) бит 4 равен 1, поэтому установите ; ${\displaystyle R\leftarrow R\cdot x{\text{ }}(=b^{13})}$

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

Мы закончили : теперь R. ${\displaystyle b^{13}}$

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

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

${\displaystyle R\leftarrow 1\,(=b^{0})}$ и . ${\displaystyle x\leftarrow b=4}$

Шаг 1) бит 1 равен 1, поэтому установите ; ${\displaystyle R\leftarrow R\cdot 4\equiv 4{\pmod {497}}}$

набор . ${\displaystyle x\leftarrow x^{2}{\text{ }}(=b^{2})\equiv 4^{2}\equiv 16{\pmod {497}}}$

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

набор . ${\displaystyle x\leftarrow x^{2}{\text{ }}(=b^{4})\equiv 16^{2}\equiv 256{\pmod {497}}}$

Шаг 3) бит 3 равен 1, поэтому установите ; ${\displaystyle R\leftarrow R\cdot x{\text{ }}(=b^{5})\equiv 4\cdot 256\equiv 30{\pmod {497}}}$

набор . ${\displaystyle x\leftarrow x^{2}{\text{ }}(=b^{8})\equiv 256^{2}\equiv 429{\pmod {497}}}$

Шаг 4) бит 4 равен 1, поэтому установите ; ${\displaystyle R\leftarrow R\cdot x{\text{ }}(=b^{13})\equiv 30\cdot 429\equiv 445{\pmod {497}}}$

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

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

Реализация на Lua

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

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

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

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

Шаг 1) ; бит 1 = 1, поэтому вычислите ; ${\displaystyle r\leftarrow r^{2}\,(=b^{0})}$ ${\displaystyle r\leftarrow r\cdot b\,(=b^{1})}$

Шаг 2) ; бит 2 = 1, поэтому вычислите ; ${\displaystyle r\leftarrow r^{2}\,(=b^{2})}$ ${\displaystyle r\leftarrow r\cdot b\,(=b^{3})}$

Шаг 3) ; бит 3 = 0, поэтому мы закончили этот шаг; ${\displaystyle r\leftarrow r^{2}\,(=b^{6})}$

Шаг 4) ; бит 4 = 1, поэтому вычислите . ${\displaystyle r\leftarrow r^{2}\,(=b^{12})}$ ${\displaystyle r\leftarrow r\cdot b\,(=b^{13})}$

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

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

Обобщения

Матрицы

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

Псевдокод

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

function Matrix_ModExp(Matrix A, int b, int c) is  if b == 0 then  return I // Единичная матрица if (b mod 2 == 1) then  return (A * Matrix_ModExp(A, b - 1, c) ) мод с Матрица D:= Matrix_ModExp(A, b/2, c) вернуть (D * D) мод c

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

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

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

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

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

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

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

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

• Сокращение Монтгомери , для вычисления остатка, когда модуль очень велик.
• Умножение Кочанского , сериализуемый метод вычисления остатка, когда модуль очень велик
• Сокращение Барретта , алгоритм вычисления остатка, когда модуль очень велик.

Рекомендации

1. «Слабый Диффи-Хеллман и атака затора». сайт слабыйdh.org . Проверено 3 мая 2019 г.
2. Шнайер 1996, с. 244.
3. И. Л. Марков, М. Саиди (2012). «Квантовые схемы с постоянной оптимизацией для модульного умножения и возведения в степень». Квантовая информация и вычисления . 12 (5–6): 0361–0394. arXiv : 1202.6614 . Бибкод : 2012arXiv1202.6614M. дои : 10.26421/QIC12.5-6-1. S2CID  16595181.

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

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