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

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

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

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

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

в = б ^и мод м = d ^{− и} mod m , где e < 0 и b ⋅ d ≡ 1 (mod m ) .

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

Прямой метод

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

с ≡ 4 ¹³ (против 497)

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

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

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

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

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

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

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

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

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

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

Выходные данные Модульный показатель c , где c = b ^и мод м

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

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

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

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

(e′ =   1)   c = (4 ⋅ 1) mod 497 = 4 mod 497 = 4

(e′ =   2)   c = (4 ⋅ 4) mod 497 = 16 mod 497 = 16

(e′ =   3)   c = (4 ⋅ 16) mod 497 = 64 mod 497 = 64

(e′ =   4)   c = (4 ⋅ 64) mod 497 = 256 mod 497 = 256

(e′ =   5)   c = (4 ⋅ 256) mod 497 = 1024 mod 497 = 30

(e′ =   6)   c = (4 ⋅ 30) mod 497 = 120 mod 497 = 120

(e′ =   7)   c = (4 ⋅ 120) mod 497 = 480 mod 497 = 480

(e′ =   8)   c = (4 ⋅ 480) mod 497 = 1920 mod 497 = 429

(e′ =   9)   c = (4 ⋅ 429) mod 497 = 1716 mod 497 = 225

(e′ = 10)   c = (4 ⋅ 225) mod 497 = 900 mod 497 = 403

(e′ = 11)   c = (4 ⋅ 403) mod 497 = 1612 mod 497 = 121

(e′ = 12)   c = (4 ⋅ 121) mod 497 = 484 mod 497 = 484

(e′ = 13)   c = (4 ⋅ 484) 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 можно записать как:

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

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

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

$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}}$

Псевдокод

Ниже приведен пример псевдокода на основе «Прикладной криптографии» Брюса Шнайера . Входные данные base , exdependent и modulus соответствуют 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 > 0 do
        if (exponent mod 2 == 1) then
            result := (result * base) mod modulus
        exponent := exponent >> 1
        base := (base * base) mod modulus
    return result

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

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

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

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

$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 exdependent ) . При работе с большими значениями экспоненты это дает существенный выигрыш в скорости по сравнению с двумя предыдущими алгоритмами, время которых равно O( экспонента ) . Например, если показатель степени был 2 ²⁰ = 1048576, этот алгоритм будет иметь 20 шагов вместо 1048576 шагов.

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

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

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

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

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

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

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

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

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

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

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

Обобщения

Матрицы

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

Псевдокод

Рекурсивный алгоритм для ModExp(A, b, c) = А ^б 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 .

и квантовое модульное возведение

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

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

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

• Python Встроенный pow() Функция (возведения в степень) [1] принимает необязательный третий аргумент, модуль
• .NET Framework BigInteger в классе есть ModPow() метод выполнения модульного возведения в степень
• Java ​ java.math.BigInteger в классе есть modPow() метод выполнения модульного возведения в степень
• MATLAB ​ powermod функция из Symbolic Math Toolbox
• Wolfram Language имеет PowerMod. функцию
• Перл ​ Math::BigInt модуль имеет bmodpow() метод [2] для выполнения модульного возведения в степень
• У Раку есть встроенный распорядок дня. expmod.
• Иди ​ big.Int тип содержит Exp() (возведение в степень) [3], третий параметр которого, если он не равен нулю, является модулем
• Библиотека PHP BC Math имеет bcpowmod() функция [4] для выполнения модульного возведения в степень
• Библиотека GNU Multiple Precision Arithmetic Library (GMP) содержит mpz_powm() функция [5] для выполнения модульного возведения в степень
• Пользовательская функция @PowerMod() для FileMaker Pro (с RSA ) примером 1024-битного шифрования
• Руби ​ 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-апплет быстрого модульного возведения в степень
• Гордон, Дэниел М. (1998). «Обзор методов быстрого возведения в степень» (PDF) . Журнал алгоритмов . 27 (1). Эльзевир Б.В.: 129–146. дои : 10.1006/jagm.1997.0913 . ISSN   0196-6774 .