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
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 −modulo n értékét . Ha az eredmény nem akkor n összetett szám ; ha az eredmény 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áulalapra mindössze db109-nél kisebb álprím létezik ( lásd oldal ) , miközben a109-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 . Aes alapra a legkisebb Euler–Jacobi-álprím az( lásd a oldala ) . A109-nél kisebb számok közöttEuler-féle álprím találhatóes alapon ( oldal ) . A teszt annyiban javítható , hogy aznégyzetgyökre modulo prímszám azé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ímes alapon a ( oldal ) . A109-nél kisebb számok közöttes alapon mindösszeerős álprím található ( 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 , hogyvalószínű prím-e : 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 lépés : Válasszunk egy számot , ami relatív prím -hez . A -t választjuk. lépés : Számítsuk ki az értéket , pl. \ . Mivel , folytatjuk a következő feltétel tesztelésével 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( the largest known probable primes ) Jegyzetek Álprímek