Pollardin rho-algoritmi

Ro-algoritmi ( -algoritmi ) on John Pollardin vuonna 1975 ehdottama algoritmi kokonaislukujen faktorointiin . Tämä algoritmi perustuu Floydin algoritmiin syklin pituuden ja syntymäpäiväparadoksin seuraamusten löytämiseksi sekvenssistä . Algoritmi on tehokkain, kun otetaan huomioon yhdistelmäluvut riittävän pienillä kertoimilla laajennuksessa. Algoritmin monimutkaisuus on arvioitu [1] . $\rho$ $O(N^{1/4})$

Pollardin ρ-algoritmi rakentaa numerosarjan , jonka alkiot muodostavat syklin, joka alkaa jostain luvusta n , jota voidaan havainnollistaa numeroiden järjestyksellä kreikkalaisen kirjaimen ρ muodossa , joka oli algoritmiperheen nimi [2 ] [3] .

Algoritmin historia

1960-luvun lopulla Robert Floyd keksi melko tehokkaan menetelmän syklin etsintäongelman ratkaisemiseksi , joka tunnetaan myös nimellä "kilpikonna ja jänis" -algoritmi [4] . John Pollard , Donald Knuth ja muut matemaatikot ovat analysoineet tämän algoritmin keskimääräistä tapauskäyttäytymistä. Algoritmiin on ehdotettu useita muutoksia ja parannuksia [5] .

Vuonna 1975 Pollard julkaisi artikkelin [6] , jossa hän Floydin syklintunnistusalgoritmiin perustuen hahmotteli ajatuksen lukutekijöiden jakamisalgoritmista, joka kulkee ajassa suhteessa [6] [1] . Algoritmin kirjoittaja kutsui sitä Monte Carlon tekijöiden muodostusmenetelmäksi, mikä heijastaa laskennan aikana syntyneiden lukujen näennäistä satunnaisuutta. Myöhemmin menetelmä sai kuitenkin edelleen nykyaikaisen nimensä - Pollardin ρ-algoritmi [7] . $N^{1/4}$

Vuonna 1981 Richard Brent ja John Pollard käyttivät algoritmia löytääkseen Fermat - lukujen pienimmät jakajat [8] . Algoritmin nopeus riippuu voimakkaasti vain alkuperäisen luvun pienimmän jakajan arvosta, mutta ei itse luvusta. Joten seitsemännen Fermat-luvun pienimmän jakajan löytäminen - , vie paljon enemmän aikaa kuin kahdennentoista Fermat-luvun jakajan löytäminen (koska sen jakaja 114689 on paljon pienempi, vaikka itse luku koostuu yli 1200 desimaalinumerosta). $F_{n}=2^{2^{n}}+1$ $5\leq n\leq 13$ ${\begin{array}{lll}F_{7}=340282366920938463463374607431768211457=59\,649\,589\,127\,497\,217\0cdot 5,\0,8 \,129\,054\,721;\end{array}}$

Osana Cunningham-projektia Pollardin algoritmi auttoi löytämään 19 numeron pituisen jakajan . Suuria jakajia voitiin myös löytää, mutta elliptisen käyrän tekijöiden menetelmän löytäminen teki Pollardin algoritmista kilpailukyvyttömän [9] . $2^{2386}+1$

Algoritmin kuvaus

Alkuperäinen versio

Tarkastellaan kokonaislukujen sarjaa siten , että ja , missä on tekijöihin jaettava luku . Alkuperäinen algoritmi näyttää tältä [10] [6] : ${x_{n}}$ $x_{0}=2$ $x_{i+1}=(x_{i}^{2}-1\,)(\mathrm {mod} \,N)$ $N$

1. Lasketaan lukujen kolmiot

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

, missä .

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

Lisäksi jokainen tällainen kolmois saadaan edellisestä. 2. Joka kerta kun luku on luvun kerrannainen (esim. ), laske suurin yhteinen jakaja millä tahansa tunnetulla menetelmällä.

i

m

m = 100

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

3. Jos , niin luvun osittainen hajoaminen löytyy, ja .

1<d_{i}<N

N

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

Löytynyt jakaja voi olla yhdistelmä, joten se on myös faktoroitava. Jos luku on yhdistelmä, jatkamme algoritmia modulolla .

d_{i}

N/d_{i}

N'=N/d_{i}

4. Laskutoimitukset toistetaan kerran. Jos samaan aikaan lukua ei esimerkiksi ole kerrottu kokonaan, valitaan toinen alkuluku .

S

x_{{0}}

Moderni versio

Olkoon positiivinen kokonaisluku, jonka haluat kertoa tekijöille. Algoritmi näyttää tältä [11] : $N$

Pieni määrä valitaan satunnaisesti [12] ja muodostetaan sekvenssi , joka määrittelee jokaisen seuraavan muodossa . $x_{{0}}$ $\{x_{n}\},n=0,1,2,...$ $x_{n+1}=F(x_{n})\,(\mathrm {mod} \,\,N)$
Samanaikaisesti jokaisessa i - vaiheessa se lasketaan joillekin , niin että esimerkiksi . $d=\mathrm {GCD} (N,|x_{i}-x_{j}|)$ $i$ $j$ $j<i$ $i = 2j$
Jos , laskenta päättyy ja edellisessä vaiheessa löydetty luku on luvun jakaja . Jos ei ole alkuluku, jakajahaku jatkuu ottamalla numeroksi . $d>1$ $d$ $N$ $N/d$ $N$ $N' = N/d$

Käytännössä funktion valinta ei ole liian vaikeasti laskettava (mutta ei samalla lineaarinen polynomi), jos sen ei tulisi tuottaa yksi-yhteen-kuvausta. Yleensä toiminnot [12] tai [13] valitaan muodossa . Toiminnot ja eivät kuitenkaan sovi [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}$

Jos tiedetään, että luvun jakaja pätee joillekin , niin on järkevää käyttää [10] . $s$ $N$ $p\equiv 1\,(\mathrm {mod} \,k)$ $k>2$ $F(x)=x^{k}+b$

Algoritmin merkittävä haittapuoli tässä toteutuksessa on tarve tallentaa suuri määrä aikaisempia arvoja . $x_{j}$

Algoritmin parannukset

Algoritmin alkuperäisessä versiossa on useita haittoja. Tällä hetkellä on olemassa useita tapoja parantaa alkuperäistä algoritmia.

Anna . Sitten, jos , niin , siis, jos pari antaa ratkaisun, niin mikä tahansa pari antaa ratkaisun . $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})$

Siksi kaikkia pareja ei tarvitse tarkistaa , vaan voimme rajoittua muodon pareihin , joissa ja kulkee peräkkäisten arvojen joukon 1, 2, 3, ... läpi ja ottaa arvot intervalli . Esimerkiksi , , ja [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]$

Tämän idean ehdotti Richard Brent vuonna 1980 [14] , ja se vähentää suoritettujen leikkausten määrää noin 25 % [15] .

Floyd kehitti toisen muunnelman Pollardin ρ-algoritmista . Floydin mukaan arvo päivitetään jokaisessa vaiheessa kaavan mukaan, joten arvot , , saadaan vaiheessa , ja GCD tässä vaiheessa lasketaan ja [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$

Esimerkki luvun tekijöistä

Tämä esimerkki osoittaa selvästi tekijöiden jakamisen ρ-algoritmin (algoritmin versio, Floydin parannuksella ) numerolle N = 8051:

Taulukko: luvun 8051 kertoimet

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)
yksi	5	26	yksi
2	26	7474	yksi
3	677	871	97

Käyttämällä muita polynomin muunnelmia voidaan myös saada 83:n jakaja: $F(x)$

Taulukko: luvun 8051 kertoimet

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)
yksi	7	52	yksi
2	52	1442	yksi
3	2707	778	yksi
neljä	1442	3932	83

Siten d 1 \u003d 97, d 2 \u003d 83 ovat luvun 8051 ei-triviaaleja jakajia.

Kun luvun jakaja on löydetty, ρ-algoritmissa ehdotetaan jatkavan laskelmia ja etsimällä luvun jakajia, jos se ei ole alkuluku. Tässä yksinkertaisessa esimerkissä tätä vaihetta ei vaadittu [11] . $N/d$ $N/d$

Pollardin ρ-algoritmin perustelu

Algoritmi perustuu tunnettuun syntymäpäiväparadoksiin .

Syntymäpäiväparadoksi, lyhyesti:
Anna . Satunnaisotokselle elementtejä kukin pienempi kuin , missä todennäköisyys , että kaksi elementtiä ovat samat . $\lambda>0$ $l+1$ $q$ $l={\sqrt {2\lambda q))$ ${\displaystyle p>1-e^{-\lambda ))$

On huomattava, että syntymäpäiväparadoksin todennäköisyys saavutetaan klo . $p = 0,5$ $\lambda \noin 0,69$

Olkoon sekvenssi koostuva eroista , jotka tarkistetaan algoritmin aikana. Määritetään uusi jono , jossa , on luvun pienin jakaja . $\{u_{n}\}$ $x_{i}-x_{j}$ $\{z_{n}\}$ $z_{n}=u_{n}\,\mathrm {mod} \,q$ $q$ $N$

Kaikki sekvenssin jäsenet ovat pienempiä kuin . Jos tarkastellaan sitä satunnaisena kokonaislukujonona, joka on pienempi kuin , niin syntymäpäiväparadoksin mukaan todennäköisyys, että sen jäsenten joukkoon putoaa kaksi identtistä, ylittää milloin , silloin sen on oltava vähintään . $\{z_{n}\}$ ${\sqrt {N}}$ $q$ $l+1$ $1/2$ $\lambda \noin 0,69$ $l$ ${\sqrt {2\lambda q}}\noin {\sqrt {1,4q}}\noin 1,18{\sqrt {q}}$

Jos Sitten , Eli joidenkin kokonaislukujen . Jos , joka pätee suurella todennäköisyydellä, luvun haluttu jakaja löytyy muodossa . Koska , silloin todennäköisyydellä, joka ylittää , jakaja löytyy iteraatioista [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\ kertaa N^{1/4}$

Algoritmin monimutkaisuus

Algoritmin monimutkaisuuden arvioimiseksi laskelmien aikana muodostettua sekvenssiä pidetään satunnaisena (tässä tapauksessa ei tietenkään voida puhua mistään kurinalaisuudesta). Pituusbittien osoittamiseksi kokonaan riittää , että etsitään kaikki sen jakajat, jotka eivät ylitä , mikä vaatii maksimissaan aritmeettisten operaatioiden eli bittioperaatioiden järjestyksen . $N$ $\beeta$ ${\sqrt {N}}$ ${\sqrt {N}}$ $N^{1/4}\beta ^{2}=2^{\beta /4}\beta ^{2}$

Siksi algoritmin monimutkaisuus on arvioitu [16] . Tämä arvio ei kuitenkaan ota huomioon suurimman yhteisen jakajan laskemisen yleiskustannuksia . Algoritmin saatu monimutkaisuus, vaikkakaan ei tarkka, on hyvin sopusoinnussa käytännön kanssa. $O(N^{1/4})$

Seuraava väite on totta: anna olla yhdistelmäluku . Sitten on sellainen vakio , että mille tahansa positiiviselle luvulle tapahtuman todennäköisyys, että Pollardin ρ-algoritmi ei löydä ei-triviaalista jakajaa ajassa , ei ylitä . Tämä lausunto on seurausta syntymäpäivien paradoksista [17] . $N$ $C$ $\lambda$ $N$ $C{\sqrt {\lambda {\sqrt {N))))(\log N)^{2}$ $e^{-\lambda }$

Toteutusominaisuudet

Algoritmin käyttämän muistin määrää voidaan vähentää merkittävästi.

int Rho-Pollard ( int N) { int x = satunnainen (1, N-2); int y = 1; int i = 0; int vaihe = 2; while (N.O.D.(N, abs (x - y)) == 1) { if (i == vaihe){ y = x; vaihe = vaihe*2; } x = (x*x + 1) (mod N); i = i + 1; } paluu N.O.D (N, abs (xy)); }

Tässä versiossa laskenta vaatii vain kolmen muuttujan , , ja tallentamisen , mikä erottaa tällaisen toteutuksen algoritmin muista lukukerroinmenetelmistä [11] . $N$ $x$ $y$

Algoritmin rinnastus

Pollardin algoritmi mahdollistaa rinnastamisen sekä jaetuilla muistijärjestelmillä että hajautetuilla muistijärjestelmillä ( sanomanvälitys ), mutta toinen tapaus on käytännön näkökulmasta mielenkiintoisin [18] .

Hajautettu muistijärjestelmä

Nykyinen rinnakkaismenetelmä perustuu siihen, että jokainen laskentasolmu suorittaa saman peräkkäisen algoritmin , mutta alkuperäinen luku ja/tai polynomi otetaan eri tavalla. Rinnakkaisemisen yksinkertaistamiseksi ehdotetaan niiden vastaanottamista satunnaislukugeneraattorilta. Tällainen rinnakkaistoteutus ei kuitenkaan tarjoa lineaarista nopeutta [19] . $x_{{0}}$ $F(x)$

Oletetaan, että esiintyjät ovat samat. Jos käytämme erilaisia sekvenssejä (eli erilaisia polynomeja ), niin todennäköisyys, että näiden sekvenssien ensimmäiset luvut ovat eri modulo , on suunnilleen yhtä suuri kuin . Näin ollen suurin kiihtyvyys voidaan arvioida [9] . $P$ $P$ $F(x)$ $k$ $s$ $\exp({-k^{2}P}/{2p})$ $P^{1/2}$

Richard Crandall ehdotti, että kiihtyvyys on saavutettavissa , mutta tätä väitettä ei ole vielä vahvistettu [20] . $O(P/(log{P})^{2})$

Jaettu muistijärjestelmä

Edellistä menetelmää voidaan luonnollisesti käyttää järjestelmissä, joissa on jaettu muisti, mutta paljon järkevämpää on käyttää yhtä generaattoria [21] . $F(x)$

Muistiinpanot

↑ 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 , Parannettu Monte Carlo -faktorointialgoritmi, s. 176.
↑ 1 2 3 Pollard, 1975 , Monte Carlo -menetelmä faktorointiin, s. 176.
↑ Koshy, 2007 , Elementary Number Theory with Applications.
↑ Childs, 2009 , Konkreettinen johdatus korkeampaan algebraan.
↑ 1 2 Brent, 1999 , Jotkut rinnakkaiset algoritmit kokonaislukujen tekijöihin jakamiseen.
↑ 1 2 3 Pollard, 1975 , Monte Carlo -menetelmä tekijöihin jakamiseen.
↑ 1 2 3 4 5 6 Ishmukhametov, 2011 , s. 64.
↑ 1 2 Mollin, 2006 , s. 215-216.
↑ Zolotykh N. Yu. Luennot tietokonealgebrasta. Luento 11. Pollardin ρ-menetelmä. Arkistoitu 30. lokakuuta 2014 Wayback Machinessa
↑ Brent, 1980 , Parannettu Monte Carlo -faktorointialgoritmi, s. 176-184.
↑ Reisel, 2012 , Valitut alueet kryptografiassa. Alkuluvut ja tietokonemenetelmät faktorointiin. 2. painos..
↑ Cormen, 2001 , Johdatus algoritmeihin. Kohta 31.9. Kokonaislukufaktorointi. Pollardin rho-heuristiikka..
↑ Ishmukhametov, 2011 , s. 63.
↑ Kosyakov, 2014 , s. 12.
↑ Kuhn, 2001 , Random Walks Revisited: Extensions of Pollard's Rho Algorithm for Computing Multiple Discrete Logathms, s. 212-229.
↑ Crandall, 1999 , Polldar-rho-tekijöiden rinnastaminen.
↑ Kosyakov, 2014 , s. 19.

Kirjallisuus

Vasilenko O. N. Lukuteoreettiset algoritmit kryptografiassa . - M .: MTSNMO , 2003. - 328 s. — ISBN 5-94057-103-4 . Arkistoitu 27. tammikuuta 2007 Wayback Machinessa
Ishmukhametov Sh. T. Luonnollisten lukujen faktorointimenetelmät: Oppikirja / Zakharov V.M. - Kazan: Kazan University, 2011. - P. 61-64. - 190 s. — ISBN 978-3-659-17639-5 .
Kosyakov M.S. Johdatus hajautettuun tietojenkäsittelyyn / NRU ITMO. - Pietari. , 2014. - 155 s.
Saksalainen O.N., Nesterenko A.Yu. Numeroteoreettiset menetelmät kryptografiassa . - M. , 2012. - 300 s.
Solovjov Yu. P., Sadovnichy V. A. , Shavgulidze E. T. , Belokurov V. V. Elliptiset käyrät ja nykyaikaiset lukuteoriaalgoritmit. - M . : Sisäinen tietokone. Issled., 2003. - 192 s. — ISBN ISBN 5-939722-27-X .
Brent RP = Jotkut rinnakkaiset algoritmit kokonaislukujen tekijöihin jakamiseen . - 1999. - S. 7 . - doi : 10.1017/S0305004100049252 .
Brent RP Parannettu Monte Carlo -faktorointialgoritmi // BIT Numerical Mathematics. - 1980. - 1. kesäkuuta ( nide 20 , painos 2 ). - s. 176-184 . — ISSN 1572-9125 . - doi : 10.1007/BF01933190 .
Chatterjee S., Sarkar P. Johdanto // Identiteettiin perustuva salaus. - Boston: Springer USA, 2008. - ISBN 978-1-59693-238-8 .
Childs, Lindsay N. Congruences // Concrete Introduction to Higher Algebra . - 3. painos - USA: Springer, 2009. - S. 471-473. - 603 s. — ISBN 978-0-387-74725-5 .
Chris Christensen. Christopher Swensonin katsaus moderniin kryptaanalyysiin: edistyneen koodin murtamisen tekniikat // Cryptologia. - 2009. - 27. tammikuuta ( nide 33 , numero 1 ). — ISSN 0161-1194 . - doi : 10.1080/01611190802293397 .
Cormen TH, Leiserson CE, Rivest RL, Stein C. Algoritmit: rakentaminen ja analyysi = Johdanto algoritmeihin. - 2. painos - USA: MIT Press, 2001. - S. 897-907. — 1180 s. — ISBN 9780262032933 .
Crandall RE = Polldar -rho -tekijöiden rinnakkaissuoritus . - 1999. Arkistoitu 6. heinäkuuta 2010.
Koshy T. Congruences // Alkulukuteoria sovellusten kanssa. - 2. painos - 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 Logathms // Selected Areas in Cryptography / Serge Vaudenay, Amr M.. - Springer Berlin Heidelberg, 2001. - P. 212 -29 - ISBN 978-3-540-43066-7 , 978-3-540-45537-0 . - doi : 10.1007/3-540-45537-x_17 .
Mollin RA Johdatus kryptografiaan / Rosen KH. - 2. - Lontoo: Chapman ja Hall, 2006. - 413 s. — ISBN 9781584886181 .
Pollard JM Monte Carlo -menetelmä faktorointiin // BIT Numerical Mathematics. - 1975. - Voi. 15, nro 3 . - s. 331-334.
Pollard JM :n lauseita faktorisaatiosta ja primaliteettitestauksesta // Mathematical Proceedings of the Cambridge Philosophical Society. - 1974. - T. 76 , no. 03 . — S. 521–528 . — ISSN 1469-8064 . - doi : 10.1017/S0305004100049252 .
Pollard JM Factorisointimenetelmät ja primaalisuustestaus. (englanniksi) = Lauseet faktorisaatiosta ja primaalitestauksesta. // Mathematical Proceedings of the Cambridge Philosophical Society. - 1974. - T. 76 , nro 3 . - S. 521 . - doi : 10.1017/S0305004100049252 .
Reisel, H. Alkuluvut ja tietokonemenetelmät faktorointiin . - 2. painos - USA: Springer, 2012. - S. 183. - 464 s. - ISBN 978-0-8176-8297-2 .
Robert W. Floyd. Epädeterministiset algoritmit // J. ACM. - 1967. - T. 14 , no. 4 . — S. 636–644 . — ISSN 0004-5411 . - doi : 10.1145/321420.321422 .

Lukuteoreettiset algoritmit
Yksinkertaisuustestit	Miller Miller - Rabin Luca - Lemaire pepina Agrawala - Kayala - Saksi Nightingale - Strassen
Alkulukujen löytäminen	Iterointi jakajien yli Eratosthenesin seula Atkinin seula Seula Sundarama
Faktorisointi	Iterointi jakajien yli Fermat menetelmä p −1 Pollardin menetelmä Pollardin ρ-algoritmi Lehmannin menetelmä Elliptisen käyrän menetelmä (Lenstran algoritmi) Dixonin algoritmi Neliömäinen seula
Diskreetti logaritmi	Gelfond-Shanks -algoritmi Polig-Hellman-algoritmi Pollardin ρ-menetelmä Pollardin kenguru-algoritmi Adlemanin algoritmi COS-algoritmi
GCD:n löytäminen	Eukleideen algoritmi Kehittynyt algoritmi Binäärinen algoritmi
Modulo-aritmetiikka	Montgomeryn algoritmi Kiinan jäännöslause
Lukujen kerto- ja jakolasku	Karatsuba-algoritmi Toom-Cook-algoritmi Schönhage-Strassen-algoritmi Fuhrer-algoritmi Harvey-van der Hoeven-algoritmi Burnickel-Ziegler-algoritmi
Neliöjuuren laskeminen	Tonelli-Shanks-algoritmi Berlekamp-Rabin-algoritmi