Algorytm faktoryzacji rho Pollarda
Z Wikipedii
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 liczb. Jeśli p jest szukanym dzielnikiem n, to NWD, gdyż zarówno n jak i 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.
- x ← 2, y ← 2; d ← 1
- While d = 1:
- x ← f(x)
- y ← f(f(y))
- d ← NWD(|x − y|, n)
- If 1 < d < n, then return d.
- 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ć:
[edytuj] Literatura
- Richard Brent. An Improved Monte Carlo Factorization Algorithm, BIT 20, 1980, pp.176-184, http://web.comlab.ox.ac.uk/oucl/work/richard.brent/pd/rpb051i.pdf
- Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Clifford Stein. Wprowadzenie do Algorytmów