Agrawala-Kayala-Saxene test

Agrawal-Kayal-Saxena-testen ( AKS-testen ) er den eneste aktuelt kendte universelle (dvs. gældende for alle tal) polynomiske , deterministiske og ubetingede (det vil sige ikke afhængige af ubeviste hypoteser) test af tallenes primalitet, baseret på en generalisering af Fermats lille sætning om polynomier.

Ordlyd

Hvis der eksisterer sådan, at og for nogen fra 1 til , så er enten et primtal eller en potens af et primtal. $r\in \mathbb {Z}$ $o_{r}(n)>\log ^{2}n$ $-en$ $\left\lfloor {\sqrt {\varphi (r)))\log(n)\right\rfloor$ $(x+a)^{n}\equiv (x^{n}+a){\pmod {x^{r}-1,\;n))$
$n$

Her og nedenfor , betegner eksponenten modulo , er den binære logaritme og er Euler-funktionen [1] . $o_{r}(n)$ $n$ $r$ $\log$ $\varphi (\cdot)$

Sammenligning af to moduler af formularen

a(x)\equiv b(x){\pmod {h(x),\;n))

for polynomier betyder, at der eksisterer sådan, at alle koefficienter af polynomiet er multipla af , hvor er ringen af polynomier fra over heltal [1] . $a(x),\;b(x)\in \mathbb {Z} [x]$ $g(x)\in \mathbb {Z} [x]$ $a(x)-b(x)-g(x)h(x)$ $n$ $\mathbb {Z} [x]$ $x$

Historie

AKS-testen blev foreslået af den indiske videnskabsmand Manindra Agrawal og hans to elever Niraj Kayal og Nitin Saxena fra Indian Institute of Technology Kanpur og blev først offentliggjort den 6. august , 2002 [2] . Før denne publikation var tilhørsforholdet mellem problemet med anerkendelse af primalitet til klassen P et åbent problem .

Beregningskompleksiteten af den oprindelige algoritme estimeres til . Forudsat at Artins formodning er sand , forbedres køretiden til . Hvis man antager rigtigheden af Sophie Germains hypotese , har tiden også en tendens til at [2] . ${\mathcal {O}}(\log ^{21/2}n)$ ${\mathcal {O}}(\log ^{6}n)$ ${\mathcal {O}}(\log ^{6}n)$

I 2005 udgav Lenstra og Pomerance en forbedret version af algoritmen med beregningsmæssig kompleksitet , hvor er det tal, der skal kontrolleres af testen [3] [4] . ${\mathcal {O}}(\log ^{6}n)$ $n$

Ifølge Agrawals formodning er der en variant af algoritmen med runtime , men Lenstra og Pomerans præsenterede et heuristisk argument, der bekræfter falskheden af denne hypotese [2] . ${\mathcal {O}}(\log ^{3}n)$

Denne algoritme er af stor teoretisk betydning, men bruges ikke i praksis, da dens beregningsmæssige kompleksitet er meget højere end den for de bedste probabilistiske algoritmer [5] . For deres opdagelse modtog forfatterne Gödel -prisen og Fulkerson-prisen i 2006 [6] .

Grundlæggende egenskaber

Algoritmens hovedegenskab er, at den på én gang er universel , polynomiel , deterministisk og ubetinget [5] , tidligere algoritmer havde maksimalt kun tre af disse fire egenskaber.

Testens universalitet betyder, at den kan bruges til at teste primaaliteten af ethvert tal. Mange hurtige test er designet til at teste tal fra et begrænset sæt. For eksempel virker Lucas-Lehmer-testen kun for Mersenne-numre , mens Pepins test kun virker for Fermat-numre [6] .

Polynomium betyder, at den maksimale køretid for algoritmen er begrænset af et polynomium i antallet af cifre i det tal, der kontrolleres. Samtidig kan test som den elliptiske kurvetest (ECPP) og Adlemann-Pomerance-Rumeli-testen (APR) bevise eller modbevise et tals enkelthed, men det er ikke bevist, at køretiden vil være polynomium for ethvert inputnummer [6] .

Determinisme garanterer et unikt foruddefineret resultat. Probabilistiske test , såsom Miller-Rabin-testen og Bailey-Pomeranz-Selfridge-Wagstaff-testen , kan teste om et tal er primtal i polynomisk tid, men giver kun et sandsynlighedssvar [6] .

Ubetingelse er den egenskab, at rigtigheden af en algoritme ikke afhænger af nogen ubeviste hypoteser. For eksempel har Miller-testen ikke denne egenskab , som selvom den er deterministisk og fungerer i polynomisk tid for et hvilket som helst inputtal, afhænger dens rigtighed af den ubeviste generaliserede Riemann-hypotese [6] .

Hovedidé

Hovedideen med algoritmen er en generalisering af Fermats lille sætning til polynomier, der siger, at for alle (hvor ringen tages uden invers ved multiplikation og nul-element) og , er enkel, hvis og kun hvis [2] [7] [8] : $a\in \mathbb {Z} _{n}^{*}$ $\mathbb {Z} _{n}$ $n\in \mathbb {N}$ $n$

$(x+a)^{n}\equiv (x^{n}+a){\pmod {n)).$

Med andre ord, hvis , , og gcd , så er prime, hvis og kun hvis betingelse (1) er opfyldt . $a\in \mathbb {Z}$ $n\in \mathbb{N}$ $n\geqslant 2$ $(a,\;n)=1$ $n$

Dette udtryk tager tid at teste, estimeret til , fordi i værste fald bør koefficienterne på venstre side evalueres. For at reducere antallet af koefficienter og kompleksiteten af beregninger, blev det valgt at bruge udtrykket [2] som en test for enkelhed : $\omega(n)$ $n$ $r$

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

som opnås ved at dividere begge dele af det oprindelige udtryk med [7] . $x^{r}-1$

Her er antallet af værdier, der skal kontrolleres, og værdien allerede begrænset af polynomiet fra [8] . $-en$ $r$ $\log n$

I dette tilfælde betragter vi i stedet for en kvotientring feltet , hvor er en irreducerbar divisor over et endeligt felt , forskellig fra . Antallet af polynomier i dette felt, som sammenligning udføres for, er estimeret: $\mathbb {F} _{p}[x]/\langle x^{r}-1\rangle$ $F=\mathbb {F} _{p}[x]/\langle h\rangle$ $h=h(x)$ ${x^{r}-1}$ $\mathbb {F} _{p}$ $x-1$

(x+a)^{n}\equiv (x^{n}+a){\pmod {x^{r}-1,\;n)).

Algoritme og dens modifikation

Input: heltal .

n>1

Hvis for heltal og , returner "sammensat" . $n=a^{b}$ $a>1$ $b>1$
Find den mindste sådan at . $r$ $o_{r}(n)>(\log _{2}(n))^{2}$
Hvis gcd er for nogle , returner "composite" . $1<$ $(a,\;n)<n$ $a\leqslant r$
Hvis , returner "simpel" . $n\leqslant r$
Hvis for alle fra 1 til det er sandt, at , returnere "simpel" . $-en$ $\left\lfloor {\sqrt {\varphi (r)))\log(n)\right\rfloor$ $(x+a)^{n}\equiv x^{n}+a{\pmod {x^{r}-1,\;n))$
Ellers returnerer "sammensat" .

Agrawal, Kayal og Saxena beviste, at algoritmen vil returnere et "primtal" , hvis og kun hvis er et primtal. $n$

Lenstra og Pomerance udgav en forbedret version af algoritmen [8] [4] :

Input: ,

n\in \mathbb{N}

n>1

Hvis for og heltal , returner "composite" . $n=a^{b}$ $a\in \mathbb {N}$ $b>1$
Lad os finde den mindste sådan at . $r$ $o_{r}(n)>(log_{2}(n))^{2}$
Hvis gcd er for nogen , returner "composite" . $(a,\;n)\neq 1$ $a\leqslant r$
Hvis for alle fra 1 til det er sandt, at , returnere "simpel" . $-en$ $\left\lfloor {\sqrt {r}}\log n\right\rfloor$ $(x+a)^{n}\equiv x^{n}+a{\pmod {\varphi (x),\;n))$
Ellers returnerer "sammensat" .

Her er funktionen den samme, det er et polynomium af grad større end , sådan at under nogle yderligere betingelser [1] [8] . $\varphi(x)$ $x^{r}-1$ $\log ^{2}n$ $\varphi (x^{n})\equiv 0{\pmod {\varphi (x)))$

Den beregningsmæssige kompleksitet af denne algoritme er . ${\mathcal {O}}(\log ^{6}n)$

Begrundelse

Begrundelsen bruger en gruppe - en gruppe af alle tal, der er modulo-rester for tal fra mængden [9] : $G$ $r$

I=\left\{\left({\frac {n}{p}}\right)^{i}\cdot p^{j}\colon i,\;j\geqslant 0\right\} .

Denne undergruppe, lad os kalde den gruppen , indeholder allerede . Gruppen er genereret modulo , og siden da . $G$ $(n,\;r)=(p,\;r)=1$ $G$ $n, s$ $r$ $o_{r}(n)>\log ^{2}n$ $|G|=t>\log ^{2}n$

Den anden gruppe brugt i beviset, , er mængden af alle polynomierester i (prime rum) modulo og . Denne gruppe er genereret af elementer i feltet og er en undergruppe af feltets multiplikative gruppe [9] . $|{\mathcal {G}}|$ $P$ $h(x)$ $s$ $x,\;x+1,\;x+2,\;\ldots ,\;x+l$ $F=\mathbb {F} _{p}[x]/\langle h(x)\rangle$ $\mathbb {F} _{p}$

De vigtigste mellemliggende lemmaer og definitioner brugt i begrundelsen af algoritmen [2] :

Lad , , og gcd . Så er prime hvis og kun hvis $a,\;n\in \mathbb {Z}$ $n\geqslant 2$ $(a,\;n)=1$ $n$ $(x+a)^{n}\equiv x^{n}+a{\pmod {n)).$
Lad LCM betegne det mindste fælles multiplum af de første tal. Så gælder følgende ulighed for: $(m)$ $m$ $m\geqslant 7$ NOC $(m)\geqslant 2^{m}.$
Der er sådan at , sådan at . $r$ ${\displaystyle r\leqslant \max {\big (}3,\;\lceil \log ^{5}n\rceil {\big )))$ $o_{r}(n)>\log ^{2}n$
Definition. For et polynomium og et tal står der, hvad der indgår i if . $f(x)$ $m\in \mathbb {N}$ $m$ $f(x)$ $\lceil f(x)\rceil ^{m}\equiv f(x^{m}){\pmod {x^{r}-1,\;p))$
Hvis tallene og er inkluderet i , så er deres produkt også inkluderet. $m$ $m'$ $f(x)$ $m\cdot m'$
Hvis nummeret er inkluderet i og , så er det også inkluderet i . $m$ $f(x)$ $g(x)$ $m$ $f(x)\cdot g(x)$
Lenstras lemma . . $|{\mathcal {G}}|\geqslant {\tbinom {t+l}{t-1}}$
Hvis det ikke er en grad , så . $n$ $s$ $|{\mathcal {G}}|\leqslant n^{\sqrt {t}}$

Praktisk anvendelse

Når en parameter evalueres, kræver algoritmen 1.000.000.000 GB ( gigabyte ) hukommelse for tal på 1024 bit. For moderne operativsystemer er dette for meget information. Hvis man antager rigtigheden af Artins hypotese og Sophie Germains hypotese om tætheden af sættet af primtal, vil værdien af parameteren estimeret til være tilstrækkelig for algoritmen . I dette tilfælde vil 1 GB hukommelse være nok. Men indtil rigtigheden af disse hypoteser er bevist, anvendes algoritmen ikke på grund af den komplekse udførelse. Donald Knuth , som placerede algoritmen i andet bind af The Art of Programming (Vol. 3), bemærkede i privat korrespondance dens rent teoretiske karakter [6] . $r={\mathcal {O}}(\log ^{5}n)$ $r$ ${\mathcal {O}}(\log ^{2}n)$

Noter

↑ 1 2 3 Agafonova, 2009 .
↑ 1 2 3 4 5 6 Agrawal, Kayal, Saxena, 2004 .
↑ H. W. Lenstra Jr. og Carl Pomerance, " Primality Testing with Gaussian Periods Archived April 28, 2021 at the Wayback Machine ", foreløbig version 20. juli 2005.
↑ 1 2 H. W. Lenstra Jr. og Carl Pomerance, " Primality testing with Gaussian periods Archived 25 February 2012 at the Wayback Machine ", version af 12. april 2011.
↑ 1 2 Barash, 2005 .
↑ 1 2 3 4 5 6 Cao, Liu, 2014 .
↑ 12 Menon , 2007 , s. 10-11.
↑ 1 2 3 4 Salembier, Southerington, 2005 .
↑ 1 2 Agrawal, Kayal, Saxena, 2004 , s. 5.

Litteratur

Barash L. Yu. AKS-algoritmen til kontrol af tal for primalitet og søgning efter konstanter for pseudo-tilfældige talgeneratorer // Security of Information Technologies. - 2005. - Nr. 2 . - S. 27-38 . Arkiveret fra originalen den 18. oktober 2014.
Agafonova IV Kontrol af tal for enkelhed: en polynomiel algoritme // Seminar om diskret harmonisk analyse og geometrisk modellering. – 2009.

på engelsk

Agrawal M. , Kayal N. , Saxena N. PRIMES er i P // Ann . Matematik. / J. Bourgain - Princeton University , 2004. - Vol. 160, Iss. 2. - S. 781-793. — ISSN 0003-486X ; 1939-8980 - doi:10.4007/ANNALS.2004.160.781
R. Crandall, Apple ACG, J. Papadopoulos, Om implementeringen af AKS-klasse primalitetstest , 2003.
Salembier R. G. , Southerington P. En implementering af AKS Primality Test - 2005. - sammenligning af implementeringer af den originale algoritme og Lenstras algoritme ved hjælp af forskellige biblioteker.
Zhengjun Cao, Lihua Liu. Bemærkninger om AKS Primality Testing Algorithm og en fejl i definitionen af P . - 2014. - arXiv : 1402.0146v1 .
Granville A. Det er let at bestemme, om et givet heltal er primtal // Bull . , New Ser., Am. Matematik. soc. / S. Friedlander - Providence, RI : American Mathematical Society , 2005. - Vol. 42, Iss. 1. - S. 3-38. — ISSN 0273-0979 ; 1088-9485 - doi:10.1090/S0273-0979-04-01037-7
Agrawal, M. og Kayal, N. og Saxena, N. Polynomisk tidsdeterministisk metode til afprøvning af primaalitet af tal . Patent US 20050027764A1 . Hentet: 15. december 2013.
Rotella C. En effektiv implementering af aks polynomial-time primality proving algoritme . — Pittsburgh, Pennsylvania, USA: School of Computer Science-Carnegie Mellon University, 2005.
Vijay Menon. Deterministisk Primality Testing - forståelse af AKS-algoritmen // CoRR . - 2007. - Bd. abs/1311.3785 .

Links

Weisstein, Eric W. AKS Primality Test (engelsk) på Wolfram MathWorld- webstedet . – kort information om AKS-testen
Phil Carmody. AKS "PRIMES in P " Algoritmersource . Hentet: 19. oktober 2014. - gennemgang af materialer på algoritmen
Li, H. Analysen og implementeringen af AKS-algoritmen og dens forbedringsalgoritmer . - 2013.
Pedro Berrizbetia. Skærpning af "Primes er i P" for en stor familie af tal. (engelsk) . – 2011.

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