Matematyka · liczby i tajemnice
Liczby pierwsze i szyfry atomy arytmetyki
Liczba pierwsza dzieli się tylko przez 1 i przez siebie. Z takich „atomów” mnożeniem da się zbudować każdą liczbę — i to na dokładnie jeden sposób. Przesiej liczby sitem Eratostenesa, wypatrz ukośne smugi w spirali Ulama, policz na zegarze, złam szyfr Cezara jak średniowieczny kryptoanalityk, a potem zbuduj własny klucz RSA — ten sam pomysł, który chroni dziś kłódkę w pasku przeglądarki.
Laboratorium · sito Eratostenesa
Zakres siatki
Kliknij najmniejszą nieskreśloną liczbę większą od 1 — sito skreśli wszystkie jej wielokrotności. Albo puść sito samo.
Drzewo rozkładu na czynniki
—Cząsteczka z atomów pierwszych
Dzielenie próbne dla małych dzielników, test Millera–Rabina i metoda rho Pollarda dla dużych (BigInt).
Wszystkie dzielniki
Dlaczego 1 nie jest pierwsza? Gdyby była, rozkład nie byłby jednoznaczny: 6 = 2 · 3 = 1 · 2 · 3 = 1 · 1 · 2 · 3… Dlatego jedynka nie jest ani pierwsza, ani złożona.
Laboratorium · spirala Ulama i otwarte zagadki
Spirala
Kolory
Środek spirali
Stanisław Ulam, polski matematyk pracujący w USA, podobno narysował tę spiralę w 1963 r., nudząc się na długim wykładzie. Smugi biorą się z wielomianów kwadratowych, które często dają liczby pierwsze — ale nikt nie umie dokładnie przewidzieć, gdzie wypadnie kolejna.
Jak gęsto rosną?
Hipoteza Goldbacha
Każda liczba parzysta większa od 2 jest sumą dwóch liczb pierwszych. Nikt tego nie udowodnił — ale komputery sprawdziły wszystkie liczby parzyste do 4 · 1018 (T. Oliveira e Silva, S. Herzog, S. Pardi, 2014; stan na 2026 r.).
Kometa Goldbacha
Licznik liczb pierwszych w tle
Sito odcinkowe w osobnym wątku (Web Worker) liczy wszystkie liczby pierwsze aż do miliarda i porównuje wynik z twierdzeniem o liczbach pierwszych.
| x | π(x) | x / ln x | Li(x) | π(x) · ln x / x |
|---|
Liczenie zatrzymuje się, gdy przełączysz tryb lub kartę przeglądarki.
Rekordzistka
Największa znana liczba pierwsza (stan na 2026 r.) to 2136 279 841 − 1 — liczba Mersenne’a o 41 024 320 cyfrach. Znalazł ją w październiku 2024 r. Luke Durant w projekcie GIMPS (Great Internet Mersenne Prime Search), używając kart graficznych w chmurze. Wydrukowana drobnym drukiem zajęłaby około 14 tysięcy stron.
Test Lucasa–Lehmera dla 2p − 1
Zagadki, nad którymi wciąż się głowimy
Goldbach (1742)
W liście do Eulera Christian Goldbach zauważył, że liczby parzyste dają się rozbić na dwie pierwsze. Im większa liczba, tym więcej rozkładów (spójrz na kometę) — a dowodu wciąż brak.
Liczby bliźniacze
Pary różniące się o 2 (11 i 13, 41 i 43…). Czy jest ich nieskończenie wiele? Nie wiadomo. W 2013 r. Yitang Zhang udowodnił, że nieskończenie wiele par różni się o mniej niż 70 milionów; zespół Polymath zszedł z tą granicą do 246.
Hipoteza Riemanna (1859)
Mówi, jak bardzo π(x) może odbiegać od Li(x). Jeden z problemów milenijnych Instytutu Claya — za dowód czeka milion dolarów.
Laboratorium · arytmetyka modularna
Działanie
Tabliczka mnożenia mod 12
Zegar w kalendarzu
Dni tygodnia liczymy modulo 7: co 7 dni wraca ten sam dzień.
Zegar 24-godzinny
Cyfry kontrolne — modulo pilnuje literówek
FIKCYJNE Przykłady są wygenerowane losowo i nie należą do nikogo. Nie wpisuj tu prawdziwych danych — strona niczego nie zapisuje ani nie wysyła, ale to dobry nawyk.
Algorytm Euklidesa — NWD
Koła zębate — NWW
Laboratorium · szyfr Cezara, podstawieniowy i Vigenère’a
Alfabet
Atak analizą częstości
szyfrogram przechwycony z gońcaPrzesuwaj, aż wysokie słupki (A, I, O, E, Z, N) trafią na swoje miejsca. W polszczyźnie najczęstsze litery to A, I, O, E, Z, N.
Szyfr podstawieniowy — każda litera ma swoją zastępczynię
Kluczy jest 32! ≈ 2,6 · 1035, więc sprawdzanie wszystkich nie wchodzi w grę. Ale częstości liter zdradzają szyfr i tak. Wpisz pod literą szyfrogramu twoje przypuszczenie, jaka litera jawna się pod nią kryje (litery uporządkowane od najczęstszej).
Szyfr Vigenère’a
Każda litera klucza to inne przesunięcie Cezara. Przez około 300 lat uchodził za „le chiffre indéchiffrable” — szyfr nie do złamania. (Alfabet łaciński; polskie litery zamieniamy na łacińskie, np. ą → a.)
Jak Kasiski złamał Vigenère’a
W 1863 r. Friedrich Kasiski zauważył, że te same fragmenty tekstu zaszyfrowane tym samym kawałkiem klucza dają te same fragmenty szyfrogramu. Odległości między powtórkami są wielokrotnościami długości klucza — wystarczy policzyć ich NWD. Potem każda kolumna to już zwykły Cezar.
Enigma i trzech Polaków
W grudniu 1932 r. Marian Rejewski odtworzył okablowanie wirników niemieckiej Enigmy, używając teorii permutacji. Razem z Jerzym Różyckim i Henrykiem Zygalskim budowali potem „bomby” i płachty perforowane. W lipcu 1939 r. pod Warszawą przekazali swoją wiedzę Brytyjczykom i Francuzom.
Zaszyfruj coś Enigmą w „Komputerze” →Laboratorium · szyfr z kluczem publicznym
1 · Dwie tajne liczby pierwsze
2 · Wiadomość (A = 1 … Ż = 32, spacja = 33)
Rozszerzony algorytm Euklidesa: skąd d?
Szukamy d, dla którego e · d ≡ 1 (mod φ(n)). Dzielimy z resztą jak w algorytmie Euklidesa i równolegle śledzimy współczynnik t.
| reszta r | iloraz q | współczynnik t |
|---|
Szyfrogram litera po literze
| litera | m | c = me mod n | cd mod n |
|---|
Uproszczenie: szyfrujemy każdą literę osobno, by było widać rachunki. Taki szyfr dałoby się złamać analizą częstości (ta sama litera → ta sama liczba). Prawdziwe RSA szyfruje duże bloki z losowym dopełnieniem (OAEP), a n ma 2048 bitów lub więcej.
Wyścig: rozłóż n, a poznasz d
Ktoś, kto zna p i q, od razu policzy d. Bezpieczeństwo RSA opiera się na tym, że rozkład wielkiego n na czynniki trwa absurdalnie długo.
Podpis cyfrowy
Odwracamy role kluczy: Bob podpisuje skrót wiadomości kluczem prywatnym (s = hd mod n), a każdy może sprawdzić podpis kluczem publicznym (se mod n = h?).
Skrót h to tu zabawkowa suma kontrolna modulo n; prawdziwe podpisy używają SHA-256 (tryb „Szyfry dziś”).
Diffie–Hellman: wspólny sekret przez podsłuchiwany kanał
Whitfield Diffie i Martin Hellman, 1976Farby łatwo zmieszać, ale bardzo trudno rozdzielić z powrotem — tak jak łatwo policzyć ga mod p, a trudno odzyskać z wyniku a (problem logarytmu dyskretnego).
Alicja
tajne a = —wysyła A = ?
sekret: ?
Ewa podsłuchuje
widzi p, g, A, B—
Bob
tajne b = —wysyła B = ?
sekret: ?
Laboratorium · kłódka w przeglądarce
Co się dzieje, gdy widzisz kłódkę (TLS 1.3, w uproszczeniu)
- Cześć! Przeglądarka wysyła listę obsługiwanych szyfrów i swoją połówkę wymiany kluczy (jak A u Diffiego–Hellmana).
- Odpowiedź serwera. Serwer odsyła swoją połówkę (B) i certyfikat — dowód tożsamości podpisany przez urząd certyfikacji.
- Sprawdzenie podpisu. Przeglądarka weryfikuje podpis cyfrowy certyfikatu i podpis serwera pod całą rozmową.
- Wspólny klucz. Obie strony liczą ten sam sekret — nikt go nie przesłał. Z niego powstaje klucz szyfru symetrycznego (np. AES).
- Szyfrowana rozmowa. Strona, hasła i formularze płyną już zaszyfrowane; podsłuchujący widzi tylko szum.
Funkcja skrótu — odcisk palca tekstu
SHA-256 zamienia dowolny tekst w 256 bitów (64 znaki szesnastkowe). Z odcisku nie da się odtworzyć tekstu, a zmiana jednej litery zmienia mniej więcej połowę bitów — to efekt lawiny. Liczymy lokalnie w przeglądarce (crypto.subtle); nic nie jest wysyłane.
Hasła: skrót, sól i siła
Porządny serwis nie przechowuje hasła, tylko jego skrót z solą (losowym dodatkiem), liczony celowo wolną funkcją (bcrypt, scrypt, Argon2).
Hasło nie opuszcza tej strony: nie jest zapisywane ani wysyłane. Ocena działa offline.
| atakujący | prób na sekundę | czas (średnio) |
|---|
Dlaczego sól?
Komputer kwantowy i kryptografia postkwantowa
W 1994 r. Peter Shor pokazał algorytm, którym duży komputer kwantowy rozkładałby liczby na czynniki szybko — to złamałoby RSA i Diffiego–Hellmana. Dzisiejsze komputery kwantowe są na to o wiele za małe i za bardzo zaszumione, ale szyfrogramy można nagrać dziś i odszyfrować za lata.
Dlatego w sierpniu 2024 r. amerykański NIST opublikował pierwsze standardy kryptografii postkwantowej: FIPS 203 (ML-KEM, wymiana kluczy oparta na kratach), FIPS 204 (ML-DSA, podpisy na kratach) i FIPS 205 (SLH-DSA, podpisy oparte na funkcjach skrótu). W marcu 2025 r. do standaryzacji wybrano też zapasowy algorytm HQC. Przeglądarki już łączą klasyczną wymianę kluczy z ML-KEM (stan na 2026 r.).
Świat kwantów →Szyfr symetryczny kontra asymetryczny
Symetryczny (AES)
Ten sam klucz zamyka i otwiera. Bardzo szybki — nim płyną właściwe dane.
Asymetryczny (RSA, krzywe eliptyczne)
Para kluczy: publiczny zamyka lub weryfikuje, prywatny otwiera lub podpisuje. Wolniejszy — służy do ustalenia klucza i podpisów.
Kłódka w przeglądarce to oba naraz: asymetryczny „uścisk dłoni”, a potem szybki szyfr symetryczny.
Oś czasu: od Euklidesa do kłódki w przeglądarce
- ok. 300 p.n.e.Euklides dowodzi, że liczb pierwszych jest nieskończenie wiele, i opisuje algorytm NWD.
- ok. 240 p.n.e.Eratostenes — sito do wyszukiwania liczb pierwszych (zmierzył też obwód Ziemi).
- I w. p.n.e.Juliusz Cezar szyfruje listy, przesuwając litery o 3.
- IX w.Al-Kindi opisuje analizę częstości liter — pierwszy znany atak na szyfry podstawieniowe.
- 1553 / 1586Bellaso i Vigenère — szyfr wieloalfabetowy z kluczem.
- 1640Fermat: ap−1 ≡ 1 (mod p). Euler (1736) dowodzi i uogólnia.
- 1801Gauss, „Disquisitiones arithmeticae” — kongruencje i arytmetyka zegarowa.
- 1863Kasiski publikuje metodę łamania szyfru Vigenère’a.
- 1932Rejewski, Różycki, Zygalski łamią Enigmę.
- 1963Stanisław Ulam rysuje spiralę liczb pierwszych.
- 1973 / 1976Clifford Cocks (brytyjski GCHQ, utajnione do 1997) i niezależnie Diffie i Hellman — kryptografia z kluczem publicznym.
- 1977Rivest, Shamir, Adleman — RSA.
- 1994Peter Shor — kwantowy algorytm rozkładu na czynniki.
- 2001NIST publikuje rodzinę skrótów SHA-2 (w tym SHA-256).
- 2024Standardy kryptografii postkwantowej NIST; rekordowa liczba pierwsza 2136 279 841 − 1.
MatematykaAtomy arytmetyki
Liczby pierwsze i złożone
Liczba pierwsza to liczba naturalna większa od 1, która ma dokładnie dwa dzielniki: 1 i samą siebie (2, 3, 5, 7, 11, 13…). Pozostałe liczby większe od 1 to liczby złożone. Podstawowe twierdzenie arytmetyki mówi, że każdą liczbę większą od 1 można zapisać jako iloczyn liczb pierwszych na dokładnie jeden sposób (z dokładnością do kolejności) — jak cząsteczkę złożoną z atomów.
Sito Eratostenesa i pierwiastek
Wypisujemy liczby 2…N, bierzemy najmniejszą nieskreśloną p (jest pierwsza) i skreślamy jej wielokrotności, zaczynając od p² — mniejsze wielokrotności mają mniejszy dzielnik i już wypadły. Gdy p² > N, możemy przestać: liczba złożona n ≤ N zawsze ma dzielnik pierwszy ≤ √n.
Ile jest liczb pierwszych?
Nieskończenie wiele — tak dowiódł Euklides. Twierdzenie o liczbach pierwszych (Hadamard i de la Vallée Poussin, 1896) mówi, że wśród liczb w okolicy x co mniej więcej ln x-ta jest pierwsza. Całka logarytmiczna Li(x) przybliża π(x) jeszcze lepiej.
Arytmetyka zegarowa, NWD i NWW
Liczby, które dają tę samą resztę z dzielenia przez m, są przystające (to kongruencja). Na tarczy o m polach każda niezerowa liczba ma odwrotność wtedy i tylko wtedy, gdy m jest pierwsza. Małe twierdzenie Fermata: jeśli p jest pierwsza i p nie dzieli a, to ap−1 ≡ 1 (mod p). Algorytm Euklidesa zastępuje większą liczbę resztą z dzielenia, aż reszta wyniesie 0 — ostatnia niezerowa reszta to NWD.
RSA w pięciu linijkach
Klucz publiczny (n, e) to otwarta kłódka, którą każdy może zatrzasnąć. Klucz prywatny d ją otwiera. Policzenie d wymaga φ(n), a to wymaga znajomości p i q. Działa to dzięki twierdzeniu Eulera: med ≡ m (mod n). Podpis cyfrowy odwraca role kluczy, a funkcja skrótu (hash) daje krótki odcisk palca, który się podpisuje.
Uproszczenia na tej stronie
RSA liczymy na małych liczbach i literę po literze, bez losowego dopełnienia — to model do nauki, nie bezpieczny szyfr. Mieszanie farb w Diffiem–Hellmanie to tylko metafora. Schemat HTTPS pomija wiele kroków protokołu TLS. Ocena hasła to górne oszacowanie entropii: hasła wymyślane przez ludzi są zwykle znacznie słabsze. Częstości liter polskich są przybliżone (zależą od rodzaju tekstu). Wykres czasu łamania RSA to ekstrapolacja rzędu wielkości.
Czy wiesz, że…?
- Liczb pierwszych jest nieskończenie wiele. Dowód Euklidesa mieści się w jednym zdaniu: pomnóż wszystkie znane liczby pierwsze i dodaj 1 — wynik nie dzieli się przez żadną z nich, więc ma dzielnik pierwszy spoza listy.
- Spiralę Ulama wymyślono podobno z nudów: w 1963 r. Stanisław Ulam bazgrał liczby w kratkę podczas długiego wykładu i zakreślił pierwsze. Ukośne smugi zaskoczyły jego samego.
- Polscy matematycy złamali Enigmę już w 1932 r. — Marian Rejewski odtworzył jej wirniki, rozwiązując równania permutacji, zanim Enigma stała się sławna w czasie wojny.
Wyzwania
- Sito własnoręcznieWykreśl sitem wszystkie liczby złożone do 100, klikając samodzielnie kolejne liczby pierwsze.nie zaliczone
- Rozkład na atomyRozłóż na czynniki pierwsze 1001 albo dowolną liczbę złożoną o co najmniej 6 cyfrach.nie zaliczone
- Goldbach powyżej tysiącaZnajdź sam liczbę pierwszą p, dla której liczba parzysta większa od 1000 to p + (inna liczba pierwsza).nie zaliczone
- Złam CezaraW ataku analizą częstości dopasuj słupki i odczytaj zagadkę.nie zaliczone
- List przez RSAZaszyfruj wiadomość kluczem publicznym i odszyfruj ją kluczem prywatnym.nie zaliczone
- Wspólny sekretUstal z Bobem wspólny sekret metodą Diffiego–Hellmana, wybierając własne liczby tajne.nie zaliczone
Wyzwania sprawdzają się same. Postęp zapisuje się w tej przeglądarce.
Zobacz też
Logarytm z „Funkcji” opisuje gęstość liczb pierwszych (n / ln n), a koła zębate zegarka to NWW w praktyce.