Potęgowanie przez kwadratowanie omija niemal wszystkie mnożenia
Aby policzyć a^n, nie trzeba mnożyć a przez siebie n-1 razy. Wykładnik można odczytać binarnie, a kolejne potęgi a², a⁴, a⁸, a¹⁶… uzyskuje się przez wielokrotne podnoszenie poprzedniego wyniku do kwadratu. Do wyniku włącza się tylko te potęgi, które odpowiadają jedynkom w zapisie binarnym n. Liczba kroków rośnie więc proporcjonalnie do liczby bitów wykładnika, czyli O(log n), a nie O(n). Różnica staje się kolosalna dla ogromnych wykładników używanych w kryptografii, gdzie szybkie potęgowanie modularne jest jedną z podstawowych operacji RSA, Diffiego–Hellmana i innych systemów.
Wykładnik jest także informacją o strukturze obliczenia
Zapis a^13 sugeruje trzynaście czynników a i dwanaście kolejnych mnożeń. Ale 13 w systemie binarnym to 1101, czyli 8+4+1. Wystarczy policzyć a², potem a⁴=(a²)² i a⁸=(a⁴)², a następnie pomnożyć a⁸·a⁴·a. Kilka operacji zastępuje liniowy łańcuch powtarzania tej samej czynności.
Dla ogólnego wykładnika n wykonujemy kolejne kwadraty podstawy, analizując bity n. Każde przesunięcie do następnego bitu odpowiada podwojeniu wykładnika przez kwadratowanie; jedynka oznacza, że bieżącą potęgę trzeba dołączyć do wyniku. Ponieważ liczba bitów n jest rzędu log2 n, liczba etapów również rośnie logarytmicznie.
Przewaga rośnie wykładniczo z rozmiarem zapisu
Tu szczególnie dobrze widać różnicę pomiędzy wartością liczby a rozmiarem jej reprezentacji. Liczba n≈2^1000 ma około tysiąca bitów, ale jej wartość ma około 300 cyfr dziesiętnych. Naiwne wykonywanie n mnożeń byłoby niewyobrażalne. Algorytm binarny potrzebuje liczby kroków zależnej od około tysiąca bitów wykładnika, nie od astronomicznej wartości n.
Oczywiście każde mnożenie bardzo dużych liczb samo ma koszt, więc pełna analiza musi uwzględniać rozmiar operandów. W arytmetyce modularnej po każdym mnożeniu redukuje się wynik modulo m, dzięki czemu liczby nie rosną bez ograniczeń. Mimo to przejście z liczby mnożeń liniowej w n do logarytmicznej jest fundamentalne.
Bez tego publiczna kryptografia byłaby niepraktyczna
Handbook of Applied Cryptography opisuje szybkie metody potęgowania jako jedne z najważniejszych operacji dla kryptografii klucza publicznego. RSA wymaga obliczeń postaci x^d mod n, a Diffie–Hellman i ElGamal również intensywnie korzystają z potęgowania w grupach skończonych. Podręcznik podkreśla, że prosta metoda wykonująca e-1 mnożeń byłaby dla typowych dużych wykładników niewykonalna.
Podstawowy algorytm square-and-multiply jest punktem wyjścia. Istnieją bardziej zaawansowane techniki — okna, łańcuchy dodawania czy specjalne reprezentacje wykładnika — które zmniejszają liczbę mnożeń jeszcze bardziej w określonych warunkach. Wszystkie rozwijają tę samą ideę: wykorzystać strukturę wykładnika, zamiast traktować potęgowanie jak ślepe powtarzanie.
Ten sam trik działa poza zwykłymi liczbami
Mechanizm nie zależy od tego, czy mnożymy zwykłe liczby całkowite. Wystarczy operacja łączna, dla której można sensownie wielokrotnie „mnożyć” element przez siebie. Dlatego analogiczne szybkie potęgowanie stosuje się do macierzy, wielomianów czy elementów grup. Potęga macierzy może np. opisywać wielokrotne zastosowanie transformacji, a jej szybkie obliczenie pozwala przyspieszać niektóre rekurencje liniowe.
To jest szersza lekcja algorytmiczna: zapis binarny nie służy tylko do magazynowania liczb. Może bezpośrednio sterować strukturą obliczenia. Każdy bit wykładnika odpowiada decyzji „kwadratuj” i ewentualnie „pomnóż do wyniku”, dzięki czemu długość reprezentacji staje się naturalną miarą pracy.
Rekurencja wynika bezpośrednio z parzystości wykładnika
Tę samą metodę można zapisać bez analizowania bitów jawnie. Jeśli n jest parzyste, a^n=(a^(n/2))^2; jeśli n jest nieparzyste, a^n=a·(a^((n-1)/2))^2. W każdym kroku wykładnik zmniejsza się mniej więcej o połowę, dlatego głębokość rekurencji jest logarytmiczna. Ta postać dobrze pokazuje, skąd bierze się przyspieszenie: algorytm nie „pomija” potęg w magiczny sposób, tylko wykorzystuje fakt, że raz policzona połowa potęgi może zostać użyta dwukrotnie przez jedno kwadratowanie. To klasyczny przykład zastąpienia powtarzania przez ponowne wykorzystanie struktury wyniku pośredniego.
Square-and-multiply jest punktem wyjścia, nie absolutnym minimum mnożeń
Binarny algorytm gwarantuje bardzo dobry ogólny sposób wykorzystania zapisu wykładnika, ale dla konkretnego wykładnika można czasem znaleźć krótszy łańcuch dodawania. Taki łańcuch zaczyna się od 1, a każdy kolejny wykładnik jest sumą dwóch wcześniej dostępnych; odpowiada to mnożeniu dwóch już policzonych potęg. Na przykład różne strategie mogą wykorzystywać powtarzające się fragmenty wykładnika albo przetwarzać kilka bitów naraz w metodach okienkowych. Handbook of Applied Cryptography omawia takie ulepszenia obok podstawowej metody. Pokazuje to ciekawą hierarchię optymalizacji: najpierw przechodzimy z liniowej liczby mnożeń do logarytmicznej dzięki reprezentacji binarnej, a potem próbujemy zmniejszać stałą i liczbę drogich mnożeń przez lepsze planowanie kolejności potęg pośrednich.