Probabil un număr prim

În teoria numerelor , un număr probabil prim ( îng. probabil prim , PRP) este un număr întreg care îndeplinește anumite condiții pe care le îndeplinesc toate numerele prime . Diferite tipuri de cele probabil simple au condiții diferite. Deoarece un prim probabil poate fi compus (astfel de numere se numesc pseudoprime ), se alege condiția pentru a face aceste excepții rare.

Testul de primalitate Fermat , bazat pe Teorema Mică a lui Fermat , funcționează după cum urmează: dat n , alegeți unele a astfel încât a și n să fie coprime și calculați a n - 1 modulo n . Dacă rezultatul este diferit de 1, atunci n este compus. Dacă rezultatul este 1, n poate fi prim, dar nu trebuie să fie; n în acest caz se spune că este (slab) probabil prim pentru a baza a .

Proprietăți

Simplitatea accesibilă este baza pentru crearea unor algoritmi eficienți de testare a primalității care își găsesc aplicații în criptografie . Acești algoritmi sunt de obicei stocastici. Ideea este că atâta timp cât există numere prime probabilistice compuse în baza a pentru orice a fix , putem spera că există vreo P < 1 astfel încât pentru orice compus n dat , dacă alegem a aleatoriu, probabilitatea ca n să fie pseudoprim . baza a , nu mai puțin de P . Dacă repetăm acest test de k ori, alegând de fiecare dată un număr nou a , probabilitatea ca n să fie pseudoprim pentru toate a testate este de cel puțin P k . Deoarece această probabilitate scade exponențial, este nevoie de k nu foarte mare pentru a face această probabilitate neglijabilă (comparativ, de exemplu, cu probabilitatea ca o eroare să apară în procesor).

Din păcate, acest lucru nu este valabil pentru numerele prime slabe probabile, deoarece există numere Carmichael , dar este adevărat pentru o selecție mai riguroasă a primelor probabile, cum ar fi numerele prime probabile puternice ( P = 1/4, testul Miller-Rabin ) sau probabile Euler prime ( P = 1/2, testul Nightingale-Strassen ).

Chiar și atunci când este necesar un algoritm de verificare deterministă, un test de primalitate probabilă este un prim pas util. Poate elimina rapid majoritatea multiplicatorilor.

Testul PRP este uneori combinat cu un mic tabel pseudoprime pentru a demonstra rapid caracterul prim al unui număr care este mai mic decât o anumită valoare de prag.

Variante

Probabil, primul lui Euler în baza a este un întreg care satisface condiții de primalitate mai puternice decât teorema: pentru orice prim p , a ( p − 1)/2 este egal în baza p , unde este simbolul Legendre . Probabil numerele prime Euler care sunt compuse sunt numite pseudoprime Euler-Jacobi în baza a . $({\tfrac {a}{p)))$ $({\tfrac {a}{p)))$

Acest test poate fi îmbunătățit folosind faptul că rădăcina pătrată a lui 1 la o bază primă este 1 și -1. Scriem n = d • 2 s + 1, unde d este impar. Un număr n este primul probabil puternic (SPRP) pentru a baza a dacă una dintre următoarele condiții este adevărată:

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

a^{d\cdot 2^{r}}\equiv -1{\pmod {n}}{\text{ pentru unele }}0\leq r\leq s-1.

Un prim probabil compozit puternic în baza a se spune că este puternic pseudoprim în baza a . Fiecare prim probabil puternic în baza a este, de asemenea, un prim probabil Euler în aceeași bază, dar nu invers.

Vezi și

Link -uri

Sisteme numerice
Seturi numărabile	numere naturale ( ) $\scriptstyle \mathbb {N}$ numere întregi ( ) $\scriptstyle \mathbb {Z}$ Rațional ( ) $\scriptstyle \mathbb {Q}$ algebric ( ) $\scriptstyle {\overline {\mathbb {Q} }}$ Perioadele Calculabil Aritmetic
Numerele reale și extensiile lor	Real ( ) $\scriptstyle \mathbb {R}$ Complex ( ) $\scriptstyle \mathbb {C}$ Cuaternioni ( ) $\scriptstyle \mathbb {H}$ Numerele Cayley (octave, octooni) ( ) $\scriptstyle \mathbb {O}$ Sedenions ( ) $\scriptstyle \mathbb {S}$ Alterniuni Dual Hipercomplex Superreale Hipermaterial ireal
Instrumente de extensie numerică	Procedura Cayley-Dixon Teorema Frobenius Teorema Hurwitz
Alte sisteme numerice	numere cardinale Numere ordinale (transfinite, ordinale) p-adic Numere supranaturale numere de interval
Vezi si	numere duble Numere irationale numerele transcendentale fascicul numeric Biquaternion