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 an − 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  db 25·109-nél kisebb álprím létezik (lásd  1005. oldal), miközben a 25·109-nél kisebb prímek száma  (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 Pk, é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  modulo p-vel, ahol  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·109-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 · 2s + 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:

 

 

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·109-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  és  számokat, melyekre , továbbá  páratlan
 -val kezdve,  kezdeti értéke 
 Növelve  értékét, kijön  és , mivel 
 2. lépés: Válasszunk egy  számot, ami relatív prím -hez. A -t választjuk.
 3. lépés: Számítsuk ki az  értéket, pl. . Mivel , folytatjuk a következő feltétel tesztelésével
 4. lépés: Számítsuk ki a  értékeket minden -re. Ha kongruens ,  valószínűleg prímszám. Ha nem,  határozottan összetett.
 
 
 
 
 Következőképpen  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 

Álprímek