Algorytm szybkiego potęgowania

Z Wikipedii

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 Θ(logn), 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.

[edytuj] Wprowadzenie

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

,

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.

[edytuj] Algorytm

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

[edytuj] Pseudokod

Dostajemy z powyższej obserwacji rekurencyjną funkcję szybkiego podnoszenia do potęgi.

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óć a²

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

funkcja potęga(x, n)
    w = x
    dla każdej, poczynając od drugiej, cyfry c rozwinięcia dwójkowego n
        w = w²
        jeżeli c jest jedynką
            w = w · x
    zwróć w