Rozkład na czynniki: Różnice pomiędzy wersjami
| [wersja nieprzejrzana] | [wersja przejrzana] |
Usunięta treść Dodana treść
Nieprzydatne Znaczniki: Wycofane usuwanie dużej ilości tekstu (filtr nadużyć) VisualEditor |
Anulowanie wersji 65629526 autorstwa 109.197.185.39 (dyskusja) – wygłup Znacznik: Anulowanie edycji |
||
Linia 1:
{{spis treści}}
'''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 <math>x</math> prowadzi do wskazania takich (pod)obiektów, których iloczyn jest równy <math>x.</math> Obiekty wynikowe nazywa się ''czynnikami'' lub ''dzielnikami'' (faktorami) obiektu <math>x.</math>
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ę [[trywialność (matematyka)|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ść|przemienności]] [[Mnożenie|mnożenia]].
Przez wyrażenie „rozkład na czynniki” rozumie się zazwyczaj rozkład na czynniki [[liczby całkowite]]j lub [[liczby naturalne|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 ==
{{zobacz też|liczby całkowite}}
Faktoryzacja liczby całkowitej <math>x</math> polega na znalezieniu takich liczb całkowitych <math>y_1, y_2, \dots, y_n,</math> że ich iloczyn jest równy danej liczbie: <math>x = y_1 y_2 \cdots y_n.</math> Domyślnie żąda się nietrywialności rozkładu: żaden z czynników <math>y_i</math> nie może być równy 1 lub <math>x.</math>
=== 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ść obliczeniowa|złożoności obliczeniowej]] faktoryzacji opiera się [[Kryptografia klucza publicznego|system kryptografii asymetrycznej]] [[RSA (kryptografia)|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 <math>n</math> przez wszystkie [[Liczba pierwsza|liczby pierwsze]] od 2 do <math>\sqrt n.</math> 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 (<math>n</math> jest iloczynem dwóch liczb pierwszych podobnej wielkości, jak w [[RSA (kryptografia)|RSA]]) algorytm ten zajmie bardzo dużo czasu.
Niektóre algorytmy opierają się na znajdowaniu takiej pary liczb <math>x</math> i <math>y,</math> gdzie <math>(x \ne y \;(\operatorname{mod} n),</math> <math>x \ne -y \;(\operatorname{mod} n)),</math> że:
: <math>x^2 = y^2 \;(\operatorname{mod} n)</math>
: <math>x^2 - y^2 = 0 \;(\operatorname{mod} n)</math>
: <math>(x-y)(x+y) = 0 \;(\operatorname{mod} n)</math>
Czyli albo <math>x = y \;(\operatorname{mod} n),</math> albo <math>x = -y \;(\operatorname{mod} n),</math> albo <math>n</math> ma wspólne dzielniki z <math>x-y</math> oraz <math>x+y,</math> a zatem sfaktoryzowaliśmy <math>n.</math>
Najprostszą metodą tego typu jest sprawdzanie dla losowych liczb <math>z</math> czy <math>z^2 \;(\operatorname{mod} n)</math> 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 <math>z^2</math> kolejnych losowanych <math>z</math> 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ć <math>z</math> i wykładniki:
: <math>z^2 = p_0^{\alpha_0} p_1^{\alpha_1} p_2^{\alpha_2} \cdots p_k^{\alpha_k},</math>
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 <math>z,</math> ż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:
: <math>x^2 = y^2 \;(\operatorname{mod} n),</math>
gdzie <math>x</math> to iloczyn odpowiednich <math>z,</math> a <math>y</math> to iloczyn odpowiednich <math>p_i</math> w potędze będącej połową sumy potęg dla <math>z</math> znajdujących się po lewej stronie. Z prawdopodobieństwem 50% (dla <math>n</math> będącego iloczynem 2 liczb) lub większym (dla <math>n</math> mającego więcej czynników) liczby te są nietrywialną taką parą <math>(x \ne y \;(\operatorname{mod} n),</math> <math>x \ne -y \;(\operatorname{mod} n)).</math> Jeśli tak nie jest, można próbować znaleźć inny zestaw liczb <math>z^2,</math> których iloczyn ma parzyste wykładniki.
Większość zaawansowanych algorytmów rozkładu na [[Czynnik pierwszy|czynniki pierwsze]] polega na znajdowaniu liczb o dobrych rozkładach w znacznie krótszym czasie.
== Wielomiany ==
{{zobacz też|wielomian|wielomian nieprzywiedlny}}
Faktoryzacja [[wielomian]]u 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 [[Zasadnicze twierdzenie algebry|zasadniczym twierdzeniem algebry]] dowolny wielomian o stopniu <math>n</math> nad [[Ciało (matematyka)|ciałem]] [[Liczby zespolone|liczb zespolonych]] można rozłożyć na iloczyn <math>n</math> wielomianów 1. stopnia.
== Zobacz też ==
* [[algorytm Dixona]]
* [[algorytm Fermata]]
* [[Algorytm faktoryzacji rho Pollarda|algorytm ρ Pollarda]]
* [[Algorytm faktoryzacji Shora|algorytm Shora]]
* [[GNFS]]
* [[metoda p-1]]
* [[sito kwadratowe]]
== Linki zewnętrzne ==
* [http://www.math.ttu.edu/~cmonico/software/ggnfs/ GGNFS]
* [http://www.cerias.purdue.edu/homes/ssw/cun/ Cunningham Project]
* [https://web.archive.org/web/20050407040231/http://home.earthlink.net/~elevensmooth/ ElevenSmooth]
* [http://www.asahi-net.or.jp/~KC2H-MSM/cn/ Factorizations of Cyclotomic Numbers]
* [http://www.math.dartmouth.edu/~carlp/ Carl Pomerance List of Papers]
{{Kontrola autorytatywna}}
| |||