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 ${\displaystyle \mathrm {O} (n^{1/4}\,\operatorname {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 ${\displaystyle x}$ i ${\displaystyle y}$ przystające modulo ${\displaystyle p,}$ wystarczy wylosować mniej więcej ${\displaystyle 1{,}177{\sqrt {p}}}$ liczb. Jeśli ${\displaystyle p}$ jest szukanym dzielnikiem ${\displaystyle n,}$ to ${\displaystyle \operatorname {NWD} \left(|x-y|,n\right)>1}$, gdyż zarówno ${\displaystyle n,}$ jak i ${\displaystyle \left|x-y\right|}$ dzielą się przez ${\displaystyle p.}$ Wystarczy zatem losować kolejne liczby i sprawdzać, czy któraś różnica ma nietrywialne wspólne dzielniki z ${\displaystyle n.}$

Zamiast zapamiętywać wszystkie wylosowane liczby i sprawdzać każdą parę, algorytm wykorzystuje metodę znajdowania cyklu funkcji. Jakaś pseudolosowa funkcja modulo ${\displaystyle n}$ jest wybierana jako generator dla dwóch sekwencji. Jedna sekwencja wykonuje dwie iteracje, w czasie gdy druga wykonuje jedną. Niech ${\displaystyle x}$ oznacza aktualną wartość w pierwszej sekwencji, a ${\displaystyle y}$ w drugiej. W każdym kroku wyliczany jest ${\displaystyle \operatorname {NWD} (|x-y|,n).}$ Jeśli wynik jest w którymś momencie równy ${\displaystyle n,}$ algorytm kończy się błędem, gdyż wtedy ${\displaystyle 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 ${\displaystyle n,}$ jest on dzielnikiem ${\displaystyle n.}$

Jeśli patrzymy na sekwencję modulo szukany dzielnik ${\displaystyle p,}$ jej wartości muszą w końcu utworzyć cykl, o długości rzędu ${\displaystyle \mathrm {O} (p^{1/2}).}$ Diagram takiej sekwencji jest przedstawiony na rysunku – przypomina grecką małą literę ${\displaystyle \rho }$ (pol. ro), stąd nazwa algorytmu.

Algorytm

Wejście: ${\displaystyle n}$ – liczba, którą próbujemy rozłożyć; ${\displaystyle f(x)}$ – pseudolosowa funkcja modulo ${\displaystyle n.}$

Wyjście: nietrywialny czynnik ${\displaystyle 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 ${\displaystyle n}$ będącego liczbą pierwszą, ale może też zwrócić błąd dla ${\displaystyle n}$ złożonego. Dlatego po błędzie można spróbować ponownie, z inną funkcją ${\displaystyle f(x).}$

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

${\displaystyle f(x)=x^{2}+c\ (\operatorname {mod} n),\ c\neq 0,-2.}$

Bibliografia

• Richard P. Brent. An Improved Monte Carlo Factorization Algorithm. „BIT”. 20, s. 176–184, 1980. (ang.). 
• Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Clifford Stein: Wprowadzenie do Algorytmów.brak strony w książce