Rozkład na czynniki

Rozkład na czynniki lub faktoryzacja – proces w kategorii obiektów wyposażonej w produkt, tj. iloczyn (rozumiany być może w szerokim sensie), który dla danego obiektu matematycznego  prowadzi do wskazania takich (pod)obiektów, których iloczyn jest równy  Obiekty wynikowe nazywa się czynnikami lub dzielnikami (faktorami) obiektu 

Zwykle wymaga się, by rozkład nie zawierał czynników, które mogą być z niego usunięte bez (istotnego) wpływu na wynik, tj. produkt mniejszej liczby obiektów da obiekt o tożsamej strukturze (lub nawet dokładnie ten sam obiekt). W szczególności unika się trywialnych rozwiązań postaci: obiekt i obiekt jednostkowy. Ważną cechą rozkładu na czynniki jest też jego jednoznaczność, która ma miejsce wtedy, gdy istnieje wyłącznie jeden rozkład obiektu (niezależny od użytej metody), zwykle z dodatkowymi wyłączeniami, np. kolejności czynników w rozkładzie w przypadku przemienności mnożenia.

Przez wyrażenie „rozkład na czynniki” rozumie się zazwyczaj rozkład na czynniki liczby całkowitej lub naturalnej (w drugim przypadku rozkład jest jednoznaczny, zachodzi równość; w pierwszym – z wyłączeniem/dokładnością do znaku czynników; w obu: nie uwzględniając kolejności czynników).

Liczby całkowite 

Faktoryzacja liczby całkowitej  polega na znalezieniu takich liczb całkowitych  że ich iloczyn jest równy danej liczbie:  Domyślnie żąda się nietrywialności rozkładu: żaden z czynników  nie może być równy 1 lub

Złożoność obliczeniowa 
O ile mnożenie jest bardzo prostą czynnością, to nie są znane żadne szybkie (działające w czasie wielomianowym względem ilości cyfr rozkładanej liczby) metody faktoryzacji. Na złożoności obliczeniowej faktoryzacji opiera się system kryptografii asymetrycznej RSA.

Przykład: mając dwie liczby 65 537 i 65 539, można szybko je pomnożyć, uzyskując 4 295 229 443. Jednak rozłożenie 4 295 229 443 na czynniki jest trudne. Wszystkie znane algorytmy działają w czasie wykładniczym wobec długości rozkładanej liczby.

Algorytmy faktoryzacji 
Najprostsza metoda polega na próbie dzielenia faktoryzowanej liczby  przez wszystkie liczby pierwsze od 2 do  Algorytm ten dobrze nadaje się do tego, żeby zacząć faktoryzować liczbę – losowa liczba ma zarówno małe, jak i duże czynniki. Połowa liczb dzieli się przez 2, co trzecia przez 3, co piąta przez 5 itd. Jeśli więc faktoryzowana liczba jest losowa, można z bardzo dużym prawdopodobieństwem pozbyć się szybko niskich czynników, po czym skończyć faktoryzację innym algorytmem. W najgorszym przypadku ( jest iloczynem dwóch liczb pierwszych podobnej wielkości, jak w RSA) algorytm ten zajmie bardzo dużo czasu.

Niektóre algorytmy opierają się na znajdowaniu takiej pary liczb  i  gdzie   że:
 
 
 

Czyli albo  albo  albo  ma wspólne dzielniki z  oraz  a zatem sfaktoryzowaliśmy 

Najprostszą metodą tego typu jest sprawdzanie dla losowych liczb  czy  jest kwadratem (zwykłym, nie modulo). Można szybko znaleźć faktoryzację niektórych liczb, ale ogólnie metoda ta nie jest dużo lepsza od prób dzielenia.

O wiele lepszym sposobem jest wybranie zestawu małych liczb pierwszych i próby faktoryzacji kwadratów  kolejnych losowanych  liczb, używając tylko tych liczb pierwszych – jeśli faktoryzacja się nie powiedzie należy odrzucić wylosowaną liczbę, jeśli się powiedzie trzeba zachować  i wykładniki:
 

a właściwie ich parzystości. Jeśli wybierze się zbyt duży zestaw liczb pierwszych, zwiększy to niepotrzebnie ilość obliczeń, jeśli wybierze zbyt mały – odrzuci zbyt dużo liczb.

Po uzbieraniu wystarczająco wielu relacji tego typu wybiera się taki podzbiór  że wszystkie potęgi po prawej stronie są parzyste (dlatego nie zachowuje się dokładnych wykładników, a jedynie ich parzystości). Nie trzeba sprawdzać wszystkich możliwych zestawów – znalezienie właściwego jest relatywnie prostym problemem równoważnym odwracaniu macierzy.

Otrzymuje się wtedy:
 

gdzie  to iloczyn odpowiednich  a  to iloczyn odpowiednich  w potędze będącej połową sumy potęg dla  znajdujących się po lewej stronie. Z prawdopodobieństwem 50% (dla  będącego iloczynem 2 liczb) lub większym (dla  mającego więcej czynników) liczby te są nietrywialną taką parą   Jeśli tak nie jest, można próbować znaleźć inny zestaw liczb  których iloczyn ma parzyste wykładniki.

Większość zaawansowanych algorytmów rozkładu na czynniki pierwsze polega na znajdowaniu liczb o dobrych rozkładach w znacznie krótszym czasie.

Wielomiany 

Faktoryzacja wielomianu to znalezienie takich wielomianów, że ich iloczyn jest równy danemu. W tym wypadku rozwiązanie nietrywialne nie może zawierać wielomianu o tym samym stopniu, co wielomian faktoryzowany. Zgodnie z zasadniczym twierdzeniem algebry dowolny wielomian o stopniu  nad ciałem liczb zespolonych można rozłożyć na iloczyn  wielomianów 1. stopnia.

Zobacz też 
 algorytm Dixona
 algorytm Fermata
 algorytm ρ Pollarda
 algorytm Shora
 GNFS
 metoda p-1
 sito kwadratowe

Linki zewnętrzne 
 GGNFS
 Cunningham Project
 
 Factorizations of Cyclotomic Numbers
 Carl Pomerance List of Papers

Teoria liczb
Arytmetyka