Pollards rho-algoritme

Ro-algoritme ( -algorithm ) er en algoritme foreslået af John Pollard i 1975 til factoring (faktoring) af heltal. Denne algoritme er baseret på Floyds algoritme til at finde cykluslængde i en sekvens og nogle konsekvenser af fødselsdagsparadokset . Algoritmen er mest effektiv ved faktorisering af sammensatte tal med tilstrækkeligt små faktorer i udvidelsen. Algoritmens kompleksitet er estimeret til [1] . $\rho$ $O(N^{1/4})$

Pollards ρ-algoritme bygger en talrække , hvis elementer danner en cyklus, startende fra et eller andet tal n , hvilket kan illustreres ved opstillingen af tal i form af det græske bogstav ρ , som var navnet på familien af algoritmer [2 ] [3] .

Algoritmens historie

I slutningen af 60'erne af det XX århundrede kom Robert Floyd med en ret effektiv metode til at løse cyklusfindingsproblemet , også kendt som "skildpadde og hare"-algoritmen [4] . John Pollard , Donald Knuth og andre matematikere har analyseret den gennemsnitlige case-adfærd for denne algoritme. Adskillige ændringer og forbedringer af algoritmen er blevet foreslået [5] .

I 1975 publicerede Pollard en artikel [6] , hvori han, baseret på Floyds cyklusdetektionsalgoritme, skitserede ideen om en talfaktoriseringsalgoritme, der kører i tid proportionalt med [6] [1] . Forfatteren af algoritmen kaldte den Monte Carlo-faktoriseringsmetoden, hvilket afspejler den tilsyneladende tilfældighed af de tal, der blev genereret under beregningen. Men senere fik metoden stadig sit moderne navn - Pollards ρ-algoritme [7] . $N^{1/4}$

I 1981 brugte Richard Brent og John Pollard en algoritme til at finde de mindste divisorer af Fermat-tal ved [8] . Algoritmens hastighed afhænger kun stærkt af værdien af den mindste divisor af det oprindelige tal, men ikke af selve tallet. Så det tager meget længere tid at finde den mindste divisor af det syvende Fermat-tal - , end at finde divisoren for det tolvte Fermat-tal (fordi dens divisor 114689 er meget mindre, selvom tallet i sig selv består af mere end 1200 decimalcifre). $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\9,5,\0,8 \,129\,054\,721;\end{array}}$

Som en del af Cunningham-projektet hjalp Pollards algoritme med at finde en divisor på 19 cifre . Store divisorer kunne også findes, men opdagelsen af den elliptiske kurvefaktoriseringsmetode gjorde Pollards algoritme ukonkurrencedygtig [9] . $2^{2386}+1$

Beskrivelse af algoritmen

Original version

Vi betragter en sekvens af heltal , sådan at og , hvor er det tal, der skal faktoriseres . Den originale algoritme ser sådan ud [10] [6] : ${x_{n}}$ $x_{0}=2$ $x_{i+1}=(x_{i}^{2}-1\,)(\mathrm {mod} \,N)$ $N$

1. Der beregnes tripler af tal

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

, hvor .

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

Desuden opnås hver sådan tripel fra den foregående. 2. Hver gang et tal er et multiplum af et tal (f.eks. ), skal du beregne den største fælles divisor ved en kendt metode.

jeg

m

m=100

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

3. Hvis , så findes en delvis dekomponering af tallet , og .

1<d_{i}<N

N

N=d_{i}\gange (N/d_{i})

Den fundne divisor kan være sammensat, så den skal også faktoriseres. Hvis tallet er sammensat, så fortsætter vi algoritmen med modulo .

d_{i}

N/d_{i}

N'=N/d_{i}

4. Beregninger gentages én gang. Hvis tallet samtidig ikke var fuldstændig faktoriseret, for eksempel, vælges et andet begyndelsestal .

S

x_{{0}}

Moderne version

Lad være et sammensat positivt heltal, som du vil faktorisere. Algoritmen ser sådan ud [11] : $N$

Et lille tal er tilfældigt udvalgt [12] og en sekvens er konstrueret , der definerer hver næste som . $x_{{0}}$ $\{x_{n}\},n=0,1,2,...$ $x_{n+1}=F(x_{n})\,(\mathrm {mod} \,\,N)$
Samtidig beregnes det ved hvert i -te trin for nogle , sådan at f.eks . $d=\mathrm {GCD} (N,|x_{i}-x_{j}|)$ $jeg$ $j$ $j<i$ $i=2j$
Hvis , så slutter beregningen, og tallet fundet i det foregående trin er en divisor af . Hvis det ikke er et primtal, fortsætter divisorsøgningsproceduren, idet der tages som et tal . $d>1$ $d$ $N$ $N/d$ $N$ $N'=N/d$

I praksis er funktionen valgt ikke for svær at beregne (men samtidig ikke et lineært polynomium), forudsat at den ikke skal generere en en-til-en mapping. Normalt er funktioner [12] eller [13] valgt som . Men funktionerne og passer ikke [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}$

Hvis man ved, at et tals divisor er gyldig for nogle , så giver det mening at bruge [10] . $s$ $N$ $p\equiv 1\,(\mathrm {mod} \,k)$ $k>2$ $F(x)=x^{k}+b$

En væsentlig ulempe ved algoritmen i denne implementering er behovet for at gemme et stort antal tidligere værdier . $x_{j}$

Algoritmeforbedringer

Den originale version af algoritmen har en række ulemper. I øjeblikket er der flere tilgange til at forbedre den originale algoritme.

Lad . Så, hvis , så derfor, hvis et par giver en løsning, så vil ethvert par give en løsning . $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})$

Derfor er det ikke nødvendigt at kontrollere alle par , men vi kan begrænse os til par af formen , hvor , og løber gennem sættet af på hinanden følgende værdier 1, 2, 3, ..., og tager værdier fra intervallet . For eksempel, , og [11] . $(x_{i},x_{j})$ $(x_{i},x_{j})$ $j=2^{k}$ $k$ $jeg$ $[2^{k}+1;2^{k+1}]$ $k=3$ $j=2^{3}=8$ $i\in[9;16]$

Denne idé blev foreslået af Richard Brent i 1980 [14] og reducerer antallet af udførte operationer med cirka 25 % [15] .

En anden variation af Pollards ρ-algoritme blev udviklet af Floyd . Ifølge Floyd opdateres værdien ved hvert trin i henhold til formlen , så værdierne , , vil blive opnået på trin , og GCD på dette trin beregnes for og [11] . $y$ $y=F^{2}(y)=F(F(y))$ $jeg$ $x_{i}=F^{i}(x_{0})$ $y_{i}=x_{2i}=F^{2i}(x_{0})$ $N$ $yx$

Et eksempel på faktorisering af et tal

Dette eksempel demonstrerer klart faktoriseringens ρ-algoritme (version af algoritmen, med Floyds forbedring ), for tallet N = 8051:

Tabel: Faktorisering af tallet 8051

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

Ved at bruge andre varianter af polynomiet kan man også få en divisor på 83: $F(x)$

Tabel: Faktorisering af tallet 8051

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

Således er d 1 \u003d 97, d 2 \u003d 83 ikke-trivielle divisorer af tallet 8051.

Efter at have fundet tallets divisor, foreslås det i ρ-algoritmen at fortsætte beregningerne og lede efter tallets divisorer, hvis det ikke er primtal. I dette simple eksempel var dette trin ikke påkrævet [11] . $N/d$ $N/d$

Begrundelse for Pollards ρ-algoritme

Algoritmen er baseret på det velkendte fødselsdagsparadoks .

Fødselsdagsparadokset, kort fortalt:
Lad . For en tilfældig stikprøve af elementer, der hver er mindre end , hvor sandsynligheden for, at to elementer er ens . $\lambda>0$ $l+1$ $q$ $l={\sqrt {2\lambda q))$ ${\displaystyle p>1-e^{-\lambda ))$

Det skal bemærkes, at sandsynligheden i fødselsdagsparadokset nås kl . $p=0,5$ $\lambda \ca. 0,69$

Lad sekvensen bestå af forskelle , kontrolleret under algoritmen. En ny sekvens bestemmes , hvor , er den mindste af divisorerne af tallet . $\{u_{n}\}$ $x_{i}-x_{j}$ $\{z_{n}\}$ $z_{n}=u_{n}\,\mathrm {mod} \,q$ $q$ $N$

Alle medlemmer af sekvensen er mindre end . Hvis vi betragter det som en tilfældig sekvens af heltal mindre end , så, ifølge fødselsdagsparadokset, vil sandsynligheden for, at to identiske vil falde blandt dets medlemmer, overstige når , så skal den være mindst . $\{z_{n}\}$ ${\sqrt {N}}$ $q$ $l+1$ $1/2$ $\lambda \ca. 0,69$ $l$ ${\sqrt {2\lambda q}}\approx {\sqrt {1.4q}}\ca. 1.18{\sqrt {q}}$

Hvis altså , det vil sige for et eller andet heltal . Hvis , som holder med høj sandsynlighed, så vil den ønskede divisor af tallet blive fundet som . Da , så med en sandsynlighed der overstiger , vil divisoren blive fundet 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\gange N^{1/4}$

Algoritmens kompleksitet

For at estimere kompleksiteten af algoritmen betragtes sekvensen konstrueret i løbet af beregninger som tilfældig (selvfølgelig kan man ikke tale om nogen strenghed i dette tilfælde). For fuldstændigt at faktorisere et antal længdebits er det nok at finde alle dens divisorer, der ikke overstiger , hvilket maksimalt kræver rækkefølgen af aritmetiske operationer eller bitoperationer. $N$ $\beta$ ${\sqrt {N}}$ ${\sqrt {N}}$ $N^{1/4}\beta ^{2}=2^{\beta /4}\beta ^{2}$

Derfor estimeres kompleksiteten af algoritmen til [16] . Dette estimat tager dog ikke højde for overhead ved beregning af den største fælles divisor . Den opnåede kompleksitet af algoritmen er, selvom den ikke er nøjagtig, i god overensstemmelse med praksis. $O(N^{1/4})$

Følgende udsagn er sandt: lad være et sammensat tal . Så er der en konstant sådan, at for ethvert positivt tal, overstiger sandsynligheden for hændelsen, at Pollards ρ-algoritme ikke finder en ikke-trivial divisor i tid , ikke . Dette udsagn følger af fødselsdagsparadokset [17] . $N$ $C$ $\lambda$ $N$ $C{\sqrt {\lambda {\sqrt {N))))(\log N)^{2}$ $e^{-\lambda }$

Implementeringsfunktioner

Mængden af hukommelse, der bruges af algoritmen, kan reduceres betydeligt.

int Rho-Pollard ( int N) { int x = tilfældig (1, N-2); int y = 1; int i = 0; int trin = 2; mens (N.O.D.(N, abs (x - y)) == 1) { if (i == fase){ y=x; trin = trin*2; } x = (x*x + 1) (mod N); i = i + 1; } retur N.O.D (N, abs (xy)); }

I denne version kræver beregningen kun at lagre tre variable , , og , hvilket adskiller algoritmen i en sådan implementering fra andre talfaktoriseringsmetoder [11] . $N$ $x$ $y$

Algoritme parallelisering

Pollards algoritme tillader parallelisering ved hjælp af både delte hukommelsessystemer og distribuerede hukommelsessystemer ( message passing ), men det andet tilfælde er det mest interessante fra et praktisk synspunkt [18] .

Distribueret hukommelsessystem

Den eksisterende metode til parallelisering ligger i det faktum, at hver computerknude udfører den samme sekventielle algoritme , men det oprindelige tal og/eller polynomium tages forskelligt. For at forenkle parallelisering foreslås det at modtage dem fra en tilfældig talgenerator. En sådan parallel implementering giver dog ikke en lineær speedup [19] . $x_{{0}}$ $F(x)$

Lad os antage, at der er identiske kunstnere. Hvis vi bruger forskellige sekvenser (det vil sige forskellige polynomier ), så vil sandsynligheden for, at de første tal i disse sekvenser vil være forskellige modulo være omtrent lig med . Den maksimale acceleration kan således estimeres til [9] . $P$ $P$ $F(x)$ $k$ $s$ $\exp({-k^{2}P}/{2p})$ $P^{1/2}$

Richard Crandall foreslog, at acceleration er opnåelig , men denne erklæring er endnu ikke blevet bekræftet [20] . $O(P/(log{P})^{2})$

Delt hukommelsessystem

Den tidligere metode kan naturligvis bruges på systemer med delt hukommelse, men det er meget mere rimeligt at bruge en enkelt generator [21] . $F(x)$

Noter

↑ 1 2 Pollard, 1974 , s. 521-528.
↑ Christensen, 2009 , 3.3.3.0.
↑ Chatterjee, 2008 , 5.2.2.
↑ Floyd, 1967 , s. 636-644.
↑ Brent, 1980 , En forbedret Monte Carlo-faktoriseringsalgoritme, s. 176.
↑ 1 2 3 Pollard, 1975 , A Monte Carlo metode til faktorisering, s. 176.
↑ Koshy, 2007 , Elementær talteori med applikationer.
↑ Childs, 2009 , En konkret introduktion til højere algebra.
↑ 1 2 Brent, 1999 , Nogle parallelle algoritmer til heltalsfaktorisering..
↑ 1 2 3 Pollard, 1975 , En Monte Carlo-metode til faktorisering.
↑ 1 2 3 4 5 6 Ishmukhametov, 2011 , s. 64.
↑ 1 2 Mollin, 2006 , s. 215-216.
↑ Zolotykh N. Yu. Forelæsninger om computeralgebra. Foredrag 11. Pollards ρ-metode. Arkiveret 30. oktober 2014 på Wayback Machine
↑ Brent, 1980 , En forbedret Monte Carlo-faktoriseringsalgoritme, s. 176-184.
↑ Reisel, 2012 , Udvalgte områder i kryptografi. Primtal og computermetoder til faktorisering. 2. udg..
↑ Cormen, 2001 , Introduktion til algoritmer. Afsnit 31.9. Heltalsfaktorisering. Pollards rho heuristik..
↑ Ishmukhametov, 2011 , s. 63.
↑ Kosyakov, 2014 , s. 12.
↑ Kuhn, 2001 , Random Walks Revisited: Extensions of Pollard's Rho Algorithm for Computing Multiple Discrete Logarithms, s. 212-229.
↑ Crandall, 1999 , Parallelization of Polldar-rho factorization.
↑ Kosyakov, 2014 , s. 19.

Litteratur

Vasilenko O. N. Talteoretiske algoritmer i kryptografi . - M .: MTSNMO , 2003. - 328 s. — ISBN 5-94057-103-4 . Arkiveret 27. januar 2007 på Wayback Machine
Ishmukhametov Sh. T. Faktoriseringsmetoder for naturlige tal: Lærebog / Zakharov V.M. - Kazan: Kazan University, 2011. - S. 61-64. — 190 s. — ISBN 978-3-659-17639-5 .
Kosyakov M.S. Introduktion til distribueret computing / NRU ITMO. - Sankt Petersborg. , 2014. - 155 s.
Tysk O.N., Nesterenko A.Yu. Talteoretiske metoder i kryptografi . - M. , 2012. - 300 s.
Solovyov Yu. P., Sadovnichy V. A. , Shavgulidze E. T. , Belokurov V. V. Elliptiske kurver og moderne talteorialgoritmer. - M . : In-t computer. issled., 2003. - 192 s. — ISBN ISBN 5-939722-27-X .
Brent RP = Nogle parallelle algoritmer til heltalsfaktorisering . - 1999. - S. 7 . - doi : 10.1017/S0305004100049252 .
Brent RP En forbedret Monte Carlo faktoriseringsalgoritme // BIT Numerisk matematik. - 1980. - 1. juni ( bind 20 , udg. 2 ). - S. 176-184 . — ISSN 1572-9125 . - doi : 10.1007/BF01933190 .
Chatterjee S., Sarkar P. Introduktion // Identitetsbaseret kryptering. - Boston: Springer US, 2008. - ISBN 978-1-59693-238-8 .
Childs, Lindsay N. Congruences // Concrete Introduction to Higher Algebra . - 3. udg. - USA: Springer, 2009. - S. 471-473. - 603 s. — ISBN 978-0-387-74725-5 .
Chris Christensen. Anmeldelse af Modern Cryptanalysis: Techniques for Advanced Code Breaking af Christopher Swenson // Cryptologia. - 2009. - 27. januar ( bind 33 , hæfte 1 ). — ISSN 0161-1194 . - doi : 10.1080/01611190802293397 .
Cormen TH, Leiserson CE, Rivest RL, Stein C. Algoritmer: konstruktion og analyse = Introduktion til algoritmer. - 2. udg. - USA: MIT Press, 2001. - S. 897-907. — 1180 s. — ISBN 9780262032933 .
Crandall RE = Parallelisering af Polldar -rho-faktorisering . - 1999. Arkiveret den 6. juli 2010.
Koshy T. Kongruenser // Elementær talteori med applikationer. - 2. udg. - 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 Logarithms // Selected Areas in Cryptography / 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 En introduktion til kryptografi / Rosen KH. - 2. - London: Chapman og Hall, 2006. - 413 s. — ISBN 9781584886181 .
Pollard JM En Monte Carlo metode til faktorisering // BIT Numerisk matematik. - 1975. - Bd. 15, nr. 3 . - S. 331-334.
Pollard JM -sætninger om faktorisering og primalitetstestning // Mathematical Proceedings of the Cambridge Philosophical Society. - 1974. - T. 76 , no. 03 . — S. 521–528 . — ISSN 1469-8064 . - doi : 10.1017/S0305004100049252 .
Pollard JM Faktoriseringsmetoder og primalitetstest. (engelsk) = Sætning om faktorisering og primalitetstest. // Mathematical Proceedings of the Cambridge Philosophical Society. - 1974. - T. 76 , nr. 3 . - S. 521 . - doi : 10.1017/S0305004100049252 .
Reisel, H. Primtal og computermetoder til faktorisering. - 2. udg. - USA: Springer, 2012. - S. 183. - 464 s. - ISBN 978-0-8176-8297-2 .
Robert W. Floyd. Nondeterministiske algoritmer // J. ACM. - 1967. - T. 14 , no. 4 . — S. 636–644 . — ISSN 0004-5411 . - doi : 10.1145/321420.321422 .

Talteoretiske algoritmer
Enkelthedstest	Miller Miller - Rabin Luca - Lemaire pepina Agrawala - Kayala - Sachsen Nightingale - Strassen
At finde primtal	Iteration over divisorer Sigte af Eratosthenes Atkins si Sigte Sundarama
Faktorisering	Iteration over divisorer Fermat metode p −1 Pollard metode Pollards ρ-algoritme Lehmanns metode Elliptisk kurvemetode (Lenstras algoritme) Dixons algoritme Firkantet sigte
Diskret logaritme	Gelfond-Shanks algoritme Polig-Hellman algoritme Pollards ρ-metode Pollards kængurualgoritme Adlemans algoritme COS algoritme
Finder GCD	Euklids algoritme Avanceret algoritme Binær algoritme
Modulo aritmetik	Montgomerys algoritme Kinesisk restsætning
Multiplikation og division af tal	Karatsuba algoritme Toom-Cook algoritme Schönhage-Strassen algoritme Fuhrer algoritme Harvey-van der Hoeven algoritme Burnickel-Ziegler algoritme
Beregning af kvadratroden	Tonelli-Shanks algoritme Berlekamp-Rabin algoritme