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.
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 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 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.