Potęgowanie modularne. Naszym celem jest policzenie
ab mod n.
Oczywiście, możemy założyć, że 0≤a<n, bo inaczej najpierw można policzyć resztę a′ z dzielenia a przez n, a dopiero potem (a′)b mod n, jako że (a′)b mod n=ab mod n. Zauważmy, że w przeciwieństwie do zwykłego potęgowania wynik nigdy nie przekracza n, czyli nie rośnie wykładniczo w stosunku do a. Pozwala to żywić nadzieję na szybsze algorytmy potęgujące. Dla rozgrzewki przeanalizujmy najpierw naiwny sposób liczenia potęgi modulo:
Policzmy zatem w następujacy sposób kolejne potęgi a występujące w iloczynie:
a⋅a mod n≡na2 mod n,(a2 mod n)⋅(a2 mod n)≡na4 mod n,…(a2k−2 mod n)⋅(a2k−2 mod n)≡na2k−1 mod n.
Tym sposobem wykonanych zostanie k−2 mnożeń i dzieleń liczb O(logn)-bitowych, czyli O(klog2n) operacji bitowych. Aby otrzymać wynik musimy jeszcze wymnożyć przez siebie te potęgi, ktorym odpowiada bit 1 w liczbie b. Wykonanych zostanie więc jeszcze co najwyżej k mnożeń (które przeplatamy braniem reszty modulo n) liczb O(logn)-bitowych.
W sumie wykonanych zostanie O(klog2n)=O(logb⋅log2n) operacji bitowych, a więc znacznie mniej niż sposobem naiwnym. Przedstawiony algorytm jest efektywny (wielomianowy względem długości wejścia).
Przykład
712 mod 10=?
Przykład
351 mod 13=?