Agrawala-Kayala-Saxene teszt

Az Agrawal-Kayal-Saxena teszt ( AKS teszt ) az egyetlen jelenleg ismert univerzális (azaz minden számra alkalmazható) polinomiális , determinisztikus és feltétel nélküli (vagyis nem bizonyítatlan hipotézisektől függő) teszt a számok elsődlegességének meghatározására, Fermat polinomokra vonatkozó kis tételének általánosítása .

Megfogalmazás

Ha létezik olyan, hogy és bármely 1-től ig , akkor vagy prímszám, vagy prímszám hatványa. $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$

Itt és lent , jelöli a kitevő modulo , a bináris logaritmus és az Euler függvény [1] . $o_{r}(n)$ $n$ $r$ $\log$ $\varphi (\cdot )$

Összehasonlítás az űrlap két moduljával

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

polinomoknál azt jelenti, hogy létezik olyan, hogy a polinom összes együtthatója többszöröse , ahol a polinomok gyűrűje egész számok felett [ 1] . $a(x),\;b(x)\in \mathbb {Z} [x]$ $g(x)\in \mathbb {Z} [x]$ ${\megjelenítési stílus a(x)-b(x)-g(x)h(x)}$ $n$ $\mathbb {Z} [x]$ $x$

Történelem

Az AKS-tesztet Manindra Agrawalindiai tudós , valamint két tanítványa, Niraj Kayal és Nitin SaxenaTechnológiai Intézet Kanpurbanaugusztus 6-án publikálták először , 2002 [2] . A jelen publikáció előtt nyitott probléma volt az elsődlegesség felismerésének problémájának a P osztályhoz való tartozása .

Az eredeti algoritmus számítási bonyolultságát a következőképpen becsüljük meg . Feltételezve , hogy Artin sejtése igaz , a futási idő -ra javul . Sophie Germain hipotézisének helyességét feltételezve az idő is hajlik [2] . ${\mathcal {O}}(\log ^{21/2}n)$ ${\mathcal {O}}(\log ^{6}n)$ ${\mathcal {O}}(\log ^{6}n)$

2005- ben a Lenstra és a Pomerance kiadta az algoritmus továbbfejlesztett változatát számítási összetettséggel , ahol a teszttel ellenőrizendő szám [3] [4] . ${\mathcal {O}}(\log ^{6}n)$ $n$

Agrawal sejtése szerint létezik az algoritmusnak egy futásidejű változata , de Lenstra és Pomerans egy heurisztikus érvet mutatott be, amely megerősítette ennek a hipotézisnek a hamisságát [2] . ${\mathcal {O}}(\log ^{3}n)$

Ennek az algoritmusnak nagy elméleti jelentősége van, de a gyakorlatban nem használják, mivel számítási bonyolultsága sokkal nagyobb, mint a legjobb valószínűségi algoritmusoké [5] . Felfedezésükért a szerzők 2006 -ban Gödel -díjat és Fulkerson-díjat kaptak [6] .

Alaptulajdonságok

Az algoritmus fő tulajdonsága, hogy egyszerre univerzális , polinom , determinisztikus és feltétel nélküli [5] , a korábbi algoritmusok ebből a négy tulajdonságból maximum hárommal rendelkeztek.

A teszt univerzalitása azt jelenti, hogy bármely szám elsődlegességének tesztelésére használható. Számos gyorstesztet arra terveztek, hogy egy korlátozott készletből származó számokat teszteljenek. Például a Lucas-Lehmer teszt csak Mersenne-számokra működik , míg a Pepin-teszt csak Fermat-számokra [6] .

A polinom azt jelenti, hogy az algoritmus maximális futási idejét az ellenőrzött szám számjegyeinek polinomja korlátozza. Ugyanakkor az olyan tesztek, mint az elliptikus görbe teszt (ECPP) és az Adlemann-Pomerance-Rumeli teszt (APR) igazolhatják vagy cáfolhatják egy szám egyszerűségét, de nem bizonyították, hogy a futási idő polinomiális lesz. tetszőleges bemeneti szám [6] .

A determinizmus egyedi előre meghatározott eredményt garantál. Valószínűségi tesztek , mint például a Miller-Rabin teszt és a Bailey-Pomeranz-Selfridge-Wagstaff teszt , meg tudják vizsgálni, hogy egy szám prím-e polinomiális időben, de csak valószínűségi választ adnak [6] .

A feltétel nélküliség az a tulajdonsága, hogy egy algoritmus helyessége nem függ igazolatlan hipotézisektől. Például a Miller-teszt nem rendelkezik ezzel a tulajdonsággal, amely bár determinisztikus és polinomiális időben működik bármilyen bemeneti számra, helyessége a bizonyítatlan általánosított Riemann-hipotézistől függ [6] .

Fő ötlet

Az algoritmus fő gondolata a Fermat-féle kis tétel polinomokra történő általánosítása, amely kimondja, hogy mindenre (ahol a gyűrűt inverzek nélkül veszi szorzás és nulla elem) és , akkor és csak akkor egyszerű, ha [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)).$

egy

Más szóval, ha , , és gcd , akkor akkor és csak akkor prím, ha az (1) feltétel teljesül . $a\in \mathbb {Z}$ $n\in \mathbb{N}$ $n\geqslant 2$ $(a,\;n)=1$ $n$

Ennek a kifejezésnek a tesztelése időbe telik, becslése szerint , mert a legrosszabb esetben a bal oldalon lévő együtthatókat kell kiértékelni. Az együtthatók számának és a számítások bonyolultságának csökkentése érdekében a [2] kifejezést választottuk az egyszerűség tesztjeként : $\omega(n)$ $n$ $r$

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

amelyet úgy kapunk, hogy az eredeti kifejezés mindkét részét elosztjuk [7]-el . $x^{r}-1$

Itt az ellenőrizendő értékek számát és az értéket már a [8] -tól származó polinom korlátozza . $a$ $r$ $\log n$

Ebben az esetben a hányados gyűrű helyett azt a mezőt tekintjük , ahol egy véges mező irreducibilis osztója a -tól eltérő . A mező azon polinomjainak száma, amelyekre összehasonlításra kerül, a következő: $\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)).

Algoritmus és módosítása

Bemenet: egész szám .

n>1

Ha egész számokra és , adja vissza az "összetett" értéket . $n=a^{b}$ $a>1$ $b>1$
Keresse meg a legkisebbet . $r$ ${\displaystyle o_{r}(n)>(\log _{2}(n))^{2))$
Ha a gcd néhányhoz tartozik , adja vissza a "kompozit" kifejezést . $1<$ $(a,\;n)<n$ $a\leqslant r$
Ha , adja vissza az "egyszerű" kifejezést . $n\leqslant r$
Ha 1-től mindenre igaz, hogy , adja vissza az "egyszerű" kifejezést . $a$ $\left\lfloor {\sqrt {\varphi (r)))\log(n)\right\rfloor$ $(x+a)^{n}\equiv x^{n}+a{\pmod {x^{r}-1,\;n))$
Ellenkező esetben az "összetett" értéket adja vissza .

Agrawal, Kayal és Saxena bebizonyította, hogy az algoritmus akkor és csak akkor ad vissza "prímszámot" , ha az prímszám. $n$

Lenstra és Pomerance közzétette az algoritmus továbbfejlesztett változatát [8] [4] :

Bemenet: ,

n\in \mathbb{N}

n>1

Ha a és egész szám , akkor adja vissza az "összetett" értéket . $n=a^{b}$ $a\in \mathbb {N}$ $b>1$
Keressük meg a legkisebbet . $r$ $o_{r}(n)>(log_{2}(n))^{2}$
Ha a gcd értéke bármely , adja vissza a "kompozit" értéket . $(a,\;n)\neq 1$ $a\leqslant r$
Ha 1-től mindenre igaz, hogy , adja vissza az "egyszerű" kifejezést . $a$ $\left\lfloor {\sqrt {r}}\log n\right\rfloor$ $(x+a)^{n}\equiv x^{n}+a{\pmod {\varphi (x),\;n))$
Ellenkező esetben az "összetett" értéket adja vissza .

Itt a függvény ugyanaz, ez egy nagyobb fokú polinom, mint , így bizonyos további feltételek mellett [1] [8] . $\varphi(x)$ $x^{r}-1$ $\log ^{2}n$ $\varphi (x^{n})\equiv 0{\pmod {\varphi (x)))$

Ennek az algoritmusnak a számítási bonyolultsága . ${\mathcal {O}}(\log ^{6}n)$

Indoklás

Az indoklás egy csoportot használ – az összes olyan számból álló csoportot, amelyek a [9] halmazból származó számok modulo maradékai : $G$ $r$

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

Ez az alcsoport, nevezzük csoportnak , már tartalmazza a -t . A csoport modulo generálódik , és mivel , akkor . $G$ $(n,\;r)=(p,\;r)=1$ $G$ $n, p$ $r$ $o_{r}(n)>\log ^{2}n$ $|G|=t>\log ^{2}n$

A bizonyításban használt második csoport, a (prímtér) modulo és -beli összes polinomi maradék halmaza . Ezt a csoportot a mező elemei hozzák létre, és a mező multiplikatív csoportjának egy alcsoportja [9] . $|{\mathcal {G}}|$ $P$ $h(x)$ $p$ $x,\;x+1,\;x+2,\;\ldots ,\;x+l$ $F=\mathbb {F} _{p}[x]/\langle h(x)\rangle$ $\mathbb {F} _{p}$

Az algoritmus indoklásában használt fő köztes lemmák és definíciók [2] :

Legyen , , és gcd . Akkor az első számú akkor és csak akkor $a,\;n\in \mathbb {Z}$ $n\geqslant 2$ $(a,\;n)=1$ $n$ $(x+a)^{n}\equiv x^{n}+a{\pmod {n)).$
Jelölje LCM az első számok legkisebb közös többszörösét . Ekkor a következő egyenlőtlenség érvényes: ${\megjelenítési stílus (m)}$ $m$ $m\geqslant 7$ NEM C $(m)\geqslant 2^{m}.$
Van olyan hogy , olyan hogy . $r$ ${\displaystyle r\leqslant \max {\big (}3,\;\lceil \log ^{5}n\rceil {\big )))$ $o_{r}(n)>\log ^{2}n$
Meghatározás. Polinom és szám esetén megmondja, hogy mit tartalmaz az if . $f(x)$ $m\in \mathbb {N}$ $m$ $f(x)$ $\lceil f(x)\rceil ^{m}\equiv f(x^{m}){\pmod {x^{r}-1,\;p))$
Ha a és számok szerepelnek a -ban , akkor a termékük is benne van. $m$ $m'$ $f(x)$ $m\cdot m'$
Ha a szám szerepel a és -ben , akkor az is benne van . $m$ $f(x)$ $g(x)$ $m$ $f(x)\cdot g(x)$
Lenstra lemmája . . $|{\mathcal {G}}|\geqslant {\tbinom {t+l}{t-1}}$
Ha nem végzettség , akkor . $n$ $p$ $|{\mathcal {G}}|\leqslant n^{\sqrt {t}}$

Gyakorlati alkalmazás

Egy paraméter kiértékelésekor az algoritmus 1 000 000 000 GB ( gigabájt ) memóriát igényel 1024 bites számokhoz. A modern operációs rendszerek számára ez túl sok információ. Feltételezve Artin hipotézisének és Sophie Germain hipotézisének a prímek halmazának sűrűségére vonatkozó helyességét , a -re becsült paraméter értéke elegendő lesz az algoritmushoz . Ebben az esetben 1 GB memória elég lesz. Amíg azonban ezeknek a hipotéziseknek a helyessége nem bizonyított, addig az algoritmust a bonyolult végrehajtás miatt nem alkalmazzuk. Donald Knuth , aki az algoritmust a The Art of Programming második kötetében (3. kötet) helyezte el, magánlevelezésben megjegyezte annak pusztán elméleti jellegét [6] . $r={\mathcal {O}}(\log ^{5}n)$ $r$ ${\mathcal {O}}(\log ^{2}n)$

Jegyzetek

↑ 1 2 3 Agafonova, 2009 .
↑ 1 2 3 4 5 6 Agrawal, Kayal, Saxena, 2004 .
↑ H. W. Lenstra Jr. és Carl Pomerance, " Primality Testing with Gaussian Periods Archivált : 2021. április 28., a Wayback Machine ", előzetes verzió 2005. július 20.
↑ 1 2 H. W. Lenstra Jr. és Carl Pomerance, " Primality testing with Gaussian periods Archivált : 2012. február 25. a Wayback Machine -nél ", 2011. április 12-i verzió.
↑ 1 2 Barash, 2005 .
↑ 1 2 3 4 5 6 Cao, Liu, 2014 .
↑ 12 Menon , 2007 , pp. 10-11.
↑ 1 2 3 4 Salembier, Southerington, 2005 .
↑ 1 2 Agrawal, Kayal, Saxena, 2004 , p. 5.

Irodalom

Barash L. Yu. Az AKS-algoritmus a számok elsődlegességének ellenőrzésére és a pszeudo-véletlen számgenerátorok állandóinak keresésére // Információs technológiák biztonsága. - 2005. - 2. sz . - S. 27-38 . Az eredetiből archiválva : 2014. október 18.
Agafonova IV Számok ellenőrzése az egyszerűség kedvéért: polinomiális algoritmus // Szeminárium a diszkrét harmonikus elemzésről és a geometriai modellezésről. – 2009.

angolul

Agrawal M. , Kayal N. , Saxena N. PRIMES itt található: P // Ann . Math. / 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, Az AKS-osztályú elsődlegességi tesztek végrehajtásáról , 2003.
Salembier R. G. , Southerington P. An Implementation of the AKS Primality Test - 2005. - az eredeti algoritmus és a Lenstra-algoritmus implementációinak összehasonlítása különböző könyvtárak segítségével.
Zhengjun Cao, Lihua Liu. Megjegyzések az AKS primalitástesztelési algoritmusához és a P definíció hibájához . - 2014. - arXiv : 1402.0146v1 .
Granville A. Könnyű meghatározni, hogy egy adott egész prímszám -e // Bull . , New Ser., Am. Math. szoc. / S. Friedlander - Providence, RI : American Mathematical Society , 2005. - Vol. 42, Iss. 1. - P. 3-38. — ISSN 0273-0979 ; 1088-9485 - doi:10.1090/S0273-0979-04-01037-7
Agrawal, M. és Kayal, N. és Saxena, N. Polinomiális idődeterminisztikus módszer a számok elsődlegességének tesztelésére . US 20050027764A1 számú szabadalom . Letöltve: 2013. december 15.
Rotella C. Az aks polinomiális idejű primalitás-bizonyító algoritmus hatékony megvalósítása . – Pittsburgh, Pennsylvania, USA: Számítástechnikai Iskola – Carnegie Mellon Egyetem, 2005.
Vijay Menon. Determinisztikus primalitásteszt – az AKS algoritmus megértése // CoRR . - 2007. - Vol. abs/1311.3785 .

Linkek

Weisstein, Eric W. AKS Primality Test (angol) a Wolfram MathWorld webhelyen . – rövid tájékoztatás az AKS tesztről
Phil Carmody. Az AKS "PRIMES in P" algoritmus erőforrása . Letöltve: 2014. október 19. - az algoritmussal kapcsolatos anyagok áttekintése
Li, H. Az AKS algoritmus elemzése és megvalósítása, valamint javítási algoritmusai . — 2013.
Pedro Berrizbetia. A "prímszám P-ben van" élesítése egy nagy számcsaládhoz. (angol) . – 2011.

Számelméleti algoritmusok
Egyszerűség tesztek	Molnár Miller – Rabin Luca - Lemaire pepina Agrawala – Kayala – Szászország Nightingale - Strassen
Prímszámok keresése	Iteráció osztók felett Eratoszthenész szita Atkin szitája Szita Sundarama
Faktorizáció	Iteráció osztók felett Fermat módszer p −1 Pollard-módszer Pollard ρ-algoritmusa Lehmann módszer Elliptikus görbe módszer (Lenstra-algoritmus) Dixon algoritmusa Négyzet alakú szita
Diszkrét logaritmus	Gelfond-Shanks algoritmus Polig-Hellman algoritmus Pollard ρ-módszere Pollard kenguru algoritmusa Adleman algoritmusa COS algoritmus
GCD keresése	Euklidész algoritmusa Speciális algoritmus Bináris algoritmus
Modulo aritmetika	Montgomery algoritmusa Kínai maradék tétel
Számok szorzása és osztása	Karatsuba algoritmus Toom-Cook algoritmus Schönhage-Strassen algoritmus Führer algoritmus Harvey-van der Hoeven algoritmus Burnickel-Ziegler algoritmus
A négyzetgyök kiszámítása	Tonelli-Shanks algoritmus Berlekamp-Rabin algoritmus