szó jelentését keresi. A DICTIOUS-ban nem csak a
szó összes szótári jelentését megtalálod, hanem megismerheted az etimológiáját, a jellemzőit és azt is, hogyan kell a
szót egyes és többes számban mondani. Minden, amit a
szóról tudni kell, itt található. A
szó meghatározása segít abban, hogy pontosabban és helyesebben fogalmazz, amikor beszélsz vagy írsz. A
és más szavak definíciójának ismerete gazdagítja a szókincsedet, és több és jobb nyelvi forráshoz juttat.
Főnév
AKS primality test (tsz. AKS primality tests)
- (informatika) AKS-algoritmus
Az AKS-prímszámteszt
A prímszámok, azaz a csak önmagukkal és 1-gyel osztható természetes számok, a matematika egyik legalapvetőbb, ugyanakkor legizgalmasabb objektumai. Évezredek óta kutatják őket, nemcsak elméleti, hanem gyakorlati okokból is: modern kriptográfiai rendszerek alapja például a nagy prímszámok előállítása és felismerése.
A prímszámteszt azt a kérdést válaszolja meg, hogy egy adott pozitív egész szám prím-e vagy sem.
A probléma háttere
A prímszámtesztelésre évszázadok során számos algoritmust dolgoztak ki:
- Primitív módszerek: osztók keresése
-ig.
- Fermat-próbák, Miller–Rabin, Solovay–Strassen: ezek valószínűségi tesztek (nem determinisztikusak). Nagyon gyorsak, de van kicsi esély a tévedésre.
- Elliptikus görbéken alapuló módszerek.
2002-ben azonban szenzációs áttörés történt. Manindra Agrawal, Neeraj Kayal és Nitin Saxena indiai matematikusok bemutatták az első determinista, polinomiális időben futó, általános prímszámtesztet: az AKS-prímszámtesztet.
Korábban a P ≠ NP probléma szempontjából is kérdéses volt, hogy létezhet-e ilyen algoritmus.
Az AKS-teszt tehát:
✅ determinista ✅ polinomiális időigényű ✅ minden természetes számra működik ✅ nem támaszkodik nem bizonyított sejtésekre
Ez egy elméleti áttörés volt. Gyakorlatban továbbra is valószínűségi módszereket használunk, mert azok sokkal gyorsabbak.
Az AKS-teszt matematikai alapja
A teszt egy rendkívül elegáns polinomazonosságon alapul, amit a következőképpen lehet megfogalmazni:
Egy
szám prím akkor és csak akkor, ha minden
-ra teljesül az alábbi kongruencia modulo
:
vagyis a polinom kifejtve, modulo
, redukálódik a fenti alakra.
Miért érdekes ez?
- Ha
prím, akkor a binomiális tétel miatt a köztes együtthatók mind oszthatók
-nel, tehát eltűnnek.
- Ha
összetett, akkor ez az azonosság általában nem teljesül.
Gond
A fenti egyenlőséget polinomként kell ellenőrizni. De ha
nagy, akkor az
polinomnak akár
fokú tagjai is lehetnek, ami exponenciális számítási költséggel járna.
Megoldás: a polinomot nem csak
, hanem
szerint is redukáljuk.
Így a polinom maradéka maximum
fokú lesz → kezelhető.
Az AKS-algoritmus lépései
Az AKS-algoritmus az alábbi lépésekből áll:
1. Ellenőrzés, hogy
prímhatvány-e
Először vizsgáljuk meg, hogy
nem prímhatvány-e, azaz van-e olyan
, hogy
,
.
Ha igen, akkor
összetett → visszatérünk.
2. Megfelelő
kiválasztása
Keressünk egy kis
számot, hogy a következő feltétel teljesüljön:
Itt
az
multiplikatív rendje modulo
, azaz a legkisebb
, hogy
.
Ez az
a polinom-redukcióhoz szükséges.
3. Közös osztók keresése
Minden
esetén számítsuk ki
-t.
- Ha találunk
-t → n összetett.
- Ha minden ilyen
-ra
, lépjünk tovább.
4. Nagy
esetén rövid-circuit
Ha
, akkor n prím.
5. A polinomteszt
Végül ellenőrizzük a következő azonosságot polinomként modulo
,
-re, néhány
értékre (konkrétan
sokra):
Ha bármelyik
-ra az azonosság nem teljesül, akkor
összetett.
Ha mindegyikre teljesül → n prím.
Példa
Nézzük pl. az
esetet (prím):
- 1. lépés: nem prímhatvány.
- 2. lépés: válasszunk pl.
, elég lesz.
- 3. lépés:
,
.
- 4. lépés:
, tehát megyünk tovább.
- 5. lépés: ellenőrizzük pl.
-re a polinomazonosságot:
Így az azonosság teljesül → 7 prím.
Bonyolultság
Az eredeti AKS algoritmus időkomplexitása:
Később optimalizálták
környékére.
Ma már elméletben polinomiális idő, de gyakorlatban továbbra is lényegesen lassabb, mint a Miller–Rabin.
Miért fontos az AKS-teszt?
- Első bizonyítottan determinisztikus polinomiális idejű algoritmus minden
-re.
- Nem függ nem bizonyított sejtésektől (pl. Riemann-sejtés).
- Elméleti mérföldkő a számelméletben.
- A P vs NP kérdés kapcsán is komoly jelentőségű volt.
Gyakorlati használat
Bár az AKS algoritmus rendkívül elegáns, gyakorlati célra ritkán használják:
- A Miller–Rabin teszt több nagyságrenddel gyorsabb.
- A nagy prímek előállításában még mindig a valószínűségi tesztek dominálnak.
Az AKS-t főleg bizonyítási eszközként értékeljük.
Összefoglalás
Az AKS-prímszámteszt:
- Nagy elméleti áttörés (2002).
- Determinista, polinomiális időben fut.
- Polinomazonosságon alapul.
- Nem függ nem bizonyított matematikai sejtésektől.
- Gyakorlatban lassú, de elméletben forradalmi.
Az algoritmus alapötlete: a prímszámok egy egyszerű, elegáns polinomazonossággal felismerhetők.
Ez megoldotta az évezredes nyitott kérdést: létezik hatékony, determinisztikus általános prímszámteszt.