Prímteszt

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

Prímteszten a matematikában vagy informatikában olyan (determinisztikus) algoritmust vagy indeterminisztikus (pl. valószínűségelmé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.

Tartalomjegyzék

[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árigény 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 és asszociatí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. 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 = 2st, 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)2. n pontosan akkor prím, ha:

1. n nem teljes hatvány,
2. n-nek nincs prímtényezője, ami \leq r,
3. (x+a)^n\equiv x^n+a\pmod{(n,x^r-1)}teljesül minden 1\leq a \leq \sqrt{r}\log negész számra.

[szerkesztés] Speciális alakú számok tesztelése

Speciális alakú számokra vannak speciális prímtesztek. Például, ha N=2^{2^n}+1 alakú Fermat-szám (n≥ 1), úgy N prím pontosan akkor, ha

3^{\frac{N-1}{2}}\equiv -1 \pmod{N}.


Ezt a szócikket át kellene olvasni, ellenőrizni a szövegét, tartalmát. További részleteket a cikk vitalapján találhatsz.