Rozkład na czynniki

Z Wikipedii, wolnej encyklopedii
Skocz do: nawigacja, szukaj
Przekierowanie Na tę stronę wskazuje przekierowanie z „Rozkład na czynniki”. Zobacz też: czynniki pierwsze.

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

Faktoryzacja liczby całkowitej x, czyli to co zwykle mamy na myśli mówiąc o faktoryzacji, to znalezienie takich liczb całkowitych y1, y2, ..., yn, że ich iloczyn jest równy danej liczbie: x = y_1 y_2 \cdots y_n, przy czym żadne z yi nie może być równe 1 lub x (tzw. faktoryzacja trywialna).

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.

Złożoność obliczeniowa[edytuj | edytuj kod]

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 65537 i 65539, można szybko je pomnożyć uzyskując 4295229443. Jednak rozłożenie 4295229443 na czynniki jest trudne. Wszystkie znane algorytmy działają w czasie wykładniczym wobec długości rozkładanej liczby.

Algorytmy faktoryzacji[edytuj | edytuj kod]

Najprostszy algorytm 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 \ne y \;(\operatorname{mod} n), x \ne -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} \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 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 \ne y \;(\operatorname{mod} n), x \ne -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.

Zobacz też[edytuj | edytuj kod]

Linki zewnętrzne[edytuj | edytuj kod]