GIMPS

GIMPS (Great Internet Mersenne Prime Search) este un proiect de calcul voluntar la scară largă pentru căutarea numerelor prime Mersenne .

Obiectivele și metodele proiectului

A determina dacă un anumit număr este prim , în general, nu este o sarcină atât de banală. Abia în 2002 s- a dovedit a fi solubil polinomial . Cu toate acestea, algoritmul determinist propus (și strict justificat teoretic) este practic nepotrivit, datorită complexității sale mari, deși polinomiale. Prin urmare, în criptografia cu cheie publică , unde sunt folosite numere prime de ordine , primalitatea este încă determinată folosind teste probabilistice eficiente , cum ar fi testul Miller-Rabin . Dacă practica se mulțumește cu numere prime cu o probabilitate apropiată de , atunci teoria nu acceptă astfel de numere: dacă se spune că un număr este prim, acest lucru trebuie dovedit riguros. Această diferență este subliniată în împărțirea algoritmilor în probabilistici și determiniști.

Dacă vă întrebați care este cel mai mare număr prim [1] cunoscut omenirii, atunci răspunsul va fi un număr prim Mersenne . Numerele Mersenne au forma . Rețineți că simplitatea unui număr implică simplitatea lui ; în caz contrar, pentru și numărul nu va fi simplu având în vedere divizibilitatea prin (ca, într-adevăr, prin ).

După cum sugerează și numele, scopul proiectului GIMPS este de a găsi noi numere prime Mersenne. Cel mai mare număr prim cunoscut până acum a fost găsit de proiectul GIMPS pe 7 decembrie 2018 și este format din 24.862.048 de cifre zecimale. Mai mult, 15 recorduri anterioare au fost stabilite și de membrii GIMPS. Motivul constă în prezența unui criteriu efectiv (determinist) pentru simplitatea lor, care poartă numele de Luc-Lemaire . Pentru a căuta numerele prime Mersenne, serverul GIMPS distribuie clienților „exponenți” simpli pentru a testa numărul de prime cu testul Luc-Lehmer.

În iulie 2022, sunt cunoscute 51 de numere prime Mersenne, în timp ce numerele de serie ale primelor 48 dintre ele sunt cunoscute în mod fiabil. Numerele de serie ale celor mai mari trei numere prime Mersenne cunoscute nu au fost încă stabilite în mod fiabil (între ele pot exista și alte numere prime Mersenne, nedescoperite încă). [2]

Semnificație practică

Primele Mersenne dețin în mod constant recordul ca cele mai mari numere prime cunoscute.

În plus, numerele prime de Mersenne joacă un rol important în unele probleme din teoria numerelor . De exemplu, Euclid a descoperit că dacă un număr este prim, atunci numărul este perfect , adică egal cu suma propriilor divizori (exemple de astfel de numere: 6=1+2+3, 28=1+2+4 +7+14, 496=1+ 2+4+8+16+31+62+124+248, iar Euler a demonstrat ulterior că toate numerele perfecte pare au forma indicată (întrebarea existenței unui număr perfect impar este încă deschis ).

Întrebarea infinitului numărului de numere prime Mersenne și a asimptoticelor lor rămâne deschisă . Primele Mersenne găsite pot servi ca punct de plecare pentru prezentarea și testarea ipotezelor despre comportamentul primelor Mersenne.

În practică, numerele prime Mersenne sunt folosite pentru a construi generatoare de numere pseudoaleatoare cu perioade mari (vezi vortexul Mersenne ).

Premii în bani

GIMPS a câștigat [3] un premiu în numerar de 100.000 USD pentru găsirea unui număr prim de peste 10 milioane de cifre zecimale și intenționează să câștige premii similare de 150.000 USD și, respectiv, 250.000 USD promise [4] de Electronic Frontier Foundation pentru găsirea numerelor prime de la mai mult de 100 de milioane și 1 miliard de cifre zecimale. Din valoarea acestui premiu, se plănuiește să se facă plăți către toți „descoperitorii” anterioarelor prime Mersenne, autorii de software și autorii unor algoritmi de căutare noi, mai eficienți (dacă se găsesc astfel de algoritmi).

Găsit în august 2008, numărul conține 12.978.189 de cifre zecimale, ceea ce a adus GIMPS un premiu de 100.000 USD. Cu toate acestea, pentru a primi următorul premiu de 150.000 USD, va trebui să verificați pentru primalitate un număr de peste 100 de milioane de cifre zecimale, fiecare dintre acestea, odată cu dezvoltarea actuală a tehnologiei de calcul și algoritmice, va necesita mai mult de trei ani.

Efect competitiv

În fiecare zi, proiectul GIMPS primește rezultatele calculelor de la sute de colaboratori. Pentru fiecare dintre ele, proiectul menține statistici, publică și actualizează periodic evaluările de performanță și performanță. Pentru a spori efectul competitiv în proiect, a fost implementată posibilitatea de a combina participanții în echipe. În acest caz, rezultatele participantului sunt creditate nu numai lui, ci și echipei sale. În ceea ce privește participanții individuali, proiectul menține și actualizează evaluările echipelor.

Echipele sunt de obicei formate după locația participanților (țara sau orașul), prin apartenența la o organizație (instituție de învățământ sau companie) sau pur și simplu din dorința de a sprijini o anumită comunitate online.

În total, peste 1000 de echipe participă la proiect. Marea majoritate a acestora sunt mici, formate din unul sau mai mulți participanți, mulți au încetat de mult să fie activi. Cele mai mari echipe includ zeci/sute de participanți și adesea deținători de o putere de calcul mare: de la câteva computere personale până la o întreagă flotă de echipamente informatice a unei companii sau universități „sponsorizate”.

Adesea, se joacă o luptă serioasă pentru fiecare linie din evaluările echipei. Unele echipe coordonează în mod intenționat acțiunile membrilor lor pentru a face o descoperire în forma prevăzută de calcul și a ajunge la poziții superioare cât mai repede posibil. În general, ratingul TOP-10 al echipei este relativ stabil, surprizele sunt prezentate în principal de noi participanți care intră pe neașteptate în joc pentru una sau alta echipă. De aceea, echipele sunt întotdeauna bucuroși să primească noi participanți, iar cei mai vechi încearcă să îi ajute cu setările hardware și software cât mai mult posibil și să-i sfătuiască în alegerea celor mai interesante tipuri de calcule.

Probabilitatea de succes

Estimările euristice arată că mai există patru numere prime Mersenne necunoscute, constând din mai puțin de 100 de milioane de cifre zecimale, iar cea mai apropiată dintre ele poate consta din aproximativ 26 de milioane de cifre [5] . Informații detaliate despre posibila distribuție a acestora , precum și costurile de muncă preconizate pentru găsirea acestora, pot fi obținute pe pagina cu statisticile proiectului. [6]

Testare hardware

Programul client GIMPS efectuează calcule intensive, monitorizându-le în mod constant acuratețea. Prin urmare, mulți îl consideră un instrument excelent pentru testarea stabilității hardware - ului computerului . Încărcările de vârf și controlul strict facilitează identificarea problemelor cu memoria, memoria cache, magistrala de date, overclockarea și supraîncălzirea procesorului etc. Pentru a facilita procedura de testare, clientul GIMPS oferă posibilitatea de a lucra în modul „testare la stres”, când se efectuează calcule pentru numerele prime Mersenne cunoscute și rezultatele calculului sunt comparate cu cele așteptate.

Sisteme de operare acceptate

Partea client a software -ului proiectului GIMPS este disponibilă [7] pentru următoarele sisteme de operare :

• Microsoft Windows 7/Vista/XP/2008/2003/2000/NT/Me/98/95. Există, de asemenea, o versiune pentru versiunile pe 64 de biți de Windows 7/Vista/XP/2008.
• Mac OS X
• GNU/Linux (versiuni pe 64 și 32 de biți)
• FreeBSD (versiuni pe 64 și 32 de biți)

Note

1. ↑ The Largest Known Primes Arhivat 22 noiembrie 2008 la Wayback Machine 
2. ↑ GIMPS: List of Known Mersenne Prime Numbers Arhivat 15 martie 2016 la Wayback Machine 
3. ↑ Numărul prim record de 12 milioane de cifre aduce un premiu de 100.000 USD arhivat 5 august 2011 la Wayback Machine 
4. ↑ Premiile EFF Cooperative Computing Arhivate pe 9 noiembrie 2008 la Wayback Machine 
5. ↑ Unde este următorul prim Mersenne? Arhivat pe 9 martie 2021 la Wayback Machine 
6. ↑ Rezumatul activității PrimeNet Arhivat 12 ianuarie 2021 la Wayback Machine 
7. ↑ Descărcați clientul GIMPS Arhivat 18 octombrie 2013 la Wayback Machine 

Link -uri

• mersenne.org ​(  ing.) - site-ul oficial GIMPS (eng.)
• Instrumente GIMPS și  statistici avansate
• Forumul oficial  GIMPS
• Evaluarea participanților la proiectul GIMPS  (ing.)
• Evaluarea echipelor din proiectul GIMPS  (ing.)