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 .
Ha létezik olyan, hogy és bármely 1-től ig , akkor vagy prímszám, vagy prímszám hatványa.
|
Itt és lent , jelöli a kitevő modulo , a bináris logaritmus és az Euler függvény [1] .
Összehasonlítás az űrlap két moduljával
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] .
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] .
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] .
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] .
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] .
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] .
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] :
|
|
egy |
Más szóval, ha , , és gcd , akkor akkor és csak akkor prím, ha az (1) feltétel teljesül .
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 :
amelyet úgy kapunk, hogy az eredeti kifejezés mindkét részét elosztjuk [7]-el .
Itt az ellenőrizendő értékek számát és az értéket már a [8] -tól származó polinom korlátozza .
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ő:
Agrawal, Kayal és Saxena bebizonyította, hogy az algoritmus akkor és csak akkor ad vissza "prímszámot" , ha az prímszám.
Lenstra és Pomerance közzétette az algoritmus továbbfejlesztett változatát [8] [4] :
Bemenet: ,Itt a függvény ugyanaz, ez egy nagyobb fokú polinom, mint , így bizonyos további feltételek mellett [1] [8] .
Ennek az algoritmusnak a számítási bonyolultsága .
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 :
Ez az alcsoport, nevezzük csoportnak , már tartalmazza a -t . A csoport modulo generálódik , és mivel , akkor .
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] .
Az algoritmus indoklásában használt fő köztes lemmák és definíciók [2] :
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] .
Számelméleti algoritmusok | |
---|---|
Egyszerűség tesztek | |
Prímszámok keresése | |
Faktorizáció | |
Diszkrét logaritmus | |
GCD keresése | |
Modulo aritmetika | |
Számok szorzása és osztása | |
A négyzetgyök kiszámítása |