Rozkład na czynniki: Różnice pomiędzy wersjami

'''Rozkład na czynniki''' lub '''faktoryzacja''' – proces, w którym dla danego obiektu znajdujeznajdują się obiekty, takie że ich [[Mnożenie|iloczyn]] jest jemu równy, przez co są one w pewnym sensie od niego prostsze.

Faktoryzacja [[liczby całkowite|liczby całkowitej]]j x, czyli to co zwykle mamy na myśli mówiąc o ''faktoryzacji'', to znalezienie takich liczb całkowitych y₁, y₂, ..., y_n, że ich iloczyn jest równy danej liczbie: <math>x = y_{1}y_{2}\cdots y_{n}</math>, przy czym żadne z y_i nie może być równe 1 lub x (tzw. faktoryzacja trywialna).

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_algebryZasadnicze twierdzenie algebry|zasadniczym twierdzeniem algebry]] dowolny wielomian o stopniu ''n'' nad [[Ciało (matematyka)|ciałem]] [[Liczby zespolone|liczb zespolonych]] można rozłożyć na iloczyn ''n'' wielomianów 1. stopnia.

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 asymetryczna|system kryptografii asymetrycznej]] [[RSA (kryptografia)|RSA]].

Przykład: mając dwie liczby 65537 i 65539, można szybko je pomnożyć uzyskując 4295229443. Jednak aby rozłożyć 4295229443 na czynniki trzeba próbować podzielić je przez wszystkie liczby pierwsze po kolei, aż natrafi się na właściwe czynniki. Dla bardzo dużych liczb, możliwych czynników pierwszych będzie o wiele za dużo, żeby dało się je wszystkie sprawdzić. Istnieją efektywniejsze algorytmy (takie jak [[sito kwadratowe]] i [[GNFS]]), jednak wszystkie one działają w czasie wykładniczym wobec długości rozkładanej liczby.

Najprostszy algorytm polega na próbie dzielenia faktoryzowanej liczby <math>n</math> przez wszystkie liczby pierwsze od 2 do <math>\sqrt n</math>. Algorytm ten dobrze nadaje się do tego, żeby zacząć faktoryzować liczbę &ndash;– 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żemy 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.

: <math>x^2 = y^2 \mod n</math>

: <math>x^2 - y^2 = 0 \mod n</math>

: <math>(x-y)(x+y) = 0 \mod n</math>

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 &ndash;– jeśli faktoryzacja się nie powiedzie odrzucamy wylosowaną liczbę, jeśli się powiedzie zachowujemy <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>

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

: <math>x^2 = y^2 \mod n</math>

== Zobacz też ==

== Linki zewnętrzne ==