Калькулятор модульного возведения в степень

Введите расчет

Основание (a)

Показатель степени (b)

Модуль (m)

Результатов

a^b mod m

445

остаток

Основание (a)	4
Показатель степени (b)	13
Модуль (m)	497

Что такое модульное возведение в степень?

Модульное возведение в степень вычисляет \(a^{b} \bmod m\) — остаток от деления степени \(a^{b}\) на модуль \(m\). Это одна из ключевых операций в теории чисел и криптографии: на ней держатся такие алгоритмы, как RSA, обмен ключами Диффи–Хеллмана и электронные подписи. Даже если \(a^{b}\) оказывается астрономически большим числом, результат по модулю \(m\) остаётся небольшим и легко вычислимым.

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

Как пользоваться калькулятором

Введите три целых числа: основание \(a\), неотрицательный показатель степени \(b\) и модуль \(m\) (положительное целое число). Нажмите «Вычислить» — и вы получите единственный остаток в диапазоне от 0 до \(m-1\). Основание может быть отрицательным: перед возведением в степень оно сначала приводится к допустимому диапазону вычетов.

Разбор формулы

Вычислить \(a^{b}\) напрямую при большом \(b\) невозможно, поэтому здесь применяется метод «возведение в квадрат и умножение» (его также называют быстрым или бинарным возведением в степень). Показатель степени читается в двоичном виде. Начинаем с результата \(r = 1\) и основания, приведённого по модулю \(m\). Для каждого бита показателя основание возводится в квадрат (по модулю \(m\)); если текущий бит равен 1, результат дополнительно умножается на основание (по модулю \(m\)). Такому подходу нужно всего около \(\log_2(b)\) умножений вместо \(b\).

Реклама

Метод возведения в квадрат и умножения обрабатывает двоичные разряды показателя, возводя в квадрат на каждом шаге и умножая, когда бит равен 1.

Разбор на примере

Вычислим \(4^{13} \bmod 497\). Показатель 13 в двоичной системе — это 1101. Пройдём по шагам метода «возведение в квадрат и умножение»:

$$4^{1} = 4, \quad 4^{2} = 16, \quad 4^{4} = 256, \quad 4^{8} = 256^{2} = 65536 \equiv 30 \pmod{497}.$$

Поскольку \(13 = 8 + 4 + 1\), перемножаем нужные степени:

$$30 \times 256 \times 4 = 30720 \equiv 445 \pmod{497}.$$

Итак, \(4^{13} \bmod 497 = \) 445.

Частые вопросы

А если показатель степени равен 0? Любое число в нулевой степени равно 1, поэтому результат — это \(1 \bmod m\) (а при \(m = 1\) он равен 0).

Может ли основание быть отрицательным? Да. Отрицательное основание сначала приводится к эквивалентному положительному вычету по модулю \(m\), так что ответ всегда лежит в диапазоне от 0 до \(m-1\).

Почему нельзя просто вычислить \(a^{b}\) и взять остаток? Для криптографических размеров \(a^{b}\) состояло бы из миллионов цифр. Взятие остатка по модулю \(m\) на каждом шаге удерживает числа небольшими, а вычисления — быстрыми.