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

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

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

<math>c \equiv b^n \pmod{m}</math>

Например, пусть нам даны ''b'' = 5, n = 3 и ''m'' = 13, тогда решение ''c'' = 8 — это остаток от деления <math>5^3</math> на 13.

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

Возведение в степень по модулю может быть выполнено и с отрицательным показателем степени n. Для этого необходимо найти число ''d'', обратное числу ''b'' по модулю ''m''. Это легко сделать с помощью [[алгоритм Евклида|алгоритма Евклида]]. Таким образом,<br />
: <math>c \equiv b^{n} \equiv d^{\left|n\right|} \pmod{m}</math> , где n < 0 и <math>b \cdot d \equiv 1 \pmod{m}</math>

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

== Простой метод ==

Самый простой способ возвести в степень по модулю — это непосредственное вычисление числа <math> b^n </math>, а затем нахождение остатка от деления этого числа на ''m''. Рассчитаем ''c'', если ''b'' = 4, n = 13 и ''m'' = 497:<br />
: <math>c \equiv 4^{13} \pmod{497}</math>

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

Следует заметить, что ''b'' имеет только один символ в длину, n имеет только два символа в длину, а значение ''b''<sup>''n''</sup> имеет 8 символов в длину.

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

Время, необходимое для возведения в степень, зависит от операционной системы и процессора. Описанный выше способ требует [[«O» большое и «o» малое|O]](''e''<sup>''n''</sup>) умножений.

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

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

Данный алгоритм основывается на том факте, что для заданных ''a'' и ''b'' следующие 2 уравнения эквивалентны:<br />
: <math>c \equiv (a \cdot b) \pmod{m}</math>
: <math>c \equiv (a \cdot (b\ (\mbox{mod}\ m))) \pmod{m}</math>

Алгоритм следующий:
# Пусть ''c'' = 1, ''n′'' = 0.
# Увеличим ''n′'' на 1.
# Установим <math>c \equiv (b \cdot c) \pmod{m}</math>.
# Если ''n′'' &lt; n, возвращаемся к шагу 2. В противном случае, ''c'' содержит правильный ответ <math>c \equiv b^n \pmod{m}</math>.

Следует отметить, что при каждом проходе шага 3, выражение <math>c \equiv b^{n'} \pmod{m}</math> верно. После того, как шаг 3 был выполнен n раз, в ''c'' содержится искомое значение. Таким образом, алгоритм основывается на подсчитывании ''n′'' до тех пор, пока ''n′'' не достигнет ''e'' и умножении на ''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(''e′<sup>n</sup>'') умножений для завершения. Однако, так как числа используемые в этих расчетах намного меньше, то время выполнения данного алгоритма уменьшается.

В псевдокоде это выглядит так:
 
  '''function''' modular_pow(base, index_n, modulus)
     c := 1
     '''for''' index_n_prime = 1 '''to''' index_n 
         c := (c * base) '''mod''' modulus
     '''return''' c

== Алгоритм быстрого возведения в степень по модулю ==
{{Основной источник|{{sfn|Теоретический минимум и алгоритмы цифровой подписи|2010|с = 56-57}}}}
Применяя алгоритм быстрого возведения в степень для '''595<sup>703</sup>''' (mod '''991'''):

Имеем n = 703 =(1010111111)<sub>2</sub> = 2<sup>0</sup>+2<sup>1</sup>+2<sup>2</sup>+2<sup>3</sup>+2<sup>4</sup>+2<sup>5</sup>+ 2<sup>7</sup>+2<sup>9</sup>.

'''595<sup>703</sup> '''= ((((((((595<sup>2</sup>)<sup>2</sup>*595)<sup>2</sup>)<sup>2</sup>* 595)<sup>2</sup>*595)<sup>2 </sup>* 595)<sup>2</sup>*595)<sup>2</sup>*595)<sup>2</sup>*595

<nowiki>=</nowiki> (((((((238<sup>2</sup>*595)<sup>2</sup>)<sup>2</sup>* 595)<sup>2</sup>*595)<sup>2 </sup>* 595)<sup>2</sup>*595)<sup>2</sup>*595)<sup>2</sup>*595

<nowiki>=</nowiki> ((((((261<sup>2</sup>)<sup>2</sup>* 595)<sup>2</sup>*595)<sup>2 </sup>* 595)<sup>2</sup>*595)<sup>2</sup>*595)<sup>2</sup>*595

<nowiki>=</nowiki> (((((733<sup>2</sup>* 595)<sup>2</sup>*595)<sup>2 </sup>* 595)<sup>2</sup>*595)<sup>2</sup>*595)<sup>2</sup>*595

<nowiki>=</nowiki> (((((167* 595)<sup>2</sup>*595)<sup>2 </sup>* 595)<sup>2</sup>*595)<sup>2</sup>*595)<sup>2</sup>*595

<nowiki>=</nowiki> ((((265<sup>2</sup>*595)<sup>2 </sup>* 595)<sup>2</sup>*595)<sup>2</sup>*595)<sup>2</sup>*595

<nowiki>=</nowiki> (((342<sup>2 </sup>* 595)<sup>2</sup>*595)<sup>2</sup>*595)<sup>2</sup>*595

<nowiki>=</nowiki> ((605<sup>2</sup>*595)<sup>2</sup>*595)<sup>2</sup>*595

<nowiki>=</nowiki> (733<sup>2</sup>*595)<sup>2</sup>*595

<nowiki>=</nowiki> (167*595)<sup>2</sup>*595

<nowiki>=</nowiki> 265<sup>2</sup>*595

<nowiki>=</nowiki> '''342'''.

== Схема «справа налево» ==
{{Основной источник|<ref name="schneier96p244">[[#Schneier96|Schneier 1996]], p. 244.</ref>}}
Другим вариантом является схема типа «справа налево». Её можно представить следующей формулой:

<math>d = a^n = </math>

<math>= a^{\sum_{i=0}^k m_i* 2^i} = </math>

<math>= a^{m_0}* a^{2m_1}* a^{2^2*m_2}* ... * a^{2^k*m_k}= </math>

<math>= a^{m_0}* (a^2)^{m_1}* (a^{2^2})^{m_2}* ... * (a^{2^k})^{m_k}= </math>

<math> = \prod_{i=0}^k {(a^{2^{i}})^{m_i}}</math>

'''<u>Пример</u>'''. Посчитаем с помощью простой двоичной схемы возведения в степень типа «справа налево» значение '''175<sup>235</sup> '''mod''' 257'''.

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

235<sub>10</sub> = 11101011<sub>2</sub>.

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

t := 175<sup>2</sup> mod 257 = 42;

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

t := 42<sup>2</sup> mod 257 = 222;

''3''. t := 222<sup>2</sup> mod 257 = 197;

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

t := 197<sup>2</sup> mod 257 = 2;

''5''. t := 2<sup>2</sup> mod 257 = 4;

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

t := 4<sup>2</sup> mod 257 = 16;

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

t := 16<sup>2</sup> mod 257 = 256;

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

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

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

=== Псевдокод ===
Рекуррентный алгоритм для ModExp(A, b, c) = A<sup>b</sup> (mod c), где ''A'' является квадратной матрицей.<br />
 '''matrix'''<span> ModExp(matrix A, int b, int c) {</span>
    '''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''.

== Реверсивное и квантовое возведение в степень по модулю ==
В [[Квантовые вычисления|квантовых вычислениях]] возведение в степень по модулю является частью [[алгоритм Шора|алгоритма Шора]]. Также, в данном алгоритме можно узнать основание и показатель степени при каждом вызове, которые позволяют различные модификации схемы<ref>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</ref>.

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

* [[Python]] содержит встроенную функцию <tt>pow()</tt><ref>{{Cite web|url = https://docs.python.org/2/library/functions.html#built-in-functions|title = Built-in Functions: official site|author = |date = |publisher = |lang = en}}</ref>
* [[.NET Framework]] содержит <tt>BigInteger</tt> class, включающий в себя ModPow()<ref>{{Cite web|url = http://msdn.microsoft.com/en-us/library/system.numerics.biginteger.modpow%28v=vs.100%29.aspx#pow|title = BigInteger.ModPow Method: official site|author = |date = |publisher = |lang = en}}</ref>
* [[Java (programming language)|Java]] содержит <tt>java.math.BigInteger</tt> class, включающий в себя modPow()<ref>{{Cite web|url = http://docs.oracle.com/javase/8/docs/api/java/math/BigInteger.html#modPow(java.math.BigInteger,%20java.math.BigInteger)|title = Class BigInteger: official site|author = |date = |publisher = |lang = en}}</ref>
* [[Perl]] содержит <tt>Math::BigInt</tt> модуль, включающий в себя метод <tt>bmodpow()</tt><ref>{{Cite web|url = http://perldoc.perl.org/Math/BigInt.html#bmodpow%28%29|title = Math::BigInt: official site|author = |date = |publisher = |lang = en}}</ref>
* [[Go]] содержит <tt>big.Int</tt> тип, включающий в себя метод <tt>Exp()</tt><ref>{{Cite web|url = http://golang.org/pkg/math/big/|title = Package big: official site|author = |date = |publisher = |lang = en}}</ref>
* [[PHP]] содержит BC Math библиотеку, включающую в себя функцию <tt>bcpowmod()</tt><ref>{{Cite web|url = http://php.net/manual/en/function.bcpowmod.php|title = bcpowmod: official site|author = |date = |publisher = |lang = en}}</ref>
* [[GNU Multi-Precision Library]] (GMP) библиотека содержит функцию <tt>mpz_powm()</tt><ref>{{Cite web|url = https://gmplib.org/manual/Integer-Exponentiation.html|title = Exponentiation Functions: official site|author = |date = |publisher = |lang = en}}</ref>

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

== Примечания ==
{{примечания}}

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

{{rq|refless|wikify|isbn}}

[[Категория:Дискретная математика]]
[[Категория:Делимость и остатки]]
[[Категория:Теоретико-числовые алгоритмы]]