Pocklington kriterium

Pocklington -testet är ett deterministiskt primattest som utvecklats av Henry Pocklington och Derrick Henry Lehmer . Pocklington-testet låter dig avgöra om ett givet tal är primtal .

Pocklingtons teorem

Låt där q är ett primtal, . Om det finns ett heltal så att gcd , så har varje primtal divisor av talet formen för någon naturlig . $n=q^{k}R+1$ $k\geqslant 1$ $a$ $a^{n-1} \equiv 1 \pmod n$ $(a^{{(n-1)}/q}-1,n)=1$ $sid$ $n$ $p=q^{k}r+1$ $r$

Bevis

Låt vara en primtal divisor av . Sedan följer av satsens villkor att och . Därför erhåller vi att moduloordningen för elementet uppfyller villkoren: , där är något heltal. Låt oss säga att det delar sig . I det här fallet , var är ett heltal. Därför är det omöjligt. Sedan är då delbart med . Antalet måste dock dela sig. Därför, för vissa . Teoremet har bevisats. $sid$ $n$ $a^{n-1}=1{\pmod {p}}$ $a^{(n-1)/q}\neq 1{\pmod {p))$ $m$ $a$ $sid$ $n-1=md$ $d$ $q$ $d$ $(n-1)/q=m(d/q)$ $(d/q)$ $a^{(n-1)/q}=1{\pmod {p))$ $n-1=md=q^{k}R$ $m$ $q^k$ $m$ $p-1$ $p=q^{k}r+1$ $r$

The Pocklington Criterion

Låt vara ett naturligt tal. Låt talet ha en primtalsdelare och . Om det finns ett heltal så att följande två villkor är uppfyllda: $n$ $n-1$ $q$ $q>{\sqrt {n}}-1$ $a$

$a^{n-1} \equiv 1 \pmod n$
tal och coprime, $n$ $a^{(n-1)/q}-1$

då är ett primtal. $n$

Bevis

Låt oss anta att det är ett sammansatt tal. Sedan finns det ett primtal — divisor , och . Observera att därför och är coprime. Därför finns det något heltal så att . Men i det här fallet (på grund av villkor 1)). Men på detta sätt erhålls en motsägelse till villkor 2). Därför är det ett primtal. $n$ $sid$ $n$ $p<{\sqrt {n))$ $q>p-1$ $q$ $p-1$ $u$ $uq\equiv 1{\pmod {p-1}}$ $a^{(n-1)/q}\equiv a^{uq(n-1)/q}=a^{u(n-1)}\equiv 1{\pmod {p))$ $n$

Omfattning

Till skillnad från Salridges teorem kräver Pocklingtons kriterium inte kunskap om den fullständiga faktoriseringen av ett tal till primtalsfaktorer och tillåter en att begränsa sig till en partiell faktorisering av ett tal . Det är lämpligt för att testa för primalitet, förutsatt att det är delbart med ett primtal , och även om det kan hittas och bevisas vara primtal. $n-1$ $n-1$ $n-1$ $q>{\sqrt {n}}-1$ $q$

Det är också värt att notera att detta kriterium endast är probabilistiskt i den meningen att ett slumpmässigt valt nummer antingen kan uppfylla GCD- villkoret eller inte. Om är ett udda primtal, , gcd , då för ett slumpmässigt valt tal är denna sannolikhet . Men så snart en sådan hittas , bevisar kriteriet att det är ett primtal. Till skillnad från probabilistiska tester (som till exempel Miller-Rabin- testet, Solovay-Strassen-testet etc.) är slutsatsen av Pocklington-testet ganska bestämd. $a$ $(a^{(n-1)/q}-1,n)=1$ $n=RF+1$ $F>{\sqrt {n}}-1$ $F=q_{1}^{\alpha _{1}}q_{2}^{\alpha _{2}}...q_{k}^{\alpha _{k)),$ $(R,F)=1$ $1<a<n$ $\prod _{i=1}^{k}(1-{\frac {1}{q_{i))})$ $a$ $n$

Den största svårigheten förknippad med användningen av detta kriterium kan vara behovet av att hitta en primtalsdelare för talet , som i praktiken kan reduceras till full faktorisering. Att hitta rätt är en mindre utmaning. Enligt Neil Koblitz är värdet ofta lämpligt att testa med Pocklington-testet. $n-1$ $a$ $a=2$

Uppskattning av beräkningskomplexitet

Även om Pocklington-testet bara bevisar att ett tal är primtal med rätt val av , är det möjligt att uppskatta dess algoritmiska komplexitet under antagandet att vi har valt det korrekt. Testets beräkningskomplexitet kommer att vara summan av komplexiteten i att faktorisera ett tal och ett tal . När man använder faktoriseringsalgoritmer med subexponentiell komplexitet kan det begränsas ovanifrån av värdet som anges i L-notation , där och beror på valet av faktoriseringsalgoritmen. $n$ $a$ $n$ $a^{(n-1)/q}-1$ $L_{a^{n}}[\alpha ,c]$ $\alfa$ $c$

Exempel

Låt oss bevisa att talet är primtal. Låt oss hitta en enkel divisor av talet , det vill säga 30. Det är , och . Siffran a=2 uppfyller båda kriterierna: $n=31$ $n-1$ $q=5$ $5>{\sqrt {31}}-1$

$2^{30}\equiv 1{\pmod {31}}$
tal och coprime, $31$ $2^{(31-1)/5}-1$

Därför är talet 31 primtal enligt Pocklington-kriteriet

Specialfall

Ett specialfall av Pocklington-kriteriet är Proth-satsen , som är ett primalitetstest för Proth-tal , där är udda och . Det ser ut så här: $n=2^{k}R+1$ $R$ $R<2^{k}$

Låt , var , , och inte dela . Då är ett primtal om och endast om villkoret är uppfyllt . $n=2^{k}R+1$ $R<2^{k}$ $Z<2^{k}+1$ $Z$ $R$ $n$ $Z^{(n-1)/2}=-1{\pmod {n))$

Se även

Litteratur

N. Koblitz, Kurs i talteori och kryptografi ISBN 5-94057-103-4
Yu. V. Romanets, PA Timofeev, VF Shangin, Informationssäkerhet i datorsystem och nätverk. 2:a upplagan, ISBN 5-256-01518-4
A. V. Cheremushkin, föreläsningar om aritmetiska algoritmer i kryptografi ISBN 5-94057-060-7