Test de primalitate

Un test de primalitate este un algoritm care, atunci când este aplicat unui număr întreg , are scopul de a determina dacă este prim . Nu trebuie confundat cu un algoritm de factorizare , care are în schimb scopul de a determina factorii primi ai unui număr: ultima operație este, de fapt, în general mai lungă și mai complexă.

Cu excepția semnificativă a metodei curbei eliptice (cunoscută sub numele de ECPP ) și a algoritmului AKS , cele mai eficiente teste de primalitate utilizate astăzi sunt probabiliste , în sensul că dau un anumit răspuns numai atunci când răspund NU (adică atunci când spun că numărul este compus) în timp ce în cazul DA asigură doar o limită inferioară a probabilității ca numărul să fie prim. Cu toate acestea, eroarea de test poate fi făcută cât de mică doriți.

Unele teste

Testul de primalitate de bază, care se bazează pe însăși definiția numărului prim, este următorul: dat un număr de intrare n , verificați dacă există un număr întreg m între 2 și n - 1, astfel încât să se împartă n . Dacă n este divizibil cu cel puțin un m, atunci n este compus, altfel este prim. Limita n -1 poate fi redusă la ${\sqrt {n}}$ ${\ displaystyle {\ sqrt {n}}}$ $\ sqrt {n}$ , ca și cum toți factorii ar fi mai mari decât această valoare, produsul lor ar fi neapărat mai mare decât n , ceea ce este absurd. În acest caz particular, testul de primărie oferă, de asemenea, factorizarea numărului.

Din secolul al XVII-lea, au fost concepuți alți algoritmi, inclusiv testul Fermat și testul Wilson ; altele au fost create pentru a fi utilizate numai pe anumite clase de numere: exemple sunt testul Lucas-Lehmer pentru numerele Mersenne , testul Proth pentru numere în forma k 2 ⁿ +1, unde k este impar și mai mic de 2 ⁿ . Testul Miller-Rabin, pe de altă parte, este probabilistic.

În prezent, cel mai utilizat test cu scop general este ECPP , bazat pe curbe eliptice .

Complexitatea computațională

Problema verificării dacă un număr este prim (numit PRIMES) este de complexitate P. Acest rezultat a fost atins în 2002 .

Anterior, s-a dovedit în 1977 de Solovay și Strassen că se afla în clasa complexității co-RP ; în 1992, Adleman și Huang, prin modificarea algoritmului Goldwasser - Kilian , au arătat că se află în clasa RP și, în consecință, în clasa ZPP , intersecția RP și co-RP.

În 2002 Agrawal, Kayal și Saxena au furnizat un algoritm determinist polinomial pentru PRIMES, cunoscut sub numele de algoritmul AKS , de complexitate $O(log(N)^{12})$ ${\ displaystyle O (jurnal (N) ^ {12})}$ $O (jurnal (N) ^ {12})$ , care se reduce la $O(log(N)^{6})$ ${\ displaystyle O (jurnal (N) ^ {6})}$ $O (jurnal (N) ^ {6})$ dacă conjectura lui Sophie Germain este valabilă.

Algoritmul a fost îmbunătățit de mai multe ori în etape succesive și pare să fi fost găsit un algoritm hibrid de complexitate ${\tilde {O}}(log(N)^{4})$ ${\ displaystyle {\ tilde {O}} (jurnal (N) ^ {4})}$ $\ tilde O (log (N) ^ {4})$ ^[1] . Cu toate acestea, în prezent, acest algoritm nu implică avantaje semnificative față de metodele probabilistice bine cunoscute și nici nu implică nimic asupra factorizării unui număr (cu excepția testului de primalitate) și, prin urmare, în criptografie bazată pe primele.

Notă

^(EN) Qi Cheng, Primality doveding via one round and one in ECPP iteratione in AKS (PDF), on cs.ou.edu. Adus 11-03-2008 .

linkuri externe

Implementarea JAVA a algoritmului AKS. , la angelusworld.com . Accesat la 2 ianuarie 2011 (arhivat din original la 7 iulie 2011) .

Portalul de matematică : accesați intrările Wikipedia care se ocupă de matematică

[1] (EN) Qi Cheng, Primality doveding via one round and one in ECPP iteratione in AKS (PDF), on cs.ou.edu. Adus 11-03-2008 .

[1]