Pollardova rho metoda

Pollardova rho metoda II

Příklad 2: Volme a = 4, M = 11.

1. Utvoříme posloupnost několika mocnin

1, 4, 16, 64, 256, 1024,4096, 16 384, ...

2. Nejmenší nezáporné zbytky při dělení těchto mocnin modulem M = 11 jsou

1, 4, 5, 9, 3, 1, 4, ... .

Samozřejmým cílem studované metody je, aby pokud možno co nejvíce přirozených čísel menších než M bylo členy posloupnosti. Vidíme, že tento cíl se nám nepodařilo splnit a volba a = 4, M = 11 nebyla šťastná. Zvolme proto a = 2, M = 11.

1. Utvořme opět posloupnost několika mocnin

 1, 2, 4, 8, 16, 32, 64, 128, 256, 512, 1024, 2048, 4096, 8192, ...

2. Nejmenší nezáporné zbytky při dělení těchto mocnin modulem M = 11 jsou

1, 2, 4, 8, 5, 10, 9, 7, 3, 6, 1, 2, ... .

Je jasné, že vytvořená posloupnost musí být periodická, avšak nyní se v získané posloupnosti předtím, než došlo k opakování, objevila všechna přirozená čísla z intervalu 1,10 . (Po sobě jdoucí čísla 1, 2, 4, 8 na začátku této posloupnosti ale nepůsobí „náhodně“).

Volme nyní a = 7, M = 11. Poznamenejme, že některé kalkulátory umožňují přímý výpočet posloupnosti nejmenších nezáporných zbytků při dělení čísel , modulem M. Kupř. na kalkulátorech TI-89 nebo TI-92 lze zadat

a opakovaně tisknout klávesu ENTER, čímž se realizuje povel zadaný ve druhém řádku. (V prvním kroku se pod hodnotou x uloží (Store) číslo 1, v dalších krocích je vždy počítán zbytek (remainder) při dělení čísla 7x číslem 11).

Tím získáme hledanou posloupnost zbytků 1, 7, 5, 2, 3, 10, 4, 6, 9, 8, 1, ... (viz obr. 4). Kalkulátory TI-83 nemají funkci remain (m, n) počítající nejmenší nezáporný zbytek při dělení přirozeného čísla m, číslem , mají však kupř. funkci iPart(z), vracející celou část čísla z, a protože na kalkulátorech této třídy lze vytvářet a ukládat programy, není nijak obtížné funkci remain(m, n) naprogramovat (což je užitečným cvičením).

Pokud se týče získané posloupnosti 1, 7, 5, 2, 3, 10, 4, 6, 9, 8, 1, ..., zdá se, že jsme byli úspěšní - získali jsme posloupnost obsahující všechna přirozená čísla z intervalu 1,10 a vypadající „náhodně“. Přistupme proto k zápisu Lehmerovy metody v obecném případě.

- zvolíme číslo M (modul),

- zvolíme násobitel 

Posloupnost   vytváříme takto:

X1 je nejmenší nezáporný zbytek při dělení čísla A.X0 číslem M; platí tedy X1= A.X0 (mod M),

X2 je nejmenší nezáporný zbytek při dělení čísla A.X1 číslem M; platí tedy X2=A.X1 (mod M), ...,

Xn+1 je nejmenší nezáporný zbytek při dělení čísla A.Xn číslem M; platí tedy Xn+1 = A.Xn (mod M).

V příkladu 2 bylo vždy X0 = 1, M = 11 a násobitel A byl 4, resp. 2, 7.

Jak se uvádí v [2], v praxi se užívá M = 231  -  1, A = 75 a firma IBM užívala podle údajů uvedených v této knize M = 231 a A = 216 + 3. Je také samozřejmé, že vygenerované posloupnosti musejí projít řadou statistických testů na náhodnost.

Poznamenejme, že právě popsaná metoda generování pseudonáhodných posloupností přirozených čísel není jediná. Zvolíme-li kupř. jisté přirozené číslo X0 a modul M a položíme -li Xi+1 = Xi 2 + 1 (mod M), i = 0, 1, ..., ukazuje zkušenost, že se často získá posloupnost pseudonáhodných čísel z intervalu  , která je pro užití v Pollardově rho metodě výhodnější než posloupnost generovaná lineární funkcí. Jak se uvádí v [1]: „The choice of this iteration function is black magic, but linear polynomials do not work, and higher degree polynomials are more costly to evaluate, and one cannot prove more about them than about x 2 + 1.“

Nyní již můžeme přistoupit k formulaci Pollardovy rho metody. Nechť N je přirozené číslo, které chceme faktorizovat. Zvolme přirozené číslo x0 a vypočtěme jistý počet členů posloupnosti nezáporných celých čísel , definovaných následovně:

xi+1 = xi 2 + 1 (mod N).

Předpokládejme, že prvočíslo p je nejmenším prvočíselným dělitelem čísla N. Dále předpokládejme, že  je posloupností pseudonáhodných čísel modulo p. Dále, nechť pro jisté dva členy xn, xm, n > m této posloupnosti platí, že xn = xm (mod p). (Příklad 1 nám dává naději, že na výskyt takovýchto členů posloupnosti  nebudeme muset čekat dlouho). Platí tedy , tedy největší společný dělitel D(xn - xm, N) > 1. Pokud zároveň  a nalezli jsme netriviální vlastní dělitel čísla N. Navíc je výhodné, že tento dělitel lze nalézt Eukleidovým algoritmem, což je, jak víme z druhé části kapitoly 1., velice efektivní metoda.

Krajně neuspokojivé by ale bylo, kdybychom vskutku museli počítat D(xn - xm, N) pro všechny dvojice  Objem výpočtů by narostl tak, že by to zcela znehodnotilo praktické využití navrhované metody. Naštěstí lze velkou část těchto propočtů ušetřit. Postačí totiž testovat jen dvojice , jak posléze ukážeme. Nyní zapišme nástin algoritmu pro Pollardovu rho - metodu: