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 ${\displaystyle x}$ prowadzi do wskazania takich (pod)obiektów, których iloczyn jest równy ${\displaystyle x.}$ Obiekty wynikowe nazywa się czynnikami lub dzielnikami (faktorami) obiektu ${\displaystyle x.}$

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 ${\displaystyle x}$ polega na znalezieniu takich liczb całkowitych ${\displaystyle y_{1},y_{2},\dots ,y_{n},}$ że ich iloczyn jest równy danej liczbie: ${\displaystyle x=y_{1}y_{2}\cdots y_{n}.}$ Domyślnie żąda się nietrywialności rozkładu: żaden z czynników ${\displaystyle y_{i}}$ nie może być równy 1 lub ${\displaystyle x.}$

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 ${\displaystyle n}$ przez wszystkie liczby pierwsze od 2 do ${\displaystyle {\sqrt {n}}.}$ 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 (${\displaystyle n}$ 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 ${\displaystyle x}$ i ${\displaystyle y,}$ gdzie ${\displaystyle (x\neq y\;(\operatorname {mod} n),}$ ${\displaystyle x\neq -y\;(\operatorname {mod} n)),}$ że:

${\displaystyle x^{2}=y^{2}\;(\operatorname {mod} n)}$

${\displaystyle x^{2}-y^{2}=0\;(\operatorname {mod} n)}$

${\displaystyle (x-y)(x+y)=0\;(\operatorname {mod} n)}$

Czyli albo ${\displaystyle x=y\;(\operatorname {mod} n),}$ albo ${\displaystyle x=-y\;(\operatorname {mod} n),}$ albo ${\displaystyle n}$ ma wspólne dzielniki z ${\displaystyle x-y}$ oraz ${\displaystyle x+y,}$ a zatem sfaktoryzowaliśmy ${\displaystyle n.}$

Najprostszą metodą tego typu jest sprawdzanie dla losowych liczb ${\displaystyle z}$ czy ${\displaystyle z^{2}\;(\operatorname {mod} n)}$ 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 ${\displaystyle z^{2}}$ kolejnych losowanych ${\displaystyle z}$ 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ć ${\displaystyle z}$ i wykładniki:

${\displaystyle z^{2}=p_{0}^{\alpha _{0}}p_{1}^{\alpha _{1}}p_{2}^{\alpha _{2}}\cdots p_{k}^{\alpha _{k}},}$

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 ${\displaystyle z,}$ ż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:

${\displaystyle x^{2}=y^{2}\;(\operatorname {mod} n),}$

gdzie ${\displaystyle x}$ to iloczyn odpowiednich ${\displaystyle z,}$ a ${\displaystyle y}$ to iloczyn odpowiednich ${\displaystyle p_{i}}$ w potędze będącej połową sumy potęg dla ${\displaystyle z}$ znajdujących się po lewej stronie. Z prawdopodobieństwem 50% (dla ${\displaystyle n}$ będącego iloczynem 2 liczb) lub większym (dla ${\displaystyle n}$ mającego więcej czynników) liczby te są nietrywialną taką parą ${\displaystyle (x\neq y\;(\operatorname {mod} n),}$ ${\displaystyle x\neq -y\;(\operatorname {mod} n)).}$ Jeśli tak nie jest, można próbować znaleźć inny zestaw liczb ${\displaystyle z^{2},}$ 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 ${\displaystyle n}$ nad ciałem liczb zespolonych można rozłożyć na iloczyn ${\displaystyle n}$ 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
• ElevenSmooth. home.earthlink.net. [zarchiwizowane z tego adresu (2005-04-07)].
• Factorizations of Cyclotomic Numbers
• Carl Pomerance List of Papers