Как вычисляется степень по модулю
Степень по модулю показывает остаток, который получится при делении ae на положительное целое m. Калькулятор принимает основание со знаком, неотрицательный показатель и модуль, а ответ всегда приводит к диапазону от 0 до m − 1. Само огромное число ae строить не нужно.
ae mod m = r, где 0 ≤ r < m
Например, обычная степень 413 равна 67 108 864. После деления на 497 остаётся 445. Бинарный алгоритм приходит к тому же ответу, но на каждом шаге хранит только текущий остаток и очередной квадрат. С большими показателями это принципиальная разница: промежуточные числа не разрастаются до миллионов цифр.
Сначала основание нормализуется. Для отрицательного a калькулятор выбирает равный ему неотрицательный остаток. Так, −2 по модулю 13 заменяется на 11, поскольку −2 и 11 отличаются на 13. После этого показатель читается в двоичной записи. Каждый его разряд требует одного возведения текущего основания в квадрат, а единичный разряд дополнительно умножает накопленный ответ.
Как читать ход вычисления
Показатель 13 в двоичной системе записывается как 1101. Это сумма 8 + 4 + 1, поэтому 413 собирается из степеней 48, 44 и 41. В раскрытом результате разряды идут справа налево: сначала вес 1, затем 2, 4 и 8. Нулевой бит пропускает умножение, но очередной квадрат всё равно готовится для следующего разряда.
После каждого действия применяется модуль. Если текущий остаток равен 200, очередной квадрат не обязан хранить число 40 000 целиком: при модуле 497 достаточно оставить 240. Повторение этого правила не меняет финальный остаток, зато удерживает вычисления в небольшом диапазоне. Для показателя длиной 100 десятичных цифр потребуется не больше 333 двоичных шагов.
Число шагов растёт примерно как двоичный логарифм показателя. Прямое умножение для степени e требует около e множителей, а повторное возведение в квадрат использует количество шагов, близкое к числу битов e. Поэтому разница между показателями 10 и 10100 для этого алгоритма измеряется сотнями шагов, а не числом умножений с сотней нулей.
Примеры с разными основаниями и модулями
🔁 Последние три цифры числа 210. Модуль 1000 оставляет три последних десятичных разряда. Получаем 210 mod 1000 = 24, потому что 1024 делится на 1000 с остатком 24. Такой приём удобен, когда полная степень не нужна.
➖ Отрицательное основание −2 и нечётная степень 5. По модулю 13 число −2 заменяется на 11. Результат равен 7: (−2)5 = −32, а −32 = 13 × (−3) + 7. Не стоит оставлять ответ −6, хотя он сравним с 7 по модулю: калькулятор всегда показывает наименьший неотрицательный остаток.
🧩 Учебный пример 413 по модулю 497. Четыре двоичных разряда показателя дают ответ 445. Проверка обычной арифметикой выглядит так: 67 108 864 = 497 × 135 027 + 445. Раскрытие калькулятора показывает более короткий путь по квадратам.
0️⃣ Нулевой показатель у числа 123 456 789. При модуле 97 получаем 1, поскольку любое ненулевое основание в нулевой степени равно 1. Алгоритму не требуется ни одного битового шага. Исключение по форме ответа возникает только при модуле 1: там даже начальная единица даёт остаток 0.
⭕ Модуль 1 для степени 53. Единственный допустимый остаток лежит в диапазоне 0 ≤ r < 1, значит, он равен 0. Это не ошибка и не потеря данных. Все целые числа сравнимы между собой по модулю 1.
🔐 Циклическая проверка 712 по модулю 13. Ответ равен 1. Поскольку 13 простое и 7 не делится на 13, этот результат согласуется с малой теоремой Ферма. Калькулятор здесь проверяет конкретную степень, а не доказывает простоту модуля.
Где применяется модульная степень
Модульное возведение встречается в задачах о циклах, последних цифрах, сравнениях и криптографии. В RSA, схемах Диффи-Хеллмана и цифровых подписях используются степени с большими целыми показателями. Калькулятор показывает математическую операцию, но не создаёт ключи и не заменяет проверенную криптографическую библиотеку: для секретных данных важны защита от утечек по времени и другие свойства реализации.
Результат зависит только от класса остатка основания. Числа 4, 501 и −493 дают одинаковую степень по модулю 497, потому что каждое нормализуется в 4. Это удобно для ручной проверки: сначала уменьшите основание, затем работайте с коротким представителем.
Каждое поле принимает точное целое до 100 цифр без перехода к обычному JavaScript Number. Пробелы между разрядами допустимы. Дроби, отрицательный показатель, нулевой и отрицательный модуль отклоняются. Для простого получения частного и остатка используйте деление с остатком. Если показатель отрицательный, сначала понадобится обратное число по модулю. Связь с количеством взаимно простых остатков объясняет функция Эйлера.
Вопросы о степени по модулю
Нулевой показатель, отрицательное основание и маленький модуль дают непривычные, но точные ответы. Условия ниже помогают отличить корректный граничный случай от ошибки исходных данных.
Что означает запись a^e mod m?
Она означает остаток от деления целой степени a^e на положительный модуль m. Калькулятор показывает наименьший неотрицательный остаток от 0 до m − 1.
Почему калькулятор не вычисляет a^e целиком?
Остаток можно брать после каждого умножения. Бинарное возведение использует последовательные квадраты и требует примерно столько шагов, сколько битов содержит показатель.
Можно ли вводить отрицательное основание?
Да. Оно сначала заменяется равным неотрицательным остатком. Например, −2 по модулю 13 нормализуется в 11, а (−2)^5 mod 13 равно 7.
Чему равна степень с показателем 0 по модулю?
Начальное значение равно 1, затем оно приводится по модулю. Поэтому a^0 mod m равно 1 при m > 1 и равно 0 при m = 1.
Почему модуль не может быть нулевым или отрицательным?
Остаток в этой форме определяется для положительного m и должен лежать от 0 до m − 1. При m = 0 такого диапазона нет, а отрицательный модуль калькулятор не использует.
Сколько шагов нужно для показателя из 100 цифр?
Не больше 333 двоичных итераций. На каждой итерации выполняется квадрат по модулю, а при единичном бите ещё одно умножение по модулю.
Подходит ли результат для настоящей криптографии?
Математический остаток точен, но интерфейс не является криптографической реализацией. Работа с секретными ключами требует специализированной библиотеки с защитой от побочных каналов и проверенными параметрами.
Почему ответ всегда неотрицательный?
Калькулятор выбирает канонического представителя класса вычетов: единственное число r из диапазона 0 ≤ r < m. Отрицательный сравнимый остаток математически эквивалентен, но хуже подходит для единого ответа.
Похожие калькуляторы
Возможно вам пригодятся ещё несколько калькуляторов по данной теме:
- Обратное число по модулю. Введите число и модуль, чтобы найти обратное число по модулю.
- Деление с остатком. Введите делимое и ненулевой делитель. Калькулятор найдёт целое частное, остаток и покажет проверку результата.
- Функция Эйлера φ(n). Введите натуральное число до 1 000 000 000 000. Калькулятор найдёт φ(n) через различные простые множители и покажет ход вычисления.
- Обычный калькулятор. Просто посчитайте чего вы там хотели.
- Рандомайзер: генератор случайных чисел. Выберите случайное число в нужном диапазоне для любых целей, в частности для розыгрышей и онлайн-лотерей в соцсетях.
- Бросить монетку онлайн. С помощью данной формы вы можете подбросить монетку онлайн любое количество раз.
- Калькулятор корней. Найдите правильное решение корней n-степени, включая квадратные и кубические.
- Калькулятор дробей. Выполните сложение, умножение, сокращение обыкновенных дробей.
- Калькулятор квадратных уравнений. Решите квадратные уравнения с помощью специальных формул, через дискриминант и по теореме Виета. Все способы решения сопровождаются примерами.
- Калькулятор дискриминанта. Введите коэффициенты a, b и c: получите дискриминант и число действительных корней.
Есть что добавить?
Напишите своё мнение, комментарий или предложение.