Возведение в степень по модулю

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

Возведение в степень по модулю — это вычисление остатка от деления натурального числа a (основание), возведенного в степень n (показатель степени), на натуральное число m (модуль). Обозначается:

$\text{[math]}$ $\text{[math]}$ $c\equiv a^{n}{\pmod {m}}$ $c\equiv a^{n}{\pmod {m}}$

Например, пусть нам даны a = 5, n = 3 и m = 13, тогда решение c = 8 — это остаток от деления $\text{[math]}$ $\text{[math]}$ $5^{3}$ $5^{3}$ на 13.

Если a, n и m неотрицательны и a < m, то единственное решение c существует, причем 0 ⩽ c < m.

Возведение в степень по модулю может быть выполнено и с отрицательным показателем степени n. Для этого необходимо найти число d, обратное числу a по модулю m. Это легко сделать с помощью алгоритма Евклида. Таким образом,

\text{[math]}

c\equiv a^{n}\equiv d^{\left|n\right|}{\pmod {m}}

c\equiv a^{n}\equiv d^{\left|n\right|}{\pmod {m}}

, где n < 0 и

\text{[math]}

a\cdot d\equiv 1{\pmod {m}}

a\cdot d\equiv 1{\pmod {m}}

Возвести в степень по модулю довольно легко, даже при больших входных значениях. А вот вычисление дискретного логарифма, то есть нахождение показателя степени n при заданных a, c и m, намного сложнее. Такое одностороннее поведение функции делает её кандидатом для использования в криптографических алгоритмах.

Простой методПравить

Самый простой способ возвести в степень по модулю — это непосредственное вычисление числа $\text{[math]}$ $\text{[math]}$ $a^{n}$ , а затем нахождение остатка от деления этого числа на m. Рассчитаем c, если a = 4, n = 13 и m = 497:

\text{[math]}

c\equiv 4^{13}{\pmod {497}}

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

a имеет только один символ в длину, n имеет только два символа в длину, а значение aⁿ имеет 8 символов в длину.

В криптографии a часто имеет 256 двоичных разрядов (77 десятичных цифр). Рассмотрим a = 5 × 10⁷⁶ и n = 17, они оба принимают вполне реальные значения. В этом примере a 77 символов в длину, а n — 2 символа в длину, но результат возведения в степень имеет 1304 символов в длину. Такие расчеты возможны на современных компьютерах, но скорость вычисления таких чисел невелика. Значения a и n увеличивают, чтобы добиться большего уровня безопасности, из-за чего значение aⁿ становится громоздким.

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

Метод, эффективно использующий памятьПравить

Данный метод требует большего числа операций, по сравнению с предыдущим. Однако, так как памяти требуется меньше и операции занимают меньшее время, то алгоритм работает гораздо быстрее.

Данный алгоритм основывается на том факте, что для заданных a и b следующие 2 уравнения эквивалентны:

\text{[math]}

c\equiv (a\cdot b){\pmod {m}}

\text{[math]}

c\equiv (a{\pmod {m}}\cdot b{\pmod {m}}){\pmod {m}}

Алгоритм следующий:

Пусть c = 1, n′ = 0.
Увеличим n′ на 1.
Установим $\text{[math]}$ $\text{[math]}$ $c\equiv (b\cdot c){\pmod {m}}$ .
Если n′ < n, возвращаемся к шагу 2. В противном случае, c содержит правильный ответ $\text{[math]}$ $\text{[math]}$ $c\equiv b^{n}{\pmod {m}}$ .

При каждом проходе шага 3, выражение $\text{[math]}$ $\text{[math]}$ $c\equiv b^{n'}{\pmod {m}}$ верно. После того, как шаг 3 был выполнен n раз, в c содержится искомое значение. Таким образом, алгоритм основывается на подсчитывании n′ до тех пор, пока n′ не достигнет n при умножении c (из предыдущей итерации цикла) на b по модулю m в текущей итерации цикла (чтобы гарантировать, что результат будет маленьким).

Например, b = 4, n = 13 и m = 497. Алгоритм проходит через шаг 3 тринадцать раз.

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

Конечный ответ c равняется 445, как и в первом методе.

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

В псевдокоде это выглядит так:

 function modular_pow(base, index_n, modulus)
    c := 1
    for index_n_prime = 1 to index_n 
        c := (c * base) mod modulus
    return c

Алгоритм быстрого возведения в степень по модулюПравить

Применяя алгоритм быстрого возведения в степень для 595⁷⁰³ (mod 991):

Имеем n = 703 =(1010111111)₂ = 2⁰+2¹+2²+2³+2⁴+2⁵+ 2⁷+2⁹.

595⁷⁰³ = ((((((((595²)²*595)²)²* 595)²*595)²* 595)²*595)²*595)²*595

= (((((((238²*595)²)²* 595)²*595)²* 595)²*595)²*595)²*595

= ((((((261²)²* 595)²*595)²* 595)²*595)²*595)²*595

= (((((733²* 595)²*595)²* 595)²*595)²*595)²*595

= (((((167* 595)²*595)²* 595)²*595)²*595)²*595

= ((((265²*595)²* 595)²*595)²*595)²*595

= (((342²* 595)²*595)²*595)²*595

= ((605²*595)²*595)²*595

= (733²*595)²*595

= (167*595)²*595

= 265²*595

= 342.

Схема «справа налево»Править

Другим вариантом является схема типа «справа налево». Её можно представить следующей формулой:

$\text{[math]}$ $\text{[math]}$ $d=a^{n}=$

$\text{[math]}$ $\text{[math]}$ $=a^{\sum _{i=0}^{k}m_{i}*2^{i}}=$

$\text{[math]}$ $\text{[math]}$ $=a^{m_{0}}*a^{2m_{1}}*a^{2^{2}*m_{2}}*...*a^{2^{k}*m_{k}}=$

$\text{[math]}$ $\text{[math]}$ $=a^{m_{0}}*(a^{2})^{m_{1}}*(a^{2^{2}})^{m_{2}}*...*(a^{2^{k}})^{m_{k}}=$

$\text{[math]}$ $\text{[math]}$ $=\prod _{i=0}^{k}{(a^{2^{i}})^{m_{i}}}$

Пример. Посчитаем с помощью простой двоичной схемы возведения в степень типа «справа налево» значение 175²³⁵ mod 257.

Представим число 235 в двоичном виде:

235₁₀ = 11101011₂.

1. d := 1 * 175 mod 257 = 175,

t := 175² mod 257 = 42;

2. d := 175 * 42 mod 257 = 154,

t := 42² mod 257 = 222;

3. t := 222² mod 257 = 197;

4. d := 154 * 197 mod 257 = 12,

t := 197² mod 257 = 2;

5. t := 2² mod 257 = 4;

6. d := 12 * 4 mod 257 = 48,

t := 4² mod 257 = 16;

7. d := 48 * 16 mod 257 = 254,

t := 16² mod 257 = 256;

8. d := 254 * 256 mod 257 = 3,

9. → d = 3. Потребовалось 7 возведений в квадрат и 6 умножений.

МатрицыПравить

Числа Фибоначчи по модулю n можно эффективно найти путём вычисления A^m (mod n) для определенного m и определенной матрицы A. Перечисленные методы легко могут быть применены в данном алгоритме. Это обеспечивает хороший тест простоты для больших чисел n (500 бит).

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

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

matrix ModExp(matrix A, int b, int c) {
   if (b == 0) return I; // Единичная матрица
   if (b % 2 == 1) return (A * ModExp(A, b-1, c)) % c; 
   matrix D = ModExp(A, b/2, c);
   return (D * D) % c;
}

Конечность циклических группПравить

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

Реверсивное и квантовое возведение в степень по модулюПравить

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

В языках программированияПравить

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

Python содержит встроенную функцию pow()^[4]
.NET Framework содержит BigInteger class, включающий в себя ModPow()^[5]
Java содержит java.math.BigInteger class, включающий в себя modPow()^[6]
Perl содержит Math::BigInt модуль, включающий в себя метод bmodpow()^[7]
Go содержит big.Int тип, включающий в себя метод Exp()^[8]
PHP содержит BC Math библиотеку, включающую в себя функцию bcpowmod()^[9]
GNU Multi-Precision Library (GMP) библиотека содержит функцию mpz_powm()^[10]

См. такжеПравить

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

ПримечанияПравить

↑ Теоретический минимум и алгоритмы цифровой подписи, 2010, с. 56-57.
↑ Schneier 1996, p. 244.
↑ Igor L. Markov, Mehdi Saeedi, «Constant-Optimized Quantum Circuits for Modular Multiplication and Exponentiation», Quantum Information and Computation, Vol. 12, No. 5&6, pp. 0361-0394, 2012.http://arxiv.org/abs/1202.6614
↑ Built-in Functions: official site (англ.). Дата обращения: 28 декабря 2014. Архивировано 1 января 2015 года.
↑ BigInteger.ModPow Method: official site (англ.). Дата обращения: 24 декабря 2014. Архивировано 28 декабря 2014 года.
↑ Class BigInteger: official site (англ.). Дата обращения: 28 декабря 2014. Архивировано 31 декабря 2014 года.
↑ Math::BigInt: official site (англ.). Дата обращения: 24 декабря 2014. Архивировано 5 июня 2020 года.
↑ Package big: official site (англ.). Дата обращения: 28 декабря 2014. Архивировано 2 января 2015 года.
↑ bcpowmod: official site (англ.). Дата обращения: 28 декабря 2014. Архивировано 28 декабря 2014 года.
↑ Exponentiation Functions: official site (англ.). Дата обращения: 28 декабря 2014. Архивировано 28 декабря 2014 года.

ЛитератураПравить

Молдовян Н. А. Теоретический минимум и алгоритмы цифровой подписи. — СПб.: БВХ-Петербург: Книжный Дом «ЛИБРОКОМ», 2010. — 304 с. — ISBN 978-5-9775-0585-7.
Schneier, Bruce. Applied Cryptography: Protocols, Algorithms, and Source Code in C, Second Edition. — 2nd. — Wiley, 1996. — ISBN 978-0-471-11709-4.
Валицкас А. И. Конспект лекций по дисциплине: Элементы абстрактной и компьютерной алгебры. // Тобольск, ТГПИ им. Д. И. Менделеева, 2004.
Габидулин Э. М, Кшевецкий А. С, Колыбельников А. И, Владимиров С. М. Защита информации (Учебное пособие): Возведение в степень по модулю (стр. 253) // МФТИ, 2014.

[_7e8222600cd9f359-1] Теоретический минимум и алгоритмы цифровой подписи, 2010, с. 56-57.

[schneier96p244-2] Schneier 1996, p. 244.

[3] Igor L. Markov, Mehdi Saeedi, «Constant-Optimized Quantum Circuits for Modular Multiplication and Exponentiation», Quantum Information and Computation, Vol. 12, No. 5&6, pp. 0361-0394, 2012.http://arxiv.org/abs/1202.6614

[4] Built-in Functions: official site (англ.). Дата обращения: 28 декабря 2014. Архивировано 1 января 2015 года.

[5] BigInteger.ModPow Method: official site (англ.). Дата обращения: 24 декабря 2014. Архивировано 28 декабря 2014 года.

[6] Class BigInteger: official site (англ.). Дата обращения: 28 декабря 2014. Архивировано 31 декабря 2014 года.

[7] Math::BigInt: official site (англ.). Дата обращения: 24 декабря 2014. Архивировано 5 июня 2020 года.

[8] Package big: official site (англ.). Дата обращения: 28 декабря 2014. Архивировано 2 января 2015 года.

[9] wmod: official site (англ.). Дата обращения: 28 декабря 2014. Архивировано 28 декабря 2014 года.

[10] Exponentiation Functions: official site (англ.). Дата обращения: 28 декабря 2014. Архивировано 28 декабря 2014 года.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]