Tekst źródłowy strony Algorytm faktoryzacji rho Pollarda

'''Algorytm faktoryzacji Rho Pollarda''' – [[algorytm]] [[Rozkład na czynniki|rozkładu liczb na czynniki pierwsze]], opracowany przez [[John Pollard|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 [[Asymptotyczne tempo wzrostu|<math>\Omicron(n^{1/4}\, \operatorname{polylog}(n))</math>]].

Algorytm ten stał się sławny, gdy użyto go do faktoryzacji ósmej [[liczby Fermata]]. Pełna faktoryzacja ''F''<sub>8</sub> zajęła 2 godziny pracy komputera [[UNIVAC|UNIVAC 1110]].

== Idea ==
[[Plik:Rho-pollard.png|right]]
Algorytm wykorzystuje [[paradoks dnia urodzin]], mówiący, że aby znaleźć z prawdopodobieństwem większym niż ½ dwie liczby <math>x</math> i <math>y</math> przystające [[modulo]] <math>p,</math> wystarczy wylosować mniej więcej <math>1{,}177\sqrt{p}</math> liczb. Jeśli <math>p</math> jest szukanym dzielnikiem <math>n,</math> to [[Największy wspólny dzielnik|<math>\operatorname{NWD} \left( |x-y|,n \right) > 1</math>]], gdyż zarówno <math>n,</math> jak i <math>\left|x-y\right|</math> dzielą się przez <math>p.</math> Wystarczy zatem losować kolejne liczby i sprawdzać, czy któraś różnica ma nietrywialne wspólne dzielniki z <math>n.</math>

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

Jeśli patrzymy na sekwencję modulo szukany dzielnik <math>p,</math> jej wartości muszą w końcu utworzyć cykl, o długości rzędu <math>\Omicron(p^{1/2}).</math> Diagram takiej sekwencji jest przedstawiony na rysunku – przypomina [[Grecja|grecką]] małą literę [[Rho (litera)|<math>\rho</math>]] (pol. ''ro''), stąd nazwa algorytmu.

== Algorytm ==
'''Wejście''': <math>n</math> – liczba, którą próbujemy rozłożyć; <math>f(x)</math> – pseudolosowa funkcja modulo <math>n.</math>

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

Aby algorytm był efektywny, zwykle używa się szybko wyliczalnych funkcji <math>f,</math> np. wielomianów ze współczynnikami całkowitymi. Najczęściej mają one postać:
: <math>f(x)=x^2+c \ (\operatorname{mod}n),\ c\neq0,-2.</math>

== Bibliografia ==
* {{cytuj pismo |imię=Richard P. |nazwisko=Brent |autor link = Richard P. Brent |tytuł = An Improved Monte Carlo Factorization Algorithm |url =http://web.comlab.ox.ac.uk/oucl/work/richard.brent/pd/rpb051i.pdf|czasopismo = BIT |wolumin = 20 |rok = 1980 |strony = 176–184 |język = en}}
* {{cytuj książkę |autor = [[Thomas H. Cormen]] |autor2 = [[Charles E. Leiserson]] |autor3 = [[Ron Rivest|Ronald L. Rivest]] |autor4 = [[Clifford Stein]] |tytuł = Wprowadzenie do Algorytmów}}

{{Teoria liczb}}

[[Kategoria:Algorytmy faktoryzacji|Rho Pollarda]]