Rozkład na czynniki

Z Wikipedii, wolnej encyklopedii
Skocz do: nawigacja, szukaj
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: , 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]

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]

Najprostszy algorytm polega na próbie dzielenia faktoryzowanej liczby przez wszystkie liczby pierwsze od 2 do . 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 ( 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 i , gdzie , , że:

Czyli albo , albo , albo ma wspólne dzielniki z oraz , a zatem sfaktoryzowaliśmy .

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

,

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 , ż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:

,

gdzie to iloczyn odpowiednich , a to iloczyn odpowiednich w potędze będącej połową sumy potęg dla znajdujących się po lewej stronie. Z prawdopodobieństwem 50% (dla będącego iloczynem 2 liczb) lub większym (dla mającego więcej czynników) liczby te są nietrywialną taką parą , . Jeśli tak nie jest, można próbować znaleźć inny zestaw liczb , 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]

Linki zewnętrzne[edytuj]