Valószínű prímek

A számelmélet területén a valószínű prímek, valószínűleg prímek vagy valószínűsíthető prímek (probable prime, PRP) olyan egész számok, melyek kielégítenek egy vagy több olyan speciális feltételt (prímtesztet), aminek minden prímszám eleget tesz, de a legtöbb összetett szám nem. A különböző fajtájú PRP-k különböző feltételeknek tesznek eleget. A valószínűsíthető prímek egy része összetett szám (ezek az álprímek), de a speciális feltételek úgy vannak megválasztva, hogy az ilyen kivételek ritkák legyenek.

A Fermat-féle teszt az összetett számok kiszűrésére, ami a kis Fermat-tételen alapszik, a következőképpen működik: vegyünk egy n pozitív egészet, válasszunk hozzá n-hez relatív prím a egészt, majd számítsuk ki a^{n − 1} modulo n értékét. Ha az eredmény nem 1, akkor n összetett szám; ha az eredmény 1, akkor n valószínűleg prím; pontosabban n ekkor „a alapra nézve valószínű prím”. Egy „a alapra nézve gyengén valószínű prím” olyan, a alapra nézve valószínű prím, ami a alapra nézve nem erősen valószínű prím (lásd lejjebb).

Adott a alapot tekintve annak valószínűsége, hogy egy összetett szám valószínűsíthető prím legyen (tehát álprím), csekély. Például 2 alapra mindössze 21 853 db 25·10⁹-nél kisebb álprím létezik (lásd 1005. oldal), miközben a 25·10⁹-nél kisebb prímek száma 1 091 987 405 (lásd prímszámláló függvény).

Tulajdonságok

Egy szám „valószínű prím” mivolta a hatékony prímteszt-algoritmusok alapköve, aminek fontos kriptográfiai alkalmazásai léteznek. Ezek az algoritmusok általában probabilisztikus jellegűek. A mögöttük álló elképzelés szerint bár léteznek összetett valószínű prímek bármely fix a alap esetén, remélhetőleg létezik egy fix P<1 valószínűség oly módon, hogy bármely összetett n számhoz véletlenszerűen kiválasztva a-t annak valószínűsége, hogy n álprím a alapra nézve, legfeljebb P. Ezek után a tesztet k alkalommal megismételve mindig újabb a alapokkal, annak valószínűsége, hogy n az összes tesztelt a alapra nézve álprím, legfeljebb P^k, és mivel ez az esély exponenciálisan csökken, viszonylag kis k esetén is már elegendően kicsi (összehasonlítva például egy számítógépes hardverhiba valószínűségével).

Az előbbi feltevés sajnos tévesnek bizonyult a gyengén valószínű prímek esetében a Carmichael-számok létezése miatt; igaz viszont a valószínűsíthető prímszám fogalmának kifinomultabb megfogalmazásaira, amilyen például az erősen valószínű prímek (P = 1/4, Miller–Rabin-teszt vagy az Euler-féle valószínű prímek (P = 1/2, Solovay–Strassen-teszt).

Még azokban az esetekben is, amikor determinisztikus prímségbizonyításra van szükség, első lépésben hasznos lehet valószínűségi prímteszteket végezni. Ezekkel gyorsan (és biztonsággal) ki lehet szűrni a legtöbb összetett számot.

Időnként a PRP-tesztet kombinálják a kis álprímek táblázatával, hogy valamely küszöbértéknél kisebb szám prímségét gyorsan igazolhassák.

Változatok

Egy „Euler-féle valószínűsíthető prím a alapra nézve” olyan egész szám, amit prímnek jelez a valamivel erősebb tétel, ami szerint bármely p prímre a^{(p − 1)/2} megegyezik $({\tfrac {a}{p}})$ modulo p-vel, ahol $({\tfrac {a}{p}})$ a Legendre-szimbólum. Az Euler-féle valószínűsíthető prímek közül az összetett számokat Euler–Jacobi-álprímnek vagy Euler-féle álprímnek nevezzük a alapra nézve. A 2-es alapra a legkisebb Euler–Jacobi-álprím az 561 (lásd a 1004. oldala). A 25·10⁹-nél kisebb számok között 11347 Euler-féle álprím található 2-es alapon ( 1005. oldal).

A teszt annyiban javítható, hogy az 1 négyzetgyökre modulo prímszám az 1 és a −1. Írjunk n = d · 2^s + 1-t, ahol d páratlan szám. Az n szám erősen valószínű prím (strong probable prime, SPRP) egy a alapra nézve, ha a következő feltételek valamelyike érvényesül:

$a^{d}\equiv 1{\pmod {n}},\;$

$a^{d\cdot 2^{r}}\equiv -1{\pmod {n}}{\text{ valamely }}0\leq r\leq s-1.\,$

Egy a alapra nézve erősen valószínű prímet, amennyiben összetett számnak bizonyul, erős álprímnek nevezzük a alapra nézve. Minden a alapra erősen valószínű prím egyben Euler-féle valószínűsíthető prím is arra az alapra, de ez fordítva nem igaz.

A legkisebb erős álprím 2-es alapon a 2047 ( 1004. oldal). A 25·10⁹-nél kisebb számok között 2-es alapon mindössze 4842 erős álprím található ( 1005. oldal).

Léteznek még a Lucas-sorozatokra épülő Lucas-féle valószínűsíthető prímek, illetve Lucas-álprímek is. A Lucas-féle prímteszt önállóan is alkalmazható. A Baillie–PSW-prímteszt a Lucas-prímtesztet kombinálja egy erős valószínűsíthető prímteszttel.

Példa SPRP-re

Teszteljük, hogy 97 valószínű prím-e:

• 1. lépés: Keressünk $d$ és $s$ számokat, melyekre $96=d\cdot 2^{s}$, továbbá $d$ páratlan
  • $s=0$-val kezdve, $d$ kezdeti értéke $96$
  • Növelve $s$ értékét, kijön $d=3$ és $s=5$, mivel $96=3\cdot 2^{5}$
• 2. lépés: Válasszunk egy $a$ számot, ami relatív prím $97$-hez. A $2$-t választjuk.
• 3. lépés: Számítsuk ki az $a^{d}{\pmod {n}}$ értéket, pl. $2^{3}{\pmod {97}}$. Mivel $\not \equiv 1{\pmod {97}}$, folytatjuk a következő feltétel tesztelésével
• 4. lépés: Számítsuk ki a $2^{3\cdot 2^{r}}{\pmod {97}}$ értékeket minden $0\leq r<s$-re. Ha kongruens $96{\pmod {97}}$, $97$ valószínűleg prímszám. Ha nem, $97$ határozottan összetett.
  • $r=0:2^{3}\equiv 8{\pmod {97}}$
  • $r=1:2^{6}\equiv 64{\pmod {97}}$
  • $r=2:2^{12}\equiv 22{\pmod {97}}$
  • $r=3:2^{24}\equiv 96{\pmod {97}}$
• Következőképpen $97$ valószínűsíthetően prímszám.

Kapcsolódó szócikkek

• Baillie–PSW-prímteszt
• Euler–Jacobi-álprím
• Carmichael-számek
• Miller–Rabin-prímteszt

További információk

• The prime glossary – Probable prime
• The PRP Top 10000 (the largest known probable primes)