Algorytm szybkiego potęgowania

Algorytm szybkiego potęgowania to technika umożliwiająca efektywne obliczenie potęgi z wykładnikiem naturalnym. Metoda ta opiera się na dwójkowej reprezentacji wykładnika potęgi, a jej złożoność, wyrażona jako liczba mnożeń, wynosi Θ(log n), gdzie n to wykładnik potęgi, którą obliczamy.

Szybkie potęgowanie jest wykorzystywane w praktycznych zastosowaniach, takich jak obliczanie reszty z dzielenia potęgi przez zdefiniowaną liczbę, na przykład w algorytmach szyfru RSA.

Wprowadzenie

Potęgowanie można zdefiniować w oparciu o mnożenie:

x^k = x ⋅ x^k-1 = x ⋅ x ⋅ x ⋅ … ⋅ x (łącznie k – 1 mnożeń).

Dla dużych wartości k liczba wymaganych operacji może stać się znaczna. W przypadku, gdy k ma j cyfr, liczba tych operacji byłaby wykładnicza w odniesieniu do j.

Algorytm

Algorytm szybkiego potęgowania wynika z obserwacji, że do obliczenia wartości a^b wystarczy znać wartość a^⌊b/2⌋ (gdzie ⌊ ⋅ ⌋ oznacza część całkowitą) i wykonać jedno lub dwa mnożenia. Na przykład, aby obliczyć 5¹⁷⁵, wystarczy znać wartość x = 5⁸⁷, a następnie obliczyć y = x² = 5¹⁷⁴, a wynik to y ⋅ 5.

W ten sposób, by przejść od 5⁸⁷ do 5¹⁷⁵, wystarczy wykonać 2 mnożenia zamiast 88, jak sugerowałaby definicja.

Pseudokod

Na podstawie powyższych obserwacji można stworzyć rekurencyjną funkcję do szybkiego obliczania wartości xⁿ:

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²

Po optymalizacji funkcja może wyglądać następująco:

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

Algorytm w wersji iteracyjnej przedstawia się tak:

w := 1
dla a = m do 1   // m - liczba 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 tego algorytmu w zmiennej w zapamiętana jest n-ta potęga liczby x.