Processing math: 100%

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

Возведение в степень по модулю — одна из операций наднатуральными числами — возведение в степень, — выполняемая помодулю. Находит применение в информатике, особенно, в областикриптографии с открытым ключом.
 Возведение в степень по модулю — это вычисление остатка от делениянатурального числа ''b ''(основание), возведенного в степень n(показатель степени), на натуральное число m (модуль).Обозначается:
cbn(modm)
 Например, пусть нам даны b = 5, n = 3 и m = 13, тогдарешение c = 8 — это остаток от деления 53 на 13.
 Если b, e и m неотрицательны и b \textlessm, то единственное решение c существует, причем 0 ⩽c \textless m.
 Возведение в степень по модулю может быть выполнено и с отрицательнымпоказателем степени n. Для этого необходимо найти число d,обратное числу b по модулю m. Это легко сделать с помощьюалгоритма Евклида. Таким образом,\\:cbnd|n|(modm) , где n \textless0 и bd1(modm)
 Возвести в степень по модулю довольно легко, даже при больших входныхзначениях. А вот вычисление дискретного логарифма, то есть нахождениепоказателя степени n при заданных b, c и m, намногосложнее. Такое одностороннее поведение функции делает её кандидатом дляиспользования в криптографических алгоритмах.

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


 Самый простой способ возвести в степень по модулю — этонепосредственное вычисление числа bn, а затем нахождение остатка отделения этого числа на m. Рассчитаем c, если b = 4,n = 13 и m = 497:\\: c413(mod497)
 Можно использовать калькулятор для вычисления 4\textsuperscript13,получим 67,108,864. Теперь возьмем это число по модулю 497 и получим445.
 Следует заметить, что b имеет только один символ в длину, n имееттолько два символа в длину, а значениеb\textsuperscriptn имеет 8 символов в длину.
 В криптографии b часто имеет 256 двоичных разрядов (77 десятичныхцифр). Рассмотрим b = 5 × 10\textsuperscript76 и e = 17,они оба принимают вполне реальные значения. В этом примере b 77символов в длину, а n — 2 символа в длину, но результат возведения встепень имеет 1304 символов в длину. Такие расчеты возможны насовременных компьютерах, но скорость вычисления таких чисел невелика.Значения b и n увеличивают, чтобы добиться большего уровнябезопасности, из-за чего значение b\textsuperscriptnстановится громоздким.
 Время, необходимое для возведения в степень, зависит от операционнойсистемы и процессора. Описанный выше способ требуетO(e\textsuperscriptn) умножений.

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


 Данный метод требует большего числа операций, по сравнению с предыдущим.Однако, так как памяти требуется меньше и операции занимают меньшеевремя, то алгоритм работает гораздо быстрее.
 Данный алгоритм основывается на том факте, что для заданных a иb следующие 2 уравнения эквивалентны:\\:c(ab)(modm)

c(a(b (mod m)))(modm)
 Алгоритм следующий:

  1. Пусть c = 1, n′ = 0.
  2. Увеличим n′ на 1.
  3. Установим c(bc)(modm).
  4. Если n′ \textless n, возвращаемся к шагу 2. В противном случае, c содержит правильный ответ cbn(modm).

 Следует отметить, что при каждом проходе шага 3, выражениеcbn(modm) верно. После того, как шаг 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′\textsuperscriptn)умножений для завершения. Однако, так как числа используемые в этихрасчетах намного меньше, то время выполнения данного алгоритмауменьшается.
 В псевдокоде это выглядит так:
 \texttt \textttfunction\texttt modular\_pow(base, index\_n, modulus)\\\texttt    c := 1\\\texttt    \textttfor\texttt index\_n\_prime = 1 \textttto\texttt index\_n \\\texttt        c := (c * base) \textttmod\texttt modulus\\\texttt    \textttreturn\texttt c

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


 Применяя алгоритм быстрого возведения в степень для595\textsuperscript703 (mod 991):
 Имеем n = 703 =(1010111111)\textsubscript2 =2\textsuperscript0+2\textsuperscript1+2\textsuperscript2+2\textsuperscript3+2\textsuperscript4+2\textsuperscript5+2\textsuperscript7+2\textsuperscript9.
 '''595\textsuperscript703 '''=((((((((595\textsuperscript2)\textsuperscript2*595)\textsuperscript2)\textsuperscript2*595)\textsuperscript2*595)\textsuperscript2*595)\textsuperscript2*595)\textsuperscript2*595)\textsuperscript2*595
 =(((((((238\textsuperscript2*595)\textsuperscript2)\textsuperscript2*595)\textsuperscript2*595)\textsuperscript2*595)\textsuperscript2*595)\textsuperscript2*595)\textsuperscript2*595
 = ((((((261\textsuperscript2)\textsuperscript2*595)\textsuperscript2*595)\textsuperscript2*595)\textsuperscript2*595)\textsuperscript2*595)\textsuperscript2*595
 = (((((733\textsuperscript2*595)\textsuperscript2*595)\textsuperscript2*595)\textsuperscript2*595)\textsuperscript2*595)\textsuperscript2*595
 = (((((167* 595)\textsuperscript2*595)\textsuperscript2*595)\textsuperscript2*595)\textsuperscript2*595)\textsuperscript2*595
 = ((((265\textsuperscript2*595)\textsuperscript2*595)\textsuperscript2*595)\textsuperscript2*595)\textsuperscript2*595
 = (((342\textsuperscript2*595)\textsuperscript2*595)\textsuperscript2*595)\textsuperscript2*595
 =((605\textsuperscript2*595)\textsuperscript2*595)\textsuperscript2*595
 = (733\textsuperscript2*595)\textsuperscript2*595
 = (167*595)\textsuperscript2*595
 = 265\textsuperscript2*595
 = 342.

Схема «справаналево»


 Другим вариантом является схема типа «справа налево». Её можнопредставить следующей формулой:
d=an=
=aki=0mi2i=
=am0a2m1a22m2...a2kmk=
=am0(a2)m1(a22)m2...(a2k)mk=
=ki=0(a2i)mi
Пример. Посчитаем с помощью простой двоичной схемы возведения встепень типа «справа налево» значение '175\textsuperscript235mod 257'.
 Представим число 235 в двоичном виде:
 235\textsubscript10 = 11101011\textsubscript2.
1. d := 1 * 175 mod 257 = 175,
 t := 175\textsuperscript2 mod 257 = 42;
2. d := 175 * 42 mod 257 = 154,
 t := 42\textsuperscript2 mod 257 = 222;
3. t := 222\textsuperscript2 mod 257 = 197;
4. d := 154 * 197 mod 257 = 12,
 t := 197\textsuperscript2 mod 257 = 2;
5. t := 2\textsuperscript2 mod 257 = 4;
6. d := 12 * 4 mod 257 = 48,
 t := 4\textsuperscript2 mod 257 = 16;
7. d := 48 * 16 mod 257 = 254,
 t := 16\textsuperscript2 mod 257 = 256;
8. d := 254 * 256 mod 257 = 3,
9. → d = 3. Потребовалось 7 возведений в квадрат и 6 умножений.

Матрицы


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

Псевдокод


 Рекуррентный алгоритм для ModExp(A, b, c) = A\textsuperscriptb (modc), где A является квадратной матрицей.\\matrix ModExp(matrix A, int b, int c) \{
 \texttt   '''if '''(b == 0) \textttreturn\texttt I; // Единичная матрица\\\texttt   '''if '''(b 

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


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

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


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

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


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

  • Python содержит встроенную функцию \textttpow
  • .NET Framework содержит \textttBigInteger class, включающий в себя ModPow
  • Java содержит \textttjava.math.BigInteger class, включающий в себя modPow
  • Perl содержит \textttMath::BigInt модуль, включающий в себя метод \textttbmodpow
  • Go содержит \textttbig.Int тип, включающий в себя метод \textttExp
  • PHP содержит BC Math библиотеку, включающую в себя функцию \textttbcpowmod
  • GNU Multi-Precision Library (GMP) библиотека содержит функцию \textttmpz\_powm