{"id":4982,"date":"2013-07-15T00:01:46","date_gmt":"2013-07-14T22:01:46","guid":{"rendered":"http:\/\/sciencetonnante.wordpress.com\/?p=4982"},"modified":"2013-07-15T00:01:46","modified_gmt":"2013-07-14T22:01:46","slug":"les-nombres-de-mersenne","status":"publish","type":"post","link":"https:\/\/scienceetonnante.com\/blog\/2013\/07\/15\/les-nombres-de-mersenne\/","title":{"rendered":"Les nombres de Mersenne"},"content":{"rendered":"

\"math_equations_300px\"<\/a>Les math\u00e9maticiens adorent les nombres premiers ! Non seulement ils sont \u00e0 la base de probl\u00e8mes simples mais encore non-r\u00e9solus, comme la conjecture de Goldbach dont je parlais ici<\/a> (tout nombre pair serait la somme de deux nombres premiers), mais les nombres premiers s’av\u00e8rent \u00e9galement tr\u00e8s utiles dans la vie r\u00e9elle, comme avec l’algorithme de cryptage RSA qui sert \u00e0 prot\u00e9ger un grand nombre de nos secrets informatiques ou bancaires (sujet d’un autre billet<\/a>).<\/p>\n

Pour ces raisons, les math\u00e9maticiens adoreraient disposer d’une machine \u00e0 fabriquer des nombres premiers<\/strong>, ou tout du moins d’une formule qui permette d’en construire \u00e0 volont\u00e9.<\/p>\n

<\/p>\n

Des formules \u00e0 fabriquer des nombres premiers<\/h3>\n

Imaginons que vous vouliez en construire une telle formule. En observant que les plus petits nombres impairs sont premiers (3,5,7), on pourrait proposer de regarder tous les nombres de la forme \\(2 n+1\\). \u00c9videmment, \u00e7a marche pour n=1,2 ou 3, mais pour n=4 on obtient 9 qui n’est pas premier, \u00e7a marche \u00e0 nouveau avec n=5,6,8 et ensuite de moins en moins !<\/p>\n

\"220px-MarinMersenne\"<\/a>Une formule beaucoup plus efficace a \u00e9t\u00e9 sugg\u00e9r\u00e9e par Euler, il s’agit de<\/p>\n

\\(n^2-n+41\\).<\/p>\n

Il se trouve que pour toute valeur de n entre 0 et 40, cette formule donne un nombre premier<\/strong> ! Mais ensuite, \u00e7a ne marche presque plus. Or pour la cryptographie notamment, on aimerait pouvoir fabriquer des grands nombres premiers.<\/p>\n

Au XVIIeme si\u00e8cle, le moine fran\u00e7ais Marin Mersenne<\/strong> a propos\u00e9 une autre formule \u00e0 fabriquer des nombres premiers : prendre \\(2^p-1\\) quand \\(p\\) est d\u00e9j\u00e0 lui m\u00eame un nombre premier. On note ce nombre \\(M_p\\) en hommage \u00e0 Mersenne.<\/p>\n

Pour les premi\u00e8res valeurs de p (2,3,5,7), \u00e7a marche nickel puisqu’on obtient 3,7,31 et 127 qui sont tous premiers. Mais pour p=11, \u00e7a ne colle pas car \\(2^{11}-1=2047\\), lequel se d\u00e9compose en 23×89. Puis \u00e7a marche \u00e0 nouveau pour p=13,17,19. Ensuite \u00e7a marche beaucoup moins bien.<\/p>\n

Pour une raison totalement inconnue, Mersenne avait conjectur\u00e9 que sa formule devait donner des nombres premiers pour p=31, 67, 127 et 257<\/strong>. Personne ne sait pourquoi il avait propos\u00e9 ceux-l\u00e0 en particulier, d’autant que les nombres de Mersenne correspondants poss\u00e8dent un tr\u00e8s grand nombre de chiffres, et qu’il lui \u00e9tait clairement impossible de faire la v\u00e9rification \u00e0 la main.<\/p>\n

Le nombre de Mersenne M67<\/h3>\n

Beaucoup de math\u00e9maticiens se sont ensuite acharn\u00e9s \u00e0 d\u00e9montrer que ces nombres de Mersenne \u00e9taient effectivement premiers … ou pas. L’une des d\u00e9monstrations les plus fameuses a concern\u00e9 le nombre M67<\/strong>, et fut l’occasion d’une conf\u00e9rence mythique \u00e0 l’American Mathematical Society\u00a0en 1903. Un d\u00e9nomm\u00e9 Franck Cole avait annonc\u00e9 un expos\u00e9 portant le titre ambitieux \u00ab\u00a0On the factorization of large numbers\u00a0\u00bb<\/em>.<\/p>\n

Au moment de son expos\u00e9, Franck Cole s’est lev\u00e9, s’est dirig\u00e9 au tableau sans dire un mot, et a pris la craie pour calculer \u00e0 la main le nombre M67, qui vaut<\/p>\n

\\(2^{67}-1 = 147\\ 573\\ 952\\ 589\\ 676\\ 412\\ 927 \\)<\/p>\n

Sur l’autre moiti\u00e9 du tableau, il a ensuite pos\u00e9 la multiplication\u00a0761 838 257 287 x 193 707 721. Puis toujours en silence, il a patiemment effectu\u00e9 \u00e0 la main le calcul, pour obtenir le r\u00e9sultat…147 573 952 589 676 412 927 !<\/p>\n

Sans avoir prononc\u00e9 un seul mot, il est retourn\u00e9 s’asseoir sous les ovations du public. M67 n’\u00e9tait donc pas premier !<\/strong> Cole a par la suite d\u00e9clar\u00e9 que cette \u00ab\u00a0d\u00e9monstration\u00a0\u00bb lui avait demand\u00e9 3 ans de travail tous les dimanches !<\/p>\n

La recherche sur les nombres de Mersenne est encore tr\u00e8s active, puisque c’est par ce moyen que les records de plus grands nombres premiers sont battus depuis pas mal d’ann\u00e9es.<\/strong> En ce moment le tenant du titre est \\(2^{57\\ 885\\ 161} -1\\). Je suis gentil, je ne vous l’\u00e9crit pas pour ne pas vous affoler, il faudrait 17 millions de chiffres !<\/p>\n

\n

Pour aller plus loin : les formules \u00e0 fabriquer des nombres premiers<\/em><\/h3>\n

On manque cruellement aujourd’hui d’une formule efficace pour fabriquer des nombres premiers. On peut en fait d\u00e9montrer que tout expression polynomiale (du genre \\(n^2-n+41\\)) finit n\u00e9cessairement par \u00e9chouer. Aucune expression de ce type ne peut donner pour tout n un nombre premier.<\/em><\/p>\n

Il existe une formule amusante qui donne syst\u00e9matiquement des nombres premiers, il s’agit de l’expression<\/em><\/p>\n

\\(E[A^{3^n}]\\)<\/em><\/p>\n

o\u00f9 \\(E[.]\\) d\u00e9signe la fonction \u00ab\u00a0partie enti\u00e8re\u00a0\u00bb, et A est une constante r\u00e9elle, appel\u00e9e constante de Mills. Le probl\u00e8me est que cette formule est impraticable car il faudrait conna\u00eetre avec une pr\u00e9cision infinie la constante A, ce qui n’est pas le cas ! On sait juste qu’elle existe, et on arrive \u00e0 calculer sa valeur approch\u00e9e, environ 1.3063778838.<\/em><\/p>\n

Plus ambitieux serait de trouver une formule qui donne TOUS les nombres premiers sans exception. \u00c9videmment on ne connait pas une telle formule, je ne sais m\u00eame pas s’il est possible qu’une telle formule existe (en utilisant que les op\u00e9rations alg\u00e9briques usuelles). Quelqu’un a une id\u00e9e ?<\/em><\/p>\n

\n","protected":false},"excerpt":{"rendered":"

Les math\u00e9maticiens adorent les nombres premiers ! Non seulement ils sont \u00e0 la base de probl\u00e8mes simples mais encore non-r\u00e9solus, comme la conjecture de Goldbach dont je parlais ici (tout nombre pair serait la somme de deux nombres premiers), mais les nombres premiers s’av\u00e8rent \u00e9galement tr\u00e8s utiles dans la vie r\u00e9elle, comme avec l’algorithme de<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"jetpack_post_was_ever_published":false,"_jetpack_newsletter_access":"","_jetpack_dont_email_post_to_subs":false,"_jetpack_newsletter_tier_id":0,"_jetpack_memberships_contains_paywalled_content":false,"_jetpack_memberships_contains_paid_content":false,"footnotes":""},"categories":[4],"tags":[2,5],"class_list":{"0":"post-4982","1":"post","2":"type-post","3":"status-publish","4":"format-standard","6":"category-mathematiques","7":"tag-arithmetique","8":"tag-nombres-premiers"},"jetpack_featured_media_url":"","jetpack_sharing_enabled":true,"post_mailing_queue_ids":[],"_links":{"self":[{"href":"https:\/\/scienceetonnante.com\/blog\/wp-json\/wp\/v2\/posts\/4982","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/scienceetonnante.com\/blog\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/scienceetonnante.com\/blog\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/scienceetonnante.com\/blog\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/scienceetonnante.com\/blog\/wp-json\/wp\/v2\/comments?post=4982"}],"version-history":[{"count":0,"href":"https:\/\/scienceetonnante.com\/blog\/wp-json\/wp\/v2\/posts\/4982\/revisions"}],"wp:attachment":[{"href":"https:\/\/scienceetonnante.com\/blog\/wp-json\/wp\/v2\/media?parent=4982"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/scienceetonnante.com\/blog\/wp-json\/wp\/v2\/categories?post=4982"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/scienceetonnante.com\/blog\/wp-json\/wp\/v2\/tags?post=4982"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}