P−1 Pollardin menetelmä

Kokeneet kirjoittajat eivät ole vielä tarkistaneet sivun nykyistä versiota, ja se voi poiketa merkittävästi 4. huhtikuuta 2019 tarkistetusta versiosta . tarkastukset vaativat 2 muokkausta .

$p-1$ Pollardin menetelmä on yksi kokonaislukujen tekijöiden laskentamenetelmistä .

Julkaisi ensimmäisen kerran brittiläinen matemaatikko John Pollard vuonna 1974 [1] . Juuri tämän algoritmin ilmestyminen johti [2] muutokseen kryptografiassa käytetyn vahvan alkuluvun käsitteessä , löyhästi sanottuna alkuluvun , jolle sillä on riittävän suuret jakajat. Nykyaikaisissa salausjärjestelmissä he yrittävät [2] käyttää vahvoja alkulukuja, koska tämä lisää käytettävien algoritmien ja järjestelmien turvallisuutta kokonaisuutena. $p-1$

Määritelmät ja matemaattinen tausta

Lukua kutsutaan - power- smooth [3] , jos kaikki sen alkujakajat, niiden potenssien osalta, joihin ne sisältyvät tämän luvun laajennukseen , täyttävät . Fermatin pienen lauseen mukaan mille tahansa alkuluvulle ja mille tahansa kokonaisluvulle , joka ja ovat koprime , tai, joka on tässä tapauksessa ekvivalentti, ei jaa , meillä on: $B$ ${\displaystyle p^{\nu ))$ $p^{\nu }\leq B$ $s$ $a$ $a$ $s$ $s$ $a$

a^{(p-1)}\equiv 1\mod p

, lisäksi .

\forall M=(p-1)l,l\in N\Rightarrow a^{M}\equiv 1\mod p

Alkuperäinen algoritmi (1974)

John Pollard julkaisi ensimmäisen kerran alla kuvatun algoritmin vuoden 1974 artikkelissaan "Theorems of Factorization and Primality Testing" Proceedings of the Cambridge Philosophical Society -julkaisussa [ 1] . Artikkeli on omistettu suuren luvun tekijöiden laskemisen monimutkaisuuden teoreettiselle arvioinnille tai, jos kyseessä on alkuluku , sen tarkistamiseen yksinkertaisuuden vuoksi. Seuraava algoritmi oli seuraus ja esimerkki Pollardin teoreettisista laskelmista. $N$ $N$

Ensimmäinen vaihe

Tehtävänä on löytää oma jakaja muulle kuin yhdelle. Ensinnäkin sinun on valittava kaksi numeroa siten, että . $N$ ${\näyttötyyli B,M,}$ ${\näyttötyyli 1<B<M<{\sqrt {N)),M<B^{2}}$
Lasketaan nyt luku , jossa kaikki alkuluvut ovat pienempiä kuin . Tässä sallitaan jonkinlainen vapaus valinnassa , mutta tiedetään varmasti, että pienille , pitäisi olla suurempi kuin yksi [1] . $M(B)=\prod _{k=1}^{m}p_{k}^{c_{k}}$ $p_{k}$ $B$ $c_{k}$ $p_{k}$ $c_{k}$
Valitsemme pienen kokonaisluvun ja laskemme $a>1$

b=a^{M(B)}\mod N

{\näyttötyyli q=(b-1,N)}

jos olemme löytäneet jakajan , muussa tapauksessa siirrymme toiseen vaiheeseen.

q\neq 1

N

Toinen vaihe

Tässä vaiheessa on tarpeen laskea sekvenssi

F_{m}\equiv b^{m-1}-1\mod N,

missä on alkuluku, toivoen, että jossain vaiheessa saamme

m

B<m<M

g_{m}=(F_{m},N)>1

Helpoin tapa [1] tehdä tämä on laskea jokainen pariton luku kertomalla luvulla , ottamalla säännöllisin väliajoin. Jos jakaja löytyy. Jos , niin tätä aluetta on tutkittava tarkemmin. $b^m$ $m$ $b^{2}$ $G_{i}=(b^{i},N)$ ${\näyttötyyli 1<G_{i}<N}$ $G_{i}=N,G_{i-1}=1$

Huomautus

Tällä menetelmällä voimme löytää vain sellaiset luvun alkujakajat , joille [1] on tosi : $s$ $N$

p-1=A

tai , jossa on -power-smooth ja on alkuluku sellainen, että [1] .

p-1=Aq

A

B

q

B<q<M

Moderni versio

Tämä uudistettu versio algoritmista alkuperäiseen verrattuna käyttää potenssilain sileyden käsitteitä ja keskittyy käytännön sovelluksiin. Ensimmäisessä vaiheessa tehtiin merkittäviä muutoksia, kun taas toinen pysyi käytännössä ennallaan, taaskaan teoreettisesta näkökulmasta mitään merkittävää ei lisätty edelliseen versioon verrattuna. Juuri alla olevaa algoritmia tarkoitetaan, kun puhutaan "Pollard-menetelmästä" [4] [5] .

Ensimmäinen vaihe

Olkoon -smooth potenssi, ja se on löydettävä luvun jakaja . Ensinnäkin lasketaan luku, jossa tulo suoritetaan kaikilla alkuluvuilla maksimitehoilla $N$ $B$ $N$ $M(B)=\prod _{i}p_{i}^{k_{i))$ $p_{i}$ $k_{i}:p_{i}^{k_{i}}<B$
Sitten haluttu jakaja [4] , jossa . ${\näyttötyyli q=(b-1,N)}$ $b=a^{M(B)}\mod N$

On kaksi mahdollista tapausta, joissa yllä oleva algoritmi epäonnistuu [5] .

Siinä tapauksessa , että voidaan varmuudella sanoa, että y :n jakaja on -sileä potenssi ja erilaisen valinnan täytyy ratkaista ongelma . ${\näyttötyyli (b-1,N)=N}$ $n$ $B$ $a$
Useimmissa tapauksissa, kun kannattaa siirtyä algoritmin toiseen vaiheeseen, mikä lisää merkittävästi tuloksen todennäköisyyttä, vaikka se ei takaa sitä. ${\näyttötyyli (b-1,N)=1}$

Esimerkki

Valitaan sitten , otetaan ja lasketaan nyt ja lopuksi . $N=10001$ $B=10$ $M(B)=2^{3}\cdot 3^{2}\cdot 5\cdot 7=2520$ $a=2$ $b=a^{M(B)}\mod N=2^{2520}\mod 10001=3578$ $(b-1,N)=(3578-1,10001)=73$

Muistiinpanot

Suurilla luvuilla luku voi osoittautua erittäin suureksi, arvoltaan verrattavissa olevaan arvoon , jolloin voi olla suositeltavaa kertoa suunnilleen sama arvo ja laskea sekvenssi $B$ $M(B)$ ${\näyttötyyli B!}$ $M(B)$ ${\displaystyle M(B)=\prod _{i}M_{i))$

a_{1}=a^{M_{1}}\mod N;

a_{k+1}=a_{k}^{M_{k+1}}\mod N

Toinen vaihe

Ensinnäkin sinun on vahvistettava rajat , yleensä [5] [4] . $B_{1}=B,B_{2}\gg B$ $B_{2}\leq B^{2}$
Algoritmin toinen vaihe löytää jakajia , niin että , missä on potenssitasoinen ja alkuluku sellainen, että . $N$ $p-1=q\cdot A$ $A$ $B$ $q$ ${\displaystyle B_{1}<q<B_{2))$

Seuraavaa varten tarvitsemme alkulukuvektorin välillä - , josta on helppo saada erovektori näiden alkulukujen välillä , lisäksi , ovat suhteellisen pieniä lukuja, ja , missä on äärellinen joukko [4] . Algoritmin toiminnan nopeuttamiseksi on hyödyllistä laskea etukäteen kaikki [4] ja käyttää valmiita arvoja. $q_{i}$ $B_1$ $B_{2}$ ${\displaystyle D=(D_{1},D_{2},...),D_{i}=q_{i+1}-q_{i))$ $D_{i}$ $D_{i}\in \Delta$ $\Delta$ $b^{\delta _{i)),\forall \delta _{i}\in \Delta$
Nyt on tarpeen laskea peräkkäin , jossa , laskettu ensimmäisessä vaiheessa, laskemalla jokaisessa vaiheessa . Heti kun , voit lopettaa tietojenkäsittelyn. $c_{0}=b_{1}\mod N,c_{i}=c_{i-1}^{\delta _{i))\mod N$ $b_{1}=a^{M(B_{1})}\mod N$ $G=(c_{i}-1,N)$ $G\neq 1$

Lähentymisehdot

Otetaan pienin jakaja , maksimi ylittää kaikki potenssit jakamalla [4] . $s$ $N$ $q^{t}=max(q_{i}^{t_{i)))$ $q_{i}^{t_{i))$ $p-1$
- Jos , niin jakaja löytyy algoritmin ensimmäisestä vaiheesta
[4] . ${\displaystyle q^{t}<B_{1))$
Muussa tapauksessa algoritmin onnistumisen kannalta on välttämätöntä, että , ja kaikki muut muodon jakajat ovat pienempiä kuin [4] . ${\displaystyle q^{t}<B_{2))$ $p-1$ $q^{r}$ $B_1$

Muutokset ja parannukset

Myöhemmin Pollard itse ilmaisi mielipiteensä mahdollisuudesta nopeuttaa algoritmia nopean Fourier-muunnoksen avulla [4] toisessa vaiheessa, mutta hän ei antanut todellisia tapoja tehdä tämä [6] .
Vielä myöhemmin, vuonna 1990, matemaatikot Peter Montgomery ja Robert Silverman tekivät sen [6] . Kirjoittajat onnistuivat lisäämään algoritmin toisen vaiheen suoritusnopeutta.

Suorituskyvyn arviointi

Ensimmäisen vaiheen monimutkaisuus on estimoituna , jolloin jäljelle jää vain korkeimman asteen termi, saadaan estimaatti algoritmin ensimmäisestä vaiheesta [4] . $O(B\cdot \ln B\cdot (\ln N)^{2}+(\ln N)^{3})$ $O(B\cdot \ln B\cdot (\ln N)^{2})$
Montgomeryn arvion mukaan toisen asteen monimutkaisuus korkeimpaan kertaluokkaan asti on [1] [4] , jossa alkulukujen määrä on pienempi kuin . Chebyshevin arvio antaa likimääräisen yhtäläisyyden . $O(\pi (B_{2}))$ $\pi(s)$ $s$ $\pi (s)\approx {\frac {s}{\ln s))$

Records

Tällä hetkellä (10.10.2016) kolme suurinta P-1-menetelmällä löydettyä alkujakajaa koostuvat 66, 64 ja 59 desimaalinumerosta [7] .

Numeroiden määrä	s	Numeronjakaja	Kenen löytämä	Kun löytyy	B	B2
66	672038771836751227845696565342450315062141551559473564642434674541 = 2 2 3 5 7 17 23 31 163 401 617 4271 13681 22877 43397 203459 1396027 6995393 13456591 211040281	$960^{119}-1$	T. Nogara	29.06.2006	$10^{8}$	$10^{{10}}$
64	1939611922516629203444058938928521328695726603873690611596368359 = 2 3 11 1187 9233729 13761367 43294577 51593573 100760321 379192511 2282985164293 + 1	$10^{243}-4\cdot 10^{121}-1$	M. Tervuren	13.09.2012	$10^{{9}}$	$10^{13}$
59	12798830540286697738097001413455268308836003073182603569933 = 2 2 17 59 107 113 20414117 223034797 269477639 439758239 481458247 1015660517 + 1	$8069000260399979023963141^{17}-1$	A. Krupp	30.06.2011	$10^{9}$	$10^{{10}}$

Sovellukset

GMP-ECM [8] - paketti sisältää -menetelmän tehokkaan soveltamisen . $p-1$
Viralliset GIMPS -asiakkaat Prime95 ja Mprime käyttävät menetelmää ehdokkaiden karsimiseen.

Katso myös

Muistiinpanot

↑ 1 2 3 4 5 6 7 Pollard, 1974 .
↑ 1 2 Karaarslan E. Primaliteettitestaustekniikat ja alkulukujen merkitys suojausprotokollissa // ICMCA'2000 : Kolmannen kansainvälisen symposiumin julkaisut Mathematical & Computational Applications - Konya : 2000. - S. 280-287.
↑ Vasilenko, 2003 , s. 60.
↑ 1 2 3 4 5 6 7 8 9 10 11 Ishmukhametov, 2011 , s. 53-55.
↑ 1 2 3 Cohen, 2000 , s. 439.
↑ 1 2 Montgomery, Silverman, 1990 .
↑ Zimmerman, Paul . Pollardin p-1 - menetelmällä löydetyt ennätystekijät . Les pages des personnels du LORIA et du Centre Inria NGE. Haettu 10. lokakuuta 2016. Arkistoitu alkuperäisestä 11. lokakuuta 2016.
↑ InriaForge: GMP-ECM (Elliptic Curve Method): Project Home . Haettu 15. marraskuuta 2012. Arkistoitu alkuperäisestä 21. heinäkuuta 2012. (määrätön)

Kirjallisuus

Pollard J. M. Lauseet faktorointi- ja primaliteettitestauksesta (englanniksi) // Mathematical Proceedings of the Cambridge Philosophical Society / B. J. Green - Cambridge University Press , 1974. - Voi. 76, Iss. 3. - P. 521-528. - 8 p. — ISSN 0305-0041 ; 1469-8064 - doi:10.1017/S0305004100049252
Cohen A. Laskennallisen algebrallisen lukuteorian kurssi - 4. painos - Berlin , Heidelberg , New York : Springer , 2000. - 550 s. - ( Matematiikan tutkinnon tekstit ) - ISBN 978-3-540-55640-4 - ISSN 0072-5285 ; 2197-5612
Vasilenko O. N. Lukuteoreettiset algoritmit kryptografiassa - M .: MTsNMO , 2003. - 328 s. — ISBN 978-5-94057-103-2
Ishmukhametov Sh. T. Luonnollisten lukujen faktorointimenetelmät : oppikirja - Kazan : Kazan University , 2011. - P. 53-55. - 190 s.
Montgomery P. , Silverman R.D. FFT-laajennus P-1-faktorointialgoritmiin // Math . Comp. - AMS , 1990. - Voi. 54, Iss. 190. - s. 839-854. — ISSN 0025-5718 ; 1088-6842 - doi:10.1090/S0025-5718-1990-1011444-3