Algorytm szybkiego potęgowania

Algorytm szybkiego potęgowania – metoda pozwalająca na szybkie obliczenie potęgi o wykładniku naturalnym. Metoda ta wykorzystuje pośrednio dwójkową reprezentację wykładnika potęgi, a jej złożoność, wyrażona jako liczba wykonywanych mnożeń, wynosi $\Theta(\log n)$, gdzie n oznacza wykładnik obliczanej potęgi.

Szybkie podnoszenie do potęgi w praktyce stosuje się do liczenia reszty z dzielenia potęgi przez ustaloną liczbę. Używa się go np. w algorytmach szyfru RSA.

Wprowadzenie

Potęgowanie definiuje się za pomocą mnożenia

$\begin{matrix} x^k = x \cdot x^{k-1} = & \underbrace{x \cdot x \cdot x \cdot \ldots \cdot x }\\ & {}^k \end{matrix}$,

co daje łącznie $k-1$ mnożeń.

Dla dużego $k$ liczba wymaganych operacji może być bardzo duża. Jeśli $k$ ma $j$ cyfr, liczba operacji byłaby wykładnicza wobec $j$.

Algorytm

Algorytm szybkiego potęgowania jest konsekwencją obserwacji, że aby obliczyć wartość $a^b$ wystarczy znać $a^{\lfloor b/2\rfloor}$ ($\lfloor\cdot\rfloor$ oznacza część całkowitą), a następnie wykonać jedno lub dwa mnożenia. Np. aby obliczyć $5^{175}$ wystarczy znać wartość $x=5^{87}$, a następnie policzyć $y=x^2=5^{174}$ i wynik wynosi $=y\cdot 5$. W ten sposób aby przejść od $5^{87}$ do $5^{175}$ wystarczy wykonać 2 mnożenia zamiast 88, jak wynikałoby to z przytoczonej wyżej definicji.

Pseudokod

Dostajemy z powyższej obserwacji rekurencyjną funkcję szybkiego obliczania wartości $x^n$.

funkcja potęga(x, n)
    jeżeli n = 0
        zwróć 1
    jeżeli n jest nieparzysta
        zwróć x · potęga(x, n - 1)
    w przeciwnym przypadku
        a = potęga(x, n/2)
    zwróć a2

Ten sam algorytm w wersji iteracyjnej wygląda następująco:

1. w:=1
2. dla wszystkich cyfr rozwinięcia dwójkowego liczby n zaczynając od najbardziej znaczącej:

jeśli cyfra jest zerem to w:=w*w

jeśli cyfra jest jedynką to w:=w*w*x

po zakończeniu powyższego algorytmu w zmiennej w jest pamiętana n-ta potęga liczby x.