Valutazione attuale: 4 / 5

Stella attivaStella attivaStella attivaStella attivaStella inattiva
 

SRBase banner

 

 

Sia k un numero naturale dispari.

Dato l’insieme , k è un numero di Riesel se ogni elemento di R è un numero composto.

 

Sia k un numero naturale dispari.

Dato l’insieme   , k è un numero di Sierpinski se ogni elemento di S è un numero composto.

 

Come abbiamo appena visto, i numeri/elementi di R ed S, hanno base b=2.

È possibile generalizzare il problema di Riesel/Sierpinski a una base intera b≥2.

 

Sia k un numero intero positivo tale che MCD(k-1,b-1)=1 e che non sia una potenza razionale di b.

Dato l’insieme  , k è un numero di Riesel base b se ogni elemento di Rb è un numero composto.

 

Sia k un numero intero positivo k tale che MCD(k+1,b-1)=1 e che non sia una potenza razionale di b.

Dato l’insieme  , k è un numero di Sierpinski base b se ogni elemento di Sb è un numero composto.

 

Per ogni base b, mediante degli specifici programmi, viene congetturato un determinato k, chiamato ck dall'inglese "conjectured k", che è certamente numero di Riesel o Sierpinski e il più piccolo (è questa la congettura!) che soddisfi tale proprietà. Si noti che, a parità di base, il ck è diverso a seconda che sia di Riesel o di Sierpinski, quindi le congetture relative vanno trattate separatamente.

Fissata una base b, per trovare che ck è il più piccolo numero di Riesel/Sierpinski, prendiamo tutti i k più piccoli di ck. Vogliamo dimostrare che per ogni k<ck non tutti i numeri nella forma k*b^n-1 (oppure k*b^n+1, a seconda del caso) sono composti, ovvero ce n'è almeno uno primo. Ed è questo quello che il progetto fa effettivamente: cercare numeri primi, che non è l'obiettivo, bensì il mezzo.
Quando viene stabilita una congettura per una determinata base, ci sono migliaia di k candidati e potenzialmente infiniti numeri candidati da testare. Allora si parte con il sieving o setacciamento, che viene svolto in separata sede, fino a una certa profondità oltre la quale cercare fattori non è più tanto conveniente rispetto all'eseguire il test di primalità stesso. Comunque, tutti i candidati che sono stati fattorizzati grazie al sieving vengono depennati dalla lista, il che è un notevole sgravio per l'hardware che invece cercherà numeri primi.
Quindi, il server del progetto manda a ogni computer numeri da testare (workunits) e, se i test hanno esito negativo, aumenta progressivamente l'esponente n (l'unico parametro rimasto su cui lavorare) alla ricerca di numeri primi più grandi. Notiamo così che la durata dei test si allunga più si va avanti. È possibile infatti che non si trovi mai il controesempio che stiamo cercando ed è quello che è accaduto sino ad ora, per esempio, nel progetto Seventeen or Bust dove oramai stiamo testando n di 32 milioni!
Detto ciò, ogni volta che viene trovato un numero primo nella forma k*b^n±1, un k viene eliminato e non verranno più testati numeri con quel k. Risolvere una congettura di Riesel/Sierpinski o semplicemente risolvere una base, cosa che nel progetto SRBase viene premiata con un badge per chi elimina l’ultimo k, significa aver eliminato tutti i k candidati per tale base.

Così SRBase aiuta Conjectures 'R Us svolgendo una parte del lavoro per risolvere questi problemi, cioè trovare il più piccolo numero di Riesel/Sierpinski per le basi b con 2≤b≤1030, ma non è l'unico progetto BOINC che lo fa. Ci sono alcuni sottoprogetti di PrimeGrid come Sierpinski/Riesel Base 5 Problem che ha l'esclusiva sui numeri di Riesel/Sierpinski con b=5, il famoso Seventeen or Bust che si occupa dei numeri di Sierpinski con b=2, ecc. Il resto del lavoro viene svolto da volontari esterni a BOINC con il software apposito, ma sempre facenti parte del circuito del calcolo distribuito.

Per quanto riguarda la fattorizzazione dei numeri di Mersenne, si tratta ancora di fare sieving, ma per un altro progetto molto più importante, GIMPS, che cerca numeri primi di Mersenne ed è responsabile della scoperta dei più grandi numeri primi al mondo, ad oggi conosciuti.

 



Per commentare questo post nel forum devi effettuare il login

Articoli

Written on 31/05/2020, 10:32 by boboviz
multisessioni-boinc-su-pcIn questa guida vedremo come creare dei client multipli su una distribuzione GNU/Linux tramite l’utilizzo dei container Docker. E come gestirli tramite...

Ultime dal Blog

Written on 19/06/2017, 14:38 by boboviz
addio-lugano-bellaCari sodali scaccolatori,come alcuni di voi sanno, il sottoscritto, oltre ad essere appassionato di Boinc, è anche "appassionato" di HPC e, visto che il...