← Laboratorium Matematyka · eksperyment

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.

n = p1a1 · p2a2 ⋯ ap−1 ≡ 1 (mod p) c = me mod n π(x) ≈ xln x
Q–Y tryby Wyzwania 0/6

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.

Liczb pierwszych—
Skreślonych złożonych—
Teraz skreślam wielokrotności—
Granica √N—
Wskazana liczbanajedź na kratkę

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).

Liczba dzielników—
Suma dzielników—

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.

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.

360 = 2³ · 3² · 5, 1001 = 7 · 11 · 13, liczba dzielników n = paqb⋯ to (a+1)(b+1)⋯

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?

π(x) ≈ xln x, Li(x) = ∫2x dtln t

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

a ≡ b (mod m) ⇔ m | (a − b), NWD(a, b) = NWD(b, a mod b), NWW(a, b) = abNWD(a, b)

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

n = pq, φ(n) = (p − 1)(q − 1), e · d ≡ 1 (mod φ(n)), c = me mod n, m = cd mod n

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.