Система модульного возведения в степень позволяет вычислять остаток от деления натурального числа (основания), возведённого в степень (показатель степени), на натуральное число (модуль). 2

Самый простой способ возвести в степень по модулю — это вычислить число, возведённое в степень, а затем найти остаток от деления этого числа на модуль. 2

Например, если даны основания a = 5, показатель степени n = 3 и модуль m = 13, то решение c = 8 — это остаток от деления 5³ на 13. 2

Для работы с отрицательным показателем степени необходимо найти число, обратное числу основанию по модулю модулю. 2 Это можно сделать с помощью алгоритма Евклида. 2

Существует алгоритм быстрого модульного возведения в степень, который использует бинарное разложение показателя степени. 3 Он выполняет последовательные возведения в квадрат числа и на каждом шаге проверяет биты показателя степени. 3 Если бит равен 1, то текущий результат умножается на основание и берётся остаток от деления на модуль. 3

Модульное возведение в степень эффективно для вычислений даже для очень больших целых чисел и находит применение в информатике, в частности в области криптографии с открытым ключом. 24