Модульное возведение в степень - Modular exponentiation - Wikipedia

Модульное возведение в степень это тип возведение в степень выполнено на модуль. Это полезно в Информатика, особенно в области криптография с открытым ключом.

Операция модульного возведения в степень вычисляет остаток, когда целое число б (база) поднята до е-я степень (показатель степени), б^е, делится на положительное число м (модуль). В символах с учетом базы б, экспонента е, а модуль м, модульное возведение в степень c является: c = б^е мод м. Из определения c, следует, что 0 ≤ c < м.

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

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

c = б^е мод м = d^−е мод м, куда е < 0 и б ⋅ d ≡ 1 (мод м).

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

Прямой метод

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

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

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

Обратите внимание, что б имеет длину всего одну цифру и это е всего две цифры в длину, но значение б^е состоит из 8 цифр.

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

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

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

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

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

(а ⋅ б) мод м = [(а мод м) ⋅ (б мод м)] мод м

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

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

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

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

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

Окончательный ответ на c поэтому 445, как и в первом методе.

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

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

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

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

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

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

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

В таких обозначениях длина из е является п биты. а_я может принимать значение 0 или 1 для любого я такой, что 0 ≤ я < п. По определению, а_{п − 1} = 1.

Значение б^е тогда можно записать как:

${\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] Входы основание, показатель степени, и модуль соответствуют б, е, и м в приведенных выше уравнениях.

функция modular_pow (основание, показатель степени, модуль) является    если модуль = 1 тогда        возвращаться 0    Утверждать :: (модуль - 1) * (модуль - 1) не выходит за пределы базового результата: = 1 основание: = основание мод модуль пока экспонента> 0 делать        если (показатель мод 2 == 1) тогда            результат: = (результат * база) мод показатель модуля: = показатель >> 1 основание: = (основание * основание) мод модуль возвращаться результат

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

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

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

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

${\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, поэтому не сбрасывать р;

набор ${\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})}$;

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

Мы сделали: р сейчас ${\displaystyle b^{13}}$.

Вот приведенный выше расчет, в котором мы вычисляем б = 4 к власти е = 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, поэтому не сбрасывать р;

набор ${\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}}}$;

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

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

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

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

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

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

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

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

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

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

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

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

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

Обобщения

Матрицы

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

Псевдокод

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

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

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

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

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

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

Программные реализации

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

• Python встроенный pow () (возведение в степень) функция [1] принимает необязательный третий аргумент, модуль
• .NET Framework с BigInteger класс имеет ModPow () метод выполнения модульного возведения в степень
• Ява с java.math.BigInteger класс имеет modPow () метод выполнения модульного возведения в степень
• Wolfram Language имеет PowerMod функция
• Perl с Math :: BigInt модуль имеет bmodpow () метод [2] выполнить модульное возведение в степень
• Раку имеет встроенную программу expmod.
• Идти с big.Int тип содержит Опыт () (возведение в степень) метод [3] чей третий параметр, если не равен нулю, является модулем
• PHP в библиотеке BC Math есть bcpowmod () функция [4] выполнить модульное возведение в степень
• В Библиотека арифметики множественной точности GNU (GMP) библиотека содержит mpz_powm () функция [5] выполнить модульное возведение в степень
• Пользовательская функция @PowerMod () за FileMaker Pro (с 1024-битной ЮАР пример шифрования)
• Рубин с openssl пакет имеет OpenSSL :: BN # mod_exp метод [6] выполнить модульное возведение в степень.
• В HP Prime В калькуляторе есть функция CAS.powmod () [7] выполнить модульное возведение в степень. Для a ^ b mod c a не может быть больше 1 EE 12. Это максимальная точность большинства калькуляторов HP, включая Prime.

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

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

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

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

внешняя ссылка

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