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

редактировать

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

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

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

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

c = b e mod m = d - e mod m, где e lt;0 и b ⋅ d ≡ 1 (mod m).

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

СОДЕРЖАНИЕ

  • 1 Прямой метод
  • 2 Метод с эффективным использованием памяти
  • 3 Бинарный метод с написанием справа налево
    • 3.1 Псевдокод
    • 3.2 Реализация на Lua
  • 4 Бинарный метод слева направо
    • 4.1 Минимальные умножения
  • 5 Обобщения
    • 5.1 Матрицы
    • 5.2 Конечные циклические группы
    • 5.3 Обратимое и квантовое модульное возведение в степень
  • 6 Программные реализации
  • 7 См. Также
  • 8 ссылки
  • 9 Внешние ссылки

Прямой метод

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

c ≡ 4 13 (мод. 497)

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

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

В сильной криптографии b часто составляет не менее 1024 бит. Рассмотрим b = 5 × 10 76 и 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 ′ lt; 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) в этом методе.

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

function modular_pow(base, exponent, modulus) is if modulus = 1 then return 0 c := 1 for e_prime = 0 to exponent-1 do c := (c * base) mod modulus return c

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

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

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

е знак равно я знак равно 0 п - 1 а я 2 я {\ Displaystyle е = \ сумма _ {я = 0} ^ {п-1} а_ {я} 2 ^ {я}}

В таком обозначениях длиной от й являются п бит. a i может принимать значение 0 или 1 для любого i такого, что 0 ≤ i lt; n. По определению a n - 1 = 1.

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

б е знак равно б ( я знак равно 0 п - 1 а я 2 я ) знак равно я знак равно 0 п - 1 б а я 2 я {\ 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:

c я знак равно 0 п - 1 б а я 2 я ( мод м ) {\ Displaystyle с \ эквив \ прод _ {я = 0} ^ {п-1} Ь ^ {а_ {я} 2 ^ {я}} {\ pmod {м}}}

Псевдокод

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

function modular_pow(base, exponent, modulus) is if modulus = 1 then return 0 Assert  :: (modulus - 1) * (modulus - 1) does not overflow base result := 1 base := base mod modulus while exponent gt; 0 do if (exponent mod 2 == 1) then result := (result * base) mod modulus exponent := exponent gt;gt; 1 base := (base * base) mod modulus return result

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

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

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

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

р 1 ( знак равно б 0 )  а также  Икс б {\ Displaystyle R \ leftarrow 1 \, (= b ^ {0}) {\ text {и}} x \ leftarrow b}.
Шаг 1) бит 1 равен 1, поэтому устанавливается ; р р Икс   ( знак равно б 1 ) {\ Displaystyle R \ leftarrow R \ cdot x {\ text {}} (= b ^ {1})}
набор. Икс Икс 2   ( знак равно б 2 ) {\ displaystyle x \ leftarrow x ^ {2} {\ text {}} (= b ^ {2})}
Шаг 2) бит 2 равен 0, поэтому не сбрасывайте R ;
набор. Икс Икс 2   ( знак равно б 4 ) {\ displaystyle x \ leftarrow x ^ {2} {\ text {}} (= b ^ {4})}
Шаг 3) бит 3 равен 1, поэтому устанавливается ; р р Икс   ( знак равно б 5 ) {\ Displaystyle R \ leftarrow R \ cdot x {\ text {}} (= b ^ {5})}
набор. Икс Икс 2   ( знак равно б 8 ) {\ displaystyle x \ leftarrow x ^ {2} {\ text {}} (= b ^ {8})}
Шаг 4) бит 4 равен 1, поэтому устанавливается ; р р Икс   ( знак равно б 13 ) {\ Displaystyle R \ leftarrow R \ cdot x {\ text {}} (= b ^ {13})}
Это последний шаг, поэтому нам не нужно возводить x в квадрат.

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

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

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

р 1 ( знак равно б 0 ) {\ Displaystyle R \ leftarrow 1 \, (= Ь ^ {0})} и. Икс б знак равно 4 {\ displaystyle x \ leftarrow b = 4}
Шаг 1) бит 1 равен 1, поэтому устанавливается ; р р 4 4 ( мод 497 ) {\ Displaystyle R \ leftarrow R \ CDOT 4 \ Equ 4 {\ pmod {497}}}
набор. Икс Икс 2   ( знак равно б 2 ) 4 2 16 ( мод 497 ) {\ Displaystyle х \ leftarrow х ^ {2} {\ текст {}} (= Ь ^ {2}) \ эквив 4 ^ {2} \ эквив 16 {\ pmod {497}}}
Шаг 2) бит 2 равен 0, поэтому не сбрасывайте R ;
набор. Икс Икс 2   ( знак равно б 4 ) 16 2 256 ( мод 497 ) {\ displaystyle x \ leftarrow x ^ {2} {\ text {}} (= b ^ {4}) \ Equiv 16 ^ {2} \ Equiv 256 {\ pmod {497}}}
Шаг 3) бит 3 равен 1, поэтому устанавливается ; р р Икс   ( знак равно б 5 ) 4 256 30 ( мод 497 ) {\ Displaystyle R \ leftarrow R \ cdot x {\ text {}} (= b ^ {5}) \ Equ 4 \ cdot 256 \ Equ 30 {\ pmod {497}}}
набор. Икс Икс 2   ( знак равно б 8 ) 256 2 429 ( мод 497 ) {\ displaystyle x \ leftarrow x ^ {2} {\ text {}} (= b ^ {8}) \ Equiv 256 ^ {2} \ Equiv 429 {\ pmod {497}}}
Шаг 4) бит 4 равен 1, поэтому устанавливается ; р р Икс   ( знак равно б 13 ) 30 429 445 ( мод 497 ) {\ Displaystyle R \ leftarrow R \ CDOT х {\ текст {}} (= Ь ^ {13}) \ экв 30 \ CDOT 429 \ эквив 445 {\ pmod {497}}}

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

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

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

function modPow(b, e, m) if m == 1 then return 0 else local r = 1 b = b % m while e gt; 0 do if e % 2 == 1 then r = (r*b) % m end b = (b*b) % m e = e gt;gt; 1 --use 'e = math.floor(e / 2)' on Lua 5.2 or older end return r end end

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

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

Инициализировать результат 1:. р 1 ( знак равно б 0 ) {\ Displaystyle г \ leftarrow 1 \, (= Ь ^ {0})}

Шаг 1) ; бит 1 = 1, поэтому вычислить ; р р 2 ( знак равно б 0 ) {\ Displaystyle г \ leftarrow г ^ {2} \, (= Ь ^ {0})} р р б ( знак равно б 1 ) {\ displaystyle r \ leftarrow r \ cdot b \, (= b ^ {1})}
Шаг 2) ; бит 2 = 1, поэтому вычислить ; р р 2 ( знак равно б 2 ) {\ Displaystyle г \ leftarrow г ^ {2} \, (= Ь ^ {2})} р р б ( знак равно б 3 ) {\ displaystyle r \ leftarrow r \ cdot b \, (= b ^ {3})}
Шаг 3) ; бит 3 = 0, поэтому мы закончили этот шаг; р р 2 ( знак равно б 6 ) {\ Displaystyle г \ leftarrow г ^ {2} \, (= Ь ^ {6})}
Шаг 4) ; бит 4 = 1, поэтому вычислим. р р 2 ( знак равно б 12 ) {\ Displaystyle г \ leftarrow г ^ {2} \, (= Ь ^ {12})} р р б ( знак равно б 13 ) {\ displaystyle r \ leftarrow r \ cdot b \, (= b ^ {13})}

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

В искусстве компьютерного программирования, Vol. 2, Получисловые алгоритмы, стр. 463, Дональд Кнут отмечает, что вопреки некоторым утверждениям, этот метод не всегда дает минимально возможное количество умножений. Наименьший контрпример для степени 15, когда двоичный метод требует шести умножений. Вместо этого сформируйте x 3 в два умножения, затем x 6, возведя в квадрат x 3, затем x 12, возведя в квадрат x 6, и, наконец, x 15, умножив x 12 и 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 // The identity matrix if (b mod 2 == 1) then return (A * Matrix_ModExp(A, b - 1, c)) mod c Matrix D := Matrix_ModExp(A, b / 2, c) return (D * D) mod c

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

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

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

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

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

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

  • Встроенная 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.

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

использованная литература

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

Последняя правка сделана 2023-08-11 12:30:16
Содержание доступно по лицензии CC BY-SA 3.0 (если не указано иное).
Обратная связь: support@alphapedia.ru
Соглашение
О проекте