Калькулятор возведения в степень по модулю
Вычислите остаток aⁿ по модулю m быстрым двоичным возведением без расчёта огромного числа aⁿ.
Остаток
3
- Метод
- двоичное возведение в степень
Что считает калькулятор
Показатель разбивается по двоичным разрядам, а после каждого умножения берётся остаток, поэтому промежуточные числа остаются небольшими.
Калькулятор показывает не только ответ, но и подстановку в формулу, чтобы вычисление можно было проверить вручную.
Формула
r = aⁿ mod m
- r
- остаток результата
- a
- целое основание
- n
- неотрицательный целый показатель
- m
- целый модуль больше единицы
- mod
- операция взятия остатка
- Отрицательное основание приводится к неотрицательному остатку.
- Вычисления выполняются целочисленно и точно.
Примеры
Расчёт при значениях по умолчанию: 7^128 mod 13
- Исходные данные: 7^128 mod 13.
- Подстановка и вычисление: 7^128 mod 13 = 3.
- Метод: двоичное возведение в степень.
Остаток: 3
Частые вопросы
›Зачем не вычислять aⁿ напрямую?
Степень может иметь миллионы цифр, хотя для остатка достаточно хранить значения меньше m.
Источники
- Элементарная теория чисел — делимость, простые числа и сравнения
Методика проверена