AKS primality test

FONT SIZE:
fontsize_dec
fontsize_inc
17-02-2018 Kurt Karkov A

AKS primality test eller AKS algoritme er en deterministisk algoritme i polynomiel tid at beslutte, om et naturligt tal er et primtal eller komposit. Den er designet af dataloger Manindra Agrawal, Neeraj Kayal og Nitin Saxena af Indian Institute of Technology Kanpur i 2002, og til sidst forbedret med andre forskere på området. Deres opdagelse sætter en stopper for et af de største problemer i talteori og beregningsmæssige kompleksitetsteori.

Problemet med primality

Problemet med primality er at finde ud af, om et naturligt tal er et primtal eller komposit. Der er meget gamle til at løse dette problem, da Eratosthenes 'si eller domsafdelingen metoder, men disse metoder er ineffektive, når du ønsker at analysere store tal. At afgøre primtal af et nummer, Eratosthenes 'si kræver en runtime, der er proportional med. På den anden side, antallet af cifre behov at skrive et sådant antal er proportional med.

I form af beregningsmæssige kompleksitet, siges det, at en effektiv metode ville kræve polynomiel tid i forhold til antallet af cifre. I dette tilfælde, du ønsker at have en algoritme, der afgør i forhold til tid, hvis det er et primtal eller komposit. Brug den store O-notation, er denne andel forkortes. AKS algoritme er den første algoritme kendt med disse egenskaber.

Historie

Før Agrawal, Kayal og Saxena beskriver deres algoritme, blev mange gjort forsøg på at løse problemet med primality effektivt. I 1798 Gauss foreslog skelne primtal fra sammensatte tal ikke var nødvendig at faktor sidstnævnte.

I 1636 præsenterede han sin berømte Fermats lille sætning af Fermat, som afslørede en funktion, der mødte alle primtal. Denne sætning hedder det, at når er et primtal, og er et relativt primtal, kongruens følgende gælder:

Det betyder, at hvis antallet stiger til strømmen og divideret med resten af ​​denne opdeling er præcist. Denne sætning blev taget som grundlag for flere primtal tests.

Den primality test Miller-Rabin blev indført i 1980. Algoritmen virker i polynomiel tid, men er probabilistisk. For eksempel, efter udførelse af Miller-Rabin test gange algoritmen eller problemstillinger et certifikat, at antallet er sammensat eller erklærer, at nummeret har en høj sandsynlighed for at være prime. Miller-Rabin test kræver en tid med en sandsynlighed for fejl i.

I 1983 Leonard Adleman, Carl Pomerance og Rumely Robert oprettet en primality test, at det er deterministisk, men hvis gennemførelsestid var eksponentiel:. Deres algoritme er baseret på komplekse teori og en generalisering af Fermats lille sætning til heltal i cyklotomiske felter. Men denne algoritme er så hurtig, at varianter at bryde poster som at kontrollere primtal af numre med mere end tusind decimaler brugt i lang tid. På trods af denne store præstation, var der stadig spørgsmålet om, hvorvidt der er en algoritme, der arbejder i polynomiel tid, og det var deterministisk.

I 1992 kom en anden klasse algoritmer baseret på elliptiske kurver, men de var ikke deterministisk.

Endelig i 1999 Manindra Agrawal studeret en variant af Fermats lille sætning. To år senere, han og hans to studerende IITK begyndte at analysere alle de egenskaber af denne variant, indtil de fandt en fuldstændig karakterisering af primtal. Baseret på denne karakteristik, i 2002 de præsenterede deres algoritme i artikel PRIMES er i P.

Fonde Algoritme

Den AKS-algoritmen er baseret på en generalisering af Fermats lille sætning til polynomier. Sætningen hedder det, at hvis og er relativt prime numre, hvor er et primtal, så kongruens er opfyldt

Det vil sige, hvis polynomium opløftet til potensen og opsplitter derefter, så den resterende del af divisionen. Desuden, hvis dette er sandt kongruens så må det være et primtal.

Selv om denne kongruens helt karakteriserer de primtal er det ikke muligt at anvende, fordi beregningen kræver mere tid end Eratosthenes 'si. I stedet er kongruens bruges

Det vil sige, ækvivalensen mellem rester af polynomier og efter at være delt af og på skift af hver koefficient. Matematikkens sprog forkortes ring. Nogle sammensatte tal opfylde dette kongruens, men hvis de vælges korrekt og konsistens til flere numre er opfyldt, så må det være enten et primtal eller i det mindste en effekt på et primtal.

"Bestil et modul nummer" betegnes matematisk. Den repræsenterer den mindste værdi for hvilke. AKS-algoritmen vælger som den mindste kompatibel.

Ud over dette, algoritmen kræver også at kende Euler funktion og den største fælles divisor.

Den korrektion algoritme er garanteret af en sætning som oprindeligt blev demonstreret af forfattere og senere sammenfattet af Lenstra, Jr. og Bernstein. I sin enkleste form, denne sætning, at hvis og er positive heltal, og hvis et endeligt sæt af heltal, så er det en effekt på et primtal, forudsat at følgende betingelser er opfyldt:

  • for hvert par af elementer, som tilhører
  • At kløft indebærer, at
  • For ethvert element er opfyldt i ringen

Formel beskrivelse

Algoritmen kan udtrykkes i pseudokode som følger:

Analyse og implementering

  • Det første skridt kan gøres for at kontrollere, at. Dette kræver en tid
  • Det andet trin kan gennemføres søger den første værdi til at kontrollere for enhver værdi. Som dette trin udføres i en tid
  • I det tredje trin kan du bruge euklidisk algoritme til at finde den største fælles divisor af to tal. Efter behov beregne disse værdier, den tid der kræves, er
  • I det fjerde trin behøver du kun sammenligne de cifre. Det tager et stykke tid
  • Det femte trin er den langsomste af alle. Det kan bruge en variant af potensopløftning ved kvadrering at beregne venstre side af hver kongruens. Det er nødvendigt at beregne disse kongruenser. Derfor dette trin tager tid

Derfor AKS algoritme kræver tid. Det vil sige, at algoritmen løser problemet AKS primtal og deterministisk i polynomiel tid. I praksis algoritmen synes at køre ad gangen. Denne gang kunne altid bevise som formodninger af to primtal er påvist.

Forrige artikel Arucas