Kalkulator potęgowania modularnego

Wzór

How this is calculated

Podaj trzy liczby całkowite: podstawę b, nieujemny wykładnik e oraz dodatni moduł m. Kalkulator zwraca resztę z dzielenia b do potęgi e przez m. Bezpośrednie obliczenie b^e byłoby niemożliwe dla dużych wykładników z powodu przepełnienia, dlatego narzędzie stosuje potęgowanie przez podnoszenie do kwadratu (znane też jako binarne potęgowanie).

Algorytm zaczyna od wyniku = 1 i redukuje podstawę modulo m. Następnie przegląda bity wykładnika od najmniej znaczącego do najbardziej znaczącego: gdy bieżący bit wynosi 1, mnoży bieżący wynik przez aktualną podstawę (mod m); w każdym kroku podnosi podstawę do kwadratu (mod m) i przesuwa wykładnik o jeden bit w prawo. Ponieważ każdy iloczyn pośredni jest redukowany modulo m, liczby pozostają małe, a nakład pracy jest proporcjonalny do log2(e) mnożeń zamiast e. Wszelkie obliczenia są wykonywane przy użyciu JavaScript BigInt, więc wyniki są dokładne niezależnie od rozmiaru.

Założenia i przypadki brzegowe: wykładnik musi być liczbą całkowitą e >= 0, a moduł dodatnią liczbą całkowitą m > 0 (mod 0 jest nieokreślone). Podstawa może być ujemna — jest najpierw normalizowana do zakresu 0..m-1 za pomocą ((b mod m) + m) mod m, więc zwracana reszta jest zawsze nieujemna. Gdy e = 0, wynik wynosi 1 mod m. Gdy m = 1, wynik wynosi zawsze 0.