Kalkulator modularnega potenciranja

Formula

How this is calculated

Vnesite tri cela števila: bazo b, nenegativni eksponent e in pozitivni modul m. Kalkulator vrne ostanek pri deljenju b na potenco e z m. Naivno računanje b^e bi pri velikih eksponentih povzročilo prekoračitev, zato orodje uporablja potenciranje s kvadriranjem (znano tudi kot binarno potenciranje).

Algoritma začne z result = 1 in reducira bazo po modulu m. Nato hodi skozi bite eksponenta od najmanj do najbolj pomembnega: kadar je trenutni bit 1, pomnoži tekoči rezultat s trenutno bazo (mod m), in pri vsakem koraku kvadrira bazo (mod m) ter eksponent premakne za en bit v desno. Ker se vsak vmesni produkt reducira po modulu m, ostajajo števila majhna, obseg dela pa je sorazmeren z log2(e) množenji namesto e množenj. Vse aritmetične operacije se izvajajo z JavaScript BigInt, zato so rezultati točni ne glede na velikost.

Predpostavke in robni primeri: eksponent mora biti celo število e >= 0, modul pa pozitivno celo število m > 0 (mod 0 ni definiran). Baza je lahko negativna; najprej se normalizira v obseg 0..m-1 z ((b mod m) + m) mod m, tako da je vrnjeni ostanek vedno nenegativen. Ko e = 0, je rezultat 1 mod m. Ko m = 1, je rezultat vedno 0.