Nouveau grand nombre premier

**JPL** · 18/12/2003 - 18h31

Dans l'actualité de ce jour je lis, à propos de la découverte du plus grand nombre premier connu :

Celui-ci, auquel ont permis d'aboutir les calculs de quelque 210 000 ordinateurs mis à contribution à travers le monde, est même encore un plus spécial puisqu'il s'agit d'un nombre premier dit de Mersenne, du nom d'un mathématicien français du XVIIe siècle. Ce type de nombre, très rare, s'exprime sous la forme 2 puissance p moins 1, avec p également nombre premier.

Bien que je ne sois pas du tout mathématicien, ce n'est pas une surprise que ce nombre soit un nombre premier de Mersenne, tout simplement parce que le programme auquel chacun peut participer ne recherche à mon souvenir que les nombres premiers de Mersenne parce qu'ils sont plus faciles à touver.
Mais comme je ne me souviens plus du tout pourquoi, ni comment on les recherche, si quelqu'un bon en math pouvait me rafraîchir la mémoire, je lui en serais très reconnaissant.

Merci.

Aether · 19/12/2003 - 11h36

Bonjour,

Pour une petite explication :
http://fr.wikipedia.org/wiki/Nombre_premier_de_Mersenne.

Jeremy · 19/12/2003 - 11h50

http://www.mersenne.org/math.htm

In dealing with Mersenne numbers, it is easy to prove that if 2P-1 is prime, then P must be a prime.

The Lucas-Lehmer primality test is remarkably simple. It states that for P > 2, 2P-1 is prime if and only if Sp-2 is zero in this sequence: S0 = 4, SN = (SN-12 - 2) mod (2P-1).

ect ...

olle · 19/12/2003 - 18h55

coucou,

sinon ça sert à qqchose ?

Jeremy · 19/12/2003 - 20h56

Heuu ... pour un nombre aussi grand non

Antikhippe · 20/12/2003 - 18h26

lut,

on peut tester la puissance des ordis comme avec le nombre pi.

Jeremy · 20/12/2003 - 18h36

Humm bof .. super Pi c'est pratique parce qu'il existe un algo qui permet de calculer n décimale de Pi. Apres il suffit de voir en combien de secodes le calcul est fait.
Mais la c'set pas des secondes mais des temps beaucoup plus long, donc pour tester la puissance d'un ordi ... :?

olle · 20/12/2003 - 23h04

c'était en effet le sens de ma remarque.
passer je ne sais combien de temps à monopoliser des centaines de miliers de processeurs pour calculer un nombre premier... c'est... inutile ?

je pense que ya beaucoup plus intéressant à faire avec. stou

**JPL** · 20/12/2003 - 23h20

sinon ça sert à qqchose ?

The Electronic Frontier Foundation is offering a $100,000 award to the first person or group to discover a ten million digit prime number. If you find such a prime with the software provided, GIMPS will claim the award and distribute the award according to the following rules.

Mais il y a toute une série de conditions... voir
http://www.mersenne.org/prize.htm

Evil.Saien · 05/01/2004 - 10h15

ca sert à rien, c'est juste pour la beauté des maths

avril · 10/01/2004 - 15h12

c peut etre un peu hors sujet mais en parlant de nombre premier, g vu un exos dans mon bouquin de maths :
2^86243 - 1 est un nombre premier
combien de chiffres son écriture décimale possede -t-elle?
ce ke jvoudré savoir:
1) comment a-t-on trouvé ke ce nombre était premier???
2) a koi elle sert ct information? ( g résolu le pb sans utiliser le fait que c un nombre premier).
jcroyé ke ct le plus grand nbr premier kon ait trouvé mais apparemment c pas cela.

Avril

T.Rex · 23/08/2004 - 13h29

Bonjour,

Un nouveau nombre premier de Mersenne a été trouvé récemment (mai 2004). Voir : http://www.mersenne.org/
$2^{24036583}-1$ On pense que c'est le 41ème et on l'appelle donc M41.

A quoi sert de chercher de tels nombres ?
Plusieurs raisons :
1) Bien sûr vérifier le fonctionnement des ordinateurs et de leurs programmes. Par exemple avec M41, j'ai trouvé un bug dans le compilateur icc d'Intel sur Linux (toujours pas corrigé ...). J'ai également trouvé que le programme parallélisé (avec des threads POSIX) qui a été utilisé était buggé : la gestion des threads ne respectait pas la norme POSIX. Et enfin, la librairie NPTL fournissant les threads elle-même avait un bug et se bloquait dans certains cas.
2) Mais aussi à développer de nouveaux algorithmes de calcul des multiplications sur des grands nombres, telle la FFT.
3) Surtout : le fun : comme vaincre un sommet jusque là invaincu (les dangers en moins et avec l'espoir quasi-certain qu'après celui-là il y en aura un autre), et (pendant un temps limité) être celui qui a trouvé le plus grand nombre premier ... ou faire partie de ceux qui y ont contribué.
4) Les nombres de Mersenne sont aussi utilisés pour la génération de nombres aléatoires.

Surtout, les nombres de Mersenne sont liés à l'histoire :
1) Fermat a prédit (avec des erreurs) la primalité de certains des nombres de Mersenne.
2) Prouver qu'un nombre N est premier autrement qu'en le divisant avec tous les nombres premiers plus petits que $sqr(N)$ a commencé avec les nombres de Fermat et les nombres de Mersenne.
Et c'est un Français (Edouard Lucas) qui le premier au 19ème siècle a trouvé le moyen d'une telle preuve.
D'ailleurs cette preuve est fascinante. Comme il est expliqué plus haut, il suffit de faire une opération très simple : $S_0 = 4 ; S_{i+1} = S_i^2 - 2 ; M_q = 2^q-1$ est premier ssi $S_{q-2} \equiv 0 (mod M_q)$
Mais la démonstration (assez difficile) prend 20-30 pages ...
Cette technique a été (et est encore) utilisée pour prouver la primalité d'autres types de nombres, bien que de nouvelles techniques soient apparues au XXème siècle.

Quand au nombres de processeurs nécessaires, il ne faut pas confondre le nombre de processeurs nécessaires pour trouver un nombre de Mersenne premier (parmi tous les autres) avec le temps nécessaire pour prouver sa primalité (2,5 jours avec une machine ia64 1.3 GHz à 8 processeurs).

Pour les nombres de Fermat : $F_n = 2^{2^n}+1$ , il faudra environ 3 ans de calcul avec une machine mono-processeur puissante pour savoir si le prochain candidat (F33 ?) est premier ou non.

Pour compléter, lire le livre de Paulo Ribenboim : Little book for Bigger Primes (2004) (en Anglais, 42-52 Euros) ou le livre de HC Williams : Édouard Lucas and Primality Testing (en anglais et un peu cher .... 92 Euros). Tous 2 sont très bien.
Le 2ème livre est TRèS intéressant car on découvre que tout ce qui est dit dans les autres livres de Théorie des Nombres sur cette méthode de preuvre de primalité n'est souvent qu'une simplification/réduction de ses possibilités : comme cette méthode n'est presque utilisée que pour les nombres de Mersenne, les auteurs trop souvent ne fournissent que la preuve minimale pour les nombres de Mersenne, en ommettant toute une théorie qui pourrait inspirer d'autres personnes.

Tony

cricri · 23/08/2004 - 13h38

2^86243 - 1 = exp(log(2)*86243)-1 en base 10 et non pas e

donc il a log(2)*86243 +1 chiffre soit 25962 ce qui est plutot petit

les nombres premier servent dans les cle de codage
on choisit 2 nombre premier qu on multiplie ca devient la cle
il est tres long a trouver les 2 nombre premier qui la constitue si on les connais pas
ca c etait dans le temps maintenant il y a de nouveau algo pour les trouver

doryphore · 23/08/2004 - 14h43

En 1994, on n'avait pas trouvé de nombres de Fermat premier.
ESt-ce que c'est fait ou bien a-t-on démontré que les nombres de Fermat sont tous premiers ou bien ni l'un ni l'autre ?
A-t-on des nouvelles des nombres parfaits impairs ?

T.Rex · 23/08/2004 - 15h25

On connaît le statut (premier, composite) de tous les nombres de Fermat Fn jusqu'à n=32 . F0, F1, F2, F3, F4 sont tous premiers. F5 jusqu'à F32 sont tous composites, mais on ne connaît pas la factorisation de tous.
Maintenant, F33 (2.58 milliards de chiffres ...) et le prochain sur la liste, et il va falloir attendre un moment avant de savoir s'il est premier ou pas !
Non, on n'a aucune théorie sur la primalité des nombres de Fermat. La seule solution consiste à utiliser le test de Pepin : $3^{(F_n-1)/2} \equiv -1 (mod F_n) <==> F_n est premier$

Quant aux nombres parfaits impairs, je crois me souvenir qu'une limite inférieure (un très grand nombres ...) a été demontrée, sans preuve de leur existence.

Tony