Szybkie potęgowanie
Wprowadzenie
Szybkie potęgowanie (ang. exponentiation by squaring lub binary exponentiation) to efektywny algorytm obliczania potęg a^n w czasie logarytmicznym. Jest fundamentalny w kryptografii, algebrze komputerowej i wielu innych dziedzinach.
Idea: Zamiast mnożyć a przez siebie n razy (O(n)), wykorzystujemy własności potęg do redukcji liczby operacji do O(log n).
Kluczowa obserwacja:
a^n = {
1 jeśli n = 0
a × a^(n-1) jeśli n nieparzyste (naiwnie)
(a^(n/2))² jeśli n parzyste
}
Szybkie potęgowanie jest wykorzystywane w:
- Kryptografii (RSA, Diffie-Hellman, podpisy cyfrowe)
- Teorii liczb (testy pierwszości, obliczenia modulo)
- Grafice komputerowej (transformacje macierzy)
- Obliczeniach numerycznych (duże wykładniki)
- Algebrze (grupy, pierścienie, ciała)
- Algorytmach probabilistycznych
Podstawy teoretyczne
Wzór rekurencyjny
Dla obliczenia a^n:
a^n = {
1 jeśli n = 0
a × a^(n-1) jeśli n = 1
(a^(n/2))² jeśli n parzyste
a × (a^(n/2))² jeśli n nieparzyste
}
Przykład: Obliczanie 2^10
2^10 = (2^5)²
2^5 = 2 × (2^2)²
2^2 = (2^1)²
2^1 = 2
Wstecz:
2^1 = 2
2^2 = 4
2^5 = 2 × 16 = 32
2^10 = 1024
Liczba operacji: log₂(n) zamiast n!
Implementacja podstawowa
Wersja rekurencyjna
Wyjście:
=== Szybkie potęgowanie (rekurencyjne) ===
a n a^n Sprawdzenie (Python)
--------------------------------------------------
2 10 1024 1024 ✓
3 5 243 243 ✓
5 0 1 1 ✓
7 12 13841287201 13841287201 ✓
10 6 1000000 1000000 ✓
Wersja iteracyjna
Wyjście:
=== Szybkie potęgowanie (iteracyjne) ===
a n a^n Sprawdzenie
----------------------------------------
2 10 1024 ✓
3 5 243 ✓
5 0 1 ✓
7 12 13841287201 ✓
10 6 1000000 ✓
Wizualizacja procesu
Wyjście:
Obliczanie 2^10 metodą szybkiego potęgowania:
n = 10 = 1010₂ (binarnie)
Krok Bit n Bieżąca potęga Wynik Operacja
--------------------------------------------------------------------------------
1 0 2 1 pomiń
2 1 4 4 1 × 4 = 4
3 0 16 4 pomiń
4 1 256 1024 4 × 256 = 1024
Wynik końcowy: 2^10 = 1024
Obliczanie 3^13 metodą szybkiego potęgowania:
n = 13 = 1101₂ (binarnie)
Krok Bit n Bieżąca potęga Wynik Operacja
--------------------------------------------------------------------------------
1 1 3 3 1 × 3 = 3
2 0 9 3 pomiń
3 1 81 243 3 × 81 = 243
4 1 6561 1594323 243 × 6561 = 1594323
Wynik końcowy: 3^13 = 1594323
Potęgowanie modularne
Kluczowe zastosowanie w kryptografii
Problem: Oblicz (a^n) mod m
Zastosowanie: RSA, Diffie-Hellman, generatory liczb pseudolosowych
Wyjście:
=== Potęgowanie modularne ===
Wyrażenie Wynik Sprawdzenie (pow)
------------------------------------------------------------
2^10 mod 1000 24 24 ✓
3^100 mod 7 4 4 ✓
5^117 mod 19 1 1 ✓
123^456 mod 789 699 699 ✓
Zastosowania w kryptografii
1. Algorytm RSA - szyfrowanie
Wyjście:
=== Demo szyfrowania RSA ===
Klucz publiczny (e, n): (17, 3233)
Klucz prywatny (d, n): (2753, 3233)
Wiadomość: 123
Zaszyfrowana: 855 (obliczone jako 123^17 mod 3233)
Odszyfrowana: 123 (obliczone jako 855^2753 mod 3233)
Weryfikacja: 123 == 123 ✓
2. Test pierwszości Fermata
Małe twierdzenie Fermata: Jeśli p jest pierwsza i a nie dzieli się przez p, to:
a^(p-1) ≡ 1 (mod p)
Wyjście:
=== Test pierwszości Fermata ===
Liczba Typ rzeczywisty Test Fermata
------------------------------------------------------------
17 pierwsza prawdopodobnie pierwsza
19 pierwsza prawdopodobnie pierwsza
21 złożona na pewno złożona
561 złożona (liczba Carmichaela) prawdopodobnie pierwsza
1009 pierwsza prawdopodobnie pierwsza
1024 złożona na pewno złożona
Rozszerzenia algorytmu
1. Potęgowanie macierzy
Wyjście:
=== Fibonacci przez potęgowanie macierzy ===
n F(n) (macierz) F(n) (rekurencja)
--------------------------------------------------
5 5 5 ✓
10 55 55 ✓
20 6765 6765 ✓
50 12586269025 12586269025 ✓
100 354224848179261915075 354224848179261915075 ✓
Porównanie wydajności
Wyjście (przykładowe):
=== Benchmark metod potęgowania ===
a^n Metoda Czas (μs) Wynik (10 cyfr)
---------------------------------------------------------------------------
2^100 Naiwna (a×a×...) 12.34 1267650600...
2^100 Szybkie (binarne) 0.89 1267650600...
2^100 Python (**) 0.45 1267650600...
3^1000 Naiwna (a×a×...) 145.67 1322070819...
3^1000 Szybkie (binarne) 1.23 1322070819...
3^1000 Python (**) 0.67 1322070819...
5^10000 Szybkie (binarne) 2.34 5282437174...
5^10000 Python (**) 1.12 5282437174...
Złożoność obliczeniowa
Analiza teoretyczna
| Metoda | Złożoność czasowa | Liczba mnożeń |
|---|---|---|
| Naiwna | O(n) | n - 1 |
| Szybkie potęgowanie | O(log n) | ⌈log₂ n⌉ do 2⌈log₂ n⌉ |
| Potęgowanie modularne | O(log n) | ⌈log₂ n⌉ do 2⌈log₂ n⌉ |
Przykład: Dla n = 1000 - Naiwna: 999 mnożeń - Szybka: ~10-20 mnożeń (redukcja 50-100×!)
Podsumowanie
Kluczowe algorytmy
✅ Rekurencyjne: Eleganckie, łatwe do zrozumienia ✅ Iteracyjne: Bardziej efektywne pamięciowo ✅ Modularne: Kluczowe dla kryptografii ✅ Macierzowe: Szybkie obliczenia Fibonacciego
Wzory kluczowe
Zastosowania
✅ RSA: Szyfrowanie i deszyfrowanie ✅ Diffie-Hellman: Wymiana kluczy ✅ Testy pierwszości: Fermat, Miller-Rabin ✅ Fibonacci: O(log n) zamiast O(n) ✅ Obliczenia numeryczne: Duże wykładniki
Co dalej?
Po opanowaniu szybkiego potęgowania, dalsze tematy to:
- Zaawansowana teoria liczb:
- Chińskie twierdzenie o resztach
- Funkcja Eulera φ(n)
-
Logarytm dyskretny
-
Kryptografia:
- Pełna implementacja RSA
- Eliptyczne krzywe (ECC)
-
Podpisy cyfrowe
-
Algorytmy numeryczne:
- Transformata Fouriera (FFT)
- Mnożenie wielomianów
- Obliczenia macierzowe
Zadania praktyczne
Zadanie 1: Ostatnia cyfra potęgi
Oblicz ostatnią cyfrę dziesiętną liczby a^n dla bardzo dużych n.
Zadanie 2: Generator Diffie-Hellman
Zaimplementuj prosty protokół wymiany kluczy Diffie-Hellman.
Zadanie 3: Fibonacci mod m
Oblicz F(n) mod m dla bardzo dużych n używając potęgowania macierzy.
Zadanie 4: Test Lucas-Lehmer
Zaimplementuj test pierwszości Lucas-Lehmer dla liczb Mersenne'a.
Zadanie 5: Potęgowanie dla grup
Rozszerz szybkie potęgowanie na operacje w dowolnej grupie (nie tylko liczby).
Następna lekcja: Gratuluję ukończenia kursu algorytmów i struktur danych!