Algorytm faktoryzacji rho Pollarda

Algorytm faktoryzacji Rho Pollardaalgorytm 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 .

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.

IdeaEdytuj

Algorytm wykorzystuje paradoks dnia urodzin, mówiący, że aby znaleźć z prawdopodobieństwem większym niż ½ dwie liczby   i   przystające modulo   wystarczy wylosować mniej więcej   liczb. Jeśli   jest szukanym dzielnikiem   to  , gdyż zarówno   jak i   dzielą się przez   Wystarczy zatem losować kolejne liczby i sprawdzać, czy któraś różnica ma nietrywialne wspólne dzielniki z  

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

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

AlgorytmEdytuj

Wejście:   – liczba, którą próbujemy rozłożyć;   – pseudolosowa funkcja modulo  

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

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

 

BibliografiaEdytuj