Для установки нажмите кнопочку Установить расширение. И это всё.

Исходный код расширения WIKI 2 регулярно проверяется специалистами Mozilla Foundation, Google и Apple. Вы также можете это сделать в любой момент.

4,5
Келли Слэйтон
Мои поздравления с отличным проектом... что за великолепная идея!
Александр Григорьевский
Я использую WIKI 2 каждый день
и почти забыл как выглядит оригинальная Википедия.
Статистика
На русском, статей
Улучшено за 24 ч.
Добавлено за 24 ч.
Альтернативы
Недавние
Show all languages
Что мы делаем. Каждая страница проходит через несколько сотен совершенствующих техник. Совершенно та же Википедия. Только лучше.
.
Лео
Ньютон
Яркие
Мягкие

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

Из Википедии — свободной энциклопедии

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

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

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

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

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

, где n < 0 и

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

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

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

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

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

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

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

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

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

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

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

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

При каждом проходе шага 3, выражение верно. После того, как шаг 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

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

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

Имеем n = 703 =(1010111111)2 = 20+21+22+23+24+25+ 27+29.

595703 = ((((((((5952)2*595)2)2* 595)2*595)2 * 595)2*595)2*595)2*595

= (((((((2382*595)2)2* 595)2*595)2 * 595)2*595)2*595)2*595

= ((((((2612)2* 595)2*595)2 * 595)2*595)2*595)2*595

= (((((7332* 595)2*595)2 * 595)2*595)2*595)2*595

= (((((167* 595)2*595)2 * 595)2*595)2*595)2*595

= ((((2652*595)2 * 595)2*595)2*595)2*595

= (((3422 * 595)2*595)2*595)2*595

= ((6052*595)2*595)2*595

= (7332*595)2*595

= (167*595)2*595

= 2652*595

= 342.

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

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

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

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

23510 = 111010112.

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

t := 1752 mod 257 = 42;

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

t := 422 mod 257 = 222;

3. t := 2222 mod 257 = 197;

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

t := 1972 mod 257 = 2;

5. t := 22 mod 257 = 4;

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

t := 42 mod 257 = 16;

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

t := 162 mod 257 = 256;

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

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

Матрицы

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

Псевдокод

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

См. также

Примечания

  1. Теоретический минимум и алгоритмы цифровой подписи, 2010, с. 56-57.
  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. bcpowmod: official site (англ.). Дата обращения: 28 декабря 2014. Архивировано 28 декабря 2014 года.
  10. 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.
Эта страница в последний раз была отредактирована 26 декабря 2022 в 20:02.
Как только страница обновилась в Википедии она обновляется в Вики 2.
Обычно почти сразу, изредка в течении часа.
Основа этой страницы находится в Википедии. Текст доступен по лицензии CC BY-SA 3.0 Unported License. Нетекстовые медиаданные доступны под собственными лицензиями. Wikipedia® — зарегистрированный товарный знак организации Wikimedia Foundation, Inc. WIKI 2 является независимой компанией и не аффилирована с Фондом Викимедиа (Wikimedia Foundation).