Быстрое возведение в степень по модулю
Калькулятор возводит большие числа в степень по модулю
![Creative Commons Attribution/Share-Alike License 3.0 (Unported)](/img/lic/by-sa.png)
Этот материал распространяется на условиях лицензии Creative Commons Attribution/Share-Alike License 3.0 (Unported). Это означает, что вы можете размещать этот контент на своем сайте или создавать на его основе собственный (в том числе и в коммерческих целях), при условии сохранения оригинального лицензионного соглашения. Кроме того, Вы должны отметить автора этой работы, путем размещения HTML ссылки на оригинал работы https://planetcalc.ru/8979/. Пожалуйста оставьте без изменения все ссылки на других авторов данной работы или работы, на основе которой создана данная работа (если таковые имеются в спроводительном тексте).
Этот калькулятор можно использовать для возведения в степень целого числа по модулю. Калькулятор позволяет задать большие целые числа и в модуле, и в основании, и в показателе степени. Используется быстрый алгоритм, описанный сразу за калькулятором.
Алгоритмы быстрого возведения в степень
Если применять наивный способ возведения в степень - просто перемножить 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
Комментарии