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 O(log n), gdzie n oznacza wykładnik obliczanej potęgi.

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

Co po rozwinięciu daje k − 1 mnożeń:

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

Algorytm szybkiego potęgowania jest konsekwencją obserwacji, że aby obliczyć wartość a^b wystarczy znać a^{[b / 2]} ([b / 2] oznacza całkowitą część z b / 2), 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 definicji.

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

Niech A będzie ustaloną liczbą wtedy pot(n) = Aⁿ definiujemy następująco:

• pot(1)=A
• pot(2*n)=pot(n)*pot(n)
• pot(2*n+1)=pot(2*n)*A dla n>0.

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

1. w:=A
2. dla wszystkich cyfr rozwinięcia dwójkowego liczby n poczynając od drugiej wykonuj:

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

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

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

Szybkie podnoszenie do potęgi w praktyce stosuje się do liczenia reszty z dzielenia potęgi przez jakąś ustaloną liczbę. Zastosowane jest np. w algorytmach szyfru RSA.