Pollards p − 1 algoritm

Pollards p − 1 algoritm är en talteoretisk heltalsfaktoriseringsalgoritm , uppfann av John Pollard 1974. Det är en specialalgoritm, vilket betyder att den endast är lämplig för heltal med specifika typer av faktorer; det är det enklaste exemplet på en algebraisk gruppfaktoriseringsalgoritm .

Faktorerna som den hittar är sådana för vilka talet som föregår faktorn, p − 1, är powersmooth ; den väsentliga observationen är att genom att arbeta i den multiplikativa gruppen modulo ett sammansatt tal N , arbetar vi också i de multiplikativa grupperna modulo alla N :s faktorer.

Förekomsten av denna algoritm leder till begreppet säkra primtal , som är primtal för vilka p − 1 är två gånger ett Sophie Germain primtal q och därmed minimalt jämnt. Dessa primtal tolkas ibland som "säkra för kryptografiska ändamål", men de kan vara osäkra — i nuvarande rekommendationer för kryptografiska starka primtal ( t.ex. ANSI X9.31), är det nödvändigt men inte tillräckligt att p − 1 har minst ett stort primtal. faktor. De flesta tillräckligt stora primtal är starka; om ett primtal som används för kryptografiska ändamål visar sig vara icke-starkt, är det mycket mer sannolikt att det beror på illvilja än genom en slumpmässig slumpgenerering . Denna terminologi anses vara föråldrad av kryptografiindustrin: ECM gör säkra primtal lika lätta att faktorisera som icke-säkra primtal, så storleken är den viktiga faktorn.

Baskoncept

Låt n vara ett sammansatt heltal med primtal p . Genom Fermats lilla teorem vet vi att för alla heltal ett coprime till p och för alla positiva heltal K :

$a^{K(p-1)}\equiv 1{\pmod {p}}$

Om ett tal x är kongruent med 1 modulo en faktor n , så kommer gcd ( x − 1, n ) att vara delbart med den faktorn.

Tanken är att göra exponenten till en stor multipel av p − 1 genom att göra den till ett tal med väldigt många primtalsfaktorer; generellt sett tar vi produkten av alla primpotenser mindre än någon gräns B . Börja med ett slumpmässigt x och ersätt det upprepade gånger med $x^{w}{\bmod {n}}$ när w löper genom dessa primpotenser. Kontrollera vid varje steg, eller en gång i slutet om du föredrar det, om gcd( x − 1, n ) inte är lika med 1.

Flera faktorer

Det är möjligt att för alla primtalsfaktorerna p av n är p − 1 delbart med små primtal, då Pollard p − 1- algoritmen ger dig n igen.

Algoritm och körtid

Den grundläggande algoritmen kan skrivas på följande sätt:

Ingångar : n : ett sammansatt antal

Utdata : en icke-trivial faktor på n eller fel

1. välj en jämnhetsgräns B
2. definiera $M=\prod _{{\text{primtal}}~q\leq B}q^{\lfloor \log _{q}{B }\rfloor }$ (obs: att explicit utvärdera M kanske inte är nödvändigt)
3. välj slumpmässigt en coprime till n (observera: vi kan faktiskt fixa a , t.ex. om n är udda, då kan vi alltid välja a = 2, slumpmässigt urval här är inte nödvändigt)
4. beräkna g = gcd( a ^M − 1, n ) (notera: exponentiering kan göras modulo n )
5. om 1 < g < n , returnera g
6. om g = 1 välj sedan ett större B och gå till steg 2 eller returnera fel
7. om g = n välj sedan ett mindre B och gå till steg 2 eller returnera fel

Om g = 1 i steg 6, indikerar detta att det inte finns några primtalsfaktorer p för vilka p-1 är B -powersmooth. Om g = n i steg 7, indikerar detta vanligtvis att alla faktorer var B -powersmooth, men i sällsynta fall kan det indikera att a hade en liten ordningsmodulo n . Dessutom, när de maximala primtalsfaktorerna för p-1 för varje primtalsfaktor p av n alla är desamma i vissa sällsynta fall, kommer denna algoritm att misslyckas.

Körtiden för denna algoritm är O( B × log B × log ² n ) ; större värden på B gör att det går långsammare, men är mer benägna att producera en faktor.

Exempel

Om vi ​​vill faktorisera talet n = 299.

1. Vi väljer B = 5.
2. Således M = 2 ² × 3 ¹ × 5 ¹ .
3. Vi väljer a = 2.
4. g = gcd( a ^M − 1, n ) = 13.
5. Eftersom 1 < 13 < 299, returnera alltså 13.
6. 299 / 13 = 23 är primtal, så det är helt faktoriserat: 299 = 13 × 23.

Hur väljer man B ?

Eftersom algoritmen är inkrementell kan den bara fortsätta att köra med gränsen ständigt ökande.

Antag att p − 1, där p är den minsta primfaktorn för n , kan modelleras som ett slumpmässigt antal med storlek mindre än √ n . Enligt Dixons sats är sannolikheten att den största faktorn av ett sådant tal är mindre än ( p − 1) ^1/ε ungefär ε ^{− ε} ; så det finns en sannolikhet på cirka 3 ⁻³ = 1/27 att ett B- värde på n ^1/6 ger en faktorisering.

I praktiken är metoden med elliptisk kurva snabbare än Pollard p − 1 metoden när faktorerna överhuvudtaget är stora; att köra p − 1-metoden upp till B = 2 ³² kommer att hitta en fjärdedel av alla 64-bitars faktorer och 1/27 av alla 96-bitars faktorer.

Tvåstegsvariant

En variant av den grundläggande algoritmen används ibland; istället för att kräva att p − 1 har alla sina faktorer mindre än B , kräver vi att den har alla utom en av dess faktorer mindre än någon B ₁ , och den återstående faktorn mindre än någon B ₂ ≫ B ₁ . Efter att ha slutfört det första steget, vilket är samma som den grundläggande algoritmen, istället för att beräkna en ny

$M'=\prod _{{\text{primes }}q\leq B_{2}}q^{\lfloor \log _ {q}B_{2}\rgolv }$

för B ₂ och kontrollera gcd( a ^M' − 1, n ) , beräknar vi

$Q=\prod _{{\text{primtal }}q\in (B_{1},B_{2}]} (H^{q}-1)$

där H = a ^M och kontrollera om gcd( Q , n ) ger en icke-trivial faktor på n . Som tidigare kan exponentieringar göras modulo n .

Låt { q ₁ , q ₂ , …} vara på varandra följande primtal i intervallet ( B ₁ , B ₂ ] och d _n = q _n − q _{n −1} skillnaden mellan på varandra följande primtal. Eftersom typiskt B ₁ > 2 , d _n är jämna tal. Fördelningen av primtal är sådan att d n _alla kommer att vara relativt små. Det föreslås att d _n ≤ ln ² B ₂ . Därför värdena på H ² , H ⁴ , H ⁶ , … ( mod n ) kan lagras i en tabell och H ^{q _n} beräknas från H ^{q _{n −1}} ⋅ H ^{d _n} , vilket sparar behovet av exponentieringar.

Genomföranden

• GMP -ECM -paketet inkluderar en effektiv implementering av p − 1-metoden.
• Prime95 och Mprime , de officiella kunderna till Great Internet Mersenne Prime Search , använder en modifierad version av p-1-algoritmen för att eliminera potentiella kandidater.

Se även

• Williams p + 1 algoritm

•   Pollard, JM (1974). "Teorem om faktorisering och primatitetstestning". Proceedings of the Cambridge Philosophical Society . 76 (3): 521–528. Bibcode : 1974PCPS...76..521P . doi : 10.1017/S0305004100049252 . S2CID 122817056 .
• Montgomery, PL; Silverman, RD (1990). "En FFT-förlängning av P − 1 factoring-algoritmen" . Beräkningsmatematik . 54 (190): 839–854. Bibcode : 1990MaCom..54..839M . doi : 10.1090/S0025-5718-1990-1011444-3 .
•   Samuel S. Wagstaff, Jr. (2013). Glädjen med att factoring . Providence, RI: American Mathematical Society. s. 138–141. ISBN 978-1-4704-1048-3 .