Rozkład na czynniki pierwsze
Wprowadzenie
Rozkład na czynniki pierwsze (faktoryzacja) to proces przedstawienia liczby naturalnej jako iloczynu liczb pierwszych. Jest to fundamentalna operacja w teorii liczb i kryptografii.
Zasadnicze twierdzenie arytmetyki głosi, że każda liczba naturalna > 1 ma jednoznaczny rozkład na czynniki pierwsze (z dokładnością do kolejności).
Przykłady:
12 = 2² × 3
60 = 2² × 3 × 5
1001 = 7 × 11 × 13
Faktoryzacja jest wykorzystywana w:
- Kryptografii (bezpieczeństwo RSA opiera się na trudności faktoryzacji dużych liczb)
- Obliczaniu NWD i NWW (metoda przez faktoryzację)
- Teorii liczb (badanie własności liczb)
- Upraszczaniu wyrażeń matematycznych
- Testowaniu pierwszości
- Algorytmach optymalizacyjnych
Podstawy teoretyczne
Zasadnicze twierdzenie arytmetyki
Twierdzenie: Każda liczba naturalna n > 1 może być przedstawiona jednoznacznie jako:
n = p₁^a₁ × p₂^a₂ × ... × pₖ^aₖ
gdzie:
- p₁, p₂, ..., pₖ to różne liczby pierwsze (p₁ < p₂ < ... < pₖ)
- a₁, a₂, ..., aₖ to wykładniki (liczby naturalne ≥ 1)
Przykłady:
360 = 2³ × 3² × 5¹
1000 = 2³ × 5³
2310 = 2 × 3 × 5 × 7 × 11
Algorytm podstawowy - próbne dzielenie
Implementacja klasyczna
Wyjście:
=== Rozkład na czynniki pierwsze (metoda podstawowa) ===
Liczba Czynniki pierwsze Rozkład
-----------------------------------------------------------------
12 2 × 2 × 3 2^2 × 3
60 2 × 2 × 3 × 5 2^2 × 3 × 5
100 2 × 2 × 5 × 5 2^2 × 5^2
1001 7 × 11 × 13 7 × 11 × 13
2310 2 × 3 × 5 × 7 × 11 2 × 3 × 5 × 7 × 11
Optymalizacje algorytmu
1. Sprawdzanie tylko do √n
Obserwacja: Jeśli n ma dzielnik > √n, to ma też dzielnik < √n.
Wyjście:
=== Rozkład z optymalizacją (√n) ===
Liczba √n Czynniki
------------------------------------------------------------
1234567 1111 127 × 9721
9876543 3142 3 × 3 × 1097393
123456789 11111 3 × 3 × 3607 × 3803
2. Zwracanie słownika z wykładnikami
Wyjście:
=== Rozkład jako słownik {p: wykładnik} ===
Liczba Słownik Reprezentacja
----------------------------------------------------------------------
360 {2: 3, 3: 2, 5: 1} 2^3 × 3^2 × 5
1000 {2: 3, 5: 3} 2^3 × 5^3
2520 {2: 3, 3: 2, 5: 1, 7: 1} 2^3 × 3^2 × 5 × 7
65536 {2: 16} 2^16
Zastosowania faktoryzacji
1. Obliczanie NWD przez faktoryzację
Wyjście:
=== NWD przez faktoryzację ===
a b Faktoryzacja a Faktoryzacja b NWD
--------------------------------------------------------------------------------
48 18 {2: 4, 3: 1} {2: 1, 3: 2} 6
360 240 {2: 3, 3: 2, 5: 1} {2: 4, 3: 1, 5: 1} 120
1001 143 {7: 1, 11: 1, 13: 1} {11: 1, 13: 1} 143
2. Obliczanie NWW przez faktoryzację
Wyjście:
=== NWW przez faktoryzację ===
a b NWD NWW a×b NWD×NWW
----------------------------------------------------------------------
12 18 6 36 216 216
15 25 5 75 375 375
48 64 16 192 3072 3072
3. Liczba dzielników
Wyjście:
=== Liczba dzielników ===
Liczba Faktoryzacja Wzór Liczba dziel. Dzielniki
----------------------------------------------------------------------------------------------------
12 {2: 2, 3: 1} (2+1) × (1+1) 6 [1, 2, 3, 4, 6, 12]
28 {2: 2, 7: 1} (2+1) × (1+1) 6 [1, 2, 4, 7, 14, 28]
60 {2: 2, 3: 1, 5: 1} (2+1) × (1+1) × (1+1) 12 [1, 2, 3, 4, 5, 6, 10, 12, 15, 20]
100 {2: 2, 5: 2} (2+1) × (2+1) 9 [1, 2, 4, 5, 10, 20, 25, 50, 100]
360 {2: 3, 3: 2, 5: 1} (3+1) × (2+1) × (1+1) 24 [1, 2, 3, 4, 5]...[180, 360]
4. Suma dzielników
Wyjście:
=== Suma dzielników ===
Liczba Faktoryzacja Dzielniki Suma Wzór
-----------------------------------------------------------------------------------------------
6 {2: 1, 3: 1} [1, 2, 3, 6] 12 σ(6)=12
12 {2: 2, 3: 1} [1, 2, 3, 4, 6, 12] 28 σ(12)=28
28 {2: 2, 7: 1} [1, 2, 4, 7, 14, 28] 56 σ(28)=56
100 {2: 2, 5: 2} [1, 2, 4, 5, 10, 20, 25, 50, 100] 217 σ(100)=217
220 {2: 2, 5: 1, 11: 1} [1, 2, 4, 5, 10, 11, 20, 22]...[110, 220] 504 σ(220)=504
Wizualizacja procesu faktoryzacji
Wyjście:
=== Wizualizacja faktoryzacji ===
Rozkład liczby 360 na czynniki pierwsze:
Krok Dzielnik n Czynnik
--------------------------------------------------
1 2 360 2
2 2 180 2
3 2 90 2
4 3 45 3
5 3 15 3
6 5 5 5 (liczba pierwsza)
Wynik: 360 = 2 × 2 × 2 × 3 × 3 × 5
Postać wykładnicza: 360 = 2^3 × 3^2 × 5
Rozkład liczby 1001 na czynniki pierwsze:
Krok Dzielnik n Czynnik
--------------------------------------------------
1 7 1001 7
2 11 143 11
3 13 13 13 (liczba pierwsza)
Wynik: 1001 = 7 × 11 × 13
Postać wykładnicza: 1001 = 7 × 11 × 13
Algorytmy zaawansowane
Metoda Fermata (dla liczb z bliskimi dzielnikami)
Wyjście:
=== Faktoryzacja metodą Fermata ===
Liczba Faktoryzacja Sprawdzenie
--------------------------------------------------
143 11 × 13 143 = 143 (✓)
1763 41 × 43 1763 = 1763 (✓)
5767 73 × 79 5767 = 5767 (✓)
8051 89 × 91 8051 = 8099 (✗)
Złożoność obliczeniowa
Porównanie algorytmów
| Algorytm | Złożoność | Zastosowanie |
|---|---|---|
| Próbne dzielenie | O(√n) | Małe liczby (< 10¹²) |
| Metoda Fermata | O(√n) | Liczby z bliskimi dzielnikami |
| Rho Pollarda | O(n^¼) | Średnie liczby |
| Kwadratowe sito | O(e^√(ln n ln ln n)) | Duże liczby |
| GNFS | O(e^(∛(ln n ln ln n))) | Bardzo duże liczby |
Uwaga: Faktoryzacja dużych liczb (np. 2048-bitowych) jest computationally hard - podstawa bezpieczeństwa RSA!
Podsumowanie
Kluczowe algorytmy
✅ Próbne dzielenie: Prosty, O(√n), dobry dla małych liczb ✅ Faktoryzacja do słownika: Zwraca {p: wykładnik} ✅ Metoda Fermata: Dobra dla bliskich dzielników ✅ Algorytmy zaawansowane: Dla bardzo dużych liczb
Zastosowania
✅ NWD i NWW: Obliczanie przez faktoryzację ✅ Liczba dzielników: τ(n) = ∏(aᵢ + 1) ✅ Suma dzielników: σ(n) = ∏(p^(a+1)-1)/(p-1) ✅ Liczby doskonałe: σ(n) = 2n ✅ Kryptografia: Trudność faktoryzacji = bezpieczeństwo
Własności
✅ Jednoznaczność: Rozkład jest unikatowy ✅ Multiplikatywność: Funkcje τ, σ są multiplikatywne ✅ Dzielniki: Wyznaczanie przez czynniki pierwsze
Co dalej?
Po opanowaniu rozkładu na czynniki pierwsze, następne kroki to:
- Lekcja 70: Liczby doskonałe
- Definicja: σ(n) = 2n
- Liczby obfite i niedoborne
-
Twierdzenie Eulera-Mersenne'a
-
Lekcja 71: Pierwiastkowanie - metoda Newtona
- Algorytm aproksymacji
- Pierwiastki wyższych stopni
-
Zastosowania numeryczne
-
Lekcja 72: Szybkie potęgowanie
- Algorytm binarny
- Potęgowanie modularne
- Zastosowania w kryptografii
Zadania praktyczne
Zadanie 1: Generator liczb pierwszych z faktoryzacji
Znajdź wszystkie liczby pierwsze do N używając faktoryzacji kolejnych liczb.
Zadanie 2: Liczby z dokładnie K dzielnikami
Znajdź wszystkie liczby ≤ N mające dokładnie K dzielników.
Zadanie 3: Najbardziej złożona liczba
Znajdź liczbę ≤ N z największą liczbą różnych czynników pierwszych.
Zadanie 4: Kalkulator funkcji arytmetycznych
Zaimplementuj funkcje τ(n), σ(n), φ(n), μ(n) używając faktoryzacji.
Zadanie 5: Test Fermata dla liczb złożonych
Użyj metody Fermata do szybkiego znajdowania dzielników liczb postaci p×q gdzie p ≈ q.
Następna lekcja: Liczby doskonałe - teoria i algorytmy