Ugrás a tartalomhoz

AKS primality test

A Wikiszótárból, a nyitott szótárból
(AKS primality test+ szócikkből átirányítva)


Főnév

AKS primality test (tsz. AKS primality tests)

  1. (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 n-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 n≥2 szám prím akkor és csak akkor, ha minden a∈ℤ-ra teljesül az alábbi kongruencia modulo n:

(x+a)n≡xn+a(modn)

vagyis a polinom kifejtve, modulo n, redukálódik a fenti alakra.

Miért érdekes ez?

  • Ha n prím, akkor a binomiális tétel miatt a köztes együtthatók mind oszthatók n-nel, tehát eltűnnek.
  • Ha n összetett, akkor ez az azonosság általában nem teljesül.

Gond

A fenti egyenlőséget polinomként kell ellenőrizni. De ha n nagy, akkor az (x+a)n polinomnak akár n fokú tagjai is lehetnek, ami exponenciális számítási költséggel járna.

Megoldás: a polinomot nem csak (modn), hanem (modxr−1) szerint is redukáljuk.

Így a polinom maradéka maximum r−1 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 n prímhatvány-e

Először vizsgáljuk meg, hogy n nem prímhatvány-e, azaz van-e olyan a,b, hogy n=ab, b≥2.

Ha igen, akkor n összetett → visszatérünk.

2. Megfelelő r kiválasztása

Keressünk egy kis r számot, hogy a következő feltétel teljesüljön:

ordr(n)>log2n

Itt ordr(n) az n multiplikatív rendje modulo r, azaz a legkisebb k, hogy nk≡1(modr).

Ez az r a polinom-redukcióhoz szükséges.

3. Közös osztók keresése

Minden 2≤a≤min⁡(r,n−1) esetén számítsuk ki gcd⁡(a,n)-t.

  • Ha találunk 1<gcd⁡(a,n)<n-t → n összetett.
  • Ha minden ilyen a-ra gcd⁡(a,n)=1, lépjünk tovább.

4. Nagy n esetén rövid-circuit

Ha n≤r, akkor n prím.

5. A polinomteszt

Végül ellenőrizzük a következő azonosságot polinomként modulo xr−1, n-re, néhány a értékre (konkrétan ⌊ϕ(r)log⁡n⌋ sokra):

(x+a)n≡xn+a(mod(xr−1),n)

Ha bármelyik a-ra az azonosság nem teljesül, akkor n összetett.

Ha mindegyikre teljesül → n prím.



Példa

Nézzük pl. az n=7 esetet (prím):

  • 1. lépés: nem prímhatvány.
  • 2. lépés: válasszunk pl. r=3, elég lesz.
  • 3. lépés: gcd⁡(2,7)=1, gcd⁡(3,7)=1.
  • 4. lépés: n>r, tehát megyünk tovább.
  • 5. lépés: ellenőrizzük pl. a=1,2-re a polinomazonosságot:

(x+1)7(modx3−1,7)≡x7+1≡x+1(modx3−1,7)

Így az azonosság teljesül → 7 prím.



Bonyolultság

Az eredeti AKS algoritmus időkomplexitása:

𝒪(log12n)

Később optimalizálták 𝒪(log6n) 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 n-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.