Pollards rho-algoritm

Ro-algoritm ( -algorithm ) är en algoritm som föreslagits av John Pollard 1975 för att faktorisera ( faktorera) heltal. Denna algoritm är baserad på Floyds algoritm för att hitta cykellängden i en sekvens och några konsekvenser av födelsedagsparadoxen . Algoritmen är mest effektiv vid faktorisering av sammansatta tal med tillräckligt små faktorer i expansionen. Algoritmens komplexitet uppskattas till [1] . $\rho$ $O(N^{1/4})$

Pollards ρ-algoritm bygger en talföljd , vars element bildar en cykel, utgående från något tal n , vilket kan illustreras genom arrangemanget av siffror i form av den grekiska bokstaven ρ , som var namnet på familjen av algoritmer [2] ] [3] .

Algoritmens historia

I slutet av 60-talet av 1900-talet kom Robert Floyd med en ganska effektiv metod för att lösa problemet med att hitta cykeln , även känd som "sköldpadda och hare"-algoritmen [4] . John Pollard , Donald Knuth och andra matematiker har analyserat det genomsnittliga fallbeteendet för denna algoritm. Flera modifieringar och förbättringar av algoritmen har föreslagits [5] .

1975 publicerade Pollard en artikel [6] där han, baserat på Floyds cykeldetekteringsalgoritm, skisserade idén om en talfaktoriseringsalgoritm som går i tid proportionell mot [6] [1] . Författaren till algoritmen kallade den Monte Carlo-faktoriseringsmetoden, vilket återspeglar den uppenbara slumpmässigheten hos siffrorna som genererades under beräkningen. Men senare fick metoden fortfarande sitt moderna namn - Pollards ρ-algoritm [7] . $N^{1/4}$

1981 använde Richard Brent och John Pollard en algoritm för att hitta de minsta divisorerna av Fermat-tal vid [8] . Algoritmens hastighet beror starkt endast på värdet av den minsta divisorn av det ursprungliga talet, men inte på själva talet. Så att hitta den minsta divisorn för det sjunde Fermat-talet - , tar mycket mer tid än att hitta divisorn för det tolfte Fermat-talet (eftersom dess divisor 114689 är mycket mindre, även om talet i sig består av mer än 1200 decimalsiffror). $F_{n}=2^{2^{n}}+1$ $5\leq n\leq 13$ ${\begin{array}{lll}F_{7}=340282366920938463463374607431768211457=59\,649\,589\,127\,497\,217\cdot 5,\9\9\04,2\,7,8 \,129\,054\,721;\end{array}}$

Som en del av Cunningham-projektet hjälpte Pollards algoritm att hitta en divisor på 19 siffror . Stora divisorer kunde också hittas, men upptäckten av metoden för faktorisering av elliptiska kurvor gjorde Pollards algoritm okonkurrenskraftig [9] . $2^{2386}+1$

Beskrivning av algoritmen

Originalversion

Vi betraktar en sekvens av heltal , så att och , där är talet som ska faktoriseras . Den ursprungliga algoritmen ser ut så här [10] [6] : ${x_{n}}$ $x_{0}=2$ $x_{i+1}=(x_{i}^{2}-1\,)(\mathrm {mod} \,N)$ $N$

1. Tripplar av siffror beräknas

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

, var .

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

Dessutom erhålls varje sådan trippel från den föregående. 2. Varje gång ett tal är en multipel av ett tal (säg, ), beräkna den största gemensamma divisorn med någon känd metod.

i

m

m=100

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

3. Om , då en partiell nedbrytning av antalet hittas, och .

1<d_{i}<N

N

N=d_{i}\ gånger (N/d_{i})

Den hittade divisorn kan vara sammansatt, så den måste också faktoriseras. Om talet är sammansatt fortsätter vi algoritmen med modulo .

d_{i}

N/d_{i}

N'=N/d_{i}

4. Beräkningarna upprepas en gång. Om numret samtidigt inte var helt faktoriserat, till exempel, väljs ett annat initialtal .

S

x_{{0}}

Modern version

Låt vara ett sammansatt positivt heltal som du vill faktorisera. Algoritmen ser ut så här [11] : $N$

Ett litet antal väljs slumpmässigt [12] och en sekvens konstrueras , som definierar varje nästa som . $x_{{0}}$ $\{x_{n}\},n=0,1,2,...$ $x_{n+1}=F(x_{n})\,(\mathrm {mod} \,\,N)$
Samtidigt, vid varje i -te steg , beräknas det för vissa , så att t.ex. $d=\mathrm {GCD} (N,|x_{i}-x_{j}|)$ $i$ $j$ $j<i$ $i=2j$
Om , då slutar beräkningen, och talet som hittades i föregående steg är en divisor av . Om det inte är ett primtal fortsätter sökproceduren för divisor, med ett tal . $d>1$ $d$ $N$ $N/d$ $N$ $N'=N/d$

I praktiken väljs funktionen inte för svårt att beräkna (men samtidigt inte ett linjärt polynom), förutsatt att den inte ska generera en en-till-en-mappning. Vanligtvis väljs funktionerna [12] eller [13] som . Men funktionerna och inte passar [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}$

Om det är känt att divisorn för ett tal är giltig för vissa , då är det vettigt att använda [10] . $sid$ $N$ $p\equiv 1\,(\mathrm {mod} \,k)$ $k>2$ $F(x)=x^{k}+b$

En betydande nackdel med algoritmen i denna implementering är behovet av att lagra ett stort antal tidigare värden . $x_{j}$

Algoritmförbättringar

Den ursprungliga versionen av algoritmen har ett antal nackdelar. För närvarande finns det flera metoder för att förbättra den ursprungliga algoritmen.

Låt . Sedan, om , då , därför, om ett par ger en lösning, då kommer vilket par som helst att ge en lösning . $F(x)=(x^{2}-1)\mathrm {mod} \,N$ $(x_{j}-x_{i})\ekvivalent 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})$

Därför finns det inget behov av att kontrollera alla par , men vi kan begränsa oss till par av formen , där , och går igenom uppsättningen av på varandra följande värden 1, 2, 3, ..., och tar värden från intervallet . Till exempel, , och [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]$

Denna idé föreslogs av Richard Brent 1980 [ 14] och minskar antalet utförda operationer med cirka 25 % [15] .

En annan variant av Pollards ρ-algoritm utvecklades av Floyd . Enligt Floyd uppdateras värdet vid varje steg enligt formeln , så värdena , , kommer att erhållas vid steget , och GCD i detta steg beräknas för och [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$

Ett exempel på faktorisering av ett tal

Det här exemplet visar tydligt faktoriseringens ρ-algoritm (version av algoritmen, med Floyds förbättring ), för talet N = 8051:

Tabell: faktorisering av talet 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)
ett	5	26	ett
2	26	7474	ett
3	677	871	97

Genom att använda andra varianter av polynomet kan man också få en divisor på 83: $F(x)$

Tabell: faktorisering av talet 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)
ett	7	52	ett
2	52	1442	ett
3	2707	778	ett
fyra	1442	3932	83

Således är d 1 \u003d 97, d 2 \u003d 83 icke-triviala divisorer av numret 8051.

Efter att ha hittat talets divisor, föreslås i ρ-algoritmen att fortsätta beräkningarna och leta efter talets divisorer om det inte är primtal. I detta enkla exempel krävdes inte detta steg [11] . $N/d$ $N/d$

Skäl för Pollards ρ-algoritm

Algoritmen bygger på den välkända födelsedagsparadoxen .

Födelsedagsparadoxen, kortfattat:
Låt . För ett slumpmässigt urval av element vart och ett mindre än , där sannolikheten för att två element är likadana . $\lambda>0$ $l+1$ $q$ $l={\sqrt {2\lambda q}}$ $p>1-e^{-\lambda }$

Det bör noteras att sannolikheten i födelsedagsparadoxen uppnås vid . $p=0,5$ $\lambda \ca 0,69$

Låt sekvensen bestå av skillnader , kontrollerade under algoritmen. En ny sekvens bestäms , där , är den minsta av talets divisorer . $\{fn}\}$ $x_{i}-x_{j}$ $\{z_{n}\}$ $z_{n}=u_{n}\,\mathrm {mod} \,q$ $q$ $N$

Alla medlemmar i sekvensen är mindre än . Om vi betraktar det som en slumpmässig sekvens av heltal mindre än , då, enligt födelsedagsparadoxen, kommer sannolikheten att två identiska kommer att falla bland dess medlemmar att överstiga när , då måste den vara minst . $\{z_{n}\}$ ${\sqrt {N}}$ $q$ $l+1$ $1/2$ $\lambda \ca 0,69$ $l$ ${\sqrt {2\lambda q}}\approx {\sqrt {1.4q}}\approx 1.18{\sqrt {q}}$

Om , alltså , det vill säga för något heltal . Om , vilket håller med hög sannolikhet, kommer den önskade divisorn för talet att hittas som . Eftersom , då med en sannolikhet som överstiger , kommer divisorn att hittas i iterationer [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\ gånger N^{1/4}$

Algoritmens komplexitet

För att uppskatta algoritmens komplexitet anses sekvensen som konstruerats under beräkningarna som slumpmässig (naturligtvis kan man inte tala om någon rigor i detta fall). För att helt faktorisera ett antal längdbitar räcker det att hitta alla dess divisorer som inte överstiger , vilket kräver maximalt ordningen för aritmetiska operationer, eller bitoperationer. $N$ $\beta$ ${\sqrt {N}}$ ${\sqrt {N}}$ $N^{1/4}\beta ^{2}=2^{\beta /4}\beta ^{2}$

Därför uppskattas komplexiteten hos algoritmen till [16] . Denna uppskattning tar dock inte hänsyn till omkostnaderna för att beräkna den största gemensamma divisorn . Den erhållna komplexiteten hos algoritmen, även om den inte är exakt, överensstämmer väl med praxis. $O(N^{1/4})$

Följande påstående är sant: låt vara ett sammansatt tal . Sedan finns det en konstant sådan att, för varje positivt tal, sannolikheten för händelsen att Pollards ρ-algoritm inte hittar en icke-trivial divisor i tiden inte överstiger . Detta uttalande följer av paradoxen med födelsedagar [17] . $N$ $C$ $\lambda$ $N$ $C{\sqrt {\lambda {\sqrt {N))))(\log N)^{2}$ $e^{-\lambda }$

Implementeringsfunktioner

Mängden minne som används av algoritmen kan reduceras avsevärt.

int Rho-Pollard ( int N) { int x = slumpmässigt (1, N-2); int y = 1; int i = 0; int steg = 2; medan (N.O.D.(N, abs (x - y)) == 1) { if (i == stadium){ y=x; steg = steg*2; } x = (x*x + 1) (mod N); i = i + 1; } retur N.O.D (N, abs (xy)); }

I denna version kräver beräkningen att endast tre variabler lagras , och , vilket skiljer algoritmen i en sådan implementering från andra talfaktoriseringsmetoder [11] . $N$ $x$ $y$

Algoritmparallellisering

Pollards algoritm tillåter parallellisering med användning av både delade minnessystem och distribuerade minnessystem ( meddelandeöverföring ), men det andra fallet är det mest intressanta ur praktisk synvinkel [18] .

Distribuerat minnessystem

Den befintliga metoden för parallellisering ligger i det faktum att varje beräkningsnod exekverar samma sekventiella algoritm , men det ursprungliga numret och/eller polynomet tas på olika sätt. För att förenkla parallellisering föreslås att man tar emot dem från en slumptalsgenerator. En sådan parallell implementering ger dock ingen linjär hastighet [19] . $x_{{0}}$ $F(x)$

Låt oss anta att det finns identiska artister. Om vi använder olika sekvenser (det vill säga olika polynom ), så kommer sannolikheten att de första talen i dessa sekvenser kommer att vara olika modulo att vara ungefär lika med . Således kan den maximala accelerationen uppskattas till [9] . $P$ $P$ $F(x)$ $k$ $sid$ $\exp({-k^{2}P}/{2p})$ $P^{1/2}$

Richard Crandall föreslog att acceleration är möjlig , men detta påstående har ännu inte verifierats [20] . $O(P/(log{P})^{2})$

System för delat minne

Den tidigare metoden kan uppenbarligen användas på system med delat minne, men det är mycket rimligare att använda en enda generator [21] . $F(x)$

Anteckningar

↑ 1 2 Pollard, 1974 , sid. 521–528.
↑ Christensen, 2009 , 3.3.3.0.
↑ Chatterjee, 2008 , 5.2.2.
↑ Floyd, 1967 , sid. 636–644.
↑ Brent, 1980 , En förbättrad Monte Carlo-faktoriseringsalgoritm, sid. 176.
↑ 1 2 3 Pollard, 1975 , A Monte Carlo method for factorization, sid. 176.
↑ Koshy, 2007 , Elementär nummerteori med tillämpningar.
^ Childs, 2009 , en konkret introduktion till högre algebra.
↑ 1 2 Brent, 1999 , Några parallella algoritmer för heltalsfaktorisering..
↑ 1 2 3 Pollard, 1975 , En Monte Carlo-metod för faktorisering.
↑ 1 2 3 4 5 6 Ishmukhametov, 2011 , sid. 64.
↑ 1 2 Mollin, 2006 , sid. 215-216.
↑ Zolotykh N. Yu. Föreläsningar om datoralgebra. Föreläsning 11. Pollards ρ-metod. Arkiverad 30 oktober 2014 på Wayback Machine
↑ Brent, 1980 , En förbättrad Monte Carlo-faktoriseringsalgoritm, sid. 176-184.
↑ Reisel, 2012 , Utvalda områden i kryptografi. Primtal och datormetoder för faktorisering. 2:a upplagan..
↑ Cormen, 2001 , Introduktion till algoritmer. Avsnitt 31.9. Heltalsfaktorisering. Pollards rho heuristik..
↑ Ishmukhametov, 2011 , sid. 63.
↑ Kosyakov, 2014 , sid. 12.
↑ Kuhn, 2001 , Random Walks Revisited: Förlängningar av Pollards Rho-algoritm för att beräkna flera diskreta logaritmer, s. 212-229.
↑ Crandall, 1999 , Parallellisering av Polldar-rho-faktorisering.
↑ Kosyakov, 2014 , sid. 19.

Litteratur

Vasilenko O. N. Talteoretiska algoritmer i kryptografi . - M. : MTSNMO , 2003. - 328 sid. — ISBN 5-94057-103-4 . Arkiverad 27 januari 2007 på Wayback Machine
Ishmukhametov Sh. T. Faktoriseringsmetoder för naturliga tal: Lärobok / Zakharov V.M. - Kazan: Kazan University, 2011. - P. 61-64. — 190 sid. — ISBN 978-3-659-17639-5 .
Kosyakov M.S. Introduktion till distribuerad beräkning / NRU ITMO. - St Petersburg. , 2014. - 155 sid.
tyska O.N., Nesterenko A.Yu. Talteoretiska metoder i kryptografi . - M. , 2012. - 300 sid.
Solovyov Yu. P., Sadovnichy V. A. , Shavgulidze E. T. , Belokurov V. V. Elliptiska kurvor och moderna talteorialgoritmer. - M . : In-t dator. issled., 2003. - 192 sid. — ISBN ISBN 5-939722-27-X .
Brent RP = Några parallella algoritmer för heltalsfaktorisering . - 1999. - S. 7 . - doi : 10.1017/S0305004100049252 .
Brent RP En förbättrad Monte Carlo-faktoriseringsalgoritm // BIT Numerisk matematik. - 1980. - 1 juni ( vol. 20 , utg. 2 ). - S. 176-184 . — ISSN 1572-9125 . - doi : 10.1007/BF01933190 .
Chatterjee S., Sarkar P. Introduktion // Identitetsbaserad kryptering. - Boston: Springer USA, 2008. - ISBN 978-1-59693-238-8 .
Childs, Lindsay N. Congruences // Concrete Introduction to Higher Algebra . - 3:e uppl. - USA: Springer, 2009. - S. 471-473. - 603 sid. — ISBN 978-0-387-74725-5 .
Chris Christensen. Recension av Modern Cryptanalysis: Techniques for Advanced Code Breaking av Christopher Swenson // Cryptologia. - 2009. - 27 januari ( vol. 33 , nummer 1 ). — ISSN 0161-1194 . - doi : 10.1080/01611190802293397 .
Cormen TH, Leiserson CE, Rivest RL, Stein C. Algoritmer: konstruktion och analys = Introduktion till algoritmer. - 2:a uppl. - USA: MIT Press, 2001. - S. 897-907. — 1180 sid. — ISBN 9780262032933 .
Crandall RE = Parallellisering av Polldar -rho-faktorisering . - 1999. Arkiverad den 6 juli 2010.
Koshy T. Kongruenser // Elementär talteori med tillämpningar. - 2:a uppl. - USA: Academic Press, 2007. - S. 238. - 771 sid. — ISBN 9780123724878 .
Kuhn F., Struik R. Random Walks Revisited: Extensions of Pollard's Rho Algorithm for Computing Multiple Discrete Logarithms // Selected Areas in Cryptography / Serge Vaudenay, Amr M.. - Springer Berlin Heidelberg, 2001. - P. 212 -229 . - ISBN 978-3-540-43066-7 , 978-3-540-45537-0 . - doi : 10.1007/3-540-45537-x_17 .
Mollin RA En introduktion till kryptografi / Rosen KH. - 2. - London: Chapman and Hall, 2006. - 413 sid. — ISBN 9781584886181 .
Pollard JM En Monte Carlo-metod för faktorisering // BIT Numerisk matematik. - 1975. - Vol. 15, nr 3 . - s. 331-334.
Pollard JM Theorems on factorization and primality testing // Mathematical Proceedings of the Cambridge Philosophical Society. - 1974. - T. 76 , nr. 03 . — S. 521–528 . — ISSN 1469-8064 . - doi : 10.1017/S0305004100049252 .
Pollard JM Faktoriseringsmetoder och primatitetstestning. (engelska) = Satser om faktorisering och primalitetstestning. // Mathematical Proceedings of the Cambridge Philosophical Society. - 1974. - T. 76 , nr 3 . - S. 521 . - doi : 10.1017/S0305004100049252 .
Reisel, H. Primtal och datormetoder för faktorisering. - 2:a uppl. - USA: Springer, 2012. - S. 183. - 464 sid. - ISBN 978-0-8176-8297-2 .
Robert W. Floyd. Icketerministiska algoritmer // J. ACM. - 1967. - T. 14 , nr. 4 . — S. 636–644 . — ISSN 0004-5411 . - doi : 10.1145/321420.321422 .

Talteoretiska algoritmer
Enkelhetstest	Mjölnare Miller - Rabin Luca - Lemaire pepina Agrawala - Kayala - Sachsen Nightingale - Strassen
Hitta primtal	Itererar över divisorer Sil av Eratosthenes Atkins såll Sikt Sundarama
Faktorisering	Itererar över divisorer Fermat-metoden p −1 Pollardmetoden Pollards ρ-algoritm Lehmanns metod Elliptisk kurvmetod (Lenstras algoritm) Dixons algoritm Fyrkantig sil
Diskret logaritm	Gelfond-Shanks algoritm Polig-Hellman algoritm Pollards ρ-metod Pollards kängurualgoritm Adlemans algoritm COS-algoritm
Hitta GCD	Euklids algoritm Avancerad algoritm Binär algoritm
Modulo aritmetik	Montgomerys algoritm Kinesisk restsats
Multiplikation och division av tal	Karatsuba algoritm Toom-Cook algoritm Schönhage-Strassen algoritm Fuhrer algoritm Harvey-van der Hoevens algoritm Burnickel-Ziegler algoritm
Beräkna kvadratroten	Tonelli-Shanks algoritm Berlekamp-Rabin algoritm