AKS primitetstest - AKS primality test

Den AKS primality test (også kjent som Agrawal-Kayal-Saxena primality test og cyclotomic AKS test ) er en deterministisk primality-beviser algoritme laget og publisert av Manindra Agrawal , Neeraj Kayal , og Nitin Saxena , dataforskere ved Indian Institute of Technology Kanpur , 6. august 2002, i en artikkel med tittelen "PRIMES is in P". Algoritmen var den første som beviselig kan avgjøre om et gitt tall er primtall eller sammensatt i polynomtid , uten å stole på matematiske formodninger som den generaliserte Riemann -hypotesen . Beviset er også kjent for ikke å stole på analyseområdet . I 2006 mottok forfatterne både Gödelprisen og Fulkersonprisen for arbeidet sitt.

Betydning

AKS er den første primalitetsbevisende algoritmen som samtidig er generell , polynom , deterministisk og ubetinget . Tidligere algoritmer hadde blitt utviklet i århundrer og oppnådde maksimalt tre av disse egenskapene, men ikke alle fire.

AKS -algoritmen kan brukes til å verifisere primiteten til et gitt generelt tall. Mange raske primitetstester er kjent som bare fungerer for tall med visse egenskaper. For eksempel fungerer Lucas - Lehmer -testen bare for Mersenne -tall , mens Pépins test bare kan brukes på Fermat -tall .
Maksimal kjøretid for algoritmen kan uttrykkes som et polynom over antall sifre i målnummeret. ECPP og APR beviser eller motbeviser definitivt at et gitt tall er primtall, men er ikke kjent for å ha polynomiske tidsgrenser for alle innganger.
Algoritmen skiller garantert deterministisk om målnummeret er primtall eller sammensatt. Randomiserte tester, som Miller - Rabin og Baillie - PSW , kan teste et gitt tall for primalitet i polynomtiden, men er kjent for å gi bare et sannsynlighetsresultat.
Riktigheten av AKS er ikke betinget på noen datterselskap uprøvd hypotese . I kontrast er Millers versjon av Miller – Rabin-testen fullt deterministisk og går i polynomisk tid over alle innspill, men korrektheten avhenger av sannheten i den ennå ikke-påviste generaliserte Riemann-hypotesen .

Selv om algoritmen er av enorm teoretisk betydning, brukes den ikke i praksis, noe som gjør den til en galaktisk algoritme . For 64-biters innganger er Baillie-PSW primitetstest deterministisk og kjører mange størrelsesordener raskere. For større innganger er ytelsen til (også ubetinget korrekt) ECPP- og APR -tester langt bedre enn AKS. I tillegg kan ECPP sende ut et primitetssertifikat som tillater uavhengig og rask verifisering av resultatene, noe som ikke er mulig med AKS -algoritmen.

Begreper

Den AKS primality test er basert på det følgende teorem: Gitt et helt tall og heltall coprime til , er prim hvis og bare hvis den polynomet kongruens relasjon ${\ displaystyle n \ geq 2}$ ${\ displaystyle a}$ ${\ displaystyle n}$ ${\ displaystyle n}$

{\ displaystyle (X+a)^{n} \ equiv X^{n}+a {\ pmod {n}}}

( 1 )

holder seg inne i polynomringen . Merk at den angir det ubestemte som genererer denne polynomiske ringen. ${\ displaystyle \ mathbb {Z} _ {n} [X]}$ ${\ displaystyle X}$

Denne setningen er en generalisering til polynomer av Fermats lille teorem . I en retning kan det enkelt bevises ved bruk av binomialsetningen sammen med følgende egenskap til binomialkoeffisienten :

{\ displaystyle {n \ velg k} \ equiv 0 {\ pmod {n}}}

for alle hvis er prime.

{\ displaystyle 0 <k <n}

{\ displaystyle n}

Selv om forholdet ( 1 ) utgjør en primitetstest i seg selv, bekrefter det at det tar eksponentiell tid : Brute force -tilnærmingen vil kreve utvidelse av polynomet og en reduksjon av de resulterende koeffisientene. ${\ displaystyle (X+a)^{n}}$ ${\ displaystyle {\ pmod {n}}}$ ${\ displaystyle n+1}$

Kongruensen er en likhet i polynomringen . Evaluering i en kvotering av skaper en øvre grense for graden av polynomene som er involvert. AKS vurderer likheten i , noe som gjør beregningskompleksiteten avhengig av størrelsen på . For klarhet uttrykkes dette som kongruens ${\ displaystyle \ mathbb {Z} _ {n} [X]}$ ${\ displaystyle \ mathbb {Z} _ {n} [X]}$ ${\ displaystyle \ mathbb {Z} _ {n} [X]/(X^{r} -1)}$ ${\ displaystyle r}$

{\ displaystyle (X+a)^{n} \ equiv (X^{n}+a) {\ pmod {X^{r} -1, n}}}

( 2 )

som er det samme som:

{\ displaystyle (X+a)^{n}-(X^{n}+a) = (X^{r} -1) g+nf}

( 3 )

for noen polynomer og . ${\ displaystyle f}$ ${\ displaystyle g}$

Vær oppmerksom på at alle primtalene tilfredsstiller denne relasjonen (å velge i ( 3 ) gir ( 1 ), som gjelder for prime). Denne kongruensen kan kontrolleres i polynomtiden når den er polynom til sifrene . AKS -algoritmen evaluerer denne kongruensen for et stort sett med verdier, hvis størrelse er polynom i forhold til sifrene . Beviset på gyldigheten av AKS -algoritmen viser at man kan finne et og et sett med verdier med egenskapene ovenfor slik at hvis kongruensene holder, er det en kraft av et primtall. ${\ displaystyle g = 0}$ ${\ displaystyle n}$ ${\ displaystyle r}$ ${\ displaystyle n}$ ${\ displaystyle a}$ ${\ displaystyle n}$ ${\ displaystyle r}$ ${\ displaystyle a}$ ${\ displaystyle n}$

Historie og kjøretid

I den første versjonen av det ovennevnte papiret viste forfatterne at algoritmens asymptotiske tidskompleksitet var (ved bruk av Õ fra stor O-notasjon )-den tolvte kraften i antall sifre i n ganger en faktor som er polylogaritmisk i antall siffer. Denne øvre grensen var imidlertid ganske løs; en utbredt formodning om fordelingen av Sophie Germain-primtalene ville, hvis det var sant, umiddelbart kutte det verste tilfellet ned til . ${\ displaystyle {\ tilde {O}} (\ log (n)^{12})}$ ${\ displaystyle {\ tilde {O}} (\ log (n)^{6})}$

I månedene etter oppdagelsen dukket det opp nye varianter (Lenstra 2002, Pomerance 2002, Berrizbeitia 2002, Cheng 2003, Bernstein 2003a/b, Lenstra og Pomerance 2003), noe som forbedret beregningshastigheten sterkt. På grunn av eksistensen av de mange variantene, refererer Crandall og Papadopoulos til "AKS-klassen" av algoritmer i sitt vitenskapelige papir "Om implementering av AKS-klasse primitetstester", publisert i mars 2003.

Som svar på noen av disse variantene, og på andre tilbakemeldinger, ble papiret "PRIMES is in P" oppdatert med en ny formulering av AKS -algoritmen og dens korrekthetsbevis. (Denne versjonen ble til slutt publisert i Annals of Mathematics .) Mens grunnideen forble den samme, ble r valgt på en ny måte, og beviset på korrekthet ble mer sammenhengende organisert. Det nye beviset stolte nesten utelukkende på oppførselen til syklotomiske polynomer over begrensede felt . Den nye øvre grensen for tidskompleksitet ble senere redusert ved hjelp av tilleggsresultater fra sileteori til . ${\ displaystyle {\ tilde {O}} (\ log (n)^{10.5})}$ ${\ displaystyle {\ tilde {O}} (\ log (n)^{7.5})}$

I 2005 demonstrerte Pomerance og Lenstra en variant av AKS som kjører i drift, noe som førte til en annen oppdatert versjon av papiret. Agrawal, Kayal og Saxena foreslo en variant som ville løpe inn hvis Agrawals formodning var sann; et heuristisk argument fra Pomerance og Lenstra antydet imidlertid at det sannsynligvis er usant. ${\ displaystyle {\ tilde {O}} (\ log (n)^{6})}$ ${\ displaystyle {\ tilde {O}} (\ log (n)^{3})}$

Algoritmen

Algoritmen er som følger:

Inndata: heltall

n > 1

.

Sjekk om n er en perfekt effekt : hvis $n = a b$ for heltall $a > 1$ og $b > 1$ , send ut kompositt .
Finn den minste r slik at $ord r (n)> (log 2 n) 2$ . (hvis r og n ikke er coprime, så hopp over denne r )
For alle 2 ≤ a ≤ min ( r , n −1), kontroller at a ikke deler n : Hvis a | n for noen 2 ≤ en ≤ min ( r , n -1), utgang kompositt .
Hvis n ≤ r , send ut prim .
For $a = 1$ å gjøre ${\ displaystyle \ left \ lfloor {\ sqrt {\ varphi (r)}} \ log _ {2} (n) \ right \ rfloor}$
if ( X + et ) ⁿ ≠ X ⁿ + et (mod X ^r - 1, N ), utgangs kompositt ;
Utgangs prime .

Her er ord _r ( n ) multiplikasjonsrekkefølgen til n modulo r , log ₂ er den binære logaritmen , og er Eulers totientfunksjon av r . ${\ displaystyle \ varphi (r)}$

Trinn 3 er vist i papiret ved å kontrollere 1 <( a , n ) < n for alle a ≤ r . Det kan sees at dette tilsvarer prøvedeling opp til r , noe som kan gjøres veldig effektivt uten å bruke gcd . På samme måte kan sammenligningen i trinn 4 erstattes med at prøvedivisjonen returnerer prime når den har kontrollert alle verdier til og med ${\ displaystyle \ left \ lfloor {\ sqrt {n}} \ right \ rfloor.}$

Når det en gang går utover veldig små innganger, dominerer trinn 5 tiden det tar. Den vesentlige reduksjonen i kompleksitet (fra eksponentiell til polynom) oppnås ved å utføre alle beregninger i den endelige ringen

{\ displaystyle R: = {\ Bigl (} {\ bigl (} \ mathbb {Z} /(n) {\ bigr)} [X] {\ Bigr)} {\ Bigl /} (X^{r} \ ! \!-\! \! 1) {\ Bigr.}}

bestående av elementer. Denne ringen inneholder bare monomialene , og koeffisientene er i som har elementer som alle kan kodes i biter. ${\ displaystyle n \ cdot r}$ ${\ displaystyle r}$ ${\ displaystyle \ {X^{0}, X^{1}, \ ldots, X^{r-1} \}}$ ${\ displaystyle \ mathbb {Z} /(n) =: \ mathbb {Z} _ {n}}$ ${\ displaystyle n}$ ${\ displaystyle \ log _ {2} (n)}$

De fleste senere forbedringer av algoritmen har konsentrert seg om å redusere størrelsen på r, noe som gjør kjerneoperasjonen i trinn 5 raskere, og ved å redusere størrelsen på s , antall løkker utført i trinn 5. Vanligvis endrer disse endringene ikke beregningen kompleksitet, men kan føre til at mange størrelsesordner tar mindre tid, f.eks. har Bernsteins siste versjon en teoretisk fart med en faktor på over 2 millioner.

Bevis på gyldighetsoversikt

For at algoritmen skal være korrekt, må alle trinnene som identifiserer n være riktige. Trinn 1, 3 og 4 er trivielt riktige, siden de er basert på direkte tester av delbarheten til n . Trinn 5 er også riktig: siden (2) er sant for ethvert valg av en coprime til n og r hvis n er prime, betyr en ulikhet at n må være sammensatt.

Algoritmens vanskelige tilfelle er den itererte uttalelsen i trinn 5. Hvis dette i den endelige ringen R tilfeldigvis resulterer i inkongruens

{\ displaystyle u \ not \ equiv v \; {\ bigl (} {\ text {mod}} (X^{r} \! \!-\! \! 1), n ​​{\ bigr)}}

dette tilsvarer

{\ displaystyle u \ equiv v \; {\ bigl (} {\ text {mod}} (X^{r} \! \! \! \! 1) {\ bigr)} \ quad \ impliserer \ quad u \ not \ equiv v \; ({\ text {mod}} n)}

,

slik at etter å ha redusert til r monomialer ved hjelp av bare må kontrolleres for. ${\ displaystyle {\ text {mod}} (X^{r} \! \!-\! \! 1)}$ ${\ displaystyle u \ not \ equiv v \; ({\ text {mod}} n)}$

Eksempel 1: n = 31 er primtall

Inndata: heltall n = 31> 1.

  If n = a^b for integers a > 1 and b > 1, output composite.
    For [ b=2, b <= log₂(n), b++,
      a=n^1/b;
      If [ a is integer, Return[Composite]]
    ];
    a=n^1/2...n^1/4={5.568, 3.141, 2.360}

  Find the smallest r such that O_r(n) > (log₂ n)².
    maxk=⌊(log₂ n)²⌋;
    maxr=Max[3, ⌈(Log₂ n)⁵⌉]; (*maxr really isn't needed*)
    nextR=True;
    For [r=2, nextR && r < maxr, r++,
      nextR=False;
      For [k=1,(!nextR) &&k ≤ maxk, k++,
        nextR=(Mod[n^k, r]==1 || Mod[n^k, r]==0)
      ]
    ];
    r--; (*the loop over increments by one*)
     
    r = 29

  If 1 < gcd(a,n) < n for some a ≤ r, output composite.
    For [a=r, a > 1, a--,
      If [(gcd=GCD[a,n]) > 1 && gcd < n, Return[Composite]]
    ];
     
    gcd={GCD(29,31)=1, GCD(28,31)=1, ..., GCD(2,31)=1} ≯ 1

  If n ≤ r, output prime.
    If [n ≤ r, Return[Prime]]; (* this step may be omitted if n > 5690034 *)
     
    31 > 29

  For a = 1 to  $\left\lfloor {\sqrt {\varphi (r)}}\log _{2}(n)\right\rfloor$  do
    if (X+a)ⁿ≠ Xⁿ+a (mod X^r − 1,n), output composite;
     
    φ[x_]:=EulerPhi[x];
    PolyModulo[f_]:=PolynomialMod[ PolynomialRemainder[f,x^r-1,x],n];
    max=Floor[Log[2,n]√φ[r]];
    For[a=1, a ≤ max, a++,
      If[PolyModulo[(x+a)ⁿ-PolynomialRemainder[xⁿ+a, x^r-1], x]≠0,
        Return[Composite]
      ]
    ];
     
    (x+a)³¹ =
      a³¹ +31a³⁰x +465a²⁹x² +4495a²⁸x³ +31465a²⁷x⁴ +169911a²⁶x⁵ +736281a²⁵x⁶ +2629575a²⁴x⁷ +7888725a²³x⁸ +20160075a²²x⁹ +44352165a²¹x¹⁰ +84672315a²⁰x¹¹ +141120525a¹⁹x¹² +206253075a¹⁸x¹³ +265182525a¹⁷x¹⁴ +300540195a¹⁶x¹⁵ +300540195a¹⁵x¹⁶ +265182525a¹⁴x¹⁷ +206253075a¹³x¹⁸ +141120525a¹²x¹⁹ +84672315a¹¹x²⁰ +44352165a¹⁰x²¹ +20160075a⁹x²² +7888725a⁸x²³ +2629575a⁷x²⁴ +736281a⁶x²⁵ +169911a⁵x²⁶ +31465a⁴x²⁷ +4495a³x²⁸ +465a²x²⁹ +31ax³⁰ +x³¹
     
    PolynomialRemainder [(x+a)³¹, x²⁹-1] =
      465a² +a³¹ +(31a+31a³⁰)x +(1+465a²⁹)x² +4495a²⁸x³ +31465a²⁷x⁴ +169911a²⁶x⁵ +736281a²⁵x⁶ +2629575a²⁴x⁷ +7888725a²³x⁸ +20160075a²²x⁹ +44352165a²¹x¹⁰ +84672315a²⁰x¹¹ +141120525a¹⁹x¹² +206253075a¹⁸x¹³ +265182525a¹⁷x¹⁴ +300540195a¹⁶x¹⁵ +300540195a¹⁵x¹⁶ +265182525a¹⁴x¹⁷ +206253075a¹³x¹⁸ +141120525a¹²x¹⁹ +84672315a¹¹x²⁰ +44352165a¹⁰x²¹ +20160075a⁹x²² +7888725a⁸x²³ +2629575a⁷x²⁴ +736281a⁶x²⁵ +169911a⁵x²⁶ +31465a⁴x²⁷ +4495a³x²⁸
     
    (A) PolynomialMod [PolynomialRemainder [(x+a)³¹, x²⁹-1], 31] = a³¹+x²
     
    (B) PolynomialRemainder [x³¹+a, x²⁹-1] = a+x²
     
    (A) - (B) = a³¹+x² - (a+x²) = a³¹-a
     
    max =  $\left\lfloor \log _{2}(31){\sqrt {\varphi (29)}}\right\rfloor$  = 26
     
    {1³¹-1=0 (mod 31), 2³¹-2=0 (mod 31), 3³¹-3=0 (mod 31), ..., 26³¹-26=0 (mod 31)}

```
  Output prime.
    31 Must be Prime
```

Der PolynomialMod er en termisk modulomdannelse av polynomet. f.eks PolynomialMod [x +2x ² +3x ³ , 3] = x +2x ² +0x ³

Referanser

Videre lesning

Dietzfelbinger, Martin (2004). Primitetstesting i polynomtid. Fra randomiserte algoritmer til PRIMES er i P . Forelesningsnotater i informatikk. 3000 . Berlin: Springer-Verlag . ISBN 3-540-40344-2. Zbl 1058.11070 .

Eksterne linker

Weisstein, Eric W. "AKS Primality Test" . MathWorld .
R. Crandall, Apple ACG og J. Papadopoulos (18. mars 2003): Om implementering av primitetstester i AKS-klassen (PDF)
Artikkel av Borneman, som inneholder bilder og informasjon om de tre indiske forskerne (PDF)
Andrew Granville: Det er lett å avgjøre om et gitt heltall er prime
The Prime Facts: From Euclid to AKS , av Scott Aaronson (PDF)
PRIMES er i P little FAQ av Anton Stiglic
2006 Gödel Prize Citation
2006 Fulkerson Prize Citation
AKS "PRIMES in P" algoritmeressurs
Grime, Dr. James. "Fool -Proof Test for Primes - Numberphile" (video) . Brady Haran . [videoen beskriver det eksponentielle tidsforholdet (1), som det kalles AKS]

Languages

In other projects