Калькулятор модульного піднесення до степеня

Формула

How this is calculated

Введіть три цілі числа: основу b, невід'ємний показник e і додатній модуль m. Калькулятор повертає остачу від ділення b у степені e на m. Наївне обчислення b^e спочатку призвело б до переповнення для великих показників, тому цей інструмент використовує піднесення до степеня зведенням у квадрат (також зване бінарним піднесенням до степеня).

Алгоритм починає з result = 1 і зводить основу за модулем m. Потім він проходить по бітах показника від молодшого до старшого: коли поточний біт дорівнює 1, він множить поточний результат на поточну основу (mod m), і на кожному кроці зводить основу в квадрат (mod m) та зсуває показник на один біт праворуч. Оскільки кожний проміжний добуток зводиться за модулем m, числа залишаються малими, а обсяг роботи пропорційний log2(e) множень, а не e. Усі арифметичні дії виконуються з JavaScript BigInt, тому результати точні незалежно від розміру.

Передумови та крайні випадки: показник повинен бути цілим числом e >= 0, а модуль — додатнім цілим числом m > 0 (mod 0 невизначено). Основа може бути від'ємною; вона спочатку нормалізується до діапазону 0..m-1 за допомогою ((b mod m) + m) mod m, тому повернута остача завжди невід'ємна. Коли e = 0, результат дорівнює 1 mod m. Коли m = 1, результат завжди дорівнює 0.