PrimeGrid

Questa voce sull'argomento matematica dell'informazione e della comunicazione è solo un abbozzo.

Contribuisci a migliorarla secondo le convenzioni di Wikipedia.

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 potenziali 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.^[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]

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.

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

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

È interessante notare come ${\displaystyle 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).

Cerca i numeri primi di Cullen, ossia nella forma ${\displaystyle 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).

Cerca i numeri primi nella forma ${\displaystyle 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).

Cerca i numeri di Proth che hanno la forma ${\displaystyle k\times 2^{n}+1}$ con ${\displaystyle k}$ dispari e ${\displaystyle 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).

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

Il client è presente sia nella forma Sieving che LLR.

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.

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 ${\displaystyle p}$ è detto "primo di Sophie Germain" se anche ${\displaystyle 2p+1}$ è un numero primo. La ricerca è concentrata sui numeri della forma ${\displaystyle k\times 2^{n}-1}$.

Se questo è primo, verranno analizzati anche:

${\displaystyle k\times 2^{n}+1}$

${\displaystyle k\times 2^{\left(n-1\right)}-1}$

${\displaystyle k\times 2^{\left(n+1\right)}-1}$

Il client è presente solo nella forma LLR.

Concluso nell'agosto 2009, immediatamente dopo la scoperta della coppia di numeri primi gemelli più grandi conosciuti ovvero 65516468355×2³³³³³³±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 ${\displaystyle k\times 2^{n}+1}$ e ${\displaystyle k\times 2^{n}-1}$ che presentino almeno 10.000 cifre (numeri primi giganti^[6]).^[7]

Esistono infiniti numeri k dispari positivi tali che ${\displaystyle k\cdot 2^{n}-1}$ sia non primo per ogni ${\displaystyle 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 ${\displaystyle k<509\,203}$ aumentando progressivamente n nella ${\displaystyle 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 ${\displaystyle k\cdot 2^{n}-1}$ per ${\displaystyle 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.

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.

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

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.

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

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

• Wikimedia Commons contiene immagini o altri file su PrimeGrid

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

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