Agrawala-Kayala-Saxene test

Agrawal-Kayal-Saxena-testet ( AKS-testet ) är det enda för närvarande kända universella (det vill säga tillämpligt på alla tal) polynom , deterministiskt och ovillkorligt (det vill säga inte beroende av obevisade hypoteser) test av talens primatitet, baserat på en generalisering av Fermats lilla sats om polynom.

Formulering

Om det finns ett sådant och för någon från 1 till , är det antingen ett primtal eller en potens av ett primtal. $r\in \mathbb {Z}$ $o_{r}(n)>\log ^{2}n$ $a$ $\left\lfloor {\sqrt {\varphi (r)))\log(n)\right\rfloor$ $(x+a)^{n}\equiv (x^{n}+a){\pmod {x^{r}-1,\;n))$
$n$

Här och nedan , betecknar exponenten modulo , är den binära logaritmen och är Euler-funktionen [1] . $o_{r}(n)$ $n$ $r$ $\logga$ $\varphi (\cdot )$

Jämförelse med två moduler av formuläret

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

för polynom betyder att det finns så att alla koefficienter av polynomet är multipler av , där är ringen av polynom från över 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$

Historik

AKS-testet föreslogs av den indiska forskaren Manindra Agrawal och hans två elever Niraj Kayal och Nitin Saxena från Indian Institute of Technology Kanpur och publicerades först den 6 augusti , 2002 [2] . Före denna publikation var det ett öppet problem att problemet med erkännande av primäritet tillhörde klassen P.

Beräkningskomplexiteten för den ursprungliga algoritmen uppskattas till . Förutsatt att Artins gissningar är sanna förbättras körtiden till . Om man antar att Sophie Germains hypotes är korrekt , tenderar tiden också att [2] . ${\mathcal {O}}(\log ^{21/2}n)$ ${\mathcal {O}}(\log ^{6}n)$ ${\mathcal {O}}(\log ^{6}n)$

2005 publicerade Lenstra och Pomerance en förbättrad version av algoritmen med beräkningskomplexitet , där är numret som ska kontrolleras av testet [3] [4] . ${\mathcal {O}}(\log ^{6}n)$ $n$

Enligt Agrawals gissning finns det en variant av algoritmen med runtime , men Lenstra och Pomerans presenterade ett heuristiskt argument som bekräftar falskheten i denna hypotes [2] . ${\mathcal {O}}(\log ^{3}n)$

Denna algoritm är av stor teoretisk betydelse, men används inte i praktiken, eftersom dess beräkningskomplexitet är mycket högre än den för de bästa probabilistiska algoritmerna [5] . För sin upptäckt fick författarna Gödelpriset och Fulkersonpriset 2006 [ 6] .

Grundläggande egenskaper

Algoritmens huvudsakliga egenskap är att den samtidigt är universell , polynomisk , deterministisk och ovillkorlig [5] , tidigare algoritmer hade maximalt endast tre av dessa fyra egenskaper.

Testets universalitet innebär att det kan användas för att testa primaaliteten av vilket nummer som helst. Många snabba tester är utformade för att testa siffror från en begränsad uppsättning. Till exempel fungerar Lucas-Lehmer-testet bara för Mersenne-nummer , medan Pepins test bara fungerar för Fermat-nummer [6] .

Polynom betyder att den maximala körtiden för algoritmen begränsas av ett polynom i antalet siffror i numret som kontrolleras. Samtidigt kan tester som det elliptiska kurvtestet (ECPP) och Adlemann-Pomerance-Rumeli-testet (APR) bevisa eller motbevisa enkelheten hos ett tal, men de har inte bevisats att körtiden kommer att vara polynom för valfritt inmatat nummer [6] .

Determinism garanterar ett unikt fördefinierat resultat. Probabilistiska tester , som Miller-Rabin-testet och Bailey-Pomeranz-Selfridge-Wagstaff-testet , kan testa om ett tal är primtal i polynomtid, men ger bara ett probabilistiskt svar [6] .

Ovillkorlighet är egenskapen att riktigheten av en algoritm inte beror på några obevisade hypoteser. Till exempel har Miller-testet inte den här egenskapen , som även om den är deterministisk och fungerar i polynomtid för alla inmatade tal, beror dess korrekthet på den obevisade generaliserade Riemann-hypotesen [6] .

Huvudidé

Huvudidén med algoritmen är en generalisering av Fermats lilla sats till polynom, som säger att för alla (där ringen tas utan inverser av multiplikation och nollelement) och , är enkel om och bara om [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)).$

ett

Med andra ord, if , , och gcd , då är prime om och endast om villkor (1) är uppfyllt . $a\in \mathbb {Z}$ $n\in \mathbb{N}$ $n\geqslant 2$ $(a,\;n)=1$ $n$

Detta uttryck tar tid att testa, uppskattat till , eftersom i värsta fall bör koefficienterna på vänster sida utvärderas. För att minska antalet koefficienter och komplexiteten i beräkningar valdes det att använda uttrycket [2] som ett test för enkelheten : $\omega(n)$ $n$ $r$

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

som erhålls genom att dividera båda delarna av det ursprungliga uttrycket med [7] . $x^{r}-1$

Här är antalet värden som ska kontrolleras och värdet redan begränsat av polynomet från [8] . $a$ $r$ $\log n$

I det här fallet, istället för en kvotring , betraktar vi fältet , där är en irreducibel divisor över ett ändligt fält , annorlunda än . Antalet polynom i detta fält som jämförelse utförs för uppskattas: $\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)).

Algoritm och dess modifiering

Inmatning: heltal .

n>1

Om för heltal och , returnera "composite" . ${\displaystyle n=a^{b))$ $a>1$ $b>1$
Hitta den minsta så att . $r$ ${\displaystyle o_{r}(n)>(\log _{2}(n))^{2))$
Om gcd är för vissa , returnera "composite" . $1<$ $(a,\;n)<n$ $a\leqslant r$
Om , returnera "enkel" . $n\leqslant r$
Om för alla från 1 till det är sant att , returnera "enkel" . $a$ $\left\lfloor {\sqrt {\varphi (r)))\log(n)\right\rfloor$ $(x+a)^{n}\equiv x^{n}+a{\pmod {x^{r}-1,\;n))$
Annars returnerar du "komposit" .

Agrawal, Kayal och Saxena bevisade att algoritmen kommer att returnera ett "primtal" om och bara om är ett primtal. $n$

Lenstra och Pomerance publicerade en förbättrad version av algoritmen [8] [4] :

Inmatning: ,

n\in \mathbb{N}

n>1

Om för och heltal , returnera "composite" . ${\displaystyle n=a^{b))$ $a\in \mathbb {N}$ $b>1$
Låt oss hitta den minsta sådan att . $r$ $o_{r}(n)>(log_{2}(n))^{2}$
Om gcd är för någon , returnera "composite" . $(a,\;n)\neq 1$ $a\leqslant r$
Om för alla från 1 till det är sant att , returnera "enkel" . $a$ $\left\lfloor {\sqrt {r}}\log n\right\rfloor$ $(x+a)^{n}\equiv x^{n}+a{\pmod {\varphi (x),\;n))$
Annars returnerar du "komposit" .

Här är funktionen densamma, det är ett polynom av grad större än , så att under vissa ytterligare villkor [1] [8] . $\varphi(x)$ $x^{r}-1$ $\log ^{2}n$ $\varphi (x^{n})\equiv 0{\pmod {\varphi (x)))$

Beräkningskomplexiteten för denna algoritm är . ${\mathcal {O}}(\log ^{6}n)$

Motivering

Motiveringen använder en grupp — en grupp av alla tal som är modulo-rester för tal från mängden [9] : $G$ $r$

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

Den här undergruppen, låt oss kalla den gruppen , innehåller redan . Gruppen genereras modulo , och sedan dess . $G$ $(n,\;r)=(p,\;r)=1$ $G$ $n, sid$ $r$ $o_{r}(n)>\log ^{2}n$ $|G|=t>\log ^{2}n$

Den andra gruppen som används i beviset, , är mängden av alla polynomrester i (primtal) modulo och . Denna grupp genereras av element i fältet och är en undergrupp till fältets multiplikativa grupp [9] . $|{\mathcal {G}}|$ $P$ $h(x)$ $sid$ $x,\;x+1,\;x+2,\;\ldots ,\;x+l$ $F=\mathbb {F} _{p}[x]/\langle h(x)\rangle$ $\mathbb {F} _{p}$

De viktigaste mellanliggande lemman och definitioner som används i motiveringen av algoritmen [2] :

Låt , och gcd . Då är prime om och bara om $a,\;n\in \mathbb {Z}$ $n\geqslant 2$ $(a,\;n)=1$ $n$ $(x+a)^{n}\equiv x^{n}+a{\pmod {n)).$
Låt LCM beteckna den minsta gemensamma multipeln av de första talen. Då gäller följande ojämlikhet för: $(m)$ $m$ $m\geqslant 7$ NOC $(m)\geqslant 2^{m}.$
Det finns sånt där , sånt där . $r$ ${\displaystyle r\leqslant \max {\big (}3,\;\lceil \log ^{5}n\rceil {\big )))$ $o_{r}(n)>\log ^{2}n$
Definition. För ett polynom och ett tal står det vad som ingå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))$
Om siffrorna och ingår i , så ingår även deras produkt . $m$ $m'$ $f(x)$ $m\cdot m'$
Om numret ingår i och , så ingår det också i . $m$ $f(x)$ $g(x)$ $m$ $f(x)\cdot g(x)$
Lenstras lemma . . $|{\mathcal {G}}|\geqslant {\tbinom {t+l}{t-1}}$
Om det inte är en examen , då . $n$ $sid$ $|{\mathcal {G}}|\leqslant n^{\sqrt {t}}$

Praktisk tillämpning

Vid utvärdering av en parameter kräver algoritmen 1 000 000 000 GB ( gigabyte ) minne för antal på 1 024 bitar. För moderna operativsystem är detta för mycket information. Om man antar att Artins hypotes och Sophie Germains hypotes om tätheten av uppsättningen av primtal är korrekt, kommer värdet på parametern uppskattad till att vara tillräckligt för algoritmen . I det här fallet räcker det med 1 GB minne. Men tills riktigheten av dessa hypoteser är bevisad, tillämpas inte algoritmen på grund av den komplexa exekveringen. Donald Knuth , som placerade algoritmen i andra volymen av The Art of Programming (Vol. 3), noterade i privat korrespondens dess rent teoretiska karaktär [6] . $r={\mathcal {O}}(\log ^{5}n)$ $r$ ${\mathcal {O}}(\log ^{2}n)$

Anteckningar

↑ 1 2 3 Agafonova, 2009 .
↑ 1 2 3 4 5 6 Agrawal, Kayal, Saxena, 2004 .
↑ H. W. Lenstra Jr. och Carl Pomerance, " Primality Testing with Gaussian Periods Archived April 28, 2021 at the Wayback Machine ", preliminär version 20 juli 2005.
↑ 1 2 H. W. Lenstra Jr. och Carl Pomerance, " Primality testing with Gaussian periods Archived 25 February 2012 at the Wayback Machine ", version av 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 , sid. 5.

Litteratur

Barash L. Yu. AKS-algoritmen för att kontrollera siffror för primalitet och söka efter konstanter för pseudo-slumptalsgeneratorer // Security of Information Technologies. - 2005. - Nr 2 . - S. 27-38 . Arkiverad från originalet den 18 oktober 2014.
Agafonova IV Kontroll av siffror för enkelhetens skull: en polynomalgoritm // Seminarium om diskret harmonisk analys och geometrisk modellering. — 2009.

på engelska

Agrawal M. , Kayal N. , Saxena N. PRIMES är i P // Ann . Matematik. / J. Bourgain - Princeton University , 2004. - Vol. 160, Iss. 2. - P. 781-793. — ISSN 0003-486X ; 1939-8980 - doi:10.4007/ANNALS.2004.160.781
R. Crandall, Apple ACG, J. Papadopoulos, On the implementation of AKS-class primality tests , 2003.
Salembier R. G. , Southerington P. An Implementation of AKS Primality Test - 2005. - jämförelse av implementeringar av den ursprungliga algoritmen och Lenstras algoritm med hjälp av olika bibliotek.
Zhengjun Cao, Lihua Liu. Anmärkningar om AKS Primality Testing Algorithm och ett fel i definitionen av P . - 2014. - arXiv : 1402.0146v1 .
Granville A. Det är lätt att avgöra om ett givet heltal är 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. och Kayal, N. och Saxena, N. Polynomisk tidsdeterministisk metod för att testa tals primalitet . Patent US 20050027764A1 . Hämtad: 15 december 2013.
Rotella C. En effektiv implementering av aks polynomial-time primality proving algoritme . — Pittsburgh, Pennsylvania, USA: School of Computer Science-Carnegie Mellon University, 2005.
Vijay Menon. Deterministisk Primality Testing - förstå AKS-algoritmen // CoRR . - 2007. - Vol. abs/1311.3785 .

Länkar

Weisstein, Eric W. AKS Primality Test (engelska) på Wolfram MathWorlds webbplats . – kort information om AKS-testet
Phil Carmody. AKS "PRIMES in P"-algoritmresursen . Hämtad: 19 oktober 2014. - genomgång av material på algoritmen
Li, H. Analysen och implementeringen av AKS-algoritmen och dess förbättringsalgoritmer . — 2013.
Pedro Berrizbetia. Att skärpa "Primes is in P" för en stor familj av siffror. (engelska) . — 2011.

Talteoretiska algoritmer
Enkelhetstest	Mjölnare Miller - Rabin Luca - Lemaire pepina Agrawala - Kayala - Sachsen Nightingale - Strassen
Hitta primtal	Itererar över divisorer Sil av Eratosthenes Atkins såll Sikt Sundarama
Faktorisering	Itererar över divisorer Fermat-metoden p −1 Pollardmetoden Pollards ρ-algoritm Lehmanns metod Elliptisk kurvmetod (Lenstras algoritm) Dixons algoritm Fyrkantig sil
Diskret logaritm	Gelfond-Shanks algoritm Polig-Hellman algoritm Pollards ρ-metod Pollards kängurualgoritm Adlemans algoritm COS-algoritm
Hitta GCD	Euklids algoritm Avancerad algoritm Binär algoritm
Modulo aritmetik	Montgomerys algoritm Kinesisk restsats
Multiplikation och division av tal	Karatsuba algoritm Toom-Cook algoritm Schönhage-Strassen algoritm Fuhrer algoritm Harvey-van der Hoevens algoritm Burnickel-Ziegler algoritm
Beräkna kvadratroten	Tonelli-Shanks algoritm Berlekamp-Rabin algoritm