Algorytm szybkiego potęgowania

Z Wikipedii, wolnej encyklopedii
Skocz do: nawigacja, szukaj
Algorytm szybkiego potęgowania
Rodzaj Potęgowanie
Złożoność
Czasowa
– wykładnik

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

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.

Wprowadzenie[edytuj]

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 .

Algorytm[edytuj]

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.

Pseudokod[edytuj]

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 .