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 .
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 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.
Algorytm 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: 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 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ą
Jako funkcji używa się wielomianów modulo ze współczynnikami całkowitymi. Najczęściej mają one postać: .
Związek z chińskim twierdzeniem o resztach Jeżeli jest iloczynem , to iterując wielomian modulo , tak naprawdę iterujemy go równolegle modulo i modulo . Zgodnie z chińskim twierdzeniem o resztach (CRT), istnieje izomorfizm pomiędzy pierścieniem a produktem pierścieni .
Oznacza to, że każda wartość w algorytmie odpowiada parze . Ponieważ (najmniejszy dzielnik) jest mniejszy od , zgodnie z paradoksem dnia urodzin ciąg wartości modulo zapętli się znacznie szybciej niż ciąg wartości modulo .
W momencie, gdy nastąpi kolizja modulo (czyli ), ale nie nastąpi jeszcze kolizja modulo (), różnica staje się wielokrotnością , ale nie wielokrotnością . Wówczas obliczenie skutecznie „wyłuskuje” czynnik .
Bibliografia
Rho Pollarda