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 ^[1] 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 ${\displaystyle ({\tfrac {a}{p}})}$ modulo p-vel, ahol ${\displaystyle ({\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^[1] 1004. oldala). A 25·10⁹-nél kisebb számok között 11347 Euler-féle álprím található 2-es alapon (^[1] 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:

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

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

Jegyzetek

1. Carl Pomerance, John L. Selfridge, Samuel S. Wagstaff, Jr. (1980. július 1.). „The pseudoprimes to 25·10⁹”. Mathematics of Computation 35 (151), 1003-1026. o. DOI:10.1090/S0025-5718-1980-0572872-7.