Algorytm faktoryzacji rho Pollarda - Google

Algorytm faktoryzacji rho Pollarda

Z Wikipedii

Skocz do: nawigacji, szukaj

Rho Pollarda to algorytm rozkładu liczb na czynniki pierwsze, opracowany przez Johna Pollarda w 1975 roku. Jest szczególnie efektywny przy rozkładaniu liczb mających niewielkie dzielniki. Dla liczb będących iloczynem dwóch liczb pierwszych tej samej długości, jego złożoność jest rzędu O(n1/4 polylog(n)).

Algorytm ten stał się sławny gdy użyto go do faktoryzacji ósmej liczby Fermata. Pełna faktoryzacja F8 zajęła 2 godziny pracy komputera UNIVAC 1110.

[edytuj] Idea

Algorytm wykorzystuje paradoks dnia urodzin, mówiący że aby znaleźć z prawdopodobieństwem większym niż 1/2 dwie liczby x i y przystające modulo p, wystarczy wylosować mniej więcej 1.177\sqrt{p} liczb. Jeśli p jest szukanym dzielnikiem n, to NWD\left( |x-y|,n \right) > 1, gdyż zarówno n jak i \left|x-y\right| dzielą się przez p. Wystarczy zatem losować kolejne liczby i sprawdzać czy któraś różnica ma nietrywialne wspólne dzielniki z n.

Zamiast zapamiętywać wszystkie wylosowane liczby i sprawdzać każdą parę, algorytm wykorzystuje metodę znajdowania cyklu funkcji. Wybierana jest jakaś pseudolosowa funkcja modulo n, jako generator dla dwóch sekwencji. Jedna sekwencja wykonuje dwie iteracje w czasie gdy druga wykonuje jedną. Niech x oznacza aktualną wartość w pierwszej sekwencji, a y w drugiej. W każdym kroku wyliczany jest NWD(|x-y|,n). Jeśli wynik jest w którymś momencie równy n, algorytm kończy się błędem (wtedy x = y, i dalsze działanie będzie już tylko powtarzaniem dotychczasowych obliczeń). Jeśli w którymkolwiek momencie wynik jest większy od 1 i mniejszy od n, jest on dzielnikiem n.

Jeśli patrzymy na sekwencję modulo szukany dzielnik p, jej wartości muszą w końcu utworzyć cykl, o długości rzędu O(p1/2). Diagram takiej sekwencji jest przedstawiony na rysunku – przypomina grecką literę ρ, stąd nazwa algorytmu.

[edytuj] Algorytm

Wejście: n, liczba którą próbujemy rozłożyć; f(x), pseudolosowa funkcja modulo n

Wyjście: nietrywialny czynnik n, albo błąd.

  1. x ← 2, y ← 2; d ← 1
  2. While d = 1:
    1. x ← f(x)
    2. y ← f(f(y))
    3. d ← NWD(|x − y|, n)
    4. If 1 < d < n, then return d.
    5. If d = n, return failure.

Warto zauważyć że algorytm zawsze kończy się błędem dla n będącego liczbą pierwszą, ale może też zwrócić błąd dla n złożonego. Dlatego po błędzie można spróbować ponownie, z inną funkcją f(x).

Aby algorytm był efektywny, zwykle używa się szybko wyliczalnych funkcji f, np. wielomianów ze współczynnikami całkowitymi. Najczęściej mają one postać:

f(x)=x^2+c\hbox{ mod }n,\,c\neq0,-2.

[edytuj] Literatura


Elvis żyje! I przechodzi kontrolę paszportową
Elvis żyje. Przynajmniej według najnowszego systemu kontroli paszportowej, co udowodnił holenderski haker. Spreparowany przez niego e-paszport na nazwisko Króla został zaakceptowany przez system amsterdamskiego lotniska. Dopiero później alarm podnieśli politycy.
Czy pokojowa Nagroda Nobla podzieli Zachód z Chinami?
Pokojowa Nagroda Nobla może wywołać spięcie na linii Zachód-Chiny. Tym razem bowiem - w 60. rocznicę uchwalenia Powszechnej Deklaracji Praw Człowieka - najpoważniejszymi kandydatami do nagrody są dwaj chińscy dysydenci: Gao Zhisheng i Hu Jia.
Zamach bombowy w domu opozycjonisty
Co najmniej 12 osób zginęło, a opozycyjny deputowany Rashid Akbar Khan Nawani jest ranny, po tym jak zamachowiec-samobójca zdetonował ładunek wybuchowy na dziedzińcu domu parlamentarzysty w środkowym Pakistanie - poinformowała policja.
Chcą jawnego procesu zabójców Politkowskiej
Centroprawicowa "Nowaja Gazieta" zażądała przeprowadzenia procesu zabójców jej dziennikarki Anny Politkowskiej w trybie jawnym. We wtorek mija druga rocznica śmierci dziennikarki, znanej ze swych krytycznych wobec polityki Kremla artykułów.
"Nobla uczciłem szampanem"
- Naturalnie czasami o tym myślałem, bo wiedziałem, że często byłem wymieniany jako kandydat. Ale nie oczekiwałem tego - powiedział Harald zur Hausen komentując poniedziałkową decyzję o przyznaniu mu Nagrody Nobla. Przyznał, że wiadomość o wyróżnieniu uczcił ze swoimi współpracownikami szklaneczką szampana.
Linki: Strona gwna