Test de simplitate

Versiunea actuală a paginii nu a fost încă examinată de colaboratori experimentați și poate diferi semnificativ de versiunea revizuită pe 21 mai 2020; verificarea necesită 1 editare .

Întrebarea de a determina dacă un număr natural este prim este cunoscută ca problema primalității. $N$

Un test de primalitate (sau test de primalitate) este un algoritm care, luând ca intrare un număr , permite fie să nu confirme ipoteza despre compoziția numărului, fie să afirme cu acuratețe simplitatea acestuia. În al doilea caz, se numește adevăratul test de primalitate. Astfel, testul de primalitate este doar o ipoteză conform căreia, dacă algoritmul nu confirmă ipoteza că numărul este compus , atunci acest număr poate fi prim cu o anumită probabilitate . Această definiție implică mai puțină încredere în conformitatea rezultatului testului cu adevărata stare de fapt decât un test de primalitate adevărată, care dă un rezultat verificat matematic. $N$ $N$

Introducere

Problemele de matematică discretă sunt printre cele mai complexe din punct de vedere matematic . Una dintre ele este problema factorizării , care constă în găsirea factorizării unui număr în factori primi. Pentru a o rezolva, trebuie să găsiți numere prime, ceea ce duce la problema simplității. Problema testului de primalitate aparține clasei de complexitate P , adică timpul de rulare al algoritmilor de rezolvare a acesteia depinde polinomial de mărimea datelor de intrare, ceea ce a fost dovedit în 2002 . Există o afirmație similară, dar nedovedită, pentru problema factorizării .

Unele aplicații ale matematicii care utilizează factorizarea necesită o serie de numere prime foarte mari alese la întâmplare. Algoritmul pentru obținerea lor, bazat pe postulatul lui Bertrand :

Algoritm:

Intrare : număr natural $N$
Soluție (căutați un număr prim aleatoriu P)
1. $P\gets$ Funcția de a genera un număr natural arbitrar pe un segment $[N,2N]$
2. Dacă este compus, atunci $P$
  1. $P\săgeată la stânga \,P+1$
  2. Dacă atunci $P=2N$
    1. $P\săgeată la stânga \,N$
3. Returnează „ - prim aleatoriu” $P$

Timpul pentru rezolvarea problemei prin acest algoritm nu este definit, dar există o mare probabilitate ca acesta să fie întotdeauna polinomial, atâta timp cât există suficiente numere prime și sunt distribuite mai mult sau mai puțin uniform . Pentru numere aleatoare simple, aceste condiții sunt îndeplinite.

Se știe ( teorema lui Euclid ) că mulțimea primelor este infinită. Teorema lui Dirichlet ( 1837 ) spune că dacă mcd , atunci există infinit de numere prime congruente cu modulo . Cu alte cuvinte, numerele prime sunt distribuite uniform în clase de reziduuri conform funcției Euler [1] pentru orice valoare a lui . Cu toate acestea, dacă numerele prime sunt distribuite uniform, dar sunt foarte puține, căutarea poate să nu fie posibilă în practică. Pentru a rezolva această a doua problemă, folosim Teorema numerelor prime ( 1896 ), conform căreia numărul de numere prime dintr-un interval crește cu . Acest număr tinde la infinit destul de repede, din care putem concluziona că și pentru valori mari există o probabilitate destul de mare ( ) de a găsi un număr prim la întâmplare. Din aceasta putem concluziona că algoritmul descris mai sus poate da răspunsul în timp polinomial dacă există un algoritm polinomial care ne permite să verificăm simplitatea unui număr arbitrar de mare , ceea ce duce la problema primalității. $(a,n)=1$ $A$ $n$ $modn$ $\varphi (n)$ $n$ $[2,n]$ $n$ $n/log(n)$ $n$ $1/ln(n)$ $n$

Informații istorice

Prima mențiune a numerelor prime este cunoscută de la Euclid ( secolul al III-lea î.Hr. ). În același timp, primul algoritm pentru găsirea numerelor prime a fost inventat de Eratosthenes ( secolul II î.Hr. ) și este acum cunoscut sub numele de sita lui Eratosthenes . Esența sa constă în excluderea secvențială din lista numerelor întregi de la multiplii altor numere prime găsite deja de „sită” [2] . Mult mai târziu, matematicianul arab Ibn al-Banna a propus enumerarea numerelor întregi nu până la , ci până la , ceea ce a făcut posibilă reducerea numărului de operații. Dezavantajul acestei metode este că, în loc să verifice un număr dat pentru simplitate, oferă o enumerare secvențială [3] a tuturor numerelor întregi până la , și, prin urmare, este ineficientă și necesită o putere de calcul semnificativă . $unu$ $n$ $2,3,5$ $n$ ${\sqrt {n}}$ $n$ ${\sqrt {n}}$

La începutul secolului al XIII-lea, Leonardo din Pisa , cunoscut sub numele de Fibonacci, a propus o secvență de numere (numită după el), una dintre proprietățile căreia este că --lea număr Fibonacci poate fi doar prim pentru numerele prime , cu excepția lui . Această proprietate poate fi utilizată atunci când se testează numerele Fibonacci pentru primalitate. El, de asemenea, independent de ibn al-Banna, a propus o metodă de verificare a simplității numerelor prin enumerare. Acest algoritm este adevărat (sau improbabil) deoarece răspunsul este întotdeauna obținut, dar extrem de ineficient. $n$ $F_{n}$ $n$ $n=4$

Primul care a folosit relațiile dintre numere pentru a defini primalitatea a fost Pietro Antonio Cataldi în lucrarea sa despre numerele perfecte. Numerele perfecte sunt acelea care sunt egale cu suma propriilor divizori. Primele șapte numere perfecte sunt 6, 28, 496, 8128, 33550336, 8589869056 și 137438691328. Cataldi a stabilit că dacă un număr este prim și numărul este de asemenea prim, atunci numărul este perfect. $n$ $2^{n}-1$ $2^{{n-1}}(2^{n}-1)$

În secolul al XVII-lea, matematicianul francez Marin Mersenne s-a angajat în studiul numerelor de forma [4] , numit mai târziu numere Mersenne în cinstea sa . Mersenne a descoperit că dintre primele 257 de numere Mersenne, doar 11 sunt prime (pentru n = 2, 3, 5, 7, 13, 17, 19, 31, 67, 127 și 257). Făcând acest lucru, a făcut mai multe greșeli ( nu este prim la p = 67 sau 257 și este la p = 61, 89 și 107). Căutarea numerelor prime printre numerele Mersenne este destul de simplă datorită testului Luc-Lehmer , care vă permite să găsiți o soluție relativ rapid. De aceea, numerele Mersenne sunt cele mai mari dintre numerele prime cunoscute în prezent. În corespondența dintre Mersenne și Fermat s-au exprimat mai multe idei cu privire la numerele prime [4] . $2^{n}-1$ $2^{n}-1$

Deci, Fermat a descoperit că, dacă un întreg nu este divizibil cu un număr prim , atunci numărul este întotdeauna divizibil cu ( Mica Teoremă a lui Fermat ). Teorema a fost generalizată mai târziu de Euler . Mai multe teste de primalitate se bazează pe Teorema Mică a lui Fermat. Fermat a sugerat, de asemenea, că numerele de formă pentru toate numerele naturale sunt prime . Acesta este într-adevăr cazul pentru . Un contraexemplu la această afirmație a fost găsit de Euler— . Pentru a testa numerele Fermat pentru primalitate, există un test Pepin eficient . Până în prezent, nu au fost găsite numere prime Fermat noi. $A$ $p$ $a^{{p-1}}-1$ $p$ $2^{2^{k}}+1$ $k$ $k=0,1,2,3,4$ $2^{2^{5}}+1=4294967297=641\cdot 6700417$

Printre alți oameni de știință, Euler, Legendre , Gauss s-au ocupat de simplitatea numerelor . Rezultate semnificative în rezolvarea problemei primalității au fost obținute de matematicianul francez Édouard Lucas în lucrarea sa despre numerele Fermat și Mersenne. Este criteriul pentru simplitatea numerelor Mersenne date de el, care este acum cunoscut sub numele de testul Lucas-Lehmer.

În 2002, a fost dezvoltat un test de primalitate polinomială deterministă, testul Agrawal-Kayal-Saxena . Apariția sa a fost prezisă de existența certificatelor de primalitate polinomială și, în consecință, de faptul că problema verificării primarității unui număr a aparținut claselor NP și co-NP în același timp.

Teste de primalitate adevărată

Algoritmii existenți pentru testarea unui număr pentru primalitate pot fi împărțiți în două categorii: teste de primalitate adevărată și teste de primalitate probabilistică. Testele adevărate ca rezultat al calculelor scot întotdeauna la iveală faptul simplității sau compoziției unui număr, un test probabilistic oferă un răspuns despre compoziția unui număr sau necompunerea acestuia cu o oarecare probabilitate [2] [4] . Pentru a spune simplu, algoritmul probabilistic spune că numărul cel mai probabil nu este compus, dar în cele din urmă se poate dovedi fie prim, fie compus. Numerele care satisfac testul de primalitate probabilistică, dar sunt compuse, se numesc pseudoprime [1] . Un exemplu de astfel de numere sunt numerele Carmichael [3] . De asemenea, puteți numi numerele Euler-Jacobi pentru testul Solovay-Strassen și pseudoprimele Lucas. $\epsilon$

Un exemplu de teste de primalitate adevărată este testul Luc-Lehmer pentru numerele Mersenne . Dezavantajul evident al acestui test este că se aplică doar unui număr de anumite tipuri de numere. Alte exemple includ cele bazate pe Mica Teoremă a lui Fermat :

Testul lui Pepin pentru numerele Fermat .
Teorema lui Proth pentru numerele lui Proth .
Testul Agrawal–Kayala–Saxene , primul test de primalitate polinomială.
Testul Luc-Lehmer-Riesel .

Precum și:

metoda iterației divizorului .
Teorema lui Wilson .
Criteriul Pocklington .
Testul Miller .
Testul Adleman-Pomerans-Rumeli , îmbunătățit [5] de Cohen și Lenstroy
Test de primalitate folosind curbe eliptice .

Teste de primalitate probabilistică

Această categorie include:

Teste de simplitate în criptografie

În prezent, numerele prime sunt utilizate pe scară largă în domeniul securității informațiilor. În primul rând, acest lucru se datorează invenției metodei de criptare a cheii publice, care este utilizată în criptarea informațiilor și în algoritmii de semnătură digitală electronică . În prezent, conform standardelor, dimensiunea numerelor prime utilizate la formarea unei semnături digitale folosind curbe eliptice este, în conformitate cu GOST R 34.10-2012, de cel puțin 254 de biți. Pentru numere atât de mari, problema determinării primei unui număr este extrem de dificilă. Metodele simple, cum ar fi metoda de enumerare, sunt nepotrivite pentru utilizare datorită faptului că necesită o cantitate extrem de mare de resurse de calcul și o cantitate mare de timp [6] .

De asemenea, determinarea primei unui număr este necesară atunci când spargerea informațiilor criptate sau semnate folosind algoritmul RSA . Pentru a deschide un astfel de mesaj, este necesar să puteți descompune un număr în doi factori primi, ceea ce este o sarcină netrivială pentru numerele mari.

Pe de altă parte, atunci când se generează chei pentru criptosisteme cu cheie publică , scheme de semnătură electronică etc., sunt folosite numere prime mari pseudoaleatoare. De exemplu, atunci când utilizați protocolul Diffie-Hellman, este necesar să aveți un număr prim care să specifice câmpul final . Prin urmare, utilizarea unui test de primalitate eficient face posibilă creșterea fiabilității algoritmilor pentru generarea unor astfel de chei.

Vezi și

Note

↑ 1 2 Kormen T., Leiser C. Algoritmi. Construcție și analiză. - M. : MTSNMO, 2002. - S. 765-772.
↑ 1 2 Vasilenko O. N. Algoritmi de teorie numerică în criptografie. - M. : MTSNMO, 2003. - 328 p.
↑ 1 2 Crandall R., Pomerance C. Prime Numbers: A Computational Perspective. — Springer, 2005.
↑ 1 2 3 Donald Knuth . Arta programarii, volumul 2. Algoritmi derivati. - M .: „Williams” , 2007.
↑ Nesterenko Yu. V. Introducere în criptografie. - Petru, 2001. - 288 p.
↑ B. Schneier. Criptografia aplicată. - S. 296-300.

Literatură

Vasilenko O. N. Capitolul 1. Testarea numerelor pentru primalitate și construirea numerelor prime mari // Algoritmi teoretici numeric în criptografie . - M. : MTSNMO, 2003. - S. 12-56. — 328 p. — ISBN 5-94057-103-4 . Arhivat pe 27 ianuarie 2007 la Wayback Machine
Nesterenko Yu. V. Capitolul 4.6. Cum se verifică un număr mare pentru simplitate // Introducere în criptografie / Ed. V. V. Iascenko. - Petru, 2001. - 288 p. - ISBN 5-318-00443-1 . Arhivat pe 25 februarie 2008 la Wayback Machine
Schneier B. Partea 3. Algoritmi criptografici. Capitolul 11 11.5. Generarea numerelor prime // Criptografie aplicată. Protocoale, algoritmi, cod sursă în limbaj C = Criptografie aplicată. Protocoale, algoritmi și cod sursă în C. - M. : Triumph, 2002. - S. 296-300. — 816 p. - 3000 de exemplare. - ISBN 5-89392-055-4 .
Kormen T., Leiser C. Capitolul 33.8. Verificarea numerelor pentru simplitate // Algoritmi. Construcție și analiză . - M. : MTSNMO, 2002. - S. 765-772. - ISBN 5-900916-37-5 .
Crandall R., Pomerance C. Capitolul 3. Recunoașterea primelor și compozitelor. Capitolul 4. „Demonstrarea primalității” // Numerele prime: o perspectivă computațională . - Springer, 2005. - S. 117-224. — ISBN 0-387-25282-7 .
Donald Knuth . Capitolul 4.5.4. Prime Factorization // The Art of Programming, Volumul 2. Algoritmii rezultați = The Art of Computer Programming, vol. 2. Algoritmi semimerici. - Ed. a 3-a. - M .: „Williams” , 2007. - S. 832. - ISBN 0-201-89684-2 .

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

Algoritmi de teoria numerelor
Teste de simplitate	Test AKC Test APR Bailey-PSU Curba eliptică criteriul Pocklington Test de fermă Testul lui Luke Testul Luc-Lehmer Testul Luc-Lehmer-Riesel teorema lui Prot Testul Pepin Testul Frobenius cuadratic Testul Nightingale-Strassen Testul Miller-Rabin
Generarea numerelor prime	sita lui Atkin Sita lui Eratosthenes Sieve Sundarama Decay Wheel
Factorizarea numerelor întregi	Metoda fracțiunii continue algoritmul lui Dixon Metoda curbei eliptice metoda Euler Algoritmul ρ al lui Pollard p −1 Metoda Pollard p +1-Metoda Williams Sita pătrată Metoda generală de sită a câmpului cu numere Metoda sită de câmp cu numere speciale Sita rațională Metoda Fermat Forme de tije pătratice Iterarea peste divizori algoritmul lui Shor
Înmulțire	Egipteanul antic Înmulțirea cu o coloană Karatsuba Algoritmul Toom-Cook Schönhage - Strassen Fuhrer
Logaritm discret	Algoritmul Gelfond-Shanks ρ-algoritm "Cangur" Polyga - Hellman calculul de ordine Funcție sită de câmp
Cel mai mare divizor comun	Algoritm binar algoritmul lui Euclid Algoritmul extins al lui Euclid Algoritmul GCD al lui Lemaire
Rădăcină pătrată modulară	Algoritmul Cipolla algoritmul Pocklington Algoritmul Gelfond-Shanks
Alti algoritmi	Metoda Chakrawala Algoritmul lui Kornakkiya LLL rădăcină pătrată întreagă Modul de exponențiere Algoritmul lui Shuf
Font italic înseamnă că algoritmul este conceput pentru numere de un tip special