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 $x$ prowadzi do wskazania takich (pod)obiektów, których iloczyn jest równy $x.$ Obiekty wynikowe nazywa się czynnikami lub dzielnikami (faktorami) obiektu $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 $x$ polega na znalezieniu takich liczb całkowitych $y_{1},y_{2},\dots ,y_{n},$ że ich iloczyn jest równy danej liczbie: $x=y_{1}y_{2}\ldots y_{n}.$ Domyślnie żąda się nietrywialności rozkładu: żaden z czynników $y_{i}$ nie może być równy 1 lub $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 $n$ przez wszystkie liczby pierwsze od 2 do ${\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 ($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 $x$ i $y,$ gdzie $(x\neq y\;(\operatorname {mod} n),$ $x\neq -y\;(\operatorname {mod} n)),$ że:

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

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

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

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

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

$z^{2}=p_{0}^{\alpha _{0}}p_{1}^{\alpha _{1}}p_{2}^{\alpha _{2}}\ldots 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 $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:

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

gdzie $x$ to iloczyn odpowiednich $z,$ a $y$ to iloczyn odpowiednich $p_{i}$ w potędze będącej połową sumy potęg dla $z$ znajdujących się po lewej stronie. Z prawdopodobieństwem 50% (dla $n$ będącego iloczynem 2 liczb) lub większym (dla $n$ mającego więcej czynników) liczby te są nietrywialną taką parą $(x\neq y\;(\operatorname {mod} n),$ $x\neq -y\;(\operatorname {mod} n)).$ Jeśli tak nie jest, można próbować znaleźć inny zestaw liczb $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 $n$ nad ciałem liczb zespolonych można rozłożyć na iloczyn $n$ wielomianów 1. stopnia.

Zobacz też

• algorytm Dixona
• metoda p-1

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
• Eric W.E.W. Weisstein Eric W.E.W., Factorization, [w:] MathWorld, Wolfram Research  (ang.). [dostęp 2024-02-02].
• Factorization (ang.), Encyclopedia of Mathematics, encyclopediaofmath.org [dostęp 2024-02-02].