Возведение в степень по модулю — одна из операций над натуральными числами — возведение в степень, — выполняемая по модулю. Находит применение в информатике, особенно, в области криптографии с открытым ключом.
Возведение в степень по модулю — это вычисление остатка от деления натурального числа b (основание), возведенного в степень n (показатель степени), на натуральное число m (модуль). Обозначается:
Например, пусть нам даны b = 5, n = 3 и m = 13, тогда решение c = 8 — это остаток от деления на 13.
Если b, n и m неотрицательны и b < m, то единственное решение c существует, причем 0 ⩽ c < m.
Возведение в степень по модулю может быть выполнено и с отрицательным показателем степени n. Для этого необходимо найти число d, обратное числу b по модулю m. Это легко сделать с помощью алгоритма Евклида. Таким образом,
Возвести в степень по модулю довольно легко, даже при больших входных значениях. А вот вычисление дискретного логарифма, то есть нахождение показателя степени n при заданных b, c и m, намного сложнее. Такое одностороннее поведение функции делает её кандидатом для использования в криптографических алгоритмах.
Самый простой способ возвести в степень по модулю — это непосредственное вычисление числа
, а затем нахождение остатка от деления этого числа на m. Рассчитаем c, если b = 4, n = 13 и m = 497:
Можно использовать калькулятор для вычисления 413, получим 67,108,864. Теперь возьмем это число по модулю 497 и получим 445.
Следует заметить, что b имеет только один символ в длину, n имеет только два символа в длину, а значение bn имеет 8 символов в длину.
В криптографии b часто имеет 256 двоичных разрядов (77 десятичных цифр). Рассмотрим b = 5 × 1076 и e = 17, они оба принимают вполне реальные значения. В этом примере b 77 символов в длину, а n — 2 символа в длину, но результат возведения в степень имеет 1304 символов в длину. Такие расчеты возможны на современных компьютерах, но скорость вычисления таких чисел невелика. Значения b и n увеличивают, чтобы добиться большего уровня безопасности, из-за чего значение bn становится громоздким.
Время, необходимое для возведения в степень, зависит от операционной системы и процессора. Описанный выше способ требует O(en) умножений.
Данный метод требует большего числа операций, по сравнению с предыдущим. Однако, так как памяти требуется меньше и операции занимают меньшее время, то алгоритм работает гораздо быстрее.
Данный алгоритм основывается на том факте, что для заданных a и b следующие 2 уравнения эквивалентны:
Алгоритм следующий:
Следует отметить, что при каждом проходе шага 3, выражение верно. После того, как шаг 3 был выполнен n раз, в c содержится искомое значение. Таким образом, алгоритм основывается на подсчитывании n′ до тех пор, пока n′ не достигнет e и умножении на b по модулю m в каждом витке цикла (чтобы гарантировать, что результат будет маленьким).
Например, b = 4, n = 13 и m = 497. Алгоритм проходит через шаг 3 тринадцать раз.
Конечный ответ c равняется 445, как и в первом методе.
Как и в первом методе, требуется O(e′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. Перечисленные методы легко могут быть применены в данном алгоритме. Это обеспечивает хороший тест простоты для больших (500 бит) чисел n.
Рекуррентный алгоритм для 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].
Возведение в степень по модулю является важной операцией в информатике и есть эффективные алгоритмы (см. выше), которые гораздо быстрее, чем простое возведение в степень и последующее взятие остатка. В языках программирования существуют библиотеки, содержащие специальную функцию для возведения в степень по модулю:
Для улучшения этой статьи желательно: |
Данная страница на сайте WikiSort.ru содержит текст со страницы сайта "Википедия".
Если Вы хотите её отредактировать, то можете сделать это на странице редактирования в Википедии.
Если сделанные Вами правки не будут кем-нибудь удалены, то через несколько дней они появятся на сайте WikiSort.ru .