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

Возведение в степень по модулю вычисляет остаток от деления целого основания, возведённого в неотрицательную целую степень, на положительный модуль. Выражение a^b mod m задаёт единственный остаток от 0 до m - 1, сравнимый с a^b по этому модулю. Прямой расчёт быстро становится непрактичным: степени достигают огромных размеров, даже если итоговый остаток мал. Этот калькулятор не создаёт такое огромное промежуточное целое число. Эффективный метод называют бинарным возведением в степень, последовательным возведением в квадрат или методом квадратов и умножений. Показатель записывается в двоичной системе и обрабатывается по битам. Сначала основание сокращается по модулю m. На каждом шаге текущий множитель возводится в квадрат по модулю m. Если соответствующий бит показателя равен единице, этот множитель умножается на результат, который сразу снова сокращается по модулю m. Благодаря сокращению каждого промежуточного значения числа остаются меньше квадрата модуля. Число шагов этого алгоритма пропорционально лишь логарифму показателя. Поэтому степень с показателем один миллиард требует примерно тридцати этапов возведения в квадрат, а не миллиарда последовательных умножений. Показанный счётчик различает возведения в квадрат и выбранные умножения, соответствующие единичным битам показателя. При нулевом показателе корректно возвращается 1 mod m. Модульная арифметика считает эквивалентными числа с одинаковым остатком. Например, 17 и 5 сравнимы по модулю 12, поскольку оба дают остаток 5. Поддерживается и отрицательное основание: сначала оно приводится к эквивалентному неотрицательному остатку. Показатель в этом калькуляторе должен быть неотрицательным. Отрицательные показатели по модулю требуют нахождения обратного по умножению, который существует только при взаимной простоте основания и модуля. Степени по модулю лежат в основе теории чисел и современной криптографии. Шифрование и подписи RSA возводят сообщения в большие степени по модулю составного числа. Обмен ключами Диффи — Хеллмана и многие системы на основе дискретного логарифма используют степени по модулю простого числа. Эта же операция применяется в тестах простоты, генераторах псевдослучайных чисел, контрольных суммах, циклических закономерностях и задачах соревнований по программированию. Все три поля обрабатываются как точные целые числа произвольного размера, а не как числа с плавающей точкой. Поэтому значения за пределами обычного безопасного диапазона целых чисел JavaScript сохраняют каждую цифру. Модуль должен быть больше единицы; запятые и десятичные точки вводить нельзя. Для ручной проверки сначала сократите основание, затем проверьте небольшие показатели последовательным умножением, беря остаток после каждого шага.