PrimeGrid

Da Wikipedia, l'enciclopedia libera.

PrimeGrid è un progetto di calcolo distribuito con lo scopo di generare un database pubblico contenente numeri primi, testare i numeri del Twin Internet Prime Search e testare un'implementazione di BOINC scritta in Perl. La ricerca dei numeri primi si basa sull'utilizzo dei crivelli (in inglese "sieving") e sul test di primalità LLR (test di Lucas–Lehmer–Riesel), una versione modificata del test di Lucas-Lehmer. Quindi quasi tutti i sottoprogetti avranno due client:

  • Sieving, secondo la teoria dei crivelli esegue un "setacciamento" per individuare i potenzialmente numeri primi da quelli sicuramente non primi (un esempio banale sarebbe quello di eliminare "a priori" i numeri pari, dei quali sarebbe inutile effettuare un test di primalità, sarebbe solo un spreco di risorse; ovviamente nel caso del Sieving la scelta è più sottile).
  • LLR, esegue il vero e proprio test di primalità (tra i numeri selezionati nella precedente fase di Sieving).

A gennaio 2012, il progetto aveva più di 8200 utenti attivi (per un totale di più di 16000 host attivi, appartenenti a 116 diverse nazioni del mondo) operando con una potenza totale stimata di più di 1445 teraFLOPS.[1]

Tutti i risultati ottenuti sono raccolti nel sito web The Primes Pages. L'aggiornamento continuo è fornito dal prof. Chris Caldwell, matematico presso l'università del Tennessee a Martin.[2]

Finalità[modifica | modifica wikitesto]

Oltre l'ovvia ricerca di base in campo matematico che il progetto si prefigge, esso porta aventi uno studio più pratico (e fortemente attuale) in quanto i numeri primi giocano un ruolo centrale anche nei sistemi crittografici, i quali sono usati per la sicurezza dei computer. Attraverso lo studio dei numeri primi sarà nota la quantità di lavoro necessaria per decifrare un codice crittografato e così sarà possibile valutare se gli attuali sistemi di sicurezza sono sufficientemente affidabili.

Sottoprogetti[modifica | modifica wikitesto]

PrimeGrid conta diversi sottoprogetti attualmente operanti o già conclusi nel tempo e alcuni di loro sono strettamente collegati:

321 Prime Search[modifica | modifica wikitesto]

Cerca i numeri primi nelle forme 3 \times 2^n+1 oppure 3 \times 2^n-1.

È interessante notare come 2^n-1 sia la forma generica dei numeri di Mersenne e che tutti i più grandi numeri primi scoperti ultimamente abbiano questa forma. I numeri primi di Mersenne sono anche legati ai numeri perfetti.

Il client è presente sia nella forma Sieving che LLR. I più grandi numeri primi scoperti (a marzo 2011) da questo sottoprogetto sono 3×27033641 +1 (2117338 cifre) e 3×26090515 -1 (1833429 cifre).

Cullen Search[modifica | modifica wikitesto]

Cerca i numeri primi di Cullen, ossia nella forma n \times 2^n + 1.

Il client è presente sia nella forma Sieving che LLR. Il più grande numero primo di Cullen (a marzo 2011) trovato dal sottoprogetto è 6679881×26679881 +1 (2010852 cifre).

Woodall Search[modifica | modifica wikitesto]

Cerca i numeri primi nella forma n \times 2^n-1. I numeri di Woodall per la loro similitudine nella rappresentazione coi numeri di Cullen vengono anche detti numeri di Cullen del secondo tipo.

Il client è presente sia nella forma Sieving che LLR. Il più grande numero primo di Woodall (a marzo 2011) trovato dal sottoprogetto è 3752948×23752948 -1 (1129757 cifre).

Proth Prime Search[modifica | modifica wikitesto]

Cerca i numeri di Proth che hanno la forma k \times 2^n+1 con k dispari e k<2^n. Tali numeri sono legati al teorema di Sierpinski.

Il client è presente sia nella forma Sieving che LLR. Il più grande numero primo di Proth conosciuto (a marzo 2011) è in realtà stato trovato dal sottoprogetto Seventeen or Bust ed è pari a 19249×213018586 +1 (3918990 cifre).

Prime Sierpinski Problem[modifica | modifica wikitesto]

Un numero di Sierpinski è un numero dispari k tale che k \times 2^n+1 sia "non primo" per qualunque numero naturale n. Cerca di verificare la congettura secondo la quale 78557 sia il più piccolo numero k di Sierpinski. Questo viene comunemente indicato come problema di Sierpinski.

Il client è presente sia nella forma Sieving che LLR.

AP26 Search[modifica | modifica wikitesto]

Concluso il 12 aprile 2010[3]. Cercava una progressione aritmetica di 26 primi, cioè una sequenza di 26 numeri primi che abbiano una differenza sempre costante.

Prima dell'inizio di questo progetto, le più lunghe progressioni aritmetiche conosciute erano composte di 25 numeri. Grazie a questo progetto, il 12 aprile 2010 è stata individuata la prima AP26 della storia. Lo scopritore è stato il francese Benoît Perichon membro del team L'Alliance Francophone.[4]

La pagina web di tutti risultati ottenuti è consultabile sul sito web di PrimeGrid.

Sophie Germain Prime Search[modifica | modifica wikitesto]

Il nome deriva da Marie-Sophie Germain, una matematica francese vissuta a cavallo tra il XVIII e XIX secolo. Cerca i numeri primi di Sophie Germain; un numero primo p è detto "primo di Sophie Germain" se anche 2p + 1 è un numero primo. La ricerca è concentrata sui numeri della forma k \times 2^n-1.

Se questo è primo, verranno analizzati anche:

k \times 2^n+1

k \times 2^ \left (n-1 \right )-1

k \times 2^ \left (n+1 \right )-1

Il client è presente solo nella forma LLR.

Twin Prime Search[modifica | modifica wikitesto]

Concluso nell'agosto 2009, immediatamente dopo la scoperta della coppia di numeri primi gemelli più grandi conosciuti ovvero 65516468355×2333333±1[5]. Due numeri primi vengono definiti gemelli quando differiscono fra loro per 2 unità (ad esempio: 5 e 7 oppure 11 e 13). Il progetto si concentrava sui numeri primi della forma k \times 2^n+1 e k \times 2^n-1 che presentino almeno 10.000 cifre (numeri primi giganti[6]).[7]

The Riesel Problem[modifica | modifica wikitesto]

Esistono infiniti numeri k dispari positivi tali che k \cdot 2^n-1 sia non primo per ogni n>1. Ogni numero k che rispetta tale legge è detto numero di Riesel. Il matematico svedese Hans Ivar Riesel ha congetturato che il numero 509 203 fosse il più piccolo numero di Riesel, ma tale congettura non è mai stata dimostrata. Questo sottoprogetto punta quindi a trovare un numero primo per ogni numero k<509\,203 aumentando progressivamente n nella k \cdot 2^n-1.

L'8 maggio 2011 è stato scoperto (tramite il client LLR), ad opera di Jakub Łuszczek (del Polish National Team), il numero primo nella forma k \cdot 2^n-1 per k=123\,547. Si tratta di un numero primo con più di un milione di cifre (1 145 367). Non restano che 60 numeri primi da scoprire per dimostrare la congettura di Riesel.[8]

Il client è presente sia nella forma Sieving che LLR. Il progetto è molto simile all'ormai abbandonato progetto di calcolo distribuito Riesel Sieve Project.

Seventeen or Bust[modifica | modifica wikitesto]

Anche questo sottoprogetto mira a risolvere il problema di Sierpinski (come Prime Sierpinski Problem). Il nome è dovuto al fatto che alla nascita del progetto, i k<78.557 erano 17. Attualmente ne rimangono solo 6, ma il nome è stato mantenuto ugualmente.
I due sottoprogetti condividono l'applicazione di sieving, infatti Seventeen or Bust ha solo il client LLR.

Tabella generale degli studi effettuati[modifica | modifica wikitesto]

Sulla piattaforma PrimeGrid hanno girato i seguenti programmi di ricerca (sottoprogetti), aggiornato a gennaio 2012:

Sottoprogetto Sottoprogetto attivo? Inizio Fine Risultati notevoli ottenuti
321 Prime Search (numeri primi nella forma 3×2n±1) 30 giugno 2008 Operante 3×26090515−1[9] e 3×27033641+1
AP26 Search N/A 27 dicembre 2008 12 aprile 2010 43142746595714191 + 23681770×23#×n, n = 0…25 (AP26)[10]
Cullen prime Search Sì (Woodall) agosto 2007 Operante 6679881×26679881+1, numero primo di Cullen più grande conosciuto[11]
Message7 No 12 giugno 2005 agosto 2005 PerlBOINC test, terminato con successo
Prime Sierpinski Problem Sì (Seventeen or Bust) 10 luglio 2008 Operante N/A
PrimeGen No marzo 2006 febbraio 2008
Proth prime Search 29 febbraio 2008 Operante 659×2617815+1, divide F(617813)[12]
Riesel Problem Marzo 2010 Operante 123547×23804809-1, scoperto da Jakub Łuszczek l'8 maggio 2011, ha più di un milione di cifre (1.145.367).[13]
RSA640 No agosto 2005 novembre 2005 N/A
RSA768 No novembre 2005 marzo 2006 N/A
Seventeen or Bust Sì (Prime Sierpinski Problem) 31 gennaio 2010 Operante 19249×213018586 +1, numero primo di Proth più grande conosciuto
Sophie Germain prime Search No 16 agosto 2009 Operante [14]
Twin Prime Search No 26 novembre 2006 25 luglio 2009 65516468355×2333333±1, la seconda coppia di primi gemelli più grande conosciuta[15]
Woodall prime Search Sì (Cullen) luglio 2007 Operante 3752948×23752948−1, più grande numero primo di Woodall conosciuto[16]

Software[modifica | modifica wikitesto]

Il software del progetto è basato sul Berkeley Open Infrastructure for Network Computing ed è usabile su GNU/Linux, Mac OS X e Microsoft Windows. In realtà ogni sottoprogetto ha un suo client che può essere compatibile o incompatibile solo con alcune piattaforme. In alcuni progetti è possibile utilizzare anche la forza computazionale delle GPU tramite stream processor (e librerie OpenCL) per schede video AMD, tramite CUDA per GPU Nvidia; ad esempio il sottoprogetto Proth Prime Search (Sieve) fa uso sia della tecnologia AMD FireStream che CUDA. Il sottoprogetto PS26 era invece in grado di funzionare anche su console PlayStation 3.

Progetti simili[modifica | modifica wikitesto]

  • GIMPS: ricerca numeri di Mersenne.
  • wep-m+2: studia le possibilità di fattorizzazione dei numeri di Mersenne +2 (cioè 2^n+1).
  • Riesel Sieve Project: "setaccia" i candidati per verificare la congettura di Riesel (ricerca il più piccolo numero di Riesel), analoga a quella di Sierpinski ma con la forma 2^n-1. Il progetto è attualmente fermo.

Note[modifica | modifica wikitesto]

  1. ^ Sito internet di BoincStats che riporta un resoconto dettagliato delle statistiche (quasi in tempo reale) di PrimeGrid.
  2. ^ Sito web del prof. Chris Caldwell.
  3. ^ Annuncio della scoperta della prima AP26.
  4. ^ Pagina web ufficiale che riporta la notizia della scoperta.
  5. ^ Annuncio della scoperta sul sito di PrimGrid.
  6. ^ Un numero primo gigante è proprio un numero primo con almeno 10,000 cifre decimali.
  7. ^ (FR) Articolo sui numeri primi gemelli sul sito web Futura-Sciences.
  8. ^ Sito web che riporta la scoperta del numero primo.
  9. ^ http://www.primegrid.com/download/321-6090515.pdf
  10. ^ Pagina web ufficiale che riporta la notizia della scoperta (12 aprile 2010).
  11. ^ http://www.primegrid.com/download/Cullen6679881.pdf
  12. ^ http://www.primegrid.com/download/PPS-F617815.pdf
  13. ^ Pagina web della scoperta.
  14. ^ Pagina web dei risultati trovati col sottoprogetto Sophie Germain Prime Search.
  15. ^ The Top Twenty: Twin Primes
  16. ^ http://www.primegrid.com/download/Woodall3752948.pdf

Voci correlate[modifica | modifica wikitesto]

Collegamenti esterni[modifica | modifica wikitesto]

matematica Portale Matematica: accedi alle voci di Wikipedia che trattano di matematica