|
NOMBRES -
Curiosités, théorie et us Accueil / Dictionnaire / Rubriques / Index / Références / Nouveautés ORIENTATION GÉNÉRALE - M'écrire - Édition du: 01/10/2005 |
|
-Ý- FAQ - Foire |
|
|||
|
ARITHMÉTIQUE |
/ Nombres premiers |
|
|
|
|
>>> CRIBLE D'ÉRATOSTHÈNE >>> GRANDS nombres premiers: à quoi ç >>> Nombres premiers RECORD >>>
RECHERCHE des nombres premiers >>> Nombres premiers en 41 - progr >>>
Premiers |
P §
Théorie des
nombres - Index §
Calcul §
Logique §
Humour |
|||
|
Pour se cultiver sur le sujet voir: §
Mon site
sur les
nombres premiers, et §
La bible en la matière - très abordable et très
complet sur les nombres en général Ces merveilleux nombres premiers de Jean-Paul Delahaye -
Belin - 2000 |
|
Rubrique Question Programmer le recherche des nombres premiers Réponse Pour les
petits nombres: voir crible d' Ératosthène Pour les gr |
|
|
|
|
Rubrique Question À quoi ça sert de chercher des nombres premiers toujours plus grand ? Réponse 1) C'est tout d'abord un défi mathématique a. Trouver des méthodes de calcul, de nouveaux algorithmes, comment accélérer les calculs b. De ces recherches gratuites découlent souvent des innovations: nouvelles méthodes et aussi, nouvelles propriétés des nombres c. On retrouve le même esprit de défi pour le calcul d'un grand nombre de décimales de Pi ou des autres constantes 2) Il y a effectivement une limite de calcul de ces nombres premiers a. Après 100 chiffres, on ne les connaît plus, sauf quelques uns b. Toute méthode pour déterminer si un nombre est premier consomme beaucoup de temps d'ordinateur c. D'où cette espèce de défi pour améliorer les méthodes 3) Pour la même raison, on ne sait pas effectuer la décomposition en facteurs des très grands nombres (>100 chiffres). a. Par contre, on sait en créer en multipliant des nombres plus petits b. On a ainsi un processus non réversible: je sais créer un grand nombre composé, mais mon voisin ne sait pas en retrouver les facteurs c. C'est la base de la cryptographie d'aujourd'hui: les messages sont codés en utilisant des clés à base de très grands nombres composés 4) Évidemment, comme partout, il y a escalade entre gendarmes et voleurs a. Certains cherchent les trucs pour déjouer ces codes: comment trouver la décomposition des très grands nombres, problème cousin de la recherche des grands nombres premiers b. Il existe des légendes qui affirment que certains grands mathématiciens seraient confinés au secret tellement l'enjeu est important |
|
|
|
|
Rubrique Question Michael
Cameron a trouvé un Mersenne premier : 2 ^ 13466917 - 1 Réponse Vous avez raison bien sûr, et Voici les trois plus grands connus à ce
jour (Mise
à jour de juillet 2002)
pour la suite et les connaître tous Mon site en http://villemin.gerard.free.fr/Wwwgvmm/Premier/record.htm et celui de Chris Cadwell Liste des records de nombres premiers http://www.utm.edu/research/primes/largest.html |
|||||||||||||||||||||||||
|
|||||||||||||||||||||||||
|
Rubrique Question Le plus grand nombre premier connu est le nombre de Mersenne 2 à la puissance 2976221 - 1 et le plus grand nombre parfait connu est (2 à la puissance 2976220)x(2 à la puissance
2976221 - 1). Toujours vrai ? Réponse Non ! et attention l'information qui suit
est vrai ce jour (juin 2001) A) En résumé Les plus grands sont: Plus grand nombre premier: (2
puissance 6 972 593) - 1 Plus grand nombre de Mersenne: (2
puissance 6 972 593) - 1 Plus grand nombre premier NON Mersenne: (843
832 puissance 65 536) + 1 Plus grand nombre parfait: 2
puissance(6 972 592) x
((2 puissance 6 972 593)
- 1) B) Nombres de Mersenne Les plus grands nombres premiers connus
sont des nombres de Mersenne Ils sont de la
forme 2 puissance n - 1 Ce type de nombres se prête à des tests plus simples comparés aux nombres quelconques Le record est détenu depuis juin 1999 avec n = 6 972 593 Soit (2 puissance 6 972 593) - 1 C'est un nombre qui a plus de 2 millions de chiffres (2 098 960) La recherche continue avec le programme GIMPS qui consiste à demander à tous les volontaires possesseurs d'un ordinateur de faire les tests de primalité sur des tranches de nombres qui leur sont alloués C) Nombres quelconque (non Mersenne) Le record est un nombre de 388 384 chiffres, découvert en 2001 C'est (843 832 puissance 65 536) + 1 Il occupe le 5e rang des plus grands nombres premiers D) Voici la table des 5 plus grands nombres premiers connus
E) On retrouve les nombres premiers sur mon site en http://villemin.gerard.free.fr/Wwwgvmm/Premier/record.htm Le site américain de référence est celui de Chris Cadwell http://www.utm.edu/research/primes/largest.html F) Nombres parfaits Nombre égal à la somme de ses diviseurs propres (Diviseurs propres: tous les diviseurs avec 1 et sans le nombre lui-même) Les nombres parfaits pairs (aujourd'hui, on n'en connaît pas d'impairs) sont de la forme 2p-1 (2p - 1) 2 puissance(p-1) x ((2 puissance p) - 1) Avec (2 puissance p) - 1 qui est premier Or ce nombre est un nombre de Mersenne Or la réciproque est vraie (Euler - 1849) Donc le plus grand nombre parfait est 2 puissance(6 972
592) x ((2 puissance 6
972 593) - 1) G) On retrouve les nombres parfaits sur mon site en http://villemin.gerard.free.fr/Wwwgvmm/Decompos/SixNbPf.htm |
|||||||||||||||||||||||||||||||
|
|||||||||||||||||||||||||||||||
|
Rubrique RECHERCHE
DES NOMBRES PREMIERS Question Je
viens de terminer un programme qui recherche les nombres premiers. Mon
prof d'algèbre m'a dit qu'il était impossible de trouver un algorithme qui Réponse 1) Formule ? Il est exact qu'il n'existe aucune formule directe permettant de dire si un nombre est premier ou non. Le professeur a raison En effet, il existe une infinité de nombres premiers répartis pratiquement au hasard (en maths on dit : de manière aléatoire) Certains mathématiciens célèbres ont cherché des formules qui produiraient toujours des nombres premiers, même si elles ne les donnent pas tous: échec complet ! Voir de telles formules en: http://villemin.gerard.free.fr/Wwwgvmm/Premier/formule.htm 2) Tests Pour déterminer si un nombre est premier, il faut donc passer en revue tous les diviseurs possibles Ces tests sont basés sur le passage au crible d'Ératosthène: http://villemin.gerard.free.fr/Wwwgvmm/Premier/introduc.htm#eratos Il y a quelques tests plus performants, utilisant des propriétés très avancées des nombres (tests de divisibilité): http://villemin.gerard.free.fr/Wwwgvmm/Premier/record.htm#Principe Les tests les plus performants portent sur une race de nombres qui semblent donner des nombres premiers … de temps en temps. Ce sont les nombres de Mersenne (m = 2 puissance p - 1 avec p lui-même premier) http://villemin.gerard.free.fr/Wwwgvmm/Decompos/Mersenne.htm 3) Algorithmes Il n'y donc pas de formule pour dire si un nombre est premier Mais il y a des tests Et, on peut donc écrire des algorithmes pour trouver les nombres premiers Mais … Car, il y a un mais majeur ! Dès que l'on atteint de grands nombres, même les plus puissants des ordinateurs devraient y passer des années et même des millénaires pour arriver au bout du test! La puissance de calcul des ordinateurs d'aujourd'hui est grande et pourtant ça ne suffit pas 4) Records Néanmoins, les mathématiciens professionnels et surtout amateurs ne s'avouent pas vaincus et continuent à compléter la liste des records des nombres premiers Ils se sont associés dans un club (GIMPS) de mise en commun de leurs ordinateurs sur Internet et, chacun ne voit attribué une petite tranche de nombres à tester En 1999, l'un d'eux a eu la chance de trouver dans sa trémie une jolie pépite d'or: il s'agit du dernier record avec le nombre 2 puissance 6 972 593 - 1 = 10 puissance 2 098 960 (soit 2 098 960 chiffres) Eh, oui ! Pas de miracle, c'est un nombre particulier: un nombre de Mersenne Pour les nombres "ordinaires" (autres que Mersenne), le record correspond à un nombre bien inférieur à celui-ci http://villemin.gerard.free.fr/Wwwgvmm/Premier/record.htm 5) Application Il est donc pratiquement
impossible de dire si un très grand nombre est premier Par contre, on sait multiplier deux très grands nombres entre-eux Cette double propriété est utilisée dans la cryptographie: émission de messages codés indéchiffrables Le principe est celui de l'échange avec double cadenas: simple, mais il fallait y penser http://villemin.gerard.free.fr/Puzzle/securite.htm |
|
|
|
|
Rubrique Question p = n*n - n + 41 Comment programmer la recherche de ces nombres Jusqu'à n = 100 Combien
sont premiers Réponse Pour n = 39, il y 39 tels premiers Pour n = 100, il y 86 tels premiers Pour n = 107, il y 91 tels premiers A) FORMULE D'EULER Il n'existe pas de formule donnant tous les nombres premiers Ni même de formule ne donnant que des nombres premiers Cependant, certaines formules donnent un fort pourcentage de nombres premiers C'est le cas de celle d'Euler p = n (n - 1) + 41 Produit de deux nombres consécutifs plus 41 Que l'on peut écrire aussi sous les deux formes suivantes p = n*n - n + 41 p' = n*n + n + 41 Le nombre p est premier pour tous les n jusqu'à 40 Et jusqu' à 39 pour p' Voir ma page sur ce sujet en http://villemin.gerard.free.fr/Wwwgvmm/Premier/formule.htm B) PROGRAMMATION Il y a deux parties Procédure de recherche si un nombre p est premier ou composé Et programme d'exploration de tous les nombres pour n de 1 à 100 Voici le programme en langage Mapple (proche de nombreux autres) Toutes les explications pas à pas pour y arriver sur ma page en http://villemin.gerard.free.fr/Wwwgvmm/Premier/eratoprg.htm |
|
|
|