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 gdzie oznacza wykładnik obliczanej potęgi.

Algorytm szybkiego potęgowania
Rodzaj

Potęgowanie

Złożoność
Czasowa


– wykładnik

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

WprowadzenieEdytuj

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

 

co daje łącznie   mnożeń.

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

AlgorytmEdytuj

Algorytm szybkiego potęgowania jest konsekwencją obserwacji, że aby obliczyć wartość   wystarczy znać   (  oznacza część całkowitą), a następnie wykonać jedno lub dwa mnożenia. Np. aby obliczyć   wystarczy znać wartość   a następnie policzyć   i wynik wynosi   W ten sposób, aby wykonać jeden krok algorytmu, czyli przejść od   do   wystarczy wykonać 2 mnożenia zamiast 88, jak wynikałoby to z przytoczonej wyżej definicji.

PseudokodEdytuj

Z powyższych obserwacji można uzyskać rekurencyjną funkcję szybkiego obliczania wartości  

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

Po optymalizacji można otrzymać następującą postać:

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

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

w:= 1
dla a = m do 1   // m - ilość miejsc binarnych liczby n
    c = a-ta cyfra binarna liczby n
    jeżeli c = 0
       w:= w · w
    jeżeli c = 1
       w:= w · w · x

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