Certificat de simplitate

În matematică și informatică , un certificat de primalitate este o dovadă riguroasă că un număr este prim . Deținerea unui certificat de primalitate vă permite să verificați dacă un număr este prim fără a recurge la teste de primalitate .

În teoria complexității computaționale , de regulă, se înțelege că dimensiunea certificatului, precum și timpul necesar pentru verificarea acestuia, depind polinom de lungimea intrării numărului, adică de numărul de cifre din aceasta.

Existența certificatelor de primalitate polinomială arată că probleme precum testarea primalității și factorizarea numerelor întregi aparțin clasei NP , întrucât, conform uneia dintre definițiile echivalente ale acestei clase, acestea sunt probleme a căror rezolvare poate fi verificată în timp polinomial dacă un se oferă certificat. În plus, aceste probleme se află în clasa co-NP , care decurge din definiția sa ca o clasă de complemente la problemele din NP - într-adevăr, oricare dintre divizorii săi netriviali poate fi un certificat polinom că un număr este compus.

Astfel, certificatele de primalitate au fost unul dintre primele indicii că testarea de primalitate nu a fost NP-completă , deoarece dacă ar fi, ar urma că o clasă NP este imbricată într-un co-NP, care, la rândul său, este de obicei[ clarifica ] considerat[ de cine? ] este incorectă. În plus, descoperirea certificatelor polinomiale a făcut ca testarea primarității să fie prima problemă despre care se știe că aparține atât NP, cât și co-NP, dar nu se știe ca fiind din clasa P. Odată cu apariția testului Agrawal-Kayal-Saxena în 2002, primul (și în prezent singurul[ când? ] ) din testul de primalitate polinomială deterministă, s-a constatat că problema se află încă în P.

Certificatul lui Pratt

Din punct de vedere istoric, conceptul de certificate de primalitate a fost introdus odată cu apariția certificatului Pratt , care a fost obținut în 1975 de Vaughan Pratt [1] , care a descris structura acestuia și a demonstrat că dimensiunea unui certificat depinde polinomial de lungimea unei înregistrări numerice. , și, de asemenea, că poate fi verificat pentru un timp polinomial. Certificatul se bazează pe testul Lucas , care, la rândul său, decurge din mica teoremă a lui Fermat :

(Teorema lui Luc) Un număr este prim dacă și numai dacă există un element în inelul modulo de reziduuri astfel încât: $p$ $p$ $a\in \mathbb {Z} _{p}$

$a^{p-1}\equiv 1{\pmod {p)}$ ,
$a^{\frac {p-1}{q}}\nu \equiv 1{\pmod {p}}$ pentru toate numerele prime care împart . $q$ $p-1$

Dovada

Condițiile scrise înseamnă exact că ordinea elementului este . $A$ $p-1$

Dacă un astfel de element există, atunci cel puțin elementele inelului de reziduuri sunt reversibile modulo , adică coprim cu . Astfel, toate numerele sunt coprime cu , ceea ce implică simplitatea acestui număr. $p-1$ $p$ $p$ $1,2,\dots ,p-1$ $p$
Dacă numărul este prim, atunci există o rădăcină primitivă în inelul modulo de reziduuri , a cărei ordine trebuie să fie egală cu . ■ $p$ $p$ $p-1$

Având un astfel de număr (numit martor al simplității ) și împărțirea în factori primi, puteți verifica rapid condițiile de mai sus - trebuie să efectuați exponențiații modulo, ceea ce se poate face pentru înmulțiri folosind exponentiația binară . Înmulțirile în sine în implementarea naivă („în coloană”) sunt efectuate în , ceea ce oferă o estimare generală a timpului de rulare în . $A$ $p-1$ $O(\log p)$ $O(\log p)$ $O(\log ^{2}p)$ $O(\log ^{4}p)$

În același timp, trebuie avut în vedere că, pe lângă condițiile de mai sus, este necesar să se verifice și dacă numerele prezentate în certificat ca prime sunt într-adevăr astfel - astfel, pe lângă mărturia de primalitate și împărțirea în factori primi, certificatul de primalitate al unui număr trebuie să includă și certificate de primalitate a tuturor factorilor indicați în el. Astfel, este convenabil să se reprezinte un certificat sub formă de arbore, în nodurile cărora există numere prime și martorii lor de primalitate corespunzători, iar descendenții nodului în care este stocat numărul sunt divizori primi ai numărului . În consecință, numărul corespunde frunzelor copacului . $p-1$ $p$ $p$ $p-1$ $p=2$

Se poate demonstra prin inducție că într-un astfel de arbore există cel mult noduri interne , adică cele care conțin un număr prim impar. Având în vedere că fiecare nod al arborelui stochează un pic pentru a scrie numere în el, putem concluziona că dimensiunea totală a arborelui nu depășește . Timpul total de verificare, la rândul său, poate fi estimat ca , deoarece este necesar să se efectueze acțiuni în fiecare dintre noduri. $4\log _{2}p-4$ $O(\log p)$ $O(\log ^{2}p)$ $O(\log ^{5}p)$ $O(\log ^{4}p)$ $O(\log p)$

În timp ce certificatele lui Pratt sunt utile în teorie și ușor de verificat, găsirea unui certificat pentru un număr necesită factorizare și alte numere potențial mari. Acest lucru este ușor de făcut în unele cazuri speciale, de exemplu, pentru numerele prime Fermat , dar în cazul general această sarcină este acum mult mai dificilă decât testul obișnuit al unui număr pentru primă. $n$ $n-1$

Influența asupra „PRIMES este în P”

Articolul „PRIMES este în P” [2] a fost o descoperire în informatica teoretică . Această lucrare, publicată de Manindra Agrawal și cei doi studenți ai săi Niraj Kayal și Nitin Saxena în august 2002, demonstrează că celebra problemă de primalitate poate fi rezolvată determinist în timp polinomial. Autorii au primit Premiul Gödel , care este de 5.000 USD [3] , și Premiul Fulkerson din 2006 pentru munca lor.

Deoarece testul de primalitate se poate face acum în timp polinomial folosind testul AKS , un număr prim poate fi văzut ca un certificat al propriei sale primari. Acest test este finalizat la timp , ceea ce face o astfel de verificare mai costisitoare decât utilizarea certificatului Pratt, dar nu necesită găsirea certificatului în sine. ${\tilde {O}}(\log ^{6}n)$

Note

↑ Vaughan Pratt. „Fiecare prim are un certificat succint”. SIAM Journal on Computing , vol. 4, pp. 214-220. 1975. Citate , text integral .
↑ Agrawal, Manindra; Kayal, Neeraj; Saxena, Nitin PRIMES este în P (engleză) // Annals of Mathematics : jurnal. - 2004. - Septembrie ( vol. 160 , nr. 2 ). - P. 781-793 . - doi : 10.4007/annals.2004.160.781 . — .
↑ Premiul Godel 2017 . Asociația Europeană pentru Informatică Teoretică . EATCS. Preluat: 29 martie 2017. (nedefinit)

Link -uri

Mathworld: Certificat de primalitate
Certificat Mathworld Pratt
Mathworld: Certificat Atkin-Goldwasser-Kilian-Morain
Vasek Chvatal . Note de curs despre dovezile de primalitate ale lui Pratt . Departamentul de Informatică. Universitatea Rutgers. Versiune PDF la Universitatea Concordia .

Algoritmi teoretici numerelor
Teste de simplitate	Miller Miller - Rabin Luca - Lemaire pepina Agrawala - Kayala - Saxonia Privighetoarea - Strassen
Găsirea numerelor prime	Iterarea peste divizori Sita lui Eratosthenes sita lui Atkin Sieve Sundarama
Factorizarea	Iterarea peste divizori Metoda Fermat p −1 Metoda Pollard Algoritmul ρ al lui Pollard metoda Lehmann Metoda curbei eliptice (algoritmul lui Lenstra) algoritmul lui Dixon Sita pătrată
Logaritm discret	Algoritmul Gelfond-Shanks Algoritmul Polig-Hellman Metoda ρ a lui Pollard Algoritmul Cangurului lui Pollard Algoritmul lui Adleman Algoritmul COS
Găsirea GCD	algoritmul lui Euclid Algoritm avansat Algoritm binar
Modul de aritmetică	Algoritmul lui Montgomery Teorema chineză a restului
Înmulțirea și împărțirea numerelor	Algoritmul Karatsuba Algoritmul Toom-Cook Algoritmul Schönhage-Strassen Algoritmul Fuhrer Algoritmul Harvey-van der Hoeven Algoritmul Burnickel-Ziegler
Calcularea rădăcinii pătrate	Algoritmul Tonelli-Shanks Algoritmul Berlekamp-Rabin