Teoria liczb: Królowa matematyki

Pierwsze i podstawowe twierdzenia

Pierwsze liczby: całkowite większe od 1, podzielne tylko przez 1 i same siebie — „atomy” arytmetyki. Podstawowe twierdzenie arytmetyki: każda liczba całkowita większa od 1 ma jednoznaczne rozkład na czynniki pierwsze (Elementy Euklidesa, około 300 p.n.e.). Dowód Euklidesa na nieskończoność pierwszych liczb: jeśli istnieje skończona liczba pierwszych p₁...pₙ, to liczbę p₁×p₂×...×pₙ + 1 nie można podzielić przez żadną z tych liczb — sprzeczność. Twierdzenie o pierwiastkach pierwszych (Hadamard, de la Vallée-Poussin, 1896): π(x) ~ x/ln(x) — liczby pierwsze rozkładają się logarytmicznie, ale nigdy nie znikają. Hipoteza dwójek pierwszych: nieskończenie wiele par (p, p+2)? Yitang Zhang (2013): udowodnił ograniczone przerwy między liczbami pierwszymi (po początkowo 70 milionów, obecnie zredukowane do 246 przez Maynard/Tao). Hipoteza Goldbacha (1742): każda parzysta liczba większa od 2 jest sumą dwóch liczb pierwszych — zweryfikowana do 4×10¹⁸, ale nieudowodniona. Liczby Mersenne’a: 2ᵖ−1 — największe znane liczby pierwsze. Do 2024 roku: 2⁸²⁵⁸⁹⁹³³−1 (24,862,048 cyfr). GIMPS: projekt obliczeniowy rozprzestrzeniony od 1996 roku szukający liczb Mersenne’a.

Artymetyka modularna i kongruencje

Artymetyka modularna: arytmetyka na reszta. a ≡ b (mod n) oznacza, że n dzieli (a−b). Artymetyka zegarowa: 14:00 ≡ 2:00 (mod 12). Twierdzenie Fermata małego: dla pierwszej potęgi p i a takiego, że gcd(a,p)=1, mamy aᵖ⁻¹ ≡ 1 (mod p) — podstawowe twierdzenie testowania pierwszości. Twierdzenie Eulera: ogólizacja twierdzenia Fermata dla złożonych modułów przy użyciu funkcji totienta Eulera φ(n). Twierdzenie chinookańskiego o reszta (CRT): system kongruencji o względnie pierwszych modułach ma jednoznaczne rozwiązanie — używane w optymalizacji RSA. Reciprocność kwadratowa (Gauss, „złoty twierdzenie”): określa, które pierwsze p mają takie x² ≡ q (mod p) rozwiązane — łączy dwa wyglądające na odległe pierwsze. Korzenne pierwotne: generatory (Z/nZ)* — istnieją dla pierwszych, potęg pierwszych i 2p^k. Problem logarytmu dyskretnego: dane g, h, n, znaleźć x takie, że gˣ ≡ h (mod n) — uważany za obliczeniowo trudny, podstawa wymiany klucza Diffie-Hellmana. Krzywe eliptyczne nad ciałami skończonymi: y² = x³ + ax + b (mod p) — bogata struktura algebraiczna, podstawa kryptografii krzywych eliptycznych (ECC).

Hipoteza Riemaniana

Funkcja zeta Riemanna: ζ(s) = Σ(1/nˢ) dla Re(s) > 1, ciągła analitycznie do wszystkich liczb zespolonych s ≠ 1. Iloczyn Eulera: ζ(s) = Π(1−p⁻ˢ)⁻¹ nad liczbami pierwszymi — łączy funkcję zeta z rozkładem liczb pierwszych. Zera banalne: ζ(s) = 0 dla s = −2, −4, −6, ... (liczby całkowite parzyste ujemne). Zera niebanalne: wszystkie inne zera leżą w półprzestrzeni krytycznej 0 < Re(s) < 1. Hipoteza Riemaniana (1859): wszystkie zera niebanalne mają Re(s) = 1/2 (leżą na "półprostej krytycznej"). Wartość: hipoteza Riemaniana implikuje najmocniejszy możliwy warunek błędu w Twierdzeniu O Liczbach Prawie Przeciwległych — liczby pierwsze są rozłożone jak najbardziej regularnie. Weryfikacja obliczeniowa: pierwszych 10¹³+ zera leżą na półpróstej krytycznej — ale dowód numeryczny nie stanowi dowodu. Problem Millena: jeden z siedmiu problemów Instytutu Matematycznego Claya — nagroda w wysokości 1 miliona dolarów. Hipoteza Riemaniana ogólne: rozszerzona na funkcje L Dirichleta, funkcje zeta Dedekinda — znaczące implikacje. Konsekwencje, jeśli jest prawdziwa: lepsze ograniczenia dla przestrzeni między liczbami pierwszymi, błędy w postępach arytmetycznych, połączenia z teorią macierzy losowych i chaosem kwantowym. Hilbert: "Jeśli obudzę się po spoczynku tysiąclecia, moim pierwszym pytaniem będzie: została udowodniona hipoteza Riemaniana?"

Zastosowania w kryptografii

RSA szyfrowanie (Rivest, Shamir, Adleman, 1977): bezpieczeństwo opiera się na trudności rozkładu dużych liczb (iloczyn dwóch dużych liczb pierwszych). Generowanie kluczy RSA: wybierz liczby pierwsze p, q (~2048 bitów każdy), oblicz n = pq, wykładnik publiczny e, wykładnik prywatny d ≡ e⁻¹ (mod φ(n)). Najlepszy algorytm rozkładu — Sieve of General Number Field — podwyrażnieni, ale nadal niepraktyczny dla modulów 2048-bitowych na komputerach klasycznych. Kryptografia krzywych eliptycznych (ECC): równoważna bezpieczenstwo do RSA z znacznie mniejszymi kluczami (256-bitowy ECC ≈ 3072-bitowy RSA). Przestawienie kluczy Diffie-Hellmana: pierwszy protokół klucza publicznego (1976) — bezpieczeństwo opiera się na problemie logarytmu diskretnego. Funkcje skrótu: SHA-256, SHA-3 — właściwości teoretyczne numeryczne zapewniają odporność na kolizje. Testowanie liczb pierwszych: Miller-Rabin (prawdopodobny), AKS (określony wielomianowy — 2002, udowodniono, że PRIMES jest w P). Threat po quantumowych komputerach: algorytm Shor rozkłada liczby całkowite w czasie wielomianowym na komputerach kwantowych — RSA i ECC zostaną złamane. Kryptografia po quantumowych atakach: oparta na siatkach (CRYSTALS-Kyber), oparta na skrócie (SPHINCS+), oparta na kodach (Classic McEliece) — odporna na ataki kwantowe. Teoria liczb: od Gaussa „królowej matematyki” — czysta i piękna — do podstaw współczesnej cyfrowej bezpieczyństwa.

Wypróbuj na żywo

Wszystko powyżej działa bezpośrednio w Twojej przeglądarce — otwórz Parametric Spirograph Patterns i zmieniaj parametry podczas działania. Nic nie jest instalowane ani przesyłane na serwer, cały model działa w jednej karcie.