AKS primality test

AKS primality test er en deterministisk primality-beviser algoritme skabt og udgivet af Manindra Agrawal, Neeraj Kayal og Nitin Saxena, dataloger ved Indian Institute of Technology Kanpur, den 6. august 2002 i et papir med titlen "PRIMES er i P ". Algoritmen bestemmer, om et tal er et primtal eller et sammensat inden polynomiel tid. Forfatterne fik i 2006 Gödel prisen og i 2006 Fulkerson prisen for dette arbejde.

Betydning

AKS er den første primality-beviser algoritme til at være samtidig generelt polynomium, deterministisk, og ubetinget. Tidligere algoritmer er blevet udviklet i århundreder og opnåede tre af disse egenskaber ved de fleste, men ikke alle fire.

  • AKS algoritme kan bruges til at kontrollere primtal af en generel antal givet. Mange hurtige primality tests er kendt, at arbejde kun for tal med bestemte egenskaber. For eksempel Lucas-Lehmer test virker kun for Mersenne numre, mens Pépins test kan anvendes til kun Fermat numre.
  • Den maksimale driftstid af algoritmen kan udtrykkes som et polynomium over antallet af cifre i måltallet. ECPP og april endegyldigt bevise eller modbevise, at et givet tal er et primtal, men er ikke kendt for at have polynomiel tid grænser for alle indgange.
  • Er garanteret algoritmen at skelne deterministisk, om måltallet er et primtal eller komposit. Randomiserede tests, såsom Miller-Rabin og Baillie-PSW, kan teste en given nummer for primtal i polynomiel tid, men er kendt for at producere kun et probabilistisk resultat.
  • Rigtigheden af ​​AKS er ikke betinget af et datterselskab uprøvede hypotese. I modsætning hertil Miller testen er fuldt deterministisk og kører i polynomiel tid over alle indgange, men dens korrekthed afhænger af sandheden af ​​endnu-uprøvede generaliseret Riemann hypotese.

Begreber

AKS primality Testen er baseret på følgende sætning: Et heltal n er et primtal, hvis og kun hvis polynomiet kongruens relation

gælder for alle heltal en Indbyrdes primisk til n. Bemærk, at x er en fri variabel. Det er aldrig substitueret med en række; du i stedet nødt til at udvide og sammenligne koefficienterne af X beføjelser.

Denne sætning er en generalisering til polynomier af Fermats lille sætning, og kan let bevises ved hjælp af binomial sætning sammen med følgende egenskab af binomial koefficient:

Mens forholdet udgør en primality test i sig selv, at kontrollere det tager eksponentiel tid. Derfor, for at reducere den beregningsmæssige kompleksitet, AKS gør brug af den tilknyttede kongruens

hvilket er det samme som:

for nogle polynomier f og g. Denne kongruens kan kontrolleres i polynomiel tid med hensyn til antallet af cifre i n, fordi det er beviseligt, at r kun behøver at være logaritmisk med hensyn til n. Bemærk, at alle primtal opfylde dette forhold giver, som holder for n primtal). Men nogle sammensatte tal også opfylde relationen. Beviset for rigtigheden for AKS består vise, at der findes et passende lille r og passende lille sæt af heltal En sådan, at hvis kongruens gælder for alle sådan i A, så er n skal være primtal.

Historie og køretid

I den første version af den ovenfor citerede papir, forfatterne beviste asymptotiske tid kompleksiteten af ​​algoritmen til at være. Med andre ord algoritmen tager mindre tid end det tolvte magt antallet af cifre i n gange en polylogarithmic faktor. Men den øvre grænse bevist i papiret var temmelig løs; ja, en udbredt formodning om fordelingen af ​​Sophie Germain primtal ville, hvis det er sandt, straks skære værste tilfælde ned til.

I månederne efter opdagelsen, nye varianter frem, hvilket forbedrede hastigheden på beregning af størrelsesordener. På grund af eksistensen af ​​de mange varianter, Crandall og Papadopoulos henvise til "AKS-klasse" af algoritmer i deres videnskabelige papir "på gennemførelsen af ​​AKS-class primality tests", der blev offentliggjort i marts 2003.

Som svar på nogle af disse varianter, og de øvrige feedback, papiret "PRIMES er i P" er opdateret med en ny formulering af AKS algoritmen og dens bevis for korrekthed. Mens den grundlæggende idé forblev den samme, blev r valgt på en ny måde, og beviset for korrekthed blev mere sammenhængende organiseret. Mens den tidligere bevis havde påberåbt sig mange forskellige metoder, den nye version næsten udelukkende på adfærd cyklotomiske polynomier over endelige legemer. Den nye version også tilladt for en forbedret bundet af den tid kompleksitet, som nu kan vises ved simple metoder at være. Brug af yderligere resultater fra sigten teori, kan dette yderligere reduceret til.

I 2005, Carl Pomerance og HW Lenstra, Jr. vist en variant af AKS, der kører i anlægget, hvis n er antallet, der skal testes - en markant forbedring i forhold til den oprindelige bundet i den oprindelige algoritme. En opdateret version af papiret er også tilgængelig.

Agrawal, Kayal og Saxena foreslå en variant af deres algoritme, som ville køre i, hvis Agrawal formodning er sand; imidlertid en heuristisk argument Hendrik Lenstra og Carl Pomerance tyder på, at det sandsynligvis er falsk.

Algoritme

Algoritmen er som følger:

  • Hvis n = a til heltal a & gt; 1 og b & gt; 1, output komposit.
  • Find det mindste r, således at Or & gt; .
  • Hvis 1 & lt; gcd & lt; n for nogle et ≤ r, sammensatte output.
  • Hvis n ≤ r, output prime.
  • For a = 1 at gøre
  • Output prime.

Her Eller er den multiplikative orden n modulo r, log er den binære logaritme, og er Eulers totient funktion af r.

Hvis n er et primtal, vil algoritmen altid returnere prime: Da n er et primtal, trin 1 og 3 vil aldrig vende tilbage komposit. Trin 5 vil heller aldrig tilbage komposit, fordi er sandt for alle primtal n. Derfor vil algoritmen tilbage prime enten i trin 4 eller i trin 6.

Omvendt, hvis n er sammensat, vil algoritmen altid returnere komposit: hvis algoritmen returnerer prime, så vil dette ske i enten trin 4 eller trin 6. I det første tilfælde, idet n ≤ r, n har en faktor A ≤ r sådan at 1 & lt; gcd & lt; n, som vil vende tilbage komposit. Den resterende mulighed er, at algoritmen returnerer premierminister i trin 6. Forfatterne 'artiklen viser, at dette ikke vil ske, fordi de mange testet i trin 5 kongruenser er tilstrækkelige til at garantere, at produktionen er sammensat.

Eksempel 1: n = 31 er Prime

  • Hvis n = a til heltal a & gt; 1 og b & gt; 1, output komposit.
  • Find det mindste r, således at Or & gt; .
  • Hvis 1 & lt; gcd & lt; n for nogle et ≤ r, sammensatte output.
  • Hvis n ≤ r, output prime.
  • For a = 1 at gøre
  • Output prime.

Hvor PolynomialMod er et begreb-wise modulo reduktion af polynomiet. f.eks. PolynomialMod = x + 2x + 0x

  0   0
Forrige artikel Bob Katsionis
Næste artikel ASV Bergedorf 85

Kommentarer - 0

Ingen kommentar

Tilføj en kommentar

smile smile smile smile smile smile smile smile
smile smile smile smile smile smile smile smile
smile smile smile smile smile smile smile smile
smile smile smile smile
Tegn tilbage: 3000
captcha