Primitetsintyg

Inom matematik och datavetenskap är ett primalitetsbevis eller primalitetsbevis ett kortfattat, formellt bevis på att ett tal är primtal. Primalitetscertifikat gör det möjligt att snabbt kontrollera ett nummers primatitet utan att behöva köra ett dyrt eller opålitligt primalitetstest . "Kunct" betyder vanligtvis att beviset bör vara högst polynomiskt större än antalet siffror i själva talet (till exempel, om talet har b bitar kan beviset innehålla ungefär b ² bitar).

Primalitetscertifikat leder direkt till bevis på att problem som primalitetstestning och komplementet till heltalsfaktorisering ligger i NP , klassen av problem som kan verifieras i polynomtid givet en lösning. Dessa problem ligger redan trivialt i co-NP . Detta var det första starka beviset för att dessa problem inte är NP-kompletta , eftersom om de var det skulle det antyda att NP är en delmängd av co-NP, ett resultat som allmänt anses vara falskt; i själva verket var detta den första demonstrationen av ett problem i NP korsar co-NP som vid den tiden inte var känt för att vara i P.

Att ta fram certifikat för komplementproblemet, för att fastställa att ett tal är sammansatt, är enkelt: det räcker för att ge en icke-trivial divisor. Vanliga probabilistiska primalitetstester såsom Baillie–PSW primalitetstestet , Fermat primalitetstestet och Miller–Rabin primatitetstestet ger också sammansättningscertifikat i händelse av att insatsen är sammansatt, men producerar inte certifikat för primära indata.

Pratt-certifikat

Begreppet primalitetscertifikat introducerades historiskt av Pratt-certifikatet , tänkt 1975 av Vaughan Pratt , som beskrev dess struktur och bevisade att den har polynomstorlek och att den är verifierbar i polynomtid. Det är baserat på Lucas primatitetstestet , som i huvudsak är motsatsen till Fermats lilla teorem med ett tillagt villkor för att göra det sant:

Lucas sats : Antag att vi har ett heltal som är så:

• a ^{n − 1} ≡ 1 (mod n ),
• för varje primfaktor q av n − 1 är det inte så att a ^{( n − 1)/ q} ≡ 1 (mod n ).

Då är n primtal.

Med tanke på en sådan a (kallad vittne ) och primtalsfaktoriseringen av n − 1 är det enkelt att snabbt verifiera ovanstående villkor: vi behöver bara göra ett linjärt antal modulära exponentieringar, eftersom varje heltal har färre primtalsfaktorer än bitar, och var och en av dessa kan göras genom exponentiering genom att kvadrera i O(log n ) multiplikationer (se big-O notation ) . Även med heltalsmultiplikation i grundskolan är detta bara O((log n ) ⁴ ) tid; genom att använda multiplikationsalgoritmen med den mest kända asymptotiska körtiden, Schönhage–Strassen-algoritmen , kan vi sänka denna till O((log n ) ³ (log log n )(log log log n )) tid, eller använda soft-O notation Õ((log n ) ³ ).

Det är dock möjligt att lura en verifierare att acceptera ett sammansatt tal genom att ge det en "primtalsfaktorisering" på n − 1 som inkluderar sammansatta tal. Anta till exempel att vi hävdar att n = 85 är primtal, vilket ger a = 4 och n − 1 = 6 × 14 som "primtalsfaktorisering". Sedan (med q = 6 och q = 14):

• 4 är coprime till 85,
• 4 ⁸⁵⁻¹ ≡ 1 (mod 85),
• 4 ^(85−1)/6 ≡ 16 (mod 85), 4 ^(85−1)/14 ≡ 16 (mod 85).

Vi skulle felaktigt dra slutsatsen att 85 är prime. Vi vill inte bara tvinga verifieraren att faktorisera antalet, så ett bättre sätt att undvika detta problem är att ge primalitetscertifikat för var och en av primfaktorerna för n − 1, som bara är mindre instanser av det ursprungliga problemet . Vi fortsätter rekursivt på detta sätt tills vi når ett tal som är känt för att vara primtal, till exempel 2. Vi slutar med ett träd med primtal, vart och ett associerat med ett vittne a . Här är till exempel ett komplett Pratt-certifikat för nummer 229:

• 229 ( a = 6, 229 − 1 = 2 ² × 3 × 19),
  • 2 (känd primtal),
  • 3 ( a = 2, 3 − 1 = 2),
    • 2 (känd primtal),
  • 19 ( a = 2, 19 − 1 = 2 × 3 ² ),
    • 2 (känd primtal),
    • 3 ( a = 2, 3 − 1 = 2),
      • 2 (känd primtal).

Detta bevisträd kan visas innehålla högst $4\log _{2}n-4$ andra värden än 2 genom ett enkelt induktivt bevis (baserat på sats 2 i Pratt). Resultatet håller för 3; i allmänhet, ta p > 3 och låt dess barn i trädet vara p ₁ , ..., p _k . Enligt den induktiva hypotesen innehåller trädet med rötter vid p _i högst $4\log _{2}p_{i}-4$ värden, så hela trädet innehåller högst

$1+\sum _{i =1}^{k}(4\log _{2}p_{i}-4)=-4k+4\log _{2}p_{1}\cdots p_{k}\leq 4\log _{ 2}s-4,$

eftersom k ≥ 2, och p ₁ ... p _k = p − 1. Eftersom varje värde har högst log n bitar, visar detta också att certifikatet har en storlek på O((log n ) ² ) bitar.

Eftersom det finns andra O(log n )-värden än 2, och varje kräver högst en exponentiering för att verifiera (och exponentieringar dominerar körtiden), är den totala tiden O((log n ) 3 (log log n ⁾ ( log log log n )), eller Õ((log n ) ³ ), vilket är ganska genomförbart för tal i det intervall som beräkningstalteoretiker vanligtvis arbetar med.

Men även om det är användbart i teorin och lätt att verifiera, kräver det att faktiskt generera ett Pratt-certifikat för n faktorisering n − 1 och andra potentiellt stora tal. Detta är enkelt för vissa speciella tal som Fermat-primtal , men för närvarande mycket svårare än enkla primalitetstestning för stora primtal av allmän form.

Atkin–Goldwasser–Kilian–Morain-certifikat

För att ta itu med problemet med effektiv certifikatgenerering för större antal beskrev Shafi Goldwasser och Joe Kilian 1986 en ny typ av certifikat baserad på teorin om elliptiska kurvor . Detta användes i sin tur av AOL Atkin och François Morain som grund för Atkin-Goldwasser-Kilian-Morain-certifikat, som är den typ av certifikat som genereras och verifieras av elliptiska kurvor som bevisar primalitetssystem . Precis som Pratt-certifikat är baserade på Lucas sats, är Atkin-Goldwasser-Kilian-Morain-certifikat baserade på följande sats av Goldwasser och Kilian (lemma 2 av "Nästan alla primtal kan snabbt certifieras"):

Sats : Antag att vi får:

• ett positivt heltal n som inte är delbart med 2 eller 3;
• M _x , M _y , A, B i $\mathbb {Z} _{n}$ (heltalen mod n ) som uppfyller M _y ² = M _x ³ + AM _x + B och med 4A ³ + 27B ² coprime till n ;
• a primtal $q>n^{1/2}+1+2n^{1/4}$ .

Då är M = (M _x , M _y ) en icke-identitetspunkt på den elliptiska kurvan y ² = x ³ + Ax + B. Låt k M vara M adderad till sig själv k gånger med hjälp av standard elliptisk kurvaddition. Sedan, om q M är identitetselementet I, så är n primtal.

Tekniskt sett kan en elliptisk kurva bara konstrueras över ett fält, och $\mathbb {Z} _{n}$ är bara ett fält om n är primtal, så vi verkar anta resultatet vi försöker att bevisa. Svårigheten uppstår i den elliptiska kurvadditionsalgoritmen, som tar inverser i fältet som kanske inte finns i $\mathbb {Z} _{n}$ . Det kan dock visas (lemma 1 av "Nästan alla primtal kan snabbt certifieras") att om vi bara utför beräkningar som om kurvan var väldefinierad och inte vid något tillfälle försöker invertera ett element utan invers, resultatet är fortfarande giltigt; om vi stöter på ett element utan invers, fastställer detta att n är sammansatt.

För att härleda ett certifikat från denna sats kodar vi först M _x , M _y , A, B och q , kodar sedan rekursivt beviset på primaliteten för q < n , och fortsätter tills vi når ett känt primtal. Detta certifikat har storlek O((log n ) ² ) och kan verifieras i O((log n ) ⁴ ) tid. Dessutom kan algoritmen som genererar dessa certifikat visas vara förväntad polynomtid för alla utom en liten del av primtal, och denna bråkdel minskar exponentiellt med storleken på primtal. Följaktligen är den väl lämpad för att generera certifierade stora slumpmässiga primtal, en applikation som är viktig i kryptografiapplikationer som att generera bevisligen giltiga RSA -nycklar.

Pocklington-baserade certifikat

Bevisbar primtalsgenerering baserad på varianter av Pocklingtons teorem (se Pocklingtons primalitetstest ) kan vara effektiva tekniker för att generera primtal (kostnaden är i allmänhet mindre än probabilistisk generering) med den extra fördelen av inbyggda primalitetscertifikat. Även om dessa kan tyckas vara speciella primtal, lägg märke till att varje primtal heltal kan genereras med en Pocklington-baserad bevisbar genereringsalgoritm.

Pocklington Primality Tests

Låt $P=Rh+1$ där $R=\prod q_{j}^{e_{j}}$ där $q_ {j}$ är distinkta primtal med $e_{j}$ ett heltal större än noll och ett vittne $g$ så att:

1. $g^{Rh}\equiv 1{\bmod {P}}$

 

 

 

 

()

2. ${\displaystyle \gcd((g^{Rh/q_{j}}-1{\bmod {P}}),$ för alla $q_{j}$ .

 

 

 

 

()

Då är P primtal om något av följande gäller:

a) (se ) $R\geq h$ eller motsvarande $R>P^{1/2}$

 

 

 

 

()

b) (se ) $\$$1/3}$ R och

• med ${\begin{array}{lr}a\equiv h{\bmod {R}}&0\leq a<R\\ b=(ha)/R\end{array}}$ ,
• så att $(a-4b)\neq 0$ och det finns ett litet primtal $r>2$ så att $(a-4b)^{r/2}\neq 1{\bmod {r}}$ .

 

 

 

 

()

Pocklington Primality Certificate

Ett Pocklington primtal certifikat består av primtal P, en uppsättning primtal $q_{j}$ dividerande $(P-1)$ , var och en med sitt eget Pocklington primtal certifikat eller tillräckligt liten för att vara ett känt primtal och ett vittne $g$ .

Bitarna som behövs för detta certifikat (och beräkningskostnadens ordning) bör variera från ungefär ${\displaystyle \log _{2}{P }\left(1+\sum _{k=1}^{\infty }{\frac {1}{3^{k}}}\right)=1.5\log _{2}{P}} för$ version ( b ) till $\log _{2}{P}\left(1+\summa _{k=1 }^{\infty }{\frac {1}{2^{k}}}\right)=2\log _{2}{P}$ för version ( a )

Ett litet exempel

Låt $P=1056893$ . Observera att $(P-1)=1621\cdot 163\cdot 2^{2}}$${1 /2}=1028.053\ldots }$ … , ${\displaystyle P^{1/3}=101.86156\$ .

• Med 'vittnet' 2 är ekvation 1 uppfylld och 2 med $q=163$ och $q=1621$ .
• För version a behöver certifikatet endast $P=1056893,\ q=1621,\ g=2$ .
• för version b behöver certifikatet bara ${\displaystyle P=1056893,\ q=163,\ g=2} ,$ men det finns lite mer arbete att göra:
  • $h=(1056893-1)/163=6484$
  • $a\equiv h\equiv 127{\bmod {163}}$ och $b=\left(6484-127\right )/163=39$
  • Att använda $r=3$ misslyckas: $\left(127^{2} -4\cdot 39\right)^{(3-1)/2}\equiv (1^{2}-0)^{1}\equiv 1{\bmod {3}}$
  • Att använda $r=5$ lyckas: ${\displaystyle \left(127^{2 }-4\cdot 39\right)^{(5-1)/2}\equiv (2^{2}-1)^{2}\equiv 2{\bmod {5}}} och$ P $\ displaystyle P}$ är prime.

Effekten av "PRIMES är i P"

"PRIMES is in P" var ett genombrott inom teoretisk datavetenskap. Denna artikel, publicerad av Manindra Agrawal , Nitin Saxena och Neeraj Kayal i augusti 2002, bevisar att det berömda problemet med att kontrollera primaliteten hos ett tal kan lösas deterministiskt i polynomtid. Författarna fick 2006 års Gödelpris och 2006 Fulkersonpris för detta arbete.

Eftersom primalitetstestning nu kan göras deterministiskt i polynomtid med AKS-primalitetstestet , kan ett primtal i sig betraktas som ett certifikat för sin egen primalitet. Detta test körs i Õ((log n ) ⁶ ) tid. I praktiken är denna metod för verifiering dyrare än verifiering av Pratt-certifikat, men kräver ingen beräkning för att fastställa själva certifikatet.

externa länkar

• Mathworld: Primalitetscertifikat
• Mathworld: Pratt-certifikat
• Mathworld: Atkin-Goldwasser-Kilian-Morain-certifikat
• The Prime Ordlista: Certificate of Primality
• Vašek Chvátal . Föreläsningsanteckningar om Pratts Primality Proofs . Institutionen för datavetenskap. Rutgers University. PDF-version vid Concordia University .
• Wim van Dam. Bevis för Pratts teorem . (Föreläsningsanteckningar, PDF)