Valószínű prímek

A Wikipédiából, a szabad enciklopédiából
Jump to navigation Jump to search

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 21 853 db 25·109-nél kisebb álprím létezik (lásd [1] 1005. oldal), miközben a 25·109-nél kisebb prímek száma 1 091 987 405 (lásd prímszámláló függvény).

Tulajdonságok[szerkesztés]

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[szerkesztés]

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[1] 1004. oldala). A 25·109-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 · 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 ([1], 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ó ([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[szerkesztés]

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[szerkesztés]

További információk[szerkesztés]

Jegyzetek[szerkesztés]

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