Potęgowanie modularne. Naszym celem jest policzenie
\( a^b\ {\sf mod} \ n . \)
Oczywiście, możemy założyć, że \( 0\leq a < n \), bo inaczej najpierw można policzyć resztę \( a' \) z dzielenia \( a \) przez \( n \), a dopiero potem \( (a')^b \ {\sf mod} \ n \), jako że \( (a')^b \ {\sf mod}\ n =a^b \ {\sf 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:
\( \begin{align*} a \cdot a \ {\sf mod} \ n & \equiv_n & a^2 \ {\sf mod} \ n , \\ (a^2 \ {\sf mod} \ n )\cdot(a^2 \ {\sf mod}\ n ) & \equiv_n & a^4 \ {\sf mod} \ n , \\ & \ldots & \\ (a^{2^{k-2}} \ {\sf mod} \ n )\cdot(a^{2^{k-2}} \ {\sf mod} \ n ) & \equiv_n & a^{2^{k-1}} \ {\sf mod} \ n . \end{align*} \)
Tym sposobem wykonanych zostanie \( k-2 \) mnożeń i dzieleń liczb \( O(\log{n}) \)-bitowych, czyli \( O(k\log^2{n}) \) 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(\log{n}) \)-bitowych.
W sumie wykonanych zostanie \( O(k\log^2{n})=O(\log{b}\cdot\log^2{n}) \) operacji bitowych, a więc znacznie mniej niż sposobem naiwnym. Przedstawiony algorytm jest efektywny (wielomianowy względem długości wejścia).
Przykład
\( 7^{12} \ {\sf mod} \ 10 =? \)
Przykład
\( 3^{51} \ {\sf mod} \ 13 =? \)