Калькулятор Power Mod

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

Результатов

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

7^256 mod 13

Основание	7
Показатель степени	256
Модуль	13

Что такое калькулятор Power Mod?

Калькулятор Power Mod вычисляет (основание^{степень}) mod m — остаток от деления степени основания на модуль. Эта операция, называемая модульным возведением в степень, встречается повсюду в теории чисел и криптографии: на ней держатся шифрование RSA, обмен ключами Диффи — Хеллмана, тесты на простоту и хеш-функции. Вычислить её «в лоб» (сначала возвести в гигантскую степень, а потом взять остаток) для больших показателей попросту невозможно, поэтому применяется быстрый алгоритм.

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

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

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

$$\text{result} = \text{Base}^{\text{Exponent}} \bmod \text{Modulus}$$

Вместо того чтобы строить огромное число основание^{степень}, калькулятор использует метод «возведения в квадрат и умножения» (его ещё называют бинарным возведением в степень). Показатель читается в двоичном виде. Начиная с результата, равного 1, алгоритм многократно возводит основание в квадрат по модулю $m$; всякий раз, когда очередной двоичный разряд показателя равен 1, это значение домножается на накопленный результат — снова с приведением по модулю $m$. Поскольку все промежуточные числа остаются меньше $m^2$, вычисление выполняется быстро даже для показателей в сотни знаков.

Блок-схема алгоритма модульного возведения в степень методом «квадрат и умножение» — Возведение в квадрат и умножение: проходим биты экспоненты, на каждом шаге возводим в квадрат и умножаем при бите 1, постоянно беря остаток по модулю $m$.

Пример вычисления

Вычислим $7^{256} \bmod 13$. Порядок числа 7 по модулю 13 делит 12, причём $7^{12} \equiv 1$. Так как $256 = 12 \times 21 + 4$, получаем $$7^{256} \equiv 7^{4} = 2401 \equiv 9 \pmod{13}.$$ Значит, ответ — 9, и калькулятор находит его мгновенно, ни разу не формируя 217-значное число $7^{256}$.

Таблица шагов вычисления base^exponent mod m повторным возведением в квадрат — На каждом шаге текущее значение возводится в квадрат и берётся остаток по модулю $m$, а в позициях с битом 1 умножается на основание.

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

А если модуль равен 1? Любое целое число сравнимо с 0 по модулю 1, поэтому результат равен 0.

Может ли показатель быть нулём? Да. Любое основание в степени 0 равно 1, поэтому результат — $1 \bmod m$ (то есть 1 при $m > 1$).

Почему нельзя просто вычислить степень напрямую? Для больших показателей промежуточное число содержало бы астрономическое количество цифр и вызвало бы переполнение. Приведение по модулю на каждом шаге удерживает значения небольшими и делает метод эффективным.

Похожие калькуляторы

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

Вычислите 2 в любой степени (2ⁿ) за секунду. Введите показатель и получите точное значение — поддерживаются отрицательные и дробные степени.

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

Вычислите (aᵐ)ⁿ по правилу степени в степени: перемножьте показатели, получите a^(m·n) и мгновенно узнайте результат.

Калькулятор булеана (множества всех подмножеств)

Постройте булеан любого множества: узнайте число подмножеств (2ⁿ) и получите полный список всех подмножеств, включая пустое, за секунду.

Калькулятор степени (x^y)

Возведите основание x в степень y (x^y) для любых вещественных чисел — отрицательных, нулевых и дробных показателей. Быстро, бесплатно и точно.

Калькулятор степени матрицы (Aⁿ)

Возведите квадратную матрицу A в целую степень n (Aⁿ = A·A·…·A) для матриц 2×2, 3×3 и 4×4. Поддерживаются n = 0 и отрицательные степени через обратную матрицу.

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

Бесплатный калькулятор степени: возводите любое основание в любую степень (основание^степень). Поддержка дробей, отрицательных и дробных показателей. Мгновенный точный результат.