Pocklingtons primathetstest

Inom matematiken är Pocklington-Lehmer-primalitetstestet ett primalitetstest utarbetat av Henry Cabourn Pocklington och Derrick Henry Lehmer . Testet använder en partiell faktorisering av $N-1$ för att bevisa att ett heltal $N$ är primtal .

Den producerar ett primalitetscertifikat som kan hittas med mindre ansträngning än Lucas primalitetsteste , vilket kräver fullständig faktorisering av $N-1$ .

Pocklington kriterium

Den grundläggande versionen av testet bygger på Pocklington-satsen (eller Pocklington-kriteriet ) som är formulerad enligt följande:

Låt $N>1$ vara ett heltal, och anta att det finns naturliga tal a och p så att

$a^{N-1}\equiv 1{\pmod {N}}$

 

 

 

 

()

p är primtal, $p\vert N-1$ och $p>{\sqrt {N}}-1$

 

 

 

 

()

$\gcd {(a^{(N-1)/p}-1,N)}=1$

 

 

 

 

()

Då är N primtal.

Notera: Ekvation ( 1 ) är helt enkelt ett Fermat-primalitetstest . Om vi ​​hittar något värde på a , som inte är delbart med N , så att ekvation ( 1 ) är falsk, kan vi omedelbart dra slutsatsen att N inte är primtal. (Detta delbarhetsvillkor anges inte explicit eftersom det antyds av ekvation ( 3 ).) Låt till exempel $N=35$ . Med $a=2$ finner vi att $a^{N-1}\equiv 9{\pmod {N}}$ . Detta är tillräckligt för att bevisa att N inte är primtal.

Bevis

Antag att N inte är primtal. Det betyder att det måste finnas ett primtal q , där $q\leq {\sqrt {N}}$ som delar N . Eftersom ${\displaystyle p>{\sqrt {N}}-1\geq q-1} ,$ p $\displaystyle p>q-1}$ , och eftersom p är primtal, $\gcd {(p,q-1)}=1$ . Det måste alltså finnas ett heltal u , en multiplikativ invers av p modulo q −1 , med egenskapen att $up\equiv 1{\pmod {q-1}}$         () och därför av Fermats lilla teorem $a^{up}\equiv a{\pmod {q}}$         () Detta innebär $1\;\;\equiv a^{N-1}{\pmod {q}}$ , av ( 1 ) sedan $q\vert N$ ${\displaystyle \equiv (a^{N-1})^{u}\equiv a^{u(N-1)}\equiv a^{up((N-1)/p) }\equiv (a^{up})^{(N-1)/p}{\pmod {q}}} , ≡$ a $displaystyle \equiv a^{ (N-1)/p}{\pmod {q}}}$ , av ( 5 ) Detta visar att q delar $\gcd()$ i ( 3 ) , och därför är denna $\gcd()\neq 1$ ; en motsägelse.

Givet N , om p och a kan hittas som uppfyller villkoren för satsen, så är N primtal. Dessutom utgör paret ( p , a ) ett primatitetscertifikat som snabbt kan verifieras för att uppfylla villkoren för satsen, vilket bekräftar N som primtal.

Den största svårigheten är att hitta ett värde på p som uppfyller ( 2 ). För det första är det vanligtvis svårt att hitta en stor primfaktor av ett stort antal. För det andra, för många primtal N existerar inte ett sådant p . Till exempel har $N=17$ inget lämpligt p eftersom $N-1=2^{4}$ , och $p =2<{\sqrt {N}}-1$ , vilket bryter mot ojämlikheten i ( 2 ) ; andra exempel inkluderar $N=19,37,41,61,71,73,$ och $97$ .

Givet p är det inte alls lika svårt att hitta a . Om N är primtal, så kommer enligt Fermats lilla teorem vilket a i intervallet $1\leq a\leq N-1$ att uppfylla ( 1 ) (dock fallen ${ \displaystyle a=1}$ och $a=N-1$ är triviala och kommer inte att uppfylla ( 3 )). Detta a kommer att uppfylla ( 3 ) så länge som ord( a ) inte delar $(N-1)/p$ . Således har ett slumpmässigt valt a i intervallet $2\leq a\leq N-2$ en god chans att fungera. Om a är en generator mod N , är dess ordning $N-1$ och därför fungerar metoden garanterat för detta val.

Generaliserat Pocklington-test

Ovanstående version av versionen av Pocklingtons teorem är ibland omöjlig att tillämpa eftersom vissa primtal $N$ är sådana att det inte finns något primtal $p$ som delar $N-1$ där $p>{\sqrt {N}}-1$ . Följande generaliserade version av Pocklingtons teorem är mer allmänt tillämplig.

Sats: Faktor N − 1 som N − 1 = AB , där A och B är relativt primtal, $A>{\sqrt {N}}$ , primtalsfaktoriseringen av A är känd, men faktoriseringen av B är inte nödvändigtvis känt.

Om det för varje primtal p av A finns ett heltal $a_{p}$ så att

${\displaystyle a_{p}^{N-1}\equiv 1{\pmod {N}}} ,$ och

 

 

 

 

()

$\gcd {(a_{p}^{(N-1)/p}-1,N)}=1$ ,

 

 

 

 

()

då är N primtal.

Bevis

Låt p vara ett primtal som delar A och låt $p^{e}$ vara den maximala potensen av p som delar A . Låt q vara en primfaktor av N . För $a_{p}$ från följdmängden $b\equiv a_{p}^{(N-1)/ p^{e}}{\pmod {q}}$ . Detta betyder $b^{p^{e}}\equiv a_{p}^{N-1}\equiv 1{\pmod {q} }$ och på grund av $\gcd {(a_{p}^{(N-1)/p}-1,N)} =1$ även $b^{p^{e-1}}\equiv a_{p}^{(N- 1)/p}\not \equiv 1{\pmod {q}}$ . Detta betyder att ordningen för $b{\pmod {q}}$ är $p^{e}$ Således, $p^{e}\vert (q-1)$ . Samma observation gäller för varje primtalsfaktor $p^{e}$ av A , vilket innebär $A\vert (q-1)$ . Specifikt betyder detta $q>A\geq {\sqrt {N}}.$ Om N vore sammansatt, skulle det nödvändigtvis ha en primtalsfaktor som är mindre än eller lika med ${\sqrt {N}}$ . Det har visat sig att det inte finns någon sådan faktor, vilket bevisar att N är primtal.

Kommentarer

Pocklington–Lehmer-primalitetstestet följer direkt av denna följd. För att använda denna följd, hitta först tillräckligt många faktorer av N − 1 så att produkten av dessa faktorer överstiger ${\sqrt {N}}$ . Kalla denna produkt A . Låt sedan B = ( N − 1)/ A vara den återstående, opåverkade delen av N − 1 . Det spelar ingen roll om B är primtal. Vi behöver bara verifiera att inget primtal som delar A också delar B , det vill säga att A och B är relativt primtal. Sedan, för varje primtal p av A , hitta en $a_{p}$ som uppfyller villkoren ( 6 ) och ( 7 ) för följden. Om $a_{p}$ s kan hittas, innebär konsekvensen att N är primtal.

Enligt Koblitz fungerar ofta $a_{p}$ = 2.

Exempel

Bestämma huruvida

$N=27457$

är prime.

Sök först efter små primtalsfaktorer för $N-1$ . Det hittar vi snabbt

$N-1=2^{6}\cdot 3\cdot B=192\cdot B$ .

Vi måste avgöra om $A=192$ och $B=(N-1)/A=143$ uppfyller villkoren för konsekvensen. $A^{2}=36864>N$ , så $A>{\sqrt {N}}$ . Därför har vi faktoriserat tillräckligt med $N-1$ för att tillämpa konsekvensen. Vi måste också verifiera att $\gcd {(A,B)}=1$ .

Det spelar ingen roll om B är primtal (det är det faktiskt inte).

Slutligen, för varje primfaktor p av A , använd försök och misstag för att hitta ett a _p som uppfyller ( 6 ) och ( 7 ) .

För $p=2$ , prova $a_{2}=2$ . Att höja $a_{2}$ till denna höga effekt kan göras effektivt med binär exponentiering :

$a_{2}^{N-1}\equiv 2^{27456}\equiv 1{\pmod {27457}}$

$\gcd {(a_{2}^{(N-1)/2}-1,N)} =\gcd {(2^{13728}-1,27457)}=27457$ .

Så $a_{2}=2$ uppfyller ( 6 ) men inte ( 7 ) . Eftersom vi tillåts olika a _p för varje p , prova $a_{2}=5$ istället:

$a_{2}^{N-1}\equiv 5^{27456}\equiv 1{\pmod {27457}}$

$\gcd {(a_{2}^{(N-1)/2}-1,N)} =\gcd {(5^{13728}-1,27457)}=1$ .

Så $a_{2}=5$ uppfyller både ( 6 ) och ( 7 ) .

För $p=3$ , den andra primfaktorn av A , prova $a_{3}=2$ :

$a_{3}^{N-1}\equiv 2^{27456}\equiv 1{\pmod {27457}}$ .

$\gcd {(a_{3}^{(N-1)/3}- 1,N)}=\gcd {(2^{9152}-1,27457)}=1$ .

$a_{3}=2$ uppfyller både ( 6 ) och ( 7 ) .

Detta fullbordar beviset på att $N=27457$ är primtal. Primalitetscertifikatet för $N=27457$ skulle bestå av de två $(p,a_{p})$ paren (2, 5) och (3, 2) .

Vi har valt små siffror för det här exemplet, men i praktiken när vi börjar faktorisera A kan vi få faktorer som i sig är så stora att deras primaalitet inte är uppenbar. Vi kan inte bevisa att N är primtal utan att bevisa att faktorerna för A också är primtal. I ett sådant fall använder vi samma test rekursivt på de stora faktorerna A , tills alla primtal är under en rimlig tröskel.

I vårt exempel kan vi med säkerhet säga att 2 och 3 är primtal, och därmed har vi bevisat vårt resultat. Primalitetscertifikatet är listan över $(p,a_{p})$ par, som snabbt kan kontrolleras i följden.

Om vårt exempel hade inkluderat stora primtalsfaktorer skulle certifikatet vara mer komplicerat. Den skulle först bestå av vår initiala omgång av a _p s som motsvarar "primtal" faktorerna för A ; Därefter, för varje faktor av A där primaliteten var osäker, skulle vi ha mer a _p , och så vidare för faktorer av dessa faktorer tills vi når faktorer som primaaliteten är säker på. Detta kan fortsätta i många lager om den initiala primeringen är stor, men det viktiga är att ett certifikat kan produceras, som på varje nivå innehåller prime som ska testas, och motsvarande a p s, som enkelt kan _verifieras .

Tillägg och varianter

Uppsatsen från 1975 av Brillhart, Lehmer och Selfridge ger ett bevis för vad som visas ovan som den "generaliserade Pocklington-satsen" som sats 4 på sidan 623. Ytterligare satser visas som tillåter mindre factoring. Detta inkluderar deras sats 3 (en förstärkning av en Proths sats från 1878):

Låt $N-1=mp$ där p är ett udda primtal så att $2p+1>{\sqrt {N}}$ . Om det finns ett a för vilket ${\displaystyle a^{(N-1)/2}\equiv -1{\pmod {N}}} ,$ men ${\displaystyle a^{m/2}\not \equiv -1{\pmod {N}}} ,$ då är N primtal.

Om N är stort är det ofta svårt att faktorisera tillräckligt med $N-1$ för att tillämpa ovanstående konsekvens. Sats 5 i Brillhart-, Lehmer- och Selfridge-papperet tillåter ett primalitetsbevis när den faktoriserade delen endast har nått ( $\displaystyle (N/2)^{1/3}}$ . Många ytterligare sådana satser presenteras som gör att man kan bevisa primaaliteten av N baserat på den partiella faktoriseringen av $N-1$ och $N+1$ .

• Leonard Eugene Dickson, "History of the Theory of Numbers" vol 1, s 370, Chelsea Publishing 1952
• Henry Pocklington, "Math. Quest. Educat. Times", (2), 25, 1914, s 43-46 (Matematiska frågor och lösningar i fortsättning på de matematiska kolumnerna i "The Educational times".)

externa länkar

• Chris Caldwell, "Primality Proving 3.1: n-1 tests and the Pepin's tests for Fermats" på Prime Pages .
• Chris Caldwell, "Primality Proving 3.2: n+1 tests and the Lucas-Lehmer test for Mersennes" på Prime Pages .