Valószínűleg prímszám

A számelméletben egy valószínűleg prímszám ( eng. valószínűleg prím , PRP) olyan egész szám , amely megfelel bizonyos feltételeknek, amelyeket minden prímszám teljesít . A valószínűleg egyszerűek különböző típusai eltérő feltételekkel rendelkeznek. Mivel egy valószínű prím lehet összetett (az ilyen számokat pszeudoprímeknek nevezzük ), a feltételt úgy választjuk meg, hogy ritkítsa ezeket a kivételeket.

A Fermat - féle kis tételen alapuló Fermat-primalitásteszt a következőképpen működik: adott n esetén válasszunk olyan a -t , amelyre a és n koprím , és számítsunk ki egy n - 1 modulo n -t . Ha az eredmény eltér 1-től, akkor n összetett. Ha az eredmény 1, akkor n lehet prím, de nem kell; n ebben az esetben azt mondjuk, hogy (gyenge) valószínűleg prím az a bázishoz .

Tulajdonságok

A megfizethető egyszerűség az alapja a hatékony elsődlegességteszt - algoritmusok létrehozásának , amelyek a kriptográfiában is alkalmazhatók . Ezek az algoritmusok általában sztochasztikusak. Az elgondolás az, hogy amíg vannak összetett valószínűségi prímek az a bázisban bármely rögzített a esetén, remélhetjük, hogy van valami P < 1, így bármely adott n összetett esetén, ha véletlenszerűen választunk , annak a valószínűsége, hogy n pszeudoprím a bázis , nem kevesebb, mint P. Ha ezt a tesztet k -szer megismételjük, minden alkalommal, amikor új a számot választunk , annak a valószínűsége, hogy n pszeudoprím minden tesztelt a esetén, legalább P k . Mivel ez a valószínűség exponenciálisan csökken, nem túl nagy k kell ahhoz, hogy ez a valószínűség elhanyagolható legyen (például a processzorban bekövetkező hiba valószínűségéhez képest).

Sajnos ez nem igaz a gyenge valószínűségi prímekre, mivel vannak Carmichael-számok , de igaz a valószínűségi prímek szigorúbb kiválasztására, mint például az erős valószínűségi prímekre ( P = 1/4, Miller-Rabin teszt ), vagy az Euler-féle valószínűségekre. prímszámok ( P = 1/2, Nightingale-Strassen teszt ).

Még akkor is, ha determinisztikus ellenőrző algoritmusra van szükség, a valószínű elsődlegesség tesztelése hasznos első lépés. Gyorsan kiküszöböli a legtöbb szorzót.

A PRP-tesztet néha egy kis pszeudoprím táblázattal kombinálják, hogy gyorsan igazolják egy bizonyos küszöbértéknél kisebb szám elsődlegességét.

Változatok

Valószínűleg az a bázisban lévő Euler-prím olyan egész szám, amely a tételnél erősebb primalitási feltételeket elégít ki: bármely p prím esetén a ( p − 1)/2 egyenlő p bázisban , ahol a Legendre szimbólum . Valószínűleg az összetett Euler-prímeket Euler-Jacobi pszeudoprímeknek nevezzük az a bázisban . $({\tfrac {a}{p)))$ $({\tfrac {a}{p)))$

Ez a teszt javítható azzal a ténnyel, hogy 1 négyzetgyöke prímbázishoz 1 és −1. n = d • 2 s + 1- et írunk , ahol d páratlan. Egy n szám erős valószínű prímszám (SPRP), amely a-t alapul véve , ha a következő feltételek egyike igaz:

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

a^{d\cdot 2^{r}}\equiv -1{\pmod {n}}{\text{ néhány }}0\leq r\leq s-1.

Egy összetett erős valószínű prím a bázisban erősen pszeudoprímnek mondható az a bázisban . Minden erős valószínű prím az a bázisban egyben valószínű Euler-prím is ugyanabban a bázisban, de fordítva nem.

Lásd még

Linkek

Numerikus rendszerek
Megszámlálható készletek	Természetes számok ( ) $\scriptstyle \mathbb {N}$ Egész számok ( ) $\scriptstyle \mathbb {Z}$ Racionális ( ) $\scriptstyle \mathbb {Q}$ Algebrai ( ) $\scriptstyle {\overline {\mathbb {Q} }}$ Időszakok Kiszámítható Számtan
Valós számok és kiterjesztéseik	Igazi ( ) $\scriptstyle \mathbb {R}$ Komplex ( ) $\scriptstyle \mathbb {C}$ Quaterniók ( ) $\scriptstyle \mathbb {H}$ Cayley-számok (oktávok, oktonok) ( ) $\scriptstyle \mathbb {O}$ Sedenions ( ) $\scriptstyle \mathbb {S}$ Alternionok Dupla Hiperkomplex Szuperreális Hiperanyag szürreális
Numerikus bővítő eszközök	Cayley-Dixon eljárás Frobenius tétel Hurwitz-tétel
Egyéb számrendszerek	tőszámnevek Sorszámok (transzfinit, sorszámok) p-adic Természetfeletti számok intervallum számok
Lásd még	dupla számok Irracionális számok transzcendentális számok számsugár Biquaternion