Rozkład na czynniki pierwsze

Rozkład na czynniki pierwsze: odcisk palca, który każda liczba ma dokładnie jeden

Każda liczba całkowita powyżej 1 jest iloczynem liczb pierwszych i — to właśnie czyni ją użyteczną — jest nim tylko na jeden sposób. Podstawowe twierdzenie arytmetyki gwarantuje jednoznaczność rozkładu, dlatego działa on jak odcisk palca i dlatego tak wiele rzeczy, od skracania ułamków po kryptografię klucza publicznego, jest na nim zbudowanych.

Jak to działa

• Rozbija liczbę na czynniki pierwsze, w postaci potęgowej i rozpisanej w całości.
• Zlicza dzielniki bez wypisywania ich, wprost z wykładników.
• Mówi, czy liczba jest pierwsza — to po prostu przypadek, gdy rozkłada się na samą siebie.

every integer above 1 factorises into primes in exactly one way

  360 = 2 x 2 x 2 x 3 x 3 x 5
      = 2^3 x 3^2 x 5

the number of divisors follows from the exponents
  d(n) = (3 + 1) x (2 + 1) x (1 + 1) = 24

Przykład z liczbami

Rozkład 360 przez wielokrotne wydzielanie najmniejszej pasującej liczby pierwszej.

1. 360 / 2 = 180
2. 180 / 2 = 90
3. 90 / 2 = 45 2 appears three times
4. 45 / 3 = 15
5. 15 / 3 = 5 3 appears twice
6. 5 / 5 = 1 5 appears once
7. result 2^3 x 3^2 x 5

360 = 2³ × 3² × 5 i żadna inna kombinacja liczb pierwszych nie da 360. Z samych wykładników wynika liczba dzielników: (3+1)(2+1)(1+1) = 24, bo każdy dzielnik wybiera od 0 do 3 dwójek, od 0 do 2 trójek i 0 albo 1 piątkę.

Jak czytać wynik

• Wzór na liczbę dzielników wart jest zapamiętania sam w sobie. Nigdy nie trzeba ich wypisywać, żeby je policzyć — dodaj jeden do każdego wykładnika i pomnóż, bo zbudowanie dzielnika to niezależny wybór, ile każdej liczby pierwszej wziąć.
• Dzielenie próbne wystarczy prowadzić do pierwiastka kwadratowego. Jeśli n ma czynnik większy niż √n, musi mieć też pasujący mniejszy, więc po przekroczeniu pierwiastka nie ma już czego szukać. Dlatego rozkład liczby sześciocyfrowej jest natychmiastowy.
• Narzędzie po 2 i 3 idzie krokiem co sześć, sprawdzając tylko 6k−1 i 6k+1. Wszystkie pozostałe reszty są już podzielne przez 2 albo 3, co za darmo pomija dwie trzecie kandydatów.
• To, że rozkład bardzo dużych liczb jest trudny, to cecha, a nie ograniczenie tego narzędzia. RSA opiera się na tym, że pomnożenie dwóch dużych liczb pierwszych jest łatwe, a ich odzyskanie nie — cała argumentacja o bezpieczeństwie to ta asymetria.

Częste pytania

Czy 1 jest liczbą pierwszą?

Nie, a wykluczenie jej to świadomy wybór, nie przeoczenie. Gdyby 1 liczyła się jako pierwsza, rozkłady przestałyby być jednoznaczne — 6 mogłoby być 2×3, albo 1×2×3, albo 1×1×2×3 — a twierdzenie, które czyni rozkład użytecznym, wymagałoby niezręcznego wyjątku w każdym sformułowaniu.

Dlaczego moja liczba rozkłada się tylko na samą siebie?

Bo jest pierwsza. Liczba pierwsza nie ma dzielników poza 1 i sobą, więc jej rozkład to pojedynczy człon z wykładnikiem jeden. Narzędzie mówi to wprost, zamiast zostawiać wnioskowanie z jednoelementowej listy.