Kalkulačka modulárneho umocňovania

Vzorec

How this is calculated

Zadajte tri celé čísla: základ b, nezáporný exponent e a kladný modul m. Kalkulačka vráti zvyšok po delení b umocneného na e hodnotou m. Naivný výpočet b^e by pre veľké exponenty pretiekol, preto tento nástroj používa umocňovanie mocnením (nazývané aj binárne umocňovanie).

Algoritmus začína s result = 1 a redukuje základ modulo m. Potom prechádza cez bity exponentu od najmenej významného po najvýznamnejší: vždy, keď je aktuálny bit 1, vynásobí bežiaci výsledok aktuálnym základom (mod m), a v každom kroku umocní základ (mod m) a posunie exponent o jeden bit doprava. Keďže každý medzivýsledok je redukovaný modulo m, čísla zostávajú malé a práca je úmerná log2(e) násobeniam namiesto e násobení. Všetky aritmetické operácie sa vykonávajú pomocou JavaScript BigInt, takže výsledky sú presné bez ohľadu na veľkosť.

Predpoklady a hraničné prípady: exponent musí byť celé číslo e >= 0 a modul musí byť kladné celé číslo m > 0 (mod 0 je nedefinovaný). Základ môže byť záporný; najprv sa normalizuje do rozsahu 0..m-1 pomocou ((b mod m) + m) mod m, takže vrátený zvyšok je vždy nezáporný. Keď e = 0, výsledok je 1 mod m. Keď m = 1, výsledok je vždy 0.