P−1 Pollardmetoden

Den aktuella versionen av sidan har ännu inte granskats av erfarna bidragsgivare och kan skilja sig väsentligt från versionen som granskades den 4 april 2019; kontroller kräver 2 redigeringar .

$p-1$ Pollards metod är en av heltalsfaktoriseringsmetoderna .

Först publicerad av den brittiske matematikern John Pollard 1974 [ 1] . Det var uppkomsten av denna algoritm som ledde [2] till en förändring av konceptet med ett starkt primtal som används i kryptografi , löst sagt, ett primtal för vilket det har tillräckligt stora delare. I moderna kryptosystem försöker man [2] använda starka primtal, eftersom detta ökar säkerheten för de algoritmer som används och systemen som helhet. $p-1$

Definitioner och matematisk bakgrund

Ett tal kallas - power- smooth [3] om alla dess primtalsdelare, i de potenser som de ingår i i expansionen av detta tal , uppfyller . Enligt Fermats lilla teorem , för vilket primtal som helst och för vilket heltal som helst så att och är coprime , eller, vilket är ekvivalent i detta fall, inte delar , har vi: $B$ ${\displaystyle p^{\nu))$ $p^{\nu }\leq B$ $sid$ $a$ $a$ $sid$ $sid$ $a$

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

dessutom .

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

Den ursprungliga algoritmen (1974)

John Pollard publicerade först algoritmen som beskrivs nedan i sin artikel från 1974 "Theorems of Factorization and Primality Testing" i Proceedings of the Cambridge Philosophical Society [ 1] . Artikeln ägnas åt den teoretiska uppskattningen av komplexiteten i att faktorisera ett stort tal eller, i fallet med ett primtal , att kontrollera det för enkelhetens skull. Följande algoritm var en konsekvens och illustration av Pollards teoretiska beräkningar. $N$ $N$

Första steget

Uppgiften är att hitta sin egen divisor för ett annat tal än ett. Först och främst måste du välja två siffror så att . $N$ $B,M,$ $1<B<M<{\sqrt {N)),M<B^{2}$
Låt oss nu beräkna talet , där är alla primtal mindre än . Här tillåts viss frihet i valet av , men det är säkert känt att för små , bör vara större än en [1] . $M(B)=\prod _{k=1}^{m}p_{k}^{c_{k}}$ $p_{k}$ $B$ $c_{k}$ $p_{k}$ $c_{k}$
Vi väljer ett litet heltal och räknar $a>1$

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

q=(b-1,N)

om vi har hittat divisorn , annars går vi till det andra steget.

q\neq 1

N

Andra steget

I detta steg är det nödvändigt att beräkna sekvensen

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

var är en prime, , hoppas att vi vid något steg får

m

B<m<M

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

Det enklaste sättet [1] att göra detta är att beräkna för varje udda tal genom att multiplicera med , ta med jämna mellanrum. Om divisorn hittas. Om , då är det nödvändigt att studera detta område mer exakt. $b^m$ $m$ $b^{2}$ $G_{i}=(b^{i},N)$ $1<G_{i}<N$ $G_{i}=N,G_{i-1}=1$

Notera

Med den här metoden kommer vi bara att kunna hitta sådana primtalsdelare för talet för vilka [1] är sant : $sid$ $N$

p-1=A

eller , där är -power-smooth och är prime så att [1] .

p-1=Aq

A

B

q

B<q<M

Modern version

Denna reviderade version av algoritmen jämfört med originalet använder begreppen maktlagsjämnhet och är fokuserad på praktiska tillämpningar. Det första steget genomgick betydande förändringar, medan det andra förblev praktiskt taget oförändrat, återigen, ur en teoretisk synvinkel, lades inget väsentligt till jämfört med den tidigare versionen. Det är algoritmen nedan som menas när man talar om "Pollardmetoden" [4] [5] .

Första steget

Låt -utjämna makt, och det krävs för att hitta divisorn för talet . Först och främst beräknas antalet där produkten utförs över alla primtal i maximala potenser $N$ $B$ $N$ $M(B)=\prod _{i}p_{i}^{k_{i))$ $pi}$ $k_{i}:p_{i}^{k_{i}}<B$
Därefter önskad divisor [4] , där . $q=(b-1,N)$ $b=a^{M(B)}\mod N$

Det finns två möjliga fall där ovanstående algoritm kommer att misslyckas [5] .

I det fall där man med säkerhet kan säga att y har en divisor som är -slät makt och ett annat val måste lösa problemet . $(b-1,N)=N$ $n$ $B$ $a$
I ett mer frekvent fall, när det är värt att flytta till det andra steget av algoritmen, vilket avsevärt ökar sannolikheten för ett resultat, även om det inte garanterar det. $(b-1,N)=1$

Exempel

Låt oss välja , då , låt oss ta och beräkna nu , och till sist . $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$

Anteckningar

För stora tal kan antalet visa sig vara mycket stort, jämförbart i värde med , i sådana fall kan det vara tillrådligt att faktorisera ungefär samma värde och beräkna sekvensen $B$ $M(B)$ $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

Andra steget

Först och främst måste du fixa gränserna , vanligtvis [5] [4] . $B_{1}=B,B_{2}\gg B$ $B_{2}\leq B^{2}$
Det andra steget av algoritmen hittar divisorer , så att , där är en effekt- jämn och primtal sådan att . $N$ $p-1=q\cdot A$ $A$ $B$ $q$ ${\displaystyle B_{1}<q<B_{2))$

För det som följer kommer vi att behöva en vektor av primtal från till , från vilken det är lätt att få en vektor av skillnader mellan dessa primtal , dessutom är relativt små tal, och , där är en ändlig mängd [4] . För att påskynda driften av algoritmen är det användbart att förberäkna alla [4] och använda färdiga värden. $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$
Nu är det nödvändigt att sekventiellt beräkna , där , beräknas i det första steget, räknar vid varje steg . Så fort kan du sluta använda datorn. $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$

Konvergensvillkor

Låt den minsta divisorn , den maximala ta över alla makter som delar [4] . $sid$ $N$ $q^{t}=max(q_{i}^{t_{i)))$ $q_{i}^{t_{i))$ $p-1$
- Om , kommer divisorn att hittas i det första steget av algoritmen
[4] . ${\displaystyle q^{t}<B_{1))$
Annars, för att algoritmen ska lyckas, är det nödvändigt att , och alla andra divisorer i formen är mindre än [4] . ${\displaystyle q^{t}<B_{2))$ $p-1$ $q^{r}$ $B_1$

Ändringar och förbättringar

Senare uttryckte Pollard själv en åsikt om möjligheten att påskynda algoritmen med den snabba Fouriertransformen [4] i det andra steget, men han gav inga riktiga sätt att göra detta [6] .
Ännu senare, 1990, gjorde matematikerna Peter Montgomery och Robert Silverman det [6] . Författarna lyckades uppnå en ökning av exekveringshastigheten för det andra steget av algoritmen.

Prestationsbedömning

Komplexiteten för det första steget uppskattas som , lämnar endast termen av högsta ordningen, vi får uppskattningen av det första steget av algoritmen [4] . $O(B\cdot \ln B\cdot (\ln N)^{2}+(\ln N)^{3})$ $O(B\cdot \ln B\cdot (\ln N)^{2})$
Enligt Montgomerys uppskattning är komplexiteten i det andra stadiet, upp till termer av högsta ordningen, [1] [4] , där är antalet primtal mindre än . Chebyshevs uppskattning ger en ungefärlig likhet . $O(\pi (B_{2}))$ $\pi(s)$ $s$ $\pi (s)\approx {\frac {s}{\ln s))$

Records

För tillfället (10/10/2016) består de tre största primtalsdivisorerna som hittats med P-1-metoden av 66, 64 och 59 decimalsiffror [7] .

Antal siffror	sid	Nummerdelare	Hittade av vem	När hittas	B	B2
66	672038771836751227845696565342450315062141551559473564642434674541 = 2 2 3 5 7 17 23 31 163 401 617 4271 13681 22877 43397 203459 1396027 6995393 13456591 217104028	$960^{119}-1$	T. Nogara	2006-06-29	$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	2012-09-13	$10^{{9}}$	$10^{13}$
59	12798830540286697738097001413455268308836003073182603569933 = 2 2 17 59 107 113 20414117 223034797 269477639 439758239 481458247 1015660517 + 1	$8069000260399979023963141^{17}-1$	A. Krupp	2011-06-30	$10^{9}$	$10^{{10}}$

Applikationer

GMP-ECM [8] - paketet inkluderar effektiv tillämpning av -metoden. $p-1$
Prime95 och Mprime, officiella GIMPS- klienter , använder en metod för att sålla bort kandidater.

Se även

Anteckningar

↑ 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 , sid. 60.
↑ 1 2 3 4 5 6 7 8 9 10 11 Ishmukhametov, 2011 , sid. 53-55.
↑ 1 2 3 Cohen, 2000 , s. 439.
↑ 1 2 Montgomery, Silverman, 1990 .
↑ Zimmerman, Paul . Rekordfaktorer hittade av Pollards p-1-metod . Les pages des personnels du LORIA et du Centre Inria NGE. Hämtad 10 oktober 2016. Arkiverad från originalet 11 oktober 2016.
↑ InriaForge: GMP-ECM (Elliptic Curve Method): Project Home . Hämtad 15 november 2012. Arkiverad från originalet 21 juli 2012. (obestämd)

Litteratur

Pollard J. M. Theorems on factorization and primality testing (engelska) // 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 Algebraic Number Theory - 4th Print Edition - Berlin , Heidelberg , New York : Springer , 2000. - 550 sid. - ( Graduate Texts in Mathematics ) - ISBN 978-3-540-55640-4 - ISSN 0072-5285 ; 2197-5612
Vasilenko O. N. Talteoretiska algoritmer i kryptografi - M. : MTsNMO , 2003. - 328 s. — ISBN 978-5-94057-103-2
Ishmukhametov Sh. T. Faktoriseringsmetoder för naturliga tal : lärobok - Kazan : Kazan University , 2011. - P. 53-55. — 190 sid.
Montgomery P. , Silverman R. D. En FFT-förlängning av P-1 factoring-algoritmen // Math . Comp. - AMS , 1990. - Vol. 54, Iss. 190. - P. 839-854. — ISSN 0025-5718 ; 1088-6842 - doi:10.1090/S0025-5718-1990-1011444-3