Un test de primalitate este un algoritm care permite să știe dacă un număr întreg este prim .
Cel mai simplu test este următorul: pentru a testa N , verificăm dacă este divizibil cu unul dintre numerele întregi incluse în sens larg între 2 și N-1. Dacă răspunsul este negativ, atunci N este prim, altfel este compus.
Mai multe modificări îmbunătățesc performanța acestui algoritm:
Testele probabiliste nu sunt teste de primalitate în sens strict (fac parte din metodele Monte-Carlo ): nu fac posibilă garantarea cu certitudine că un număr este prim, dar costul lor redus în timp de calcul îi face să fie candidați excelenți pentru aplicațiile din criptologie depind adesea în mod critic de numerele prime mari și acceptă o rată de eroare cu condiția să fie foarte scăzută: acestea sunt numite prime industriale (în) . Ideea de bază a testării primalității unui număr N este următoarea:
După mai multe iterații, dacă N nu este recunoscut ca număr compus , este declarat probabil prim .
Dat fiind un test, pot exista anumite numere compuse care sunt declarate „probabil prime” indiferent de martor. Astfel de numere rezistente la test se numesc numere pseudoprime pentru acest test.
Cel mai simplu test de primărie probabilistică este testul de primărie Fermat . Testul de primărie Miller-Rabin și testul de primărie Solovay-Strassen sunt variante mai sofisticate care detectează toți compușii. Oricare dintre aceste teste este utilizat atunci când este necesar un număr prim după un calcul cât mai scurt posibil, acceptând în același timp o mică marjă de îndoială, de exemplu în criptarea RSA sau în protocolul de schimb al cheilor Diffie-Hellman .
Testul ciclotomic este un test de primărie determinist; demonstrăm că timpul său de execuție este O ( n înfundă (log (n)) ), unde n este numărul de cifre ale lui N și c este o constantă independentă de n . Complexitatea sa este mai mică decât polinomul .
Testul de primalitate al curbei eliptice poate fi demonstrat că rulează O ( n 6 ), dar numai utilizând unele conjecturi ale teoriei numerice analitice care nu au fost încă dovedite, dar acceptate pe scară largă ca fiind adevărate. În practică, acest test este mai lent decât testul ciclotomic pentru numere cu mai mult de 10.000 de cifre.
Implementarea acestor două metode este destul de dificilă, iar riscul de eroare datorat implementării este, prin urmare, mai mare decât cele ale metodelor probabilistice menționate mai sus.
Dacă ipoteza generalizată Riemann este adevărată, testul Miller-Rabin poate fi convertit într-o versiune deterministă cu un timp de execuție Õ ( n 4 ). În practică, acest algoritm este mai lent decât cele două precedente.
În 2002, Manindra Agrawal, Neeraj Kayal și Nitin Saxena au descris un test de primărie determinist ( testul de primărie AKS ) care se desfășoară la Õ ( n 12 ). Mai mult, conform unei supoziții (nedovedită, prin urmare, dar recunoscută pe scară largă ca fiind adevărată), ar fi executată în Õ ( n 6 ). Prin urmare, este primul test de primalitate determinist al timpului de execuție polinomial . În practică, acest algoritm este mai lent decât celelalte metode.
Teoria numerelor oferă metode; un bun exemplu este testul Lucas-Lehmer pentru a testa dacă un număr este prim. Acest test este legat de faptul că ordinea multiplicativă a unui anumit număr a modulo n este n -1 pentru un număr prim n când a este o rădăcină primitivă . Dacă putem arăta că a este o rădăcină primitivă pentru n , putem arăta că n este prim.
În teoria complexității , problema PRIMES este problema deciziei de apartenență la limbajul formal care conține numere prime, scrise în binar:
BONUS = {10, 11, 101, 111, 1011, ...}
unde 10, 11, 101, 111, 1011 ... sunt scrierile binare ale numerelor prime 2, 3, 5, 7, 11 etc.
PRIMES este în co-NP : într-adevăr, COMPOZITELE sale complementare, adică decizia de a aparține setului de numere non prime, este în NP , deoarece putem decide COMPOZITE în timp polinomial prin numărul de cifre ale numărului care urmează să fie testat , pe o mașină Turing nedeterministă , prin ghicirea unui factor.
În 1975, Vaughan Pratt (ro) a arătat că există un certificat pentru PREMIUMS verificabil în timp polinomial. Astfel, PRIMES este, de asemenea, în NP și, prin urmare, în NP ∩ coNP .
Algoritmii Solovay-Strassen și Miller-Rabin arată că PRIMES este în coRP . În 1992, algoritmul Adleman - Huang arată că PRIMES este în RP . Astfel, PRIMES este în ZPP = RP ∩ coRP .
Testul de primărie Adleman - Pomerance - Rumely (en) din 1983 arată că PRIMES este în QP (timp cvasi-polinomial), o clasă care nu sa dovedit a fi comparabilă cu una dintre clasele menționate mai sus.
Testul AKS primality este un algoritm în timp polinomial și în cele din urmă arată PRIMELE este în P . Dar PRIMES nu sa dovedit a fi -P completă . Nu știm dacă PRIMES este în NC sau, de exemplu, în LOGSPACE . Dar știm că PRIMES nu este în AC 0 .