Быстрое возведение в степень по модулю

Этот калькулятор можно использовать для возведения в степень целого числа по модулю. Калькулятор позволяет задать большие целые числа и в модуле, и в основании, и в показателе степени. Используется быстрый алгоритм, описанный сразу за калькулятором.

Возведение в степень по модулю

Основание

Показатель

Модуль

Рассчитать

Результат

 

 Ссылка  Сохранить  Виджет

Алгоритмы быстрого возведения в степень

Если применять наивный способ возведения в степень - просто перемножить p-1 раз основание, нам потребуется на единицу меньше умножений, чем показатель степени. Несмотря на всю мощь современных компьютеров, такой способ нам не подходит, так как мы собираемся использовать для показателя числа даже большие, чем стандартные 64-битные целые. Например, в простом числе Мерсена: 618970019642690137449562111, уменьшая на единицу которое мы используем как значение показателя степени по-умолчанию, насчитывается 89 двоичных разрядов (см. Сколько бит занимает число).
Чтобы оперировать подобными показателями требуются алгоритмы быстрого возведения в степень.

В калькуляторе Возведение полинома в степень мы уже задействовали один быстрый алгоритм возведения в степень, основанный на дереве степеней, который позволяет свести к минимуму число операций умножения. Однако для огромных показателей реализация этого алгоритма с хранением в памяти всего дерева степеней не подходит из-за ограничений по ресурсам.
Поэтому в данном калькуляторе для вычисления степени мы применяем библиотеку bigInt, реализующую двоичный алгоритм, не требующий дополнительной памяти. Вариант этого алгоритма описан в той же статье, однако обработка двоичных разрядов показателя степени происходит там последовательно со старшего бита до младшего. В нашем случае это несколько неудобно, так как мы используем большие целые и не вдаваясь в реализацию хранилища целых, мы заранее не представляем, сколько разрядов они занимают в памяти.

Двоичный алгоритм возведения в степень справа налево

Поэтому алгоритм обрабатывает двоичное представление показателя степени начиная с младшего бита и кончая старшим (слева направо), согласно следующему алгоритму:

a //основание степени
e //показатель степени
m //модуль
 //Вычисление степени
r ⟵ 1      
while (e!=0) {
            if (e mod 2 = 1) r ⟵ r * a mod m;
            e ⟵ e / 2;
            a = a*a mod m;
        }
output ⟵ r