Rozkład na czynniki

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}\ldots 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.}$ 

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.

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}}\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 ${\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.

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.

• algorytm Dixona
• metoda p-1

• 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].