| dbo:abstract
|
- 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 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). (hu)
- 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 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). (hu)
|
