Primegrid
Il existe deux types d'applications sur Primegrid :
- « Sieve » : ce sont des applications utilisant un crible c'est-à-dire utilisant la liste des nombres premiers déjà connues pour en trouver d'autre. Plus précisément le but de ces applications est d'éliminer les nombres non premiers d'une liste de nombres. L'exemple le plus simple et le plus connu (mais pas utilisé dans Primegrid) est le crible d'Ératosthène. Ces applications sont adaptées au parallélisme et donc au GPU.
- « LLR » ou autre : ces applications utilisent un test de primalité pour déterminer si un nombre donné est premier ou non. « LLR » (acronyme de Lucas–Lehmer–Riesel test) est le nom d'un test de primalité déterministe pour les nombres de la forme N = k⋅2n − 1, avec 2n > k. Pour plus d'information sur les différents algorithmes voir la fin du post.
Pour résumé les applications « Sieve » servent à éliminer rapidement une partie des nombres qui ne sont pas premier et les applications « LLR » permettent de tester si les nombres (restant) sont premiers ou non.
Voici une liste des différents sous-projets de Primegrid répartis par thème.
Projets en cours : Autour des nombres de Sophie GermainProjet concerné :Sophie Germain Prime Search (SGS) (début de la recherche : août 2009)
Description :Définition : On appelle nombre premier de Sophie Germain tout nombre premier p tel que le nombre 2p+1 soit aussi premier.
Exemple : 5 est un nombre premier de Sophie Germain car 5 est premier et 2 x 5 + 1 = 11 est aussi premier.
Conjecture : Il existe une infinité de nombres premiers de Sophie Germain.
Ces nombres ont été introduit vers 1825 par la mathématicienne
Marie-Sophie Germain qui démontra le
dernier théorème de Fermat pour de tels nombres premiers.
Aujourd'hui les nombres premiers de Sophie Germain sont utilisés en cryptographie et jouent un rôle important dans le
test de primalité AKS. De plus ils vérifient la propriété suivante.
Proposition : Si p est un nombre premier de Sophie Germain qui peut s'écrire de la forme p=4k-1 avec k > 1 alors le nombre 2p+1 divise
le nombre de Mersenne M
p = 2
p - 1.
L'application
SGS cherche des nombres premiers p de la forme k⋅2
n - 1 avec (en octobre 2014) n = 1 290 000 et k aux alentours de 1,5x10
12 ce qui donne des nombres à environ 380 000 chiffres. Si p est premier, le programme cherchera si les nombres p+2 = k⋅2
n + 1, (p-1)/2 = k⋅2
n-1 - 1 et 2p+1 = k⋅2
n+1 - 1 sont premiers. A noter que cette application cherche aussi des
nombres premiers jumeaux c'est-à-dire des nombres premiers p tel que p+2 soit aussi premier (cf.
Twin Prime Search).
État des résultats (2014) : Le plus grand nombre premier de Sophie Germain est 18 543 637 900 515 x 2
666 667 - 1. Il a été trouvé en avril 2012 et possède un peu plus de 200 000 chiffres.
Voici la liste des plus grands nombres premiers de Sophie Germain :
http://primes.utm.edu/top20/page.php?sort=SophieGermainRéférence :
http://www.primegrid.com/forum_thread.php?id=1450Biographie : Marie-Sophie Germain (1776 – 1831) est une est une mathématicienne et philosophe française. Elle est connue pour le théorème d’arithmétique qui porte son nom, pour ses échanges avec le mathématicien Carl Friedrich Gauss et pour ses travaux sur l’élasticité des corps.
Autour des nombres de ProthProjet concerné :Proth Prime Search (PPS et PPSE et MEGA et PPS-Sieve) (début de la recherche : février 2008)
321 Prime Search (321 et 321-Sieve) (début de la recherche : juin 2008)
Description :Définition : On appelle nombre premier de Proth tout nombre premier de la forme k⋅2
n + 1 avec k un nombre impair vérifiant k < 2
n.
Exemples : 3 = 2
1 + 1 ; 5 = 2
2 + 1 et 41 = 5 x 2
3 + 1 sont des nombres premiers de Proth.
L'application
PPS s'intéresse aux nombres premiers de Proth avec k < 1200 et n aux alentours de 2 100 000 ce qui donne des nombres à environ 650 000 chiffres.
L'application
PPSE s'intéresse aux nombres premiers de Proth avec 1 200 < k < 10 000 et n aux alentours de 1 300 000 ce qui donne des nombres à environ 400 000 chiffres.
L'application
MEGA s'intéresse aux nombres premiers de Proth avec 100 < k < 300 et 3 322 000 < n < 3 600 000 ce qui donne des nombres à plus de 1 000 000 chiffres.
L'application
321 s'intéresse aux nombres premiers de Proth de la forme 3 x 2
n + 1 et aux nombres premiers de la forme 3 x 2
n - 1 avec 11 000 000 < n < 25 000 000 ce qui donne des nombres à plus de 3 400 000 chiffres.
État des résultats (2014) : Le plus grand nombre premier de Proth connu en septembre 2014 est 19 249 x 2
13 018 586 + 1. Il a été découvert en mai 2007 et possède un peu plus de 3,9 millions de chiffres.
Le plus grand nombre premier trouvé par le sous-projet
321 Prime Search est 3 x 2
10 829 346 + 1. Il a été découvert en janvier 2014 et possède un peu plus de 3,2 millions de chiffres.
Voici la liste des plus grands nombres premiers de Proth :
http://primes.utm.edu/top20/page.php?id=66Référence :
http://www.primegrid.com/forum_thread.php?id=2665Biographie : François Proth (1852 – 1879) est un mathématicien autodidacte français (aussi agriculteur), qui a vécu près de Verdun. Il s'intéressa surtout à l'étude des nombres premiers et établit le
théorème de Proth.
Autour des nombres de CullenProjet concerné :Cullen prime search (CUL) (début de la recherche : août 2007)
Description :Définition : On appelle nombre premier de Cullen tout nombre premier de la forme n⋅2
n + 1.
Exemple : 3 est un nombre premier de Cullen car 3 est premier et 3 = 1 x 2
1 + 1. Le deuxième nombre de Cullen est 141 x 2
141 + 1.
Remarques : Il a été montré en 1976 qu'il y avait très peu de nombres premiers de Cullen.
Conjecture : Il existe une infinité de nombres premiers de Cullen. De plus on ne sait pas s'il existe un nombre premier p tel que p⋅2
p + 1 soit aussi premier.
L'application
CUL cherche des nombres premiers de Cullen avec n aux alentours de 12 500 000 ce qui donne des nombres à plus de 3 750 000 chiffres.
État des résultats (2014) : Le plus grand nombre premier de Cullen est 6 679 881 × 2
6 679 881 + 1. Il a été trouvé en août 2009 et possède un peu plus de 2 000 000 de chiffres.
Voici la liste des plus grands nombres premiers de Cullen :
http://primes.utm.edu/top20/page.php?id=6Référence :
https://en.wikipedia.org/wiki/Cullen_numberBiographie : James Cullen (1867 – 1933) est un prêtre jésuite irlandais et mathématicien de renom. Il a introduit en 1905 les nombres de Cullen.
Autour des nombres de WoodallProjet concerné :Woodall prime search (WOO) (début de la recherche : juillet 2007)
Description :Définition : On appelle nombre premier de Woodall tout nombre premier de la forme n⋅2
n - 1.
Exemple : 7 est un nombre premier de Woodall car 7 est premier et 7 = 2 x 2
2 - 1.
Remarques : Comme pour les nombres de Cullen, il y a très peu de nombres premiers de Woodall. Cependant il y a plus de "petits" exemples de nombre de Woodall (1, 7, 23, 63, 159, 383, 895, …).
Conjecture : Il existe une infinité de nombres premiers de Woodall.
L'application
WOO cherche des nombres premiers de Woodall avec n aux alentours de 13 000 000 ce qui donne des nombres à plus de 4 000 000 chiffres.
État des résultats (2014) : Le plus grand nombre premier de Woodall est 3 752 948 × 2
3 752 948 − 1. Il a été trouvé en décembre 2007 et possède un peu plus de 1 000 000 de chiffres.
Voici la liste des plus grands nombres premiers de Woodall :
http://primes.utm.edu/top20/page.php?sort=WoodallRéférence :
https://fr.wikipedia.org/wiki/Nombre_de_WoodallBiographie : Herbert J. Woodall est un mathématicien britannique. Il a introduit en 1917 les nombres de Woodall.
Autour des nombres de SierpińskiProjets concernés :Seventeen or Bust (SOB) (début de la recherche : janvier 2010)
Prime Sierpinski Problem (PSP) (début de la recherche : juillet 2008)
Extended Sierpinski Problem (ESP et ESP-Sieve) (début de la recherche : mars 2010)
Description :Définition : On dit que k est un nombre de Sierpiński s'il est impair et si pour tout entier naturel n, le nombre k⋅2
n + 1 n'est pas premier.
Exemples : 3 n'est pas un nombre de Sierpiński car pour n = 2 on a 3 x 2
2 + 1 = 13 qui est un nombre premier.
En 1962, John Selfridge démontre que 78 557 est un nombre de Sierpiński. Pour cela il démontre que pour tout entier naturel n, le nombre 78557 x 2
n + 1 est divisible par (au moins) l'un de ces nombres : 3, 5, 7, 13, 19, 37, 73.
En 1960, Wacław Sierpiński montre la proposition suivante
Proposition : Il existe une infinité de nombre de Sierpiński.
Résoudre le problème de Sierpiński consiste à trouver le plus petit nombre de Sierpiński.Conjecture : 78 557 est le plus petit nombre de Sierpiński.
On sait que 78 557 est bien un nombre de Sierpiński. Il reste donc à montrer que pour tout entier impair k inférieur à 78 556, on peut trouver un nombre premier de la forme k⋅2
n + 1.
État des résultats (2014) : Pour montrer la conjecture il ne reste plus qu'à montrer que six nombres ne sont pas des nombres de Sierpiński.
En voici la liste : 10223 ; 21181 ; 22699 ; 24737 ; 55459 ; 67607.
L'application
Seventeen or Bust (SOB) a pour but de résoudre le le problème de Sierpiński en trouvant un nombre premier de la forme k⋅2
n + 1 pour chaque k dans la liste de nombres précédente. Ce projet s'appelle « Seventeen or Bust » car au lancement (en 2002) il fallait montrer que 17 nombres n'étaient pas des nombres de Sierpiński. Depuis le projet a réussi à en exclure 11 d'entre eux (il devrait aujourd'hui se nommer « Six or Bust » mais le nom original a été gardé). Le dernier nombre premier trouvé par ce projet est 33 661 x 2
7 031 232 + 1, qui a été découvert en octobre 2007 et il possède plus de 2 000 000 de chiffres.
Référence :
http://www.primegrid.com/forum_thread.php?id=1647Résoudre le problème des nombres premiers de Sierpiński consiste à trouver le plus petit nombre de Sierpiński qui est premier.Conjecture : 271 129 est le plus petit nombre premier de Sierpiński.
On sait que 271 129 est bien un nombre premier de Sierpiński. Il reste donc à vérifier que c'est le plus petit.
État des résultats (2014) : Pour montrer la conjecture il ne reste plus qu'à montrer que onze nombres ne sont pas des nombres premiers de Sierpiński.
En voici la liste : 10223 ; 22699 ; 67607 ; 79309 ; 79817 ; 152267 ; 156511 ; 168451 ; 222113 ; 225931 ; 237019.
L'application
Prime Sierpinski Problem (PSP) a pour but de résoudre le problème des nombres premiers de Sierpiński en trouvant un nombre premier de la forme k⋅2
n + 1 pour chaque k dans la liste de nombres précédente. Depuis le début de la recherche, le projet a réussi à montrer que 18 nombres n'était pas des nombres premiers de Sierpiński. Le dernier nombre premier trouvé par ce projet est 90 527 x 2
9 162 167 + 1, qui a été découvert en juin 2010 et il possède un peu plus de 2 750 000 chiffres.
Référence :
http://www.mersenneforum.org/showthread.php?t=2665Résoudre le problème étendu de Sierpiński consiste à trouver le deuxième plus petit nombre de Sierpiński.Conjecture : 271 129 est le deuxième plus petit nombre de Sierpiński.
En supposant les deux premières conjectures établies, cela n’entraîne pas que 271 129 soit le deuxième plus petit nombre de Sierpiński. C'est pour cela que ce problème étend la recherche des nombres de Sierpiński entre 78 557 et 271 129. De plus comme le problème des nombres premiers de Sierpiński s'intéresse déjà aux nombres premiers de Sierpiński inférieurs à 271 129, ce problème s'intéresse exclusivement aux nombres non premiers entre 78 557 et 271 129 pouvant être de Sierpiński.
État des résultats (2014) : Pour montrer la conjecture il ne reste plus qu'à montrer que douze nombres ne sont pas des nombres de Sierpiński.
En voici la liste : 91549 ; 99739 ; 131179 ; 161041 ; 163187 ; 193997 ; 200749 ; 202705 ; 209611 ; 227723 ; 229673 ; 238411.
L'application
Extended Sierpinski Problem (ESP et ESP-Sieve) a pour but de résoudre le problème étendu de Sierpiński en trouvant un nombre premier de la forme k⋅2
n + 1 pour chaque k dans la liste de nombres précédente. Depuis le début de la recherche, le projet a réussi à montrer que 19 nombres n'était pas des nombres premiers de Sierpiński. Le dernier nombre premier trouvé par ce projet est 211 195 x 2
3 224 974 + 1, qui a été découvert en mars 2013 et il possède plus de 950 000 chiffres.
Référence :
http://www.primegrid.com/forum_thread.php?id=5758Biographie : Wacław Franciszek Sierpiński (Varsovie, 1882 - Varsovie, 1969) est un mathématicien polonais, connu pour ses contributions à la théorie des ensembles, la théorie des nombres, la théorie des fonctions et la topologie.
Autour des nombres de RieselProjets concernés :The Riesel Problem (TRP et TRP-Sieve) (début de la recherche : mars 2010)
Description :Le problème de Riesel est très similaire au problème de Sierpiński mais au lieu de considérer les nombre de la forme k⋅2
n + 1, on considère ici les nombres de la forme k⋅2
n - 1.
Définition : On dit que k est un nombre de Riesel s'il est impair et si pour tout entier naturel n, le nombre k⋅2
n - 1 n'est pas premier.
Exemples : 5 n'est pas un nombre de Riesel car pour n = 4 on a 5 x 2
4 - 1 = 79 qui est un nombre premier.
En 1956, Hans Riesel démontre que 509 203 est un nombre de Riesel. Il démontre par la même occasion que pour tout entier naturel q, le nombre 509 203 + 11 184 810 x q est un nombre de Riesel. On a ainsi la proposition suivante.
Proposition : Il existe une infinité de nombre de Sierpiński.
Résoudre le problème de Riesel consiste à trouver le plus petit nombre de Riesel.Conjecture : 509 203 est le plus petit nombre de Riesel.
On sait que 509 203 est bien un nombre de Riesel. Il reste donc à montrer que pour tout entier impair k inférieur à 509 203, on peut trouver un nombre premier de la forme k⋅2
n - 1.
État des résultats (2014) : Pour montrer la conjecture il ne reste plus qu'à montrer que 50 nombres ne sont pas des nombres de Riesel.
En voici la liste : 2293 ; 9221 ; 23669 ; 31859 ; 38473 ; 46663 ; 67117 ; 74699 ; 81041 ; 93839 ; 97139 ; 107347 ; 121889 ; 129007 ; 143047 ; 146561 ; 161669 ; 192971 ; 206039 ; 206231 ; 215443 ; 226153 ; 234343 ; 245561 ; 250027 ; 273809 ; 315929 ; 319511 ; 324011 ; 325123 ; 327671 ; 336839 ; 342847 ; 344759 ; 362609 ; 363343 ; 364903 ; 365159 ; 368411 ; 371893 ; 384539 ; 386801 ; 397027 ; 409753 ; 444637 ; 470173 ; 474491 ; 477583 ; 485557 ; 494743.
Les applications
TRP et TRP-Sieve ont pour but de résoudre le le problème de Riesel en trouvant un nombre premier de la forme k⋅2
n - 1 pour chaque k dans la liste de nombres précédente. Depuis son lancement ce projet a réussi à montrer que 14 nombres n'étaient pas de Riesel. Le dernier nombre premier trouvé par ce projet est 502 573 x 2
7 181 987 - 1, qui a été découvert en octobre 2014 et il possède plus de 2 150 000 de chiffres.
Référence :
http://www.primegrid.com/forum_thread.php?id=1731Contrairement au problème des nombres premiers de Sierpiński, il n'y a pas de problème des nombres premiers de Riesel puisque 509 203 est premier.
Biographie : Hans Riesel ( Stockholm, 1929 - ) est un mathématicien suédois. Il est célèbre pour avoir trouvé en 1957 le dix-huitième nombre premier de Mersenne, demeuré jusqu'en 1961 le plus grand nombre premier connu. Il a également étudié et donné leur nom aux nombres de Riesel. Cependant les nombres de Sierpiński ont reçu plus d'attention que les nombres de Riesel, peut-être parce que l'article de Riesel était en suédois.