Algorytm faktoryzacji rho Pollarda

Z Wikipedii, wolnej encyklopedii
Skocz do: nawigacja, 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 \Omicron(n^{1/4}\, \operatorname{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.

Idea[edytuj | edytuj kod]

Rho-pollard.png

Algorytm wykorzystuje paradoks dnia urodzin, mówiący, że aby znaleźć z prawdopodobieństwem większym niż ½ 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 \operatorname{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  \operatorname{NWD}(|x-y|,n). Jeśli wynik jest w którymś momencie równy n, algorytm kończy się błędem, gdyż 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 \Omicron(p^{1/2}). Diagram takiej sekwencji jest przedstawiony na rysunku – przypomina grecką małą literę \rho (pol. ro), stąd nazwa algorytmu.

Algorytm[edytuj | edytuj kod]

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
Dopóki d = 1:
    xf(x)
    yf(f(y))
    d ← NWD(|xy|, n)
    Jeśli 1 < d < n, to zwróć d.
    Jeśli d = n, to zasygnalizuj porażkę.

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 \ (\operatorname{mod}n),\ c\neq0,-2.

Bibliografia[edytuj | edytuj kod]