PrimeGrid

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 uno 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.

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.

Finalità

Oltre l'ovvia ricerca di base in campo matematico che il progetto si prefigge, esso porta avanti 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

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

321 Prime Search

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×2^7033641 +1 (2117338 cifre) e 3×2^6090515 -1 (1833429 cifre).

Cullen Search

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×2^6679881 +1 (2010852 cifre).

Woodall Search

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×2^3752948 -1 (1129757 cifre).

Proth Prime Search

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×2^13018586 +1 (3918990 cifre).

Prime Sierpinski Problem

Un numero di Sierpiński è 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

Concluso il 12 aprile 2010. 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.

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

Sophie Germain Prime Search

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

Concluso nell'agosto 2009, immediatamente dopo la scoperta della coppia di numeri primi gemelli più grandi conosciuti ovvero 65516468355×2³³³³³³±1. 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).

The Riesel Problem

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.

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

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

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)	Sì	30 giugno 2008	Operante	3×26090515−1 e 3×27033641+1
AP26 Search	N/A	27 dicembre 2008	12 aprile 2010	43142746595714191 + 23681770×23#×n, n = 0…25 (AP26)
Cullen prime Search	Sì (Woodall)	agosto 2007	Operante	6679881×26679881+1, numero primo di Cullen più grande conosciuto
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	Sì	29 febbraio 2008	Operante	659×2617815+1, divide F(617813)
Riesel Problem	Sì	Marzo 2010	Operante	123547×23804809-1, scoperto da Jakub Łuszczek l'8 maggio 2011, ha più di un milione di cifre (1.145.367).
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
Twin Prime Search	No	26 novembre 2006	25 luglio 2009	65516468355×2333333±1, la seconda coppia di primi gemelli più grande conosciuta
Woodall prime Search	Sì (Cullen)	luglio 2007	Operante	3752948×23752948−1, più grande numero primo di Woodall conosciuto

Software

Il software del progetto è basato sul Berkeley Open Infrastructure for Network Computing ed è usabile su GNU/Linux, macOS 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

• 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.

Voci correlate

• Numero primo
• Lista dei progetti di calcolo distribuito
• Twin Internet Prime Search
• GIMPS
• Berkeley Open Infrastructure for Network Computing

Altri progetti

Altri progetti

• Wikimedia Commons

• Wikimedia Commons contiene immagini o altri file su PrimeGrid

Collegamenti esterni

• (EN) Sito ufficiale, su primegrid.com.