Algorytm faktoryzacji rho Pollarda

Algorytm faktoryzacji Rho Pollarda – 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(n^{1/4}\mathrm{polylog}(n))$.

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

Idea

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 $\mathrm{NWD}(|x-y|,n)>1$, gdyż zarówno $n,$ jak i $|x-y|$ 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. Jakaś pseudolosowa funkcja modulo $n$ jest wybierana 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 $\mathrm{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 $O(p^{1/2}).$ Diagram takiej sekwencji jest przedstawiony na rysunku – przypomina grecką małą literę $\rho$ (pol. ro), stąd nazwa algorytmu.

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
Dopóki d = 1:
    x ← f(x)
    y ← f(f(y))
    d ← NWD(|x − y|, 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(\mathrm{mod}n),c\ne 0,-2.$

Bibliografia

• Szablon:Cytuj pismo
• Szablon:Cytuj książkę