Prímteszt

Prímteszten a matematikában vagy informatikában olyan (determinisztikus) algoritmust vagy indeterminisztikus (például 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.

Tetszőleges számok tesztelése

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özött olyan, 1-től különböző szám, ami az adott egész számnak osztója, akkor a szám nem prím; ellenben viszont, ha nincs, akkor ez a szám egy prímszá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 sem nem prím, sem 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 osztanunk, 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 például 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.

Wilson-prímteszt

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

$(n-1)!\equiv -1{\bmod {n}}\Leftrightarrow$n prím.

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

Fermat-prímteszt

Ha p prím, akkor $a^{p}-a$ osztható p-vel, ahol p nem osztója a-nak.

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 euklideszi 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 szám. Ha nem, akkor 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.

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 ez legfeljebb a b-k egynegyedére igaz. 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.

(Sokan félreértelmezik a fentieket, és úgy gondolják, hogy sok teszt szükséges. Nem veszik figyelembe, hogy ha n összetett, ami nagyon ritkán fordul elő egy nagyobb, véletlenszerűen választott páratlan számnál - ha az átmegy a teszten. Pl. 2^64-ig 31894014 db (b=2) álprím és 4,25656*10^17 prímszám van, tehát kevesebb, mint 2^(-32) valószínűséggel összetett - pedig csak egy teszt.)

A BPSW-teszt

Kidolgozói, névadói: Robert Baillie, Carl Pomerance, John L. Selfridge, és Samuel S. Wagstaff, Jr.

Jelenleg (2013 július) a leghatékonyabb valószínűségi prímteszt: nem bizonyítja egy szám prím voltát, ha átmegy a teszten, de erősen valószínűsíti: P=99,9999...%. Ellenben bizonyítja az összetettségét, ha bukik rajta.

A BPSW-teszt két teszt kombinációja: egy Miller–Rabin-teszt (b=2, ld. előbb), és egy Lucas-Selfridge teszt. Utóbbinak a lényege, hogy ha n osztója az első Lucas-sor n+1. elemének, azaz

$U_{n+1}\equiv 0{\pmod {n}}$

akkor n prím vagy Lucas-álprím.

A BPSW-teszt fő erejét az a tény adja, hogy a rész-teszteknek különböző típusú álprímjei vannak, melyeknek nincs eddig ismert közös eleme, tehát nem ismerünk még olyan összetett számot, amelyik átmenne mindkét teszten. Bizonyított, hogy 2⁶⁴-ig (kb.18 trillió) nincs BPSW-álprím.

Pomerance feltételezi, hogy végtelen sok álprímje van ennek a tesztnek is. Zhuo Chen és John Greene megadott egy 2¹²⁴⁸ (376 jegyű szám!) elemű számhalmazt, melyben 740 álprím is lehet.

A BPSW-teszt még sokkal erősebbé tehető Lucas-V teszttel, jelentős plusz számítások nélkül:

$V_{n+1}\equiv 2Q{\pmod {n}}$

ahol V a 2. Lucas sor, Q pedig a teszt Selfridge Method A* -gal kiválasztott (=> D, P, Q) paramétere.

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_{10}$ n)². 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 n$egész számra.

Speciális alakú számok tesztelése (Pepin-teszt)

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}}.$

További információk

• Alice és Bob - 23. rész: Alice és Bob prímszámok után nyomoz
• Alice és Bob - 24. rész: Alice és Bob komolyabb fegyverekhez nyúl
• Alice és Bob - 26. rész: Alice és Bob átlépi a célvonalat

Források

• N. Koblitz: A Course in Number Theory and Cryptography
• Szobol: IMC módszer
• Donald Knuth: A számítógépprogramozás művészete
• Baillie, Robert, and Samuel S. Wagstaff, Jr.: Lucas pseudoprimes.
• https://web.archive.org/web/20130828131627/http://www.trnicely.net/misc/bpsw.html