AKS-primaliteitstest - AKS primality test

De AKS-primaliteitstest (ook bekend als Agrawal-Kayal-Saxena-primaliteitstest en cyclotomische AKS-test ) is een deterministisch priembewezen algoritme gemaakt en gepubliceerd door Manindra Agrawal , Neeraj Kayal en Nitin Saxena , computerwetenschappers van het Indian Institute of Technology Kanpur , op 6 augustus 2002, in een artikel getiteld "PRIMES is in P". Het algoritme was het eerste dat aantoonbaar kan bepalen of een bepaald getal priemgetal of samengesteld is in polynomiale tijd , zonder te vertrouwen op wiskundige vermoedens zoals de algemene Riemann-hypothese . Het bewijs is ook opmerkelijk omdat het niet vertrouwt op het gebied van analyse . In 2006 ontvingen de auteurs zowel de Gödelprijs als de Fulkersonprijs voor hun werk.

Belang

AKS is het eerste priembewezen algoritme dat tegelijkertijd algemeen , polynoom , deterministisch en onvoorwaardelijk is . Eerdere algoritmen waren eeuwenlang ontwikkeld en bereikten hoogstens drie van deze eigenschappen, maar niet alle vier.

Het AKS-algoritme kan worden gebruikt om de primaliteit van een gegeven algemeen nummer te verifiëren . Er zijn veel snelle priemtesten bekend die alleen werken voor getallen met bepaalde eigenschappen. De Lucas-Lehmer-test werkt bijvoorbeeld alleen voor Mersenne-getallen , terwijl de test van Pépin alleen op Fermat-getallen kan worden toegepast .
De maximale looptijd van het algoritme kan worden uitgedrukt als een polynoom over het aantal cijfers in het doelnummer. ECPP en APR bewijzen of weerleggen overtuigend dat een bepaald getal priemgetal is, maar het is niet bekend dat ze polynomiale tijdsgrenzen hebben voor alle invoer.
Het algoritme maakt gegarandeerd deterministisch onderscheid of het doelgetal priem of samengesteld is. Gerandomiseerde tests, zoals Miller-Rabin en Baillie-PSW , kunnen elk willekeurig getal testen op priemgetallen in polynomiale tijd, maar het is bekend dat ze slechts een probabilistisch resultaat opleveren.
De juistheid van AKS is niet afhankelijk van enige onbewezen subsidiaire hypothese . Daarentegen Miller's versie van de Miller-Rabin-test is volledig deterministisch en loopt in polynomiale tijd over alle inputs, maar de juistheid ervan hangt af van de waarheid van de nog onbewezen gegeneraliseerde Riemann-hypothese .

Hoewel het algoritme van enorm theoretisch belang is, wordt het in de praktijk niet gebruikt, waardoor het een galactisch algoritme wordt . Voor 64-bits ingangen is de Baillie-PSW-primaliteitstest deterministisch en verloopt vele ordes van grootte sneller. Voor grotere inputs zijn de prestaties van de (ook onvoorwaardelijk correcte) ECPP- en APR- tests veel beter dan die van AKS. Bovendien kan ECPP een priemcertificaat afgeven dat onafhankelijke en snelle verificatie van de resultaten mogelijk maakt, wat niet mogelijk is met het AKS-algoritme.

concepten

De AKS-primaliteitstest is gebaseerd op de volgende stelling: Gegeven een geheel getal en een geheel getal coprime to , is priem dan en slechts dan als de polynomiale congruentierelatie $n\geq 2$ $een$ $n$ $n$

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

( 1 )

houdt binnen de polynoomring . Merk op dat het onbepaalde aangeeft dat deze polynoomring genereert. $\mathbb {Z} _{n}[X]$ $X$

Deze stelling is een generalisatie naar veeltermen van de kleine stelling van Fermat . In één richting kan het gemakkelijk worden bewezen met behulp van de binomiale stelling samen met de volgende eigenschap van de binomiale coëfficiënt :

{n \kies k}\equiv 0 {\pmod {n}}

voor alles als priem is.

0<k<n

n

Hoewel de relatie ( 1 ) op zichzelf een priemtest vormt, kost het verifiëren ervan exponentiële tijd : de brute force- benadering zou de uitbreiding van de polynoom en een verlaging van de resulterende coëfficiënten vereisen . $(X+a)^{n}$ ${\pmod {n}}$ $n+1$

De congruentie is een gelijkheid in de polynoomring . Evalueren in een quotiëntring van creëert een bovengrens voor de graad van de betrokken veeltermen. De AKS evalueert de gelijkheid in , waardoor de rekencomplexiteit afhankelijk is van de grootte van . Voor de duidelijkheid wordt dit uitgedrukt als de congruentie $\mathbb {Z} _{n}[X]$ $\mathbb {Z} _{n}[X]$ $\mathbb {Z} _{n}[X]/(X^{r}-1)$ $r$

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

( 2 )

wat hetzelfde is als:

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

( 3 )

voor sommige veeltermen en . $f$ $g$

Merk op dat alle priemgetallen aan deze relatie voldoen (kiezen in ( 3 ) geeft ( 1 ), wat geldt voor priemgetal). Deze congruentie kan worden gecontroleerd in polynomiale tijd wanneer het polynoom is met de cijfers van . Het AKS-algoritme evalueert deze congruentie voor een grote reeks waarden, waarvan de grootte polynoom is voor de cijfers van . Het bewijs van geldigheid van het AKS-algoritme laat zien dat men een en een reeks waarden met de bovenstaande eigenschappen kan vinden, zodat als de congruenties gelden, het een macht van een priemgetal is. $g=0$ $n$ $r$ $n$ $een$ $n$ $r$ $een$ $n$

Geschiedenis en looptijd

In de eerste versie van het hierboven geciteerde artikel bewezen de auteurs dat de asymptotische tijdcomplexiteit van het algoritme (met behulp van Õ van de grote O-notatie ) is - de twaalfde macht van het aantal cijfers in n keer een factor die polylogaritmisch is in de aantal getallen. Deze bovengrens was echter nogal los; een wijdverbreide gissing over de verdeling van de Sophie Germain-priemgetallen zou, indien waar, het ergste geval onmiddellijk terugbrengen tot . ${\tilde {O}}(\log(n)^{12})$ ${\tilde {O}}(\log(n)^{6})$

In de maanden na de ontdekking verschenen er nieuwe varianten (Lenstra 2002, Pomerance 2002, Berrizbeitia 2002, Cheng 2003, Bernstein 2003a/b, Lenstra en Pomerance 2003), die de rekensnelheid aanzienlijk verbeterden. Vanwege het bestaan van de vele varianten verwijzen Crandall en Papadopoulos naar de "AKS-klasse" van algoritmen in hun wetenschappelijke artikel "On the implementatie van AKS-class primality tests", gepubliceerd in maart 2003.

Als reactie op sommige van deze varianten, en op andere feedback, werd het artikel "PRIMES is in P" bijgewerkt met een nieuwe formulering van het AKS-algoritme en van het bewijs van correctheid. (Deze versie werd uiteindelijk gepubliceerd in Annals of Mathematics .) Hoewel het basisidee hetzelfde bleef, werd r op een nieuwe manier gekozen en was het bewijs van correctheid coherenter georganiseerd. Het nieuwe bewijs was bijna uitsluitend gebaseerd op het gedrag van cyclotomische veeltermen over eindige velden . De nieuwe bovengrens van tijdcomplexiteit werd later verlaagd met behulp van aanvullende resultaten uit de zeeftheorie naar . ${\tilde {O}}(\log(n)^{10.5})$ ${\tilde {O}}(\log(n)^{7.5})$

In 2005 demonstreerden Pomerance en Lenstra een variant van AKS die in bedrijf is, wat leidde tot een nieuwe bijgewerkte versie van het papier. Agrawal, Kayal en Saxena voorgesteld een variant die zou draaien in als Agrawal Het vermoeden van waar zou zijn; een heuristisch argument van Pomerance en Lenstra suggereerde echter dat het waarschijnlijk onjuist is. ${\tilde {O}}(\log(n)^{6})$ ${\tilde {O}}(\log(n)^{3})$

Het algoritme

Het algoritme is als volgt:

Invoer: geheel getal

n > 1

.

Controleer of n een volmaakte macht is : als $n = a b$ voor gehele getallen $a > 1$ en $b > 1$ , output composiet .
Vind de kleinste r zodanig dat $orde r (n) > (log 2 n) 2$ . (als r en n niet coprime zijn, sla deze r dan over )
Controleer voor alle 2 ≤ a ≤ min ( r , n −1) of a n niet deelt : Als a | n voor ongeveer 2 ≤ a ≤ min ( r , n −1), output composiet .
Indien n ≤ r , output prime .
Voor $een = 1$ om te doen $\left\lfloor {\sqrt {\varphi (r)}}\log _{2}(n)\right\rfloor$
if ( X + a ) ⁿ ≠ X ⁿ + a (mod X ^r - 1, n ), uitgang composiet ;
Uitgang prime .

Hier ord _r ( n ) de multiplicatieve orde van n modulo r , log ₂ is de binaire logaritme , en is Euler totient functie van r . $\varphi (r)$

Stap 3 wordt in het papier controleren 1 <( a , n ) < n voor een ≤ r . Het kan worden gezien dat dit equivalent is aan proefdeling tot r , wat zeer efficiënt kan worden gedaan zonder ggd te gebruiken . Op dezelfde manier kan de vergelijking in stap 4 worden vervangen door de proefdeling prime te laten retourneren nadat deze alle waarden tot en met . heeft gecontroleerd $\left\lfloor {\sqrt {n}}\right\rfloor.$

Eenmaal voorbij zeer kleine inputs, domineert stap 5 de tijd die nodig is. De essentiële reductie in complexiteit (van exponentieel naar polynoom) wordt bereikt door alle berekeningen in de eindige ring uit te voeren

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

bestaande uit elementen. Deze ring bevat alleen de monomen en de coëfficiënten in die moet elementen allemaal codeerbaar in bits. $n\cdot r$ $r$ $\{X^{0},X^{1},\ldots ,X^{r-1}\}$ ${\ Displaystyle \ mathbb {Z} / (n) =: \ mathbb {Z} _ {n}}$ $n$ $\log _{2}(n)$

De meeste latere verbeteringen die aan het algoritme zijn aangebracht, waren gericht op het verkleinen van de grootte van r , waardoor de kernbewerking in stap 5 sneller wordt, en op het verkleinen van de grootte van s , het aantal lussen dat in stap 5 werd uitgevoerd. Deze wijzigingen veranderen doorgaans niets aan de rekenkundige complexiteit, maar kan leiden tot vele ordes van grootte die minder tijd nodig hebben, bijvoorbeeld de definitieve versie van Bernstein heeft een theoretische versnelling met een factor van meer dan 2 miljoen.

Bewijs van geldigheid overzicht

Om het algoritme correct te laten zijn, moeten alle stappen die n identificeren correct zijn. Stappen 1, 3 en 4 zijn triviaal correct, omdat ze gebaseerd zijn op directe tests van de deelbaarheid van n . Stap 5 is ook correct: aangezien (2) geldt voor elke keuze van een priemgetal naar n en r als n een priemgetal is, betekent een ongelijkheid dat n samengesteld moet zijn.

Het moeilijke geval van het algoritme is de herhaalde verklaring in stap 5. Als dit binnen de eindige Ring R toevallig resulteert in de incongruentie

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

dit is gelijk aan

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

,

zodat na reductie tot de r monomials door middel van alleen hoeft te worden gecontroleerd. ${\text{mod }}(X^{r}\!\!-\!\!1)$ $u\not \equiv v\;({\text{mod}}n)$

Voorbeeld 1: n = 31 is priem

Invoer: geheel getal 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
```

Waarbij PolynomialMod een termgewijze modulo-reductie van de polynoom is. bijv. PolynomialMod[x+2x ² +3x ³ , 3] = x+2x ² +0x ³

Referenties

Verder lezen

Dietzfelbinger, Martin (2004). Primaliteitstesten in polynomiale tijd. Van gerandomiseerde algoritmen naar PRIMES staat in P . Collegenota's in de informatica. 3000 . Berlijn: Springer-Verlag . ISBN 3-540-40344-2. Zbl 1.058,11070 .

Externe links

Weisstein, Eric W. "AKS-primaliteitstest" . MathWereld .
R. Crandall, Apple ACG en J. Papadopoulos (18 maart 2003): Over de implementatie van priemtests van de AKS-klasse (PDF)
Artikel door Borneman, met foto's en informatie over de drie Indiase wetenschappers (PDF)
Andrew Granville: Het is gemakkelijk om te bepalen of een bepaald geheel getal een priemgetal is
De belangrijkste feiten: van Euclides tot AKS , door Scott Aaronson (PDF)
De PRIMES staat in P kleine FAQ door Anton Stiglic
2006 Gödelprijs Citation
2006 Fulkerson Prize Citation
De AKS "PRIMES in P"-algoritmebron
Grime, Dr. James. "Fool-Proof Test voor priemgetallen - Numberphile" (video) . Brady Haran . [de video beschrijft de exponentiële tijdrelatie (1), die het AKS noemt]

Languages

In other projects