PAGE EN CONSTRUCTION
Cette page a pour but de décrire et d'expliquer les théorèmes et conjectures mathématiques sur lesquels les différents projets travaillent.
Voici la liste (encore provisoire et risque de diminuer) des différents projets mathématiques décrits :
- ABC@home
- Collatz Conjecture
- Enigma@Home
- Moo! Wrapper
- NumberFields@home
- Primaboinca (http://forum.boinc-af.org/index.php/topic,6270.msg396081.html#msg396081)
- PrimeGrid (http://forum.boinc-af.org/index.php/topic,6270.msg396082.html#msg396082)
- PRPNet
- Rectilinear Crossing Number
- SubsetSum@Home
- SZTAKI Desktop Grid
- Yoyo@home
Je voudrais remercier Sébastien pour avoir mis en place sur le forum les balises jstex permettant d'écrire des formules mathématiques (en LaTex).
Par exemple
[jstex]n! \sim \sqrt{2 \pi n} \left( \frac{n}{e} \right)^n[/jstex]
donne
n! \sim \sqrt{2 \pi n} \left( \frac{n}{e} \right)^n
Primaboinca
Primaboinca est un projet qui essaye d'infirmer ou à défaut de renforcer deux conjectures de théorie des nombres. Ces conjectures sont utiles dans l'élaboration du meilleur algorithme de primalité déterministe actuellement connu.
Avant d'énoncer ces deux conjectures (conjecture d'Agrawal et conjecture de Popovych) , voici une rapide présentation de l'algorithme AKS.
L'algorithme AKS
L'algorithme AKS est le premier et actuellement le meilleur algorithme de primalité déterministe (c'est-à-dire qui détermine de façon certaine si un nombre est premier contrairement aux algorithmes probabilistes). Il a été découvert en 2002 par les trois mathématiciens indiens Agrawal-Kayal-Saxena (d'où le nom AKS).
Sa complexité est polynomiale, ce qui est théoriquement très performant pour ce type de problème mais il n'est que très rarement utilisé dans la pratique car il n'est efficace que sur les très grands nombres premiers.
L'algorithme AKS repose sur la généralisation suivante du petit théorème de Fermat :
Théorème : Soit a et n des entiers naturels premiers entre eux. On a alors
n \text{ est premier } \Leftrightarrow (X+a)^n=X^n+a ~~\text{ dans }~~ \mathbb{Z}/n\mathbb{Z}[X]
Référence : https://fr.wikipedia.org/wiki/Test_de_primalit%C3%A9_AKS
Conjecture d'Agrawal
Le théorème ci dessus nous donne un test de primalité relativement simple. Pour déterminer si n est premier il suffit d'évaluer la relation (X+a)n=Xn+a.
Cependant dans les cas les moins favorables il faut tout de même évaluer les n coefficients du polynôme (X+a)n.
C'est pourquoi Agrawal a proposé en 2002 la conjecture suivante ayant pour but de simplifier le calcul.
Conjecture : Soit r un nombre premier qui ne divise pas n. On a
(X-1)^n=X^n-1 ~\text{ dans }~ \mathbb{Z}_n[X]/(X^r-1) ~\Rightarrow~ n \text{ est premier ou } n^2 \equiv 1 ~[r]
Hendrik Lenstras et Carl Pomerances ont, par des arguments heuristiques, suggéré qu'il existait une infinité de contre-exemples à cette conjecture et donc que cette conjecture était fausse. Cependant aucun contre-exemple n'a encore été trouvé.
Un des buts de ce projet est de tester cette conjecture. Cela a été fait pour tout n < 1010 sans avoir trouvé de contre-exemple.
Références : http://www.cse.iitk.ac.in/users/manindra/algebra/primality_v6.pdf et https://en.wikipedia.org/wiki/Agrawal%27s_conjecture
Conjecture de Popovych
Cette conjecture est une version avec des hypothèses plus fortes de la conjecture d'Agrawal (dont on pense qu'elle est fausse).
Conjecture : Soit r un nombre premier qui ne divise pas n.
Si
(X-1)^n=X^n-1 ~\text{ et }~ (X+2)^n=X^n+2 ~\text{ dans }~ \mathbb{Z}_n[X]/(X^r-1)
alors
n \text{ est premier ou } n^2 \equiv 1 ~[r]
Références : http://eprint.iacr.org/2009/008.pdf
Si l'une de ces conjectures est vraie, la complexité de l'algorithme AKS pourrait être réduite d'un O((log n)6) à un O((log n)3).
Primegrid (suite)
Autour des nombres de Sierpiński et de Riesel en base 5
Projets concernés :
Sierpinski/Riesel Base 5 Problem (SR5) (début de la recherche : juin 2013)
Description :
Ce projet est une extension en base 5 des problèmes de Sierpiński et de Riesel. C'est-à-dire qu'au lieu de s'intéresser aux nombres de la forme k⋅2n + 1 et k⋅2n - 1, on s'intéresse ici aux nombres de la forme k⋅5n + 1 et k⋅5n - 1. Le but est toujours de déterminer le plus petit nombre de Sierpiński (resp. Riesel) en base 5.
Définition : On dit que k est un nombre de Sierpiński (resp. Riesel) en base 5 s'il est impair et si pour tout entier naturel n, le nombre k⋅5n + 1 (resp. k⋅5n - 1) n'est pas premier.
Robert Smith a présenté l'idée des nombres de Sierpiński/Riesel en base 5 le 17 September 2004, dans le groupe primeform de yahoo. Il proposa que k = 346 802 est le plus petit nombre de Riesel en base 5. Peu après, Guido Smetrijns proposa que k = 159 986 est le plus petit nombre de Sierpiński en base 5.
État des résultats (2014) :
Pour les nombres de Sierpiński en base 5 : pour montrer que 159 986 est le plus petit nombre de Sierpiński en base 5 il reste à vérifier que 37 nombres ne sont pas des nombres de Sierpiński en base 5.
En voici la liste : 6436 ; 7528 ; 10918 ; 26798 ; 29914 ; 31712 ; 36412 ; 41738 ; 44348 ; 44738 ; 45748 ; 51208 ; 58642 ; 60394 ; 62698 ; 64258 ; 67612 ; 67748 ; 71492 ; 74632 ; 76724 ; 77072 ; 81556 ; 83936 ; 84284 ; 90056 ; 92158 ; 92906 ; 93484 ; 105464 ; 118568 ; 126134 ; 138514 ; 139196 ; 144052 ; 152588 ; 154222.
Pour les nombres de Riesel en base 5 : pour montrer que 346 802 est le plus petit nombre de Riesel en base 5 il reste à vérifier que 79 nombres ne sont pas des nombres de Riesel en base 5.
En voici la liste : 3622 ; 4906 ; 23906 ; 26222 ; 35248 ; 35816 ; 52922 ; 53546 ; 63838 ; 64598 ; 66916 ; 68132 ; 71146 ; 76354 ; 81134 ; 88444 ; 92936 ; 100186 ; 102818 ; 102952 ; 109238 ; 109838 ; 109862 ; 127174 ; 131848 ; 134266 ; 136804 ; 143632 ; 145462 ; 145484 ; 146264 ; 146756 ; 147844 ; 151042 ; 152428 ; 154844 ; 159388 ; 164852 ; 170386 ; 170908 ; 171362 ; 177742 ; 180062 ; 182398 ; 187916 ; 189766 ; 190334 ; 194368 ; 195872 ; 201778 ; 204394 ; 206894 ; 207494 ; 213988 ; 231674 ; 238694 ; 239062 ; 239342 ; 246238 ; 248546 ; 259072 ; 265702 ; 267298 ; 271162 ; 273662 ; 285598 ; 285728 ; 296024 ; 298442 ; 301562 ; 304004 ; 306398 ; 313126 ; 318278 ; 322498 ; ; 325922 ; 327926 ; 335414 ; 338866.
L'application SR5 a pour but de résoudre le les problèmes de Sierpiński/Riesel en base 5. Le dernier nombre premier trouvé par ce projet est 109 208 · 51 816 285 + 1, qui a été découvert en octobre 2014 et il possède plus de 1 250 000 de chiffres.
Référence : http://www.primegrid.com/forum_thread.php?id=5087
Autour des nombres premiers de Fermat généralisés
Projets concernés :
Generalized Fermat Prime Search (GFN-Short et GFN-WR) (début de la recherche : janvier 2012)
Description :
Avant de parler de nombres de Fermat généralisés, définissons tout d'abord les nombres de Fermat.
Définition : On appelle nombre de Fermat tout entier naturel qui peut s'écrire sous la forme 22n + 1. On note alors Fn = 22n + 1 (on pourra aussi noté ce nombre F(2,n)).
Exemples : Les cinq premiers nombre de Fermat sont F0 = 3 ; F1 = 5 ; F2 = 17 ; F3 = 257 ; F4 = 65537.
Ces nombres ont été introduits par le mathématicien français Pierre de Fermat au XVIIème siècle. A l'époque, les calculs se faisant à la main, il n'a pas pu déterminer que le nombre F5 n'est pas premier et il conjectura que tous les nombres de Fermat sont premiers. Cette conjecture se révéla fausse lorsqu'en 1732 (soit environ un siècle après), le mathématicien suisse Leonhard Euler démontra que F5 = 4 294 967 297 n'est pas premier. Aujourd'hui on a démontré que tous les nombres Fn pour 4 < n < 33 ne sont pas premiers et on ne connaît aucun autre nombre de Fermat qui soit premier hormis les cinq premiers exemples.
Voici aujourd'hui différentes questions non résolues que se posent les mathématiciens sur les nombres de Fermat :
- Les nombres de Fermat sont-ils tous non premier à partir de n = 5 ?
- Y a-t-il une infinité de nombres de Fermat qui soient premiers ?
- Y a-t-il une infinité de nombres de Fermat qui ne soient pas premiers ?
Pour finir sur les nombres de Fermat (non généralisés) voici une propriété qui motive l'étude des nombres premier de Proth dans la recherche de diviseur des nombres de Fermat.
Proposition : Tout facteur (diviseur) premier du nombre de Fermat Fn est de la forme k⋅2m + 1 où k est un entier impair et m ≥ n + 2.
État des résultats (2014) : En juillet 2014 l'application MEGA du projet Proth Prime Search détermina que 193 x 23 329 782 + 1 divise F3 329 780. Le nombre F3 329 780 est donc le plus grand nombre de Fermat connu (en octobre 2014) qui ne soit pas premier.
Venons-en maintenant aux nombres de Fermat généralisés.
Définition : On appelle nombre de Fermat généralisé tout entier naturel qui peut s'écrire sous la forme b2n + 1 avec b un entier supérieur à 2. On note alors F(b,n) = b2n + 1.
Remarques : Lorsque b=2 on retrouve les nombres de Fermat Fn.
Proposition : Si F(b,n) est premier alors b est pair.
Ces dernières années, les nombres de Fermat généralisés ont pris une place importante dans la recherche de grands nombres premiers en raison de la facilité à prouver leur primalité. Ainsi bon nombre des plus grands nombres premiers connus aujourd'hui sont des nombres premiers de Fermat généralisés.
État des résultats (2014) : Le plus grand nombre premier de Fermat généralisé est F(475 856 , 19) = 475 856524 288 + 1. Il a été trouvé en août 2012 et possède un peu moins de 3 000 000 de chiffres.
Voici la liste des plus grands nombres premiers de Fermat généralisé : http://primes.utm.edu/top20/page.php?id=12
L'application GFN-Short cherche des nombres premiers de la forme F(b,n) avec 480 000 < b < 510 000 et n = 20 ce qui donne des nombres à environ 6 000 000 chiffres.
L'application GFN-WR cherche des nombres premiers de la forme F(b,n) avec 28 500 < b < 33 500 et n = 22 ce qui donne des nombres à environ 18 500 000 chiffres. L'application GFN-WR a donc pour objectif de trouver le plus grand nombre premier connu (qui a actuellement en octobre 2014 un peu moins de 17 500 000 chiffres).
Référence : http://www.primegrid.com/forum_thread.php?id=3980
Biographie : Pierre de Fermat (https://fr.wikipedia.org/wiki/Pierre_de_Fermat) (1601 – 1665) est un magistrat, polymathe et surtout mathématicien français, surnommé « le prince des amateurs ». Il est aussi poète, habile latiniste et helléniste, et s'est intéressé aux sciences physiques ; on lui doit notamment le principe de Fermat en optique.
Projets terminés :
AP26 Search (AP26) (début de la recherche : décembre 2008 / fin de la recherche : avril 2010)
Cette application avait pour but de déterminer une progression arithmétique de nombres premiers de longueur 26.
Définition : On appelle progression arithmétique de nombres premiers de longueur k, une suite de k nombres premiers telle que la différence de deux termes consécutifs de cette suite est constante. Autrement dit la suite u1, u2, ... uk est progression arithmétique de nombres premiers si il existe un entier naturel r tel que pour tout entier n compris entre 1 et k-1 on a un+1 - un = r et un est premier.
Exemples :
3, 7, 11 est une progression arithmétique de nombres premiers de longueur 3 (et de raison r=4).
199, 409, 619, 829, 1039, 1249, 1459, 1669, 1879, 2089 est une progression arithmétique de nombres premiers de longueur 10 (et de raison r=210).
Théorème de Green-Tao : Pour tout entier naturel k, il existe une progression arithmétique de nombres premiers de longueur k.
On peut donc en théorie trouver une progression arithmétique de nombres premiers de longueur arbitraire.
État des résultats : Ce projet a trouvé une progression arithmétique de nombres premiers de longueur 26 :
43 142 746 595 714 191+ 23 681 770*23*n pour n allant de 0 à 25
Primegen (début de la recherche : mars 2006 / fin de la recherche : février 2008)
Ce projet avait pour but d'établir une liste exhaustive des nombres premier à partir de 1.
Twin Prime Search (TPS) (début de la recherche : novembre 2006 / fin de la recherche : juillet 2009)
Ce projet avait pour but de chercher des nombres premiers jumeaux. Il a été remplacer par le projet Sophie Germain Prime Search.
Définition : On dit que deux nombres premiers sont jumeaux s'ils ont un écart de 2 (leur différence vaut 2).
Exemple : 3 et 5 ou 11 et 13 sont des nombres premiers jumeaux.
Conjecture : Il existe une infinité de nombres premiers jumeaux.
État des résultats : Actuellement (octobre 2014) le plus grand nombre premier jumeau est 3 756 801 695 685 x 2666 669 ± 1. Il possède 200 700 chiffres et a été trouvé en décembre 2011 par ce projet.
Annexes :
Notion du nombre de chiffres et récapitulatif des records de chaque application
Pour mesurer la taille des nombres premiers, on utilise souvent le nombre de chiffres (sous-entendu en base 10).
Définition : Pour tout entier naturel non nul n, on définit le nombre de chiffres de n comme étant l'unique entier k vérifiant 10k-1 ≤ n < 10k.
Exemples : 12 a 2 chiffres, 100 a 3 chiffres.
On peut très facilement calculer le nombre de chiffres d'un grand nombre grâce à la proposition suivante.
Proposition : Le nombre de chiffres d'un entier naturel non nul n est égal à
\text{E} \left( \frac{\ln(n)}{\ln(10)} \right) + 1
avec ln la fonction logarithme népérien et E la fonction partie entière.
Voici la liste des records de chaque application ou en lien avec les nombres premiers.
- Plus grand nombre premier connu (en 2014) : 257 885 161 - 1 qui possède 17 425 170 chiffres
- Plus grand nombre premier connu (en 1980) : 244 497 - 1 qui possède 13 395 chiffres
- Plus grand nombre premier connu (en 1951) : 180 x (2127 - 1)2 + 1 qui possède 79 chiffres
- Plus grande liste exhaustive de nombres premiers (en 2014) : tous les nombre premier à moins de 17 chiffres
- Sophie Germain Prime Search : 18 543 637 900 515 x 2666 667 - 1 qui possède 200 701 chiffres
- Proth Prime Search : 7 x 25 775 996 + 1 qui possède 1 738 749 chiffres
- 321 Prime Search : 3 x 210 829 346 + 1 qui possède 3 259 959 chiffres
- Cullen prime search : 6 679 881 x 26 679 881 + 1 qui possède 2 010 852 chiffres
- Woodall prime search : 3 752 948 x 23 752 948 - 1 qui possède 1 129 757 chiffres
- Seventeen or Bust : 19 249 X 213 018 586 + 1 qui possède 3 918 990 chiffres
- Prime Sierpinski Problem : 90 527 x 29 162 167 + 1 qui possède 2 758 093 chiffres
- Extended Sierpinski Problem : 211 195 x 23 224 974 + 1 qui possède 970 820 chiffres
- The Riesel Problem : 502 573 x 27 181 987 - 1 qui possède 2 162 000 chiffres
- Sierpinski/Riesel Base 5 Problem : 109 208 x 51 816 285 + 1 qui possède 1 269 534 chiffres
- Generalized Fermat Prime Search : 475856524288 + 1 qui possède 2 976 633 chiffres
- Twin Prime Search : 3 756 801 695 685 x 2666 669 ± 1 qui possède 200 700 chiffres
A titre de comparaison, on utilise en cryptographie (dans RSA-2048 par exemple) des nombres premiers avec environ 300 chiffres.
Référence : http://primes.utm.edu
Probabilité de trouver un nombre premier
Après leur découverte, voici deux grandes questions portant sur les nombres premiers que les mathématiciens se sont posées :
- Y en a-t-il beaucoup / sont-ils rares ?
- Comment sont-ils répartis ?
En 1896 le mathématicien français Jacques Hadamard (https://fr.wikipedia.org/wiki/Jacques_Hadamard) et le mathématicien belge Charles-Jean de La Vallée Poussin (https://fr.wikipedia.org/wiki/Charles-Jean_de_La_Vall%C3%A9e_Poussin) démontrent indépendamment le Théorème des nombres premiers (https://fr.wikipedia.org/wiki/Th%C3%A9or%C3%A8me_des_nombres_premiers) qui répond en partie à ces deux questions.
Théorème des nombres premiers : Pour tout nombre réel x, on note π(x) le nombre de nombres premiers inférieur à x (par exemple π(12) = 5 et π(19/3) = 3).
On a alors l'équivalent suivant :
\pi(x)~ \underset{x \to \infty}{\sim} ~\frac{x}{\ln(x)}
Concrètement ce théorème nous donne la quantité de nombres premiers quand on va vers l’infini. Alors y en a-t-il beaucoup ?
La réponse est plutôt oui ! Par exemple il y a énormément plus de nombres premiers que de carrés parfaits.
De plus le théorème précédent nous permet de calculer une estimation de la probabilité de trouver un nombre premier.
Application au calcul de probabilité : Si on appelle P(x) la probabilité de trouver un nombre premier en piochant un entier entre 0 et x de manière aléatoire (uniforme),
on a P(x) = π(x)/x ≈ 1/ln(x).
Appliquons ce résultat :
On a (d'après le théorème) environ 1 chance sur 7 de trouver un nombre premier entre 1 et 1 000 (en réalité c'est plutôt 1 chance sur 6)
On a (d'après le théorème) environ 1 chance sur 13.8 de trouver un nombre premier entre 1 et 1 000 000 (en réalité c'est plutôt 1 chance sur 12.7)
On a (d'après le théorème) environ 1 chance sur 53 de trouver un nombre premier à moins de 23 chiffres (en réalité c'est plutôt 1 chance sur 52)
Pour les petits exemples voir ici (https://fr.wikipedia.org/wiki/Th%C3%A9or%C3%A8me_des_nombres_premiers#Exemples_d.27estimations_num.C3.A9riques)
Maintenant pour les grands nombres premiers (ce qui nous intéresse :hyperbon:) voici quelques exemples :
On a environ 1 chance sur 4 605 000 de trouver un nombre premier à environ 2 000 000 de chiffres.
On a environ 1 chance sur 11 513 000 de trouver un nombre premier à environ 5 000 000 de chiffres (soit pratiquement autant de chance que de gagner au loto).
On a environ 1 chance sur 45 000 000 de trouver le plus grand nombre premier (connu).
Les algorithmes de primalité
On appelle algorithme de primalité un algorithme qui détermine si un nombre donné est premier ou non. Il en existe deux types : les déterministes et les probabilistes.
Les algorithmes de primalité déterministes renvoient tout simplement si le nombre est premier ou non de façon certaine.
Les algorithmes de primalité probabilistes sont plus rapide que les déterministes mais ils renvoient :
- Soit que le nombre testé est de façon certaine non premier
- Soit qu'il y a une probabilité (en général grande) que le nombre testé soit premier. Dans ce cas (assez rare) on dit que le nombre est pseudo-premier et il faut utiliser un algorithme déterministe pour être certain que le nombre soit premier.
Primegrid utilise trois types d'applications :
- les applications « Sieve » utilisent des algorithmes de criblage qui ont pour but d'exclure rapidement une partie des nombres non premiers d'une liste de nombres
- l'application GFN teste la primalité des nombres de Fermat généralisé
- l'application LRR teste la primalité des nombres de la forme k⋅bn ± 1
Contrairement à ce que laisse penser son nom, l'application LLR n'utilise pas que l'algorithme LLR. Voici les différents algorithmes utilisés par cette application :
Pour les nombres en base 2 :
- Les nombres de la forme k⋅2n + 1 sont testés par l'algorithme de Proth (https://fr.wikipedia.org/wiki/Th%C3%A9or%C3%A8me_de_Proth).
- Les nombres de la forme k⋅2n - 1 sont testés par l'algorithme de Lucas-Lehmer-Riesel (https://en.wikipedia.org/wiki/Lucas%E2%80%93Lehmer%E2%80%93Riesel_test).
Pour les nombres en base quelconque :
- Les nombres de la forme k⋅bn + 1 sont testés par l'algorithme N-1 de Pocklington (https://en.wikipedia.org/wiki/Pocklington_primality_test).
- Les nombres de la forme k⋅bn - 1 sont testés par l'algorithme N+1 de Morrison.
Pour plus d'information sur l'application LLR voir : http://www.mersenneforum.org/showthread.php?t=19167