Enkelthedscertifikat

Inden for matematik og datalogi er et certifikat for primalitet et strengt bevis på, at et tal er primtal . At have et primalitetscertifikat giver dig mulighed for at kontrollere, at et tal er primtal uden at ty til primalitetstest .

I teorien om beregningskompleksitet er det som regel underforstået, at størrelsen af certifikatet, såvel som den tid, der kræves til at verificere det, afhænger polynomielt af længden af nummerindtastningen, det vil sige antallet af cifre i det.

Eksistensen af polynomielle primalitetscertifikater viser, at problemer såsom primalitetstest og faktorisering af heltal tilhører NP-klassen , da disse ifølge en af de ækvivalente definitioner af denne klasse er problemer, hvis løsning kan verificeres i polynomiets tid, hvis en yderligere certifikat leveres. Derudover ligger disse problemer i co-NP- klassen , som følger af dens definition som en klasse af komplementer til problemer fra NP - ja, enhver af dens ikke-trivielle divisorer kan være et polynomielt certifikat for, at et tal er sammensat.

Primalitetscertifikater var således en af de første indikationer på, at primalitetstestning ikke var NP-komplet , da hvis det var, ville det følge, at en NP-klasse er indlejret i en co-NP, hvilket igen normalt er[ afklare ] overvejet[ af hvem? ] er forkert. Derudover gjorde opdagelsen af polynomielle certifikater primalitetstestning til det første problem, der vides at tilhøre både NP og co-NP, men ikke kendt for at være i klasse P. Med fremkomsten af Agrawal-Kayal-Saxena-testen i 2002, var den første (og i øjeblikket den eneste[ hvornår? ] ) af den deterministiske polynomiale primalitetstest, blev det fundet, at problemet stadig ligger i P.

Pratts certifikat

Historisk set blev begrebet primalitetscertifikater introduceret med fremkomsten af Pratt-certifikatet , som blev opnået i 1975 af Vaughan Pratt [1] , som beskrev dets struktur og beviste, at størrelsen af et certifikat afhænger polynomisk af længden af en nummerpost , og også at det kan verificeres for en polynomisk tid. Certifikatet er baseret på Lucas-testen , som igen følger af Fermats lille teorem :

(Lucs sætning) Et tal er primtal, hvis og kun hvis der er et element i modulo-ringen af rester , således at: $s$ $s$ $a\in \mathbb {Z} _{p}$

$a^{p-1}\equiv 1{\pmod {p))$ ,
$a^{\frac {p-1}{q}}\not \equiv 1{\pmod {p}}$ for alle primtal , der deler . $q$ $p-1$

Bevis

De skrevne betingelser betyder præcis, at rækkefølgen af elementet er . $-en$ $p-1$

Hvis et sådant element eksisterer, så er i det mindste elementerne i ringen af rester reversible modulo , det vil sige coprime med . Således er alle tal coprime med , hvilket indebærer enkelheden af dette tal. $p-1$ $s$ $s$ $1,2,\dots ,p-1$ $s$
Hvis tallet er primtal, så er der en primitiv rod i modulo-ringen af rester , hvis rækkefølge skal være lig med . ■ $s$ $s$ $p-1$

Hvis du har et sådant tal (kaldet et vidne om enkelhed ) og opdeler i primfaktorer, kan du hurtigt kontrollere ovenstående betingelser - du skal udføre eksponentieringer modulo, hvilket kan gøres for multiplikationer ved hjælp af binær eksponentiering . Selve multiplikationerne i den naive implementering ("i en kolonne") udføres i , hvilket giver et samlet estimat af køretiden i . $-en$ $p-1$ $O(\log p)$ $O(\log p)$ $O(\log ^{2}p)$ $O(\log ^{4}p)$

Samtidig skal man huske på, at det udover ovenstående betingelser også er nødvendigt at kontrollere, at de tal, der fremlægges i attesten som primtal, virkelig er sådanne - altså udover vidnet om primalitet og opdeling i primtalsfaktorer, skal et nummers primalitetsbevis også indeholde certifikater for primalitet for alle de faktorer, der er angivet i det. Det er således praktisk at repræsentere et certifikat i form af et træ, i hvis knudepunkter der er primtal og deres tilsvarende primalitetsvidner, og efterkommerne af den knude, hvor tallet er gemt , er primtalsdelere af tallet . Derfor svarer tallet til træets blade . $p-1$ $s$ $s$ $p-1$ $p=2$

Det kan påvises ved induktion, at der højst er interne knudepunkter i et sådant træ , det vil sige dem, der indeholder et ulige primtal. I betragtning af, at hver knude i træet gemmer en smule til at skrive tal i det, kan vi konkludere, at træets samlede størrelse ikke overstiger . Den samlede kontroltid kan til gengæld estimeres til , da det er nødvendigt at udføre handlinger i hver af knudepunkterne. $4\log _{2}s-4$ $O(\log p)$ $O(\log ^{2}p)$ $O(\log ^{5}p)$ $O(\log ^{4}p)$ $O(\log p)$

Mens Pratts certifikater er nyttige i teorien og nemme at verificere, kræver det faktorisering og andre potentielt store tal at finde et certifikat for et tal. Dette er let at gøre i nogle specielle tilfælde, for eksempel for Fermat-primtal , men i det generelle tilfælde er denne opgave nu meget vanskeligere end den sædvanlige test af et tal for primehed. $n$ $n-1$

Indflydelse på "PRIMES er i P"

Artiklen "PRIMES is in P" [2] var et gennembrud inden for teoretisk datalogi . Dette papir, udgivet af Manindra Agrawal og hans to elever Niraj Kayal og Nitin Saxena i august 2002, beviser, at det berømte primalitetsproblem kan løses deterministisk i polynomisk tid. Forfatterne blev tildelt Gödel-prisen , som er $5.000 [3] , og 2006 Fulkerson-prisen for deres arbejde.

Fordi primalitetstesten nu kan udføres i polynomisk tid ved hjælp af AKS-testen , kan et primtal ses som et certifikat for sin egen primalitet. Denne test afsluttes i tide , hvilket gør en sådan verifikation dyrere end at bruge Pratt-certifikatet, men det kræver ikke at finde selve certifikatet. ${\tilde {O}}(\log ^{6}n)$

Noter

↑ Vaughan Pratt. "Hver prime har et kortfattet certifikat". SIAM Journal on Computing , vol. 4, s. 214-220. 1975. Citater , Fuldtekst .
↑ Agrawal, Manindra; Kayal, Neeraj; Saxena, Nitin PRIMES er på P (engelsk) // Annals of Mathematics : tidsskrift. - 2004. - September ( bind 160 , nr. 2 ). - s. 781-793 . - doi : 10.4007/annals.2004.160.781 . — .
↑ Godel-prisen 2017 . European Association for Theoretical Computer Science . EATCS. Hentet: 29. marts 2017. (ubestemt)

Links

Mathworld: Primalitetsbevis
Mathworld Pratt-certifikat
Mathworld: Atkin-Goldwasser-Kilian-Morain-certifikat
Vasek Chvatal . Forelæsningsnoter om Pratts Primality Proofs . Institut for Datalogi. Rutgers Universitet. PDF-version på Concordia University .

Talteoretiske algoritmer
Enkelthedstest	Miller Miller - Rabin Luca - Lemaire pepina Agrawala - Kayala - Sachsen Nightingale - Strassen
At finde primtal	Iteration over divisorer Sigte af Eratosthenes Atkins si Sigte Sundarama
Faktorisering	Iteration over divisorer Fermat metode p −1 Pollard metode Pollards ρ-algoritme Lehmanns metode Elliptisk kurvemetode (Lenstras algoritme) Dixons algoritme Firkantet sigte
Diskret logaritme	Gelfond-Shanks algoritme Polig-Hellman algoritme Pollards ρ-metode Pollards kængurualgoritme Adlemans algoritme COS algoritme
Finder GCD	Euklids algoritme Avanceret algoritme Binær algoritme
Modulo aritmetik	Montgomerys algoritme Kinesisk restsætning
Multiplikation og division af tal	Karatsuba algoritme Toom-Cook algoritme Schönhage-Strassen algoritme Fuhrer algoritme Harvey-van der Hoeven algoritme Burnickel-Ziegler algoritme
Beregning af kvadratroden	Tonelli-Shanks algoritme Berlekamp-Rabin algoritme