Pollardův rho algoritmus

Ro-algoritmus ( -algorithm ) je algoritmus navržený Johnem Pollardem v roce 1975 pro faktorování (faktorování) celých čísel. Tento algoritmus je založen na Floydově algoritmu pro nalezení délky cyklu v sekvenci a některých důsledcích narozeninového paradoxu . Algoritmus je nejúčinnější při faktorizaci složených čísel s dostatečně malými faktory v expanzi. Složitost algoritmu je odhadnuta jako [1] . $\rho$ $O(N^{1/4})$

Pollardův ρ-algoritmus buduje číselnou posloupnost , jejíž prvky tvoří cyklus začínající od nějakého čísla n , což lze ilustrovat uspořádáním čísel ve tvaru řeckého písmene ρ , což byl název rodiny algoritmů [2 ] [3] .

Historie algoritmu

Na konci 60. let 20. století přišel Robert Floyd s poměrně účinnou metodou pro řešení problému hledání cyklu , známou také jako algoritmus „želva a zajíc“ [4] . John Pollard , Donald Knuth a další matematici analyzovali chování průměrného případu tohoto algoritmu. Bylo navrženo několik úprav a vylepšení algoritmu [5] .

V roce 1975 Pollard publikoval článek [6] , ve kterém na základě Floydova algoritmu detekce cyklu nastínil myšlenku algoritmu faktorizace čísel, který běží v čase úměrně [6] [1] . Autor algoritmu nazval metodu faktorizace Monte Carlo, odrážející zdánlivou náhodnost čísel generovaných během výpočtu. Později však metoda stále dostala svůj moderní název - Pollardův ρ-algoritmus [7] . $N^{1/4}$

V roce 1981 Richard Brent a John Pollard použili algoritmus k nalezení nejmenších dělitelů Fermatových čísel na [8] . Rychlost algoritmu silně závisí pouze na hodnotě nejmenšího dělitele původního čísla, nikoli však na čísle samotném. Nalezení nejmenšího dělitele sedmého Fermatova čísla - , tedy zabere mnohem více času než nalezení dělitele dvanáctého Fermatova čísla (protože jeho dělitel 114689 je mnohem menší, ačkoli samotné číslo se skládá z více než 1200 desetinných číslic). $F_{n}=2^{2^{n}}+1$ $5\leq n\leq 13$ ${\begin{array}{lll}F_{7}=340282366920938463463374607431768211457=59\,649\,589\,127\,497\,217\0\0,86,5\ \,129\,054\,721;\end{array}}$

V rámci projektu Cunningham pomohl Pollardův algoritmus najít dělitele o délce 19 číslic . Bylo možné také nalézt velké dělitele, ale objev metody faktorizace eliptické křivky učinil Pollardův algoritmus nekonkurenční [9] . $2^{2386}+1$

Popis algoritmu

Původní verze

Uvažujeme posloupnost celých čísel , taková, že a , kde je číslo, které má být faktorizováno . Původní algoritmus vypadá takto [10] [6] : ${x_{n}}$ $x_{0}=2$ $x_{i+1}=(x_{i}^{2}-1\,)(\mathrm {mod} \,N)$ $N$

1. Počítají se trojice čísel

(x_{i},x_{2i},Q_{i}),i=1,2,...

, kde .

Q_{i}\equiv \prod _{j=1}^{i}(x_{2j}-x_{j})\,(\mathrm {mod} \,N)

Navíc je každá taková trojice získána z předchozí. 2. Pokaždé, když je číslo násobkem čísla (řekněme, ), vypočítejte největšího společného dělitele jakoukoli známou metodou.

i

m

m=100

d_{i}=\mathrm {GCD} (Q_{i},N)

3. Jestliže , pak je nalezen částečný rozklad čísla a .

1<d_{i}<N

N

N=d_{i}\krát (N/d_{i})

Nalezený dělitel může být složený, takže musí být také faktorizován. Pokud je číslo složené, pak pokračujeme v algoritmu s modulo .

d_{i}

N/d_{i}

N'=N/d_{i}

4. Výpočty se jednou opakují . Pokud současně nebylo číslo úplně rozloženo, například se zvolí jiné počáteční číslo .

S

x_{{0}}

Moderní verze

Nechť je složené kladné celé číslo, které chcete faktorizovat. Algoritmus vypadá takto [11] : $N$

Náhodně se vybere malé číslo [12] a vytvoří se sekvence , která definuje každou další jako . $x_{{0}}$ $\{x_{n}\},n=0,1,2,...$ $x_{n+1}=F(x_{n})\,(\mathrm {mod} \,\,N)$
Současně se v každém i -tém kroku počítá pro nějaké , jako například . $d=\mathrm {GCD} (N,|x_{i}-x_{j}|)$ $i$ $j$ $j<i$ $i=2j$
Jestliže , pak výpočet skončí a číslo nalezené v předchozím kroku je dělitelem . Pokud to není prvočíslo, pak postup hledání dělitele pokračuje a vezme se jako číslo . $d>1$ $d$ $N$ $N/d$ $N$ $N'=N/d$

V praxi se volí funkce nepříliš náročná na výpočet (ale zároveň ne lineární polynom), pokud by neměla generovat zobrazení jedna ku jedné. Obvykle jsou funkce [12] nebo [13] vybrány jako . Funkce a však nesedí [10] . $F(x)$ $F(x)$ $F(x)=x^{2}\pm 1(\mathrm {mod} \,N)$ $F(x)=x^{2}\pm a(\mathrm {mod} \,N)$ $x^{2}-2$ $x^{2}$

Pokud je známo, že dělitel čísla platí pro nějaké , pak má smysl použít [10] . $p$ $N$ $p\equiv 1\,(\mathrm {mod} \,k)$ $k>2$ $F(x)=x^{k}+b$

Významnou nevýhodou algoritmu v této implementaci je nutnost ukládat velké množství předchozích hodnot . $x_{j}$

Vylepšení algoritmu

Původní verze algoritmu má řadu nevýhod. V současné době existuje několik přístupů ke zlepšení původního algoritmu.

Nechte _ Pak, jestliže , pak , tedy, pokud pár dává řešení, pak jakýkoli pár dá řešení . $F(x)=(x^{2}-1)\mathrm {mod} \,N$ $(x_{j}-x_{i})\equiv 0(\mathrm {mod} \,p)$ $(f(x_{j})-f(x_{i}))\equiv 0(\mathrm {mod} \,p)$ $(x_{i},x_{j})$ $(x_{i+k},x_{j+k})$

Není tedy potřeba kontrolovat všechny páry , ale můžeme se omezit na páry tvaru , kde a prochází množinou po sobě jdoucích hodnot 1, 2, 3, ..., a přebírá hodnoty od interval . Například , , a [11] . $(x_{i},x_{j})$ $(x_{i},x_{j})$ $j=2^{k}$ $k$ $i$ $[2^{k}+1;2^{k+1}]$ $k=3$ $j=2^{3}=8$ $i\in[9;16]$

Tuto myšlenku navrhl Richard Brent v roce 1980 [14] a snižuje počet provedených operací přibližně o 25 % [15] .

Další variaci Pollardova ρ-algoritmu vyvinul Floyd . Podle Floyda se hodnota aktualizuje v každém kroku podle vzorce , takže hodnoty , , budou získány v kroku a GCD v tomto kroku se vypočítá pro a [11] . $y$ $y=F^{2}(y)=F(F(y))$ $i$ $x_{i}=F^{i}(x_{0})$ $y_{i}=x_{2i}=F^{2i}(x_{0})$ $N$ $yx$

Příklad rozkladu čísla na rozklad

Tento příklad jasně demonstruje faktorizační ρ-algoritmus (verze algoritmu s Floydovým vylepšením ) pro číslo N = 8051:

Tabulka: rozklad čísla 8051

n = 8051, F ( x ) = ( x 2 + 1) mod n , x 0 = y 0 = 2
i	x i = F ( x i -1 )	y i = F ( F ( y i -1 ))	GCD(\| x i − y i \|, 8051)
jeden	5	26	jeden
2	26	7474	jeden
3	677	871	97

Pomocí jiných variant polynomu lze také získat dělitel 83: $F(x)$

Tabulka: rozklad čísla 8051

n = 8051, F ( x ) = ( x 2 + 3) mod n , x 0 = y 0 = 2
i	x i = F ( x i -1 )	y i = F ( F ( y i -1 ))	GCD(\| x i − y i \|, 8051)
jeden	7	52	jeden
2	52	1442	jeden
3	2707	778	jeden
čtyři	1442	3932	83

Tedy d 1 \u003d 97, d 2 \u003d 83 jsou netriviální dělitelé čísla 8051.

Po nalezení dělitele čísla se v ρ-algoritmu navrhuje pokračovat ve výpočtech a hledat dělitele čísla , pokud není prvočíslo. V tomto jednoduchém příkladu nebyl tento krok vyžadován [11] . $N/d$ $N/d$

Odůvodnění Pollardova ρ-algoritmu

Algoritmus je založen na známém narozeninovém paradoxu .

Narozeninový paradox, stručně:
Let . Pro náhodný vzorek prvků je každý menší než , kde , pravděpodobnost, že dva prvky jsou stejné . $\lambda>0$ $l+1$ $q$ $l={\sqrt {2\lambda q}}$ $p>1-e^{-\lambda }$

Je třeba poznamenat, že pravděpodobnost v narozeninovém paradoxu je dosažena při . $p=0,5$ $\lambda \cca 0,69$

Nechte sekvenci sestávat z rozdílů , kontrolovaných během algoritmu. Určí se nová posloupnost , kde , je nejmenší z dělitelů čísla . $\{u_{n}\}$ $x_{i}-x_{j}$ $\{z_{n}\}$ $z_{n}=u_{n}\,\mathrm {mod} \,q$ $q$ $N$

Všechny členy posloupnosti jsou menší než . Pokud ji budeme považovat za náhodnou posloupnost celých čísel menších než , pak podle narozeninového paradoxu pravděpodobnost, že mezi její členy padnou dvě stejná, překročí když , pak musí být alespoň . $\{z_{n}\}$ ${\sqrt {N}}$ $q$ $l+1$ $1/2$ $\lambda \cca 0,69$ $l$ ${\sqrt {2\lambda q}}\přibližně {\sqrt {1,4q}}\přibližně 1,18{\sqrt {q}}$

Pokud , tedy , tedy pro nějaké celé číslo . Jestliže , což s vysokou pravděpodobností platí, pak požadovaný dělitel čísla bude nalezen jako . Protože , pak s pravděpodobností převyšující , bude dělitel nalezen v iteracích [11] . $z_{i}=z_{j}$ $x_{i}-x_{j}\equiv 0\,\mathrm {mod} \,q$ $x_{i}-x_{j}=kq$ $k$ $x_{i}\neq x_{j}$ $q$ $N$ $\mathrm {GCD} (N,|x_{i}-x_{j}|)$ ${\sqrt {q}}\leq n^{1/4}$ $1/2$ $N$ $1,18\krát N^{1/4}$

Složitost algoritmu

Pro odhad složitosti algoritmu je posloupnost vytvořená v průběhu výpočtů považována za náhodnou (samozřejmě v tomto případě nelze hovořit o žádné přísnosti). K úplnému faktorizaci počtu bitů délky stačí najít všechny jeho dělitele nepřesahující , což vyžaduje maximálně řád aritmetických operací neboli bitových operací. $N$ $\beta$ ${\sqrt {N}}$ ${\sqrt {N}}$ $N^{1/4}\beta ^{2}=2^{\beta /4}\beta ^{2}$

Proto je složitost algoritmu odhadnuta jako [16] . Tento odhad však nebere v úvahu režii výpočtu největšího společného dělitele . Získaná složitost algoritmu, i když není přesná, je v dobré shodě s praxí. $O(N^{1/4})$

Platí následující tvrzení: nechť je složené číslo . Pak existuje konstanta taková, že pro žádné kladné číslo pravděpodobnost události, že Pollardův ρ-algoritmus nenajde netriviálního dělitele v čase , nepřekročí . Toto tvrzení vyplývá z paradoxu narozenin [17] . $N$ $C$ $\lambda$ $N$ $C{\sqrt {\lambda {\sqrt {N))))(\log N)^{2}$ $e^{-\lambda }$

Funkce implementace

Množství paměti používané algoritmem lze výrazně snížit.

int Rho-Pollard ( int N) { int x = náhodné (1, N-2); int y = 1; int i = 0; int stadium = 2; zatímco (N.O.D.(N, abs (x - y)) == 1) { if (i == stadium){ y=x; etapa = etapa*2; } x = (x*x + 1) (mod N); i = i + 1; } návrat N.O.D (N, abs (xy)); }

V této verzi výpočet vyžaduje uložení pouze tří proměnných , , a , což odlišuje algoritmus v takové implementaci od jiných metod faktorizace čísel [11] . $N$ $X$ $y$

Paralelizace algoritmu

Pollardův algoritmus umožňuje paralelizaci jak pomocí systémů se sdílenou pamětí , tak pomocí systémů s distribuovanou pamětí ( předávání zpráv ), ale z praktického hlediska je nejzajímavější druhý případ [18] .

Distribuovaný paměťový systém

Stávající metoda paralelizace spočívá v tom, že každý výpočetní uzel provádí stejný sekvenční algoritmus , avšak původní číslo a/nebo polynom jsou brány jinak. Pro zjednodušení paralelizace se navrhuje přijímat je z generátoru náhodných čísel. Taková paralelní implementace však neposkytuje lineární zrychlení [19] . $x_{{0}}$ $F(x)$

Předpokládejme, že existují identičtí interpreti. Pokud použijeme různé posloupnosti (tedy různé polynomy ), pak pravděpodobnost, že první čísla v těchto posloupnostech budou různá modulo , bude přibližně rovna . Maximální zrychlení lze tedy odhadnout jako [9] . $P$ $P$ $F(x)$ $k$ $p$ $\exp({-k^{2}P}/{2p})$ $P^{1/2}$

Richard Crandall navrhl, že zrychlení je dosažitelné , ale toto tvrzení ještě nebylo ověřeno [20] . $O(P/(log{P})^{2})$

Systém sdílené paměti

Předchozí způsob lze samozřejmě použít na systémech se sdílenou pamětí, mnohem rozumnější je však použít jediný generátor [21] . $F(x)$

Poznámky

↑ 1 2 Pollard, 1974 , s. 521–528.
↑ Christensen, 2009 , 3.3.3.0.
↑ Chatterjee, 2008 , 5.2.2.
↑ Floyd, 1967 , str. 636–644.
↑ Brent, 1980 , Vylepšený faktorizační algoritmus Monte Carlo, str. 176.
↑ 1 2 3 Pollard, 1975 , Metoda Monte Carlo pro faktorizaci, s. 176.
↑ Koshy, 2007 , Elementární teorie čísel s aplikacemi.
↑ Childs, 2009 , Konkrétní úvod do vyšší algebry.
↑ 1 2 Brent, 1999 , Některé paralelní algoritmy pro faktorizaci celých čísel.
↑ 1 2 3 Pollard, 1975 , Monte Carlo metoda pro faktorizaci.
↑ 1 2 3 4 5 6 Ishmukhametov, 2011 , str. 64.
↑ 1 2 Mollin, 2006 , str. 215-216.
↑ Zolotykh N. Yu.Přednášky o počítačové algebře. Přednáška 11. Pollardova ρ-metoda. Archivováno 30. října 2014 na Wayback Machine
↑ Brent, 1980 , Vylepšený faktorizační algoritmus Monte Carlo, str. 176-184.
↑ Reisel, 2012 , Vybrané oblasti kryptografie. Prvočísla a počítačové metody faktorizace. 2. vyd..
↑ Cormen, 2001 , Úvod do algoritmů. Část 31.9. Faktorizace celých čísel. Pollardova rho heuristika..
↑ Ishmukhametov, 2011 , str. 63.
↑ Kosyakov, 2014 , s. 12.
↑ Kuhn, 2001 , Random Walks Revisited: Extensions of Pollard's Rho Algorithm for Computing Multiple Discrete Logarithms, str. 212-229.
↑ Crandall, 1999 , Paralelizace Polldar-rho faktorizace.
↑ Kosyakov, 2014 , s. 19.

Literatura

Vasilenko O. N. Číselné teoretické algoritmy v kryptografii . - M. : MTSNMO , 2003. - 328 s. — ISBN 5-94057-103-4 . Archivováno 27. ledna 2007 na Wayback Machine
Ishmukhametov Sh. T. Faktorizační metody pro přirozená čísla: Učebnice / Zakharov V.M. - Kazan: Kazan University, 2011. - S. 61-64. — 190 str. — ISBN 978-3-659-17639-5 .
Kosjakov M.S. Úvod do distribuovaného počítání / NRU ITMO. - Petrohrad. , 2014. - 155 s.
Němec O.N., Nesterenko A.Yu. Metody teorie čísel v kryptografii . - M. , 2012. - 300 s.
Solovyov Yu. P., Sadovnichy V. A. , Shavgulidze E. T. , Belokurov V. V. Eliptické křivky a moderní algoritmy teorie čísel. - M . : Počítač In-t. issled., 2003. - 192 s. — ISBN ISBN 5-939722-27-X .
Brent RP = Některé paralelní algoritmy pro rozklad na celé číslo . - 1999. - S. 7 . - doi : 10.1017/S0305004100049252 .
Brent RP Vylepšený faktorizační algoritmus Monte Carlo // BIT Numerical Mathematics. - 1980. - 1. června ( 20. díl , 2. vydání ). - S. 176-184 . — ISSN 1572-9125 . - doi : 10.1007/BF01933190 .
Chatterjee S., Sarkar P. Úvod // Identity-Based Encryption. - Boston: Springer US, 2008. - ISBN 978-1-59693-238-8 .
Childs, Lindsay N. Congruences // Konkrétní úvod do vyšší algebry . - 3. vyd. - USA: Springer, 2009. - S. 471-473. - 603 s. — ISBN 978-0-387-74725-5 .
Chris Christensen. Recenze Moderní kryptoanalýzy: Techniky pro pokročilé prolamování kódu od Christophera Swensona // Cryptologia. - 2009. - 27. ledna ( díl 33 , číslo 1 ). — ISSN 0161-1194 . - doi : 10.1080/01611190802293397 .
Cormen TH, Leiserson CE, Rivest RL, Stein C. Algoritmy: konstrukce a analýza = Úvod do algoritmů. - 2. vyd. - USA: MIT Press, 2001. - S. 897-907. — 1180 s. — ISBN 9780262032933 .
Crandall RE = Paralelizace faktorizace Polldar -rho . - 1999. Archivováno 6. července 2010.
Koshy T. Congruences // Elementární teorie čísel s aplikacemi. - 2. vyd. - USA: Academic Press, 2007. - S. 238. - 771 s. — ISBN 9780123724878 .
Kuhn F., Struik R. Random Walks Revisited: Extensions of Pollard's Rho Algorithm for Computing Multiple Discrete Logaritms // Vybrané oblasti v kryptografii / Serge Vaudenay, Amr M.. - Springer Berlin Heidelberg, 2001. - S. 212-229 - ISBN 978-3-540-43066-7 , 978-3-540-45537-0 . - doi : 10.1007/3-540-45537-x_17 .
Mollin RA Úvod do kryptografie / Rosen KH. - 2. - London: Chapman and Hall, 2006. - 413 s. — ISBN 9781584886181 .
Pollard JM Metoda Monte Carlo pro faktorizaci // BIT Numerical Mathematics. - 1975. - Sv. 15, č. 3 . - S. 331-334.
Pollard JM Věty o faktorizaci a testování primálnosti // Mathematical Proceedings of the Cambridge Philosophical Society. - 1974. - T. 76 , čís. 03 . — S. 521–528 . — ISSN 1469-8064 . - doi : 10.1017/S0305004100049252 .
Pollard JM Faktorizační metody a testování primálnosti. (anglicky) = Věty o faktorizaci a testování primálnosti. // Mathematical Proceedings of the Cambridge Philosophical Society. - 1974. - T. 76 , č. 3 . - S. 521 . - doi : 10.1017/S0305004100049252 .
Reisel, H. Prvočísla a počítačové metody faktorizace. - 2. vyd. - USA: Springer, 2012. - S. 183. - 464 s. - ISBN 978-0-8176-8297-2 .
Robert W. Floyd. Nedeterministické algoritmy // J. ACM. - 1967. - T. 14 , čís. 4 . — S. 636–644 . — ISSN 0004-5411 . - doi : 10.1145/321420.321422 .

Číselné teoretické algoritmy
Testy jednoduchosti	Mlynář Miller - Rabin Luca - Lemaire pepina Agravala - Kayala - Sasko Slavík - Strassen
Hledání prvočísel	Iterace přes dělitele Eratosthenovo síto Atkinovo síto Síto Sundarama
Faktorizace	Iterace přes dělitele Fermatova metoda p −1 Pollardova metoda Pollardův ρ-algoritmus Lehmannova metoda Metoda eliptické křivky (Lenstrův algoritmus) Dixonův algoritmus Čtvercové síto
Diskrétní logaritmus	Gelfond-Shanksův algoritmus Polig-Hellmanův algoritmus Pollardova ρ-metoda Pollardův algoritmus klokana Adlemanův algoritmus COS algoritmus
Hledání GCD	Euklidův algoritmus Pokročilý algoritmus Binární algoritmus
Modulová aritmetika	Montgomeryho algoritmus Čínská věta o zbytku
Násobení a dělení čísel	Algoritmus Karatsuba Toom-Cookův algoritmus Schönhage-Strassenův algoritmus Fuhrerův algoritmus Algoritmus Harvey-van der Hoeven Burnickel-Zieglerův algoritmus
Výpočet druhé odmocniny	Tonelli-Shanksův algoritmus Algoritmus Berlekamp-Rabin