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

Эта статья требует дополнительных ссылок для проверки . Пожалуйста, помогите улучшить эту статью , добавив цитаты из надежных источников . Материал, не полученный от источника, может быть оспорен и удален. Найти источники:  «Модульное возведение в степень»  -  новости  · газеты  · книги  · ученый  · JSTOR ( февраль 2018 г. ) ( Узнайте, как и когда удалить это сообщение шаблона )

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

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

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

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

c = b ^e mod m = d ^{- e} mod m , где e <0 и b ⋅ d ≡ 1 (mod m ) .

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

Прямой метод [ править ]

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

c ≡ 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 ) умножений.

Эффективный с памятью метод [ править ]

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

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

( a ⋅ b ) 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 .
• e ′ = 2. c = (4 ⋅ 4) mod 497 = 16 mod 497 = 16 .
• e ′ = 3. c = (16 ⋅ 4) mod 497 = 64 mod 497 = 64 .
• e ′ = 4. c = (64 ⋅ 4) mod 497 = 256 mod 497 = 256 .
• e ′ = 5. c = (256 4) mod 497 = 1024 mod 497 = 30 .
• e ′ = 6. c = (30 4) mod 497 = 120 mod 497 = 120 .
• e ′ = 7. c = (120 4) mod 497 = 480 mod 497 = 480 .
• e ′ = 8. c = (480 4) mod 497 = 1920 mod 497 = 429 .
• e ′ = 9. c = (429 ⋅ 4) mod 497 = 1716 mod 497 = 225 .
• e ′ = 10. c = (225 4) mod 497 = 900 mod 497 = 403 .
• e ′ = 11. c = (403 4) mod 497 = 1612 mod 497 = 121 .
• e ′ = 12. c = (121 4) mod 497 = 484 mod 497 = 484 .
• e ′ = 13. c = (484 ⋅ 4) mod 497 = 1936 mod 497 = 445 .

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

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

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

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

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

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

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

${\ Displaystyle е = \ сумма _ {я = 0} ^ {п-1} а_ {я} 2 ^ {я}}$

В таком обозначениях длиной от й являются п бит. a _i может принимать значение 0 или 1 для любого i, такого что 0 ≤ i < n . По определению a _{n - 1} = 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 с \ эквив \ прод _ {я = 0} ^ {п-1} Ь ^ {а_ {я} 2 ^ {я}} {\ pmod {м}}}$

Псевдокод [ править ]

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

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

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

Первая строка кода просто выполняет умножение . Если${\ displaystyle \ prod _ {я = 0} ^ {n-1} b ^ {a_ {i} 2 ^ {i}} {\ pmod {m}}}$равен нулю, код не выполняется, так как это эффективно умножает текущую сумму на единицу. Есливместо единицы, переменная base (содержащая значение 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 {и}} 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 (логарифмическая экспонента ) . При работе с большими значениями экспоненты это дает существенное преимущество в скорости по сравнению с двумя предыдущими алгоритмами, время которых равно O ( экспонента ) . Например, если показатель степени равен 2 ²⁰ = 1048576, этот алгоритм будет иметь 20 шагов вместо 1048576 шагов.

Реализация в Lua [ править ]

Функция modPow (Ь, е, м) , если т == 1 , то  возвращает 0 остальное  локальное R = 1 b = b% m в то время как e> 0 делать,  если e% 2 == 1, то г = (г * б)% м конец e = e >> 1 - используйте 'e = math.floor (e / 2)' в Lua 5.2 или старше б = (Ь ^ 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, Получисловые алгоритмы , стр. 463, Дональд Кнут отмечает, что вопреки некоторым утверждениям, этот метод не всегда дает минимально возможное количество умножений. Наименьший контрпример для степени 15, когда двоичный метод требует шести умножений. Вместо этого сформируйте x ³ в два умножения, затем x ⁶ , возведя в квадрат x ³ , затем x ¹² , возведя в квадрат x ⁶ , и, наконец, x ¹⁵ , умножив x ¹² и x ^3., тем самым добиваясь желаемого результата всего за пять умножений. Тем не менее, за этим следуют многие страницы, описывающие, как в целом могут быть созданы такие последовательности.

Обобщения [ править ]

Матрицы [ править ]

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

Псевдокод

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

function Matrix_ModExp (Matrix A, int b, int c) is  if b == 0 then  return I // Идентификационная матрица if (b mod 2 == 1) затем  return (A * Matrix_ModExp (A, b - 1, c) ) мод c Матрица D: = Matrix_ModExp (A, b / 2, c) return (D * D) mod c

Конечные циклические группы [ править ]

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

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

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

Программные реализации [ править ]

Реализация алгоритма Викибука имеет страницу по теме: Модульное возведение в степень

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

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

См. Также [ править ]

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

Ссылки [ править ]

Внешние ссылки [ править ]

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