Algorytm szybkiego potęgowania
Z Wikipedii, wolnej encyclopedia
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 fakty Rodzaj, Czasowa ...
Rodzaj | |
---|---|
Złożoność | |
Czasowa |
|
Zamknij
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.