P−1 Metoda Pollard

Versiunea actuală a paginii nu a fost încă examinată de colaboratori experimentați și poate diferi semnificativ de versiunea revizuită pe 4 aprilie 2019; verificările necesită 2 modificări .

$p-1$ Metoda lui Pollard este una dintre metodele de factorizare a întregilor .

Publicat pentru prima dată de matematicianul britanic John Pollard în 1974 [1] . Apariția acestui algoritm a condus [2] la o schimbare a conceptului de număr prim puternic folosit în criptografie , vorbind vag, un număr prim pentru care are divizori suficient de mari. În criptosistemele moderne, ei încearcă [2] să folosească numere prime puternice, deoarece acest lucru crește securitatea algoritmilor utilizați și a sistemelor în ansamblu. $p-1$

Definiții și fundal matematic

Un număr se numește - power- smooth [3] dacă toți divizorii săi primi, în puterile în care sunt incluși în extinderea acestui număr , satisfac . Conform micii teoreme a lui Fermat , pentru orice număr prim și pentru orice număr întreg astfel încât și sunt coprim , sau, care este echivalent în acest caz, nu împarte , avem: $B$ ${\displaystyle p^{\nu ))$ $p^{\nu }\leq B$ $p$ $A$ $A$ $p$ $p$ $A$

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

, mai mult .

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

Algoritmul original (1974)

John Pollard a publicat pentru prima dată algoritmul descris mai jos în articolul său din 1974 „Theorems of Factorization and Primality Testing” în Proceedings of the Cambridge Philosophical Society [ 1] . Articolul este dedicat estimării teoretice a complexității factorizării unui număr mare sau, în cazul unui număr prim , verificării lui pentru simplitate. Următorul algoritm a fost o consecință și o ilustrare a calculelor teoretice ale lui Pollard. $N$ $N$

Prima etapă

Sarcina este să-și găsească propriul divizor al unui număr diferit de unul. În primul rând, trebuie să alegeți două numere astfel încât . $N$ $B,M,$ $1<B<M<{\sqrt {N}),M<B^{2}$
Să calculăm acum numărul , unde toate numerele prime sunt mai mici decât . Aici este permisă o oarecare libertate în alegerea lui , dar se știe sigur că pentru mic , ar trebui să fie mai mare decât unu [1] . $M(B)=\prod _{k=1}^{m}p_{k}^{c_{k))$ $p_{k}$ $B$ $c_{k}$ $p_{k}$ $c_{k}$
Alegem un întreg mic și calculăm $a>1$

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

q=(b-1,N)

dacă am găsit divizorul , în caz contrar trecem la a doua etapă.

q\neq 1

N

Etapa a doua

La acest pas, este necesar să se calculeze secvența

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

unde este un prim, , sperând că la un pas vom ajunge

m

B<m<M

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

Cel mai simplu mod [1] de a face acest lucru este de a calcula pentru fiecare număr impar prin înmulțirea cu , luând la intervale regulate. Dacă se găsește divizorul. Dacă , atunci este necesar să studiem această zonă mai precis. $b^m$ $m$ $b^{2}$ $G_{i}=(b^{i},N)$ $1<G_{i}<N$ $G_{i}=N,G_{i-1}=1$

Notă

Folosind această metodă, vom putea găsi numai astfel de divizori primi ai numărului pentru care [1] este adevărată : $p$ $N$

p-1=A

sau , unde este -power-smooth și este prim astfel încât [1] .

p-1=Aq

A

B

q

B<q<M

Versiunea modernă

Această versiune revizuită a algoritmului, în comparație cu originalul, folosește conceptele de uniformitate a legii puterii și se concentrează pe aplicații practice. Prima etapă a suferit modificări semnificative, în timp ce a doua a rămas practic neschimbată, din nou, din punct de vedere teoretic, nu s-a adăugat nimic semnificativ față de versiunea anterioară. Algoritmul de mai jos este cel care se referă atunci când oamenii vorbesc despre „metoda Pollard” [4] [5] .

Prima etapă

Fie -smooth puterea, și este necesar să se găsească divizorul numărului . În primul rând, se calculează numărul în care produsul se realizează peste toate numerele prime în puteri maxime $N$ $B$ $N$ $M(B)=\prod _{i}p_{i}^{k_{i)}$ $p_{i}$ $k_{i}:p_{i}^{k_{i}}<B$
Apoi divizorul dorit [4] , unde . $q=(b-1,N)$ $b=a^{M(B)}\mod N$

Există două cazuri posibile în care algoritmul de mai sus va eșua [5] .

În cazul în care se poate spune cu siguranță că y are un divizor care este puterea netedă și o alegere diferită trebuie să rezolve problema . $(b-1,N)=N$ $n$ $B$ $A$
Într-un caz mai frecvent, când merită să treceți la a doua etapă a algoritmului, ceea ce crește semnificativ probabilitatea unui rezultat, deși nu o garantează. $(b-1,N)=1$

Exemplu

Să alegem , atunci , să luăm și să calculăm acum , și în sfârșit . $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$

Note

Pentru numere mari , numărul se poate dovedi a fi foarte mare, comparabil ca valoare cu , în astfel de cazuri poate fi recomandabil să factorizați aproximativ aceeași valoare și să calculați succesiunea $B$ $M(B)$ $B!$ $M(B)$ $M(B)=\prod _{i}M_{i)$

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

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

Etapa a doua

În primul rând, trebuie să fixați limitele , de obicei [5] [4] . $B_{1}=B,B_{2}\gg B$ $B_{2}\leq B^{2}$
A doua etapă a algoritmului găsește divizori , astfel încât , unde este o putere netedă și prim astfel încât . $N$ $p-1=q\cdot A$ $A$ $B$ $q$ $B_{1}<q<B_{2}$

Pentru cele ce urmează, vom avea nevoie de un vector de numere prime de la până la , din care să se obțină ușor un vector de diferențe între aceste numere prime , de altfel , sunt numere relativ mici, iar , unde este o mulțime finită [4] . Pentru a accelera funcționarea algoritmului, este util să precalculați toate [4] și să folosiți valori gata făcute. $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$
Acum este necesar să se calculeze secvenţial , unde , calculat în prima etapă, numărând la fiecare pas . De îndată ce , puteți opri calcularea. $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$

Condiții de convergență

Fie cel mai mic divizor , maximul să fie luat peste toate puterile împărțind [4] . $p$ $N$ $q^{t}=max(q_{i}^{t_{i)))$ $q_{i}^{t_{i)}$ $p-1$
- Dacă , atunci divizorul va fi găsit la prima etapă a algoritmului
[4] . $q^{t}<B_{1)$
În caz contrar, pentru succesul algoritmului, este necesar ca , și toți ceilalți divizori ai formei să fie mai mici decât [4] . $q^{t}<B_{2}$ $p-1$ $q^{r)$ $B_1$

Modificări și îmbunătățiri

Ulterior, Pollard însuși și-a exprimat o părere despre posibilitatea de a accelera algoritmul folosind transformata Fourier rapidă [4] în a doua etapă, dar nu a oferit modalități reale de a face acest lucru [6] .
Chiar mai târziu, în 1990, matematicienii Peter Montgomery și Robert Silverman au făcut- o [6] . Autorii au reușit să obțină o creștere a vitezei de execuție a celei de-a doua etape a algoritmului.

Evaluarea performanței

Complexitatea primei etape este estimată ca , lăsând doar termenul de ordinul cel mai înalt, se obține estimarea primei etape a algoritmului [4] . $O(B\cdot \ln B\cdot (\ln N)^{2}+(\ln N)^{3})$ $O(B\cdot \ln B\cdot (\ln N)^{2})$
Conform estimării lui Montgomery, complexitatea celei de-a doua etape, până la termeni de ordinul cel mai înalt, este [1] [4] , unde numărul de numere prime este mai mic decât . Estimarea lui Cebyshev oferă o egalitate aproximativă . $O(\pi (B_{2}))$ $\pi(s)$ $s$ $\pi (s)\aprox {\frac {s}{\ln s)}$

Înregistrări

În acest moment (10.10.2016), cei mai mari trei divizori primi găsiți prin metoda P-1 constau din 66, 64 și 59 de cifre zecimale [7] .

Numărul de cifre	p	Divizor de număr	Găsit de cine	Când a fost găsit	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}}$

Aplicații

GMP-ECM [8] - pachetul include aplicarea eficientă a metodei -. $p-1$
Prime95 și MPrime, clienți oficiali GIMPS , folosesc o metodă pentru a elimina candidații.

Vezi și

Note

↑ 1 2 3 4 5 6 7 Pollard, 1974 .
↑ 1 2 Karaarslan E. Primality Testing Techniques and The Importance of Prime Numbers in Security Protocols // ICMCA'2000 : Proceedings of the Third International Symposium Mathematical & Computational Applications - Konya : 2000. - P. 280-287.
↑ Vasilenko, 2003 , p. 60.
↑ 1 2 3 4 5 6 7 8 9 10 11 Ișmukhametov, 2011 , p. 53-55.
↑ 1 2 3 Cohen, 2000 , pp. 439.
↑ 1 2 Montgomery, Silverman, 1990 .
↑ Zimmerman, Paul . Factori de înregistrare găsiți prin metoda p-1 a lui Pollard . Les pages des personnels du LORIA și du Centre Inria NGE. Consultat la 10 octombrie 2016. Arhivat din original pe 11 octombrie 2016.
↑ InriaForge: GMP-ECM (Eliptic Curve Method): Project Home . Consultat la 15 noiembrie 2012. Arhivat din original la 21 iulie 2012. (nedefinit)

Literatură

Pollard J. M. Theorems on factorization and primality testing (engleză) // Mathematical Proceedings of the Cambridge Philosophical Society / B. J. Green - Cambridge University Press , 1974. - Vol. 76, Iss. 3. - P. 521-528. - 8p. — ISSN 0305-0041 ; 1469-8064 - doi:10.1017/S0305004100049252
Cohen A. A Course in Computational Algebric Number Theory - Ediția a 4-a tipărită - Berlin , Heidelberg , New York : Springer , 2000. - 550 p. - ( Texte de absolvent în matematică ) - ISBN 978-3-540-55640-4 - ISSN 0072-5285 ; 2197-5612
Vasilenko O. N. Algoritmi teoretici numeric în criptografie - M. : MTsNMO , 2003. - 328 p. — ISBN 978-5-94057-103-2
Ishmukhametov Sh. T. Metode de factorizare pentru numere naturale : manual - Kazan : Universitatea din Kazan , 2011. - P. 53-55. — 190 p.
Montgomery P. , Silverman R. D. O extensie FFT a algoritmului de factoring P-1 // Math . Comp. - AMS , 1990. - Vol. 54, Iss. 190. - P. 839-854. — ISSN 0025-5718 ; 1088-6842 - doi:10.1090/S0025-5718-1990-1011444-3