Faktoryzacja (częściej nazywana także faktoryzacją) to rozkład liczby na czynniki, czyli przedstawienie jej jako iloczynu mniejszych liczb. W praktyce interesuje nas przede wszystkim rozkład liczby złożonej na liczby, które mnożąc się razem dają liczbę wyjściową. Te mniejsze liczby nazywamy dzielnikami lub czynnikami. Warto pamiętać, że 1 jest dzielnikiem każdej liczby, ale nie jest liczbą pierwszą.

Faktoryzacja w najszerszym sensie oznacza rozbijanie liczby złożonej na czynniki pierwsze – czyli liczby, które mają dokładnie dwa dzielniki: 1 i samą siebie. Przykładowo, 12 można zapisać jako 4 × 3, ale ponieważ 4 nie jest liczbą pierwszą, podstawową (czyli pierwszorzędową) faktoryzacją 12 jest 2 × 2 × 3, zwyczajowo zapisywane w postaci z wykładnikami jako 2^2 × 3. Zwróć uwagę, że 1 nie występuje w zapisie faktoryzacji pierwszej, a rozkład liczby 1 traktuje się jako iloczyn pusty.

Podstawowe własności

  1. Fundamentalne twierdzenie arytmetyki: każda liczba całkowita większa niż 1 ma przedstawienie jako iloczyn liczb pierwszych i to przedstawienie jest jednoznaczne z dokładnością do kolejności czynników (np. 72 = 2^3 × 3^2).
  2. Odwrotność: każdemu wielomianowi (zbiorowi) czynników pierwszych z określonymi wykładnikami odpowiada dokładnie jedna liczba naturalna.

Przykłady i zapis

Przykłady zapisów faktoryzacji:

  • 12 = 2 × 2 × 3 = 2^2 × 3
  • 72 = 2 × 2 × 2 × 3 × 3 = 2^3 × 3^2

W zapisie zwykle uporządkowuje się czynniki rosnąco (lub nierosnąco) i składa wykładniki przy powtarzających się czynnikach, co ułatwia porównywanie rozkładów.

Metody faktoryzacji

W zależności od wielkości liczby stosuje się różne metody:

  • Dzielenie próbne (trial division): dzielimy przez kolejne liczby pierwsze (2, 3, 5, 7, ...) aż do pierwiastka kwadratowego z liczby. Proste i skuteczne dla małych liczb.
  • Udoskonalone dzielenie: testowanie tylko kandydatów w postaci 6k±1 lub użycie sito Eratostenesa do wygenerowania listy dzielników.
  • Algorytmy probabilistyczne: np. Pollard rho — szybki w praktyce dla wielu średniej wielkości liczb.
  • Algorytmy deterministyczne i hybrydowe: algorytm kwadratowy przesiewowy (Quadratic Sieve) oraz zaawansowany algorytm General Number Field Sieve (GNFS) — obecnie najszybszy znany algorytm do faktoryzacji bardzo dużych liczb całkowitych.
  • Elliptic Curve Method (ECM): skuteczny do znajdowania względnie małych czynników dużych liczb.

Prosty algorytm dzielenia próbnego (opis krok po kroku)

  1. Usuń czynnik 2: dziel ile się da przez 2, zapisując liczbę powtórzeń jako wykładnik.
  2. Sprawdzaj kolejne nieparzyste kandydujące dzielniki d = 3, 5, 7, ... aż do sqrt(n). Przy każdym znalezieniu dzielnika dziel dalej otrzymany iloraz.
  3. Jeżeli po wszystkich próbach pozostała liczba jest większa niż 1, to jest ona liczbą pierwszą i jest ostatnim czynnikiem.

Zastosowania

Faktoryzacja ma znaczenie praktyczne i teoretyczne: w teorii liczb jest podstawowym narzędziem analizy własności liczb całkowitych; w informatyce i bezpieczeństwie — fakt, że rozkład dużych liczb na czynniki pierwsze jest trudny obliczeniowo, wykorzystuje się w systemach kryptograficznych. Przykładowo, algorytmy typu RSA opierają się na trudności faktoryzacji dużych semiprymów — iloczynów dwóch dużych liczb pierwszych. Z tego powodu postęp w technikach faktoryzacji bezpośrednio wpływa na bezpieczeństwo kryptografii.

Dodatkowe uwagi

  • Faktoryzacja liczb ujemnych: zwykle rozważamy faktoryzację wartości bezwzględnej, dopisując ewentualnie czynnik −1.
  • Unikalność faktoryzacji oznacza, że kolejność czynników nie ma znaczenia — liczbę jednoznacznie określa wielomian czynników pierwszych z wykładnikami.
  • Dla praktycznych zastosowań do faktoryzacji dużych liczb używa się gotowych bibliotek i programów, które implementują powyższe algorytmy oraz optymalizacje.

Jeśli chcesz, mogę pokazać krok po kroku faktoryzację konkretnej liczby albo przygotować prosty skrypt (np. w Pythonie) realizujący dzielenie próbne lub Pollard rho.