AKS primality test (tsz. AKS primality tests)

1. (informatika) AKS-algoritmus

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 prímszámtesztelésre évszázadok során számos algoritmust dolgoztak ki:

• Primitív módszerek: osztók keresése ${\textstyle {\sqrt {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.

A teszt egy rendkívül elegáns polinomazonosságon alapul, amit a következőképpen lehet megfogalmazni:

Egy ${\textstyle n\geq 2}$ szám prím akkor és csak akkor, ha minden ${\textstyle a\in \mathbb {Z} }$-ra teljesül az alábbi kongruencia modulo ${\textstyle n}$:

$${\displaystyle (x+a)^{n}\equiv x^{n}+a{\pmod {n}}}$$

vagyis a polinom kifejtve, modulo ${\textstyle n}$, redukálódik a fenti alakra.

Miért érdekes ez?

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

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

Megoldás: a polinomot nem csak ${\textstyle {\pmod {n}}}$, hanem ${\textstyle {\pmod {x^{r}-1}}}$ szerint is redukáljuk.

Így a polinom maradéka maximum ${\textstyle r-1}$ fokú lesz → kezelhető.

Az AKS-algoritmus az alábbi lépésekből áll:

Először vizsgáljuk meg, hogy ${\textstyle n}$ nem prímhatvány-e, azaz van-e olyan ${\textstyle a,b}$, hogy ${\textstyle n=a^{b}}$, ${\textstyle b\geq 2}$.

Ha igen, akkor ${\textstyle n}$ összetett → visszatérünk.

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

$${\displaystyle {\text{ord}}_{r}(n)>\log ^{2}n}$$

Itt ${\textstyle {\text{ord}}_{r}(n)}$ az ${\textstyle n}$ multiplikatív rendje modulo ${\textstyle r}$, azaz a legkisebb ${\textstyle k}$, hogy ${\textstyle n^{k}\equiv 1{\pmod {r}}}$.

Ez az ${\textstyle r}$ a polinom-redukcióhoz szükséges.

Minden ${\textstyle 2\leq a\leq \min(r,n-1)}$ esetén számítsuk ki ${\textstyle \gcd(a,n)}$-t.

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

Ha ${\textstyle n\leq r}$, akkor n prím.

Végül ellenőrizzük a következő azonosságot polinomként modulo ${\textstyle x^{r}-1}$, ${\textstyle n}$-re, néhány ${\textstyle a}$ értékre (konkrétan ${\textstyle \lfloor {\sqrt {\phi (r)}}\log n\rfloor }$ sokra):

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

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

Ha mindegyikre teljesül → n prím.

Nézzük pl. az ${\textstyle n=7}$ esetet (prím):

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

$${\displaystyle (x+1)^{7}{\pmod {x^{3}-1,7}}\equiv x^{7}+1\equiv x+1{\pmod {x^{3}-1,7}}}$$

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

Az eredeti AKS algoritmus időkomplexitása:

$${\displaystyle {\mathcal {O}}(\log ^{12}n)}$$

Később optimalizálták ${\textstyle {\mathcal {O}}(\log ^{6}n)}$ környékére.

Ma már elméletben polinomiális idő, de gyakorlatban továbbra is lényegesen lassabb, mint a Miller–Rabin.

• Első bizonyítottan determinisztikus polinomiális idejű algoritmus minden ${\textstyle 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.

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.

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.

• AKS primality test - Szótár.net (en-hu)
• AKS primality test - Sztaki (en-hu)
• AKS primality test - Merriam–Webster
• AKS primality test - Cambridge
• AKS primality test - WordNet
• AKS primality test - Яндекс (en-ru)
• AKS primality test - Google (en-hu)
• AKS primality test - Wikidata
• AKS primality test - Wikipédia (angol)