Prímteszt

A Wikipédiából, a szabad enciklopédiából.

Prímteszten a matematikában vagy informatikában olyan (determinisztikus) algoritmust vagy indeterminisztikus (pl. valószínűség-elméleti) módszereket is megengedő eljárást értünk, melynek ismeretében bármely adott egész számról, vagy csak bizonyos típusú számokról (véges sok lépésben) el tudjuk dönteni, hogy prímszám-e, vagy pedig összetett. Ettől lényegesen különböző és sokkal nehezebb feladat egy adott szám prímtényezőinek a megtalálása (prímfelbontás).

A következőkben csak a pozitív számok prímteszteléséről fogunk szólni, hisz egy negatív szám akkor és csak akkor prím, ha ellentettje, mint egész szám, szintén prím.

[szerkesztés] Tetszőleges számok tesztelése

[szerkesztés] Naiv módszer

A legegyszerűbb módszer a következő: az adott egész számot sorra elosztjuk a nála határozottan kisebb pozitív egész számokkal; ha van ezek közt olyan 1-től különböző, ami osztója, akkor a szám nem prím, ellenben viszont prím.

Egy nagyon primitív pszeudokód formájában a következőképp „algoritmizálhatjuk” ezt:

1). legyen s=2; és olvassuk be a tesztelendő n egész számot,
2). ha n=0 vagy n=1, akkor se nem prím, se nem összetett; STOP; ha n>2, menjünk 3).-ra
3). Képezzük az m=<n mod s> maradékot; ha ez 0 és m<n, akkor n nem prím, STOP; ha m=n, akkor n prím, STOP; ha pedig az előző esetek egyike sem teljesül, ekkor tehát m<n és m nem nulla, legyen s=s+1, és menjünk 3).-ra.

Az eljárás elég lassú, de a tárhely növelésével gyorsítható. Ez azon alapul, hogy nem kell a számnál kisebb összes természetes egésszel osztunk, hanem nyilván elegendő ezt csak a nála kisebb prímekkel megtenni. Ehhez készíteni kell egy prímszámtáblázatot, ami pl. az eratoszthenészi szita módszerén vagy más szitálási eljárásokon alapulhat. A számokat elég a négyzetgyökükig vizsgálni, hiszen a szorzás kommutatív művelet.

[szerkesztés] Wilson-prímteszt

Ennek a prímtesztnek, legalábbis ma, csak elméleti jelentősége van (tehát gyakorlatilag semmi); a Wilson-tételen alapul:

Az n>1 szám akkor és csak akkor prím, ha n|(n-1)!+1.

Azonban ennek használatához az n! faktoriális függvényt kellene számolni, erre pedig jelenleg nincs hatékony eljárás.

[szerkesztés] Fermat-prímteszt

[szerkesztés] A Solovay-Strassen teszt

Egy adott páratlan n számról a következőképpen döntjük el, hogy prím-e: választunk véletlenszerűen egy 0<b<n egész számot, Ezután kiszámítjuk, az euklidészi algoritmus segítségével, a (b, n) legnagyobb közös osztót, ha ez egynél nagyobb, akkor készen vagyunk, n összetett. Ha nem, kiszámítjuk egyrészt $b^{\frac{n-1}{2}}$ n-nel vett legkisebb abszolút értékű maradékát, másrészt a : $\left(\frac{b}{n}\right)$ Jacobi-szimbólum értékét. Ha n prím, akkor a két értéknek, az Euler-kritérium értelmében, meg kell egyezni. Fontos megjegyezni, hogy noha a Jacobi-szimbólum n prímfelbontása segítségével van definiálva, értéke anélkül is gyorsan kiszámítható. Ha n összetett, akkor legfeljebb 1/2 annak a valószínűsége, hogy véletlen b-re ez a két érték megegyezik. Ezért sokszor ismételjük a fenti próbát véletlenszerűen választott b értékekkel. Ha a két szám akár csak egyszer is eltér, akkor biztosak lehetünk benne, hogy n összetett. Ha viszont mindig megegyeznek, akkor igen nagy valószínűséggel prím.

[szerkesztés] A Miller–Rabin-teszt

Legyen n a tesztelendő páratlan szám, $n - 1 = 2 s t$ , t páratlan. Legyen 0<b<n.

$b^t\equiv 1 \pmod{n}$ vagy van olyan $0\leq r<s$ , hogy $b^{2^r t}\equiv -1 \pmod{n}$ .

Ha n prímszám, akkor a fenti állítás minden b-re teljesül, ha n összetett, akkor legfeljebb a b-k egynegyedére. Ezért véletlenszerűen választunk b értékeket, és ha mondjuk 100 egymásutáni választásra igaz a fenti állítás, akkor n nagy valószínűséggel prím.

[szerkesztés] Az AKS-algoritmus

2002 augusztusában három indiai matematikus: Manindra Agrawal, Neeraj Kayal és Nitin Saxena polinomiális prímtesztet talált ki. Ez a prímek következő karakterizációján alapul: Legyen $n \geq 2$ természetes szám, r olyan n-nél kisebb természetes szám, hogy n rendje r-rel osztva nagyobb, mint (log n)². n pontosan akkor prím, ha: