Bonjour à tous et à toutes,
après avoir entendu ce matin aux infos que des scientifiques avaient trouvé le plus grand nombre premier, je me suis posé deux petites questions que j'aimerai vous soumettre :
1- Pourquoi se taroder la tête à savoir quel est le plus grand nombre premier? Ça va servir à quoi exactement?
2- Avec les super-calculateurs actuels, je m'étonne que le record ne soit pas sans cesse battu. N'existe-t-il pas une fonction de recherche?
1/les nombres premiers servent pour beaucoup de choses. L'utilisation la plus intéressante que je leur connaisse est la cryptographie (la crypto RSA les utilise, jusqu'à un certain point). Trouver des nombres sans cesse plus grand permet, je pense, de sécuriser un maximum les informations secrètes.
2/Je pense qu'il y a surement des fonctions de recherches, mais à un point, les nombres deviennent tellement grands que la mémoire des ordinateurs n'y suffisent plus, je pense.
Tu as bien dit Kron.
Cependant Joshua j'attire ton attention sur un fait : il n'y a pas de "plus grand nombre premier".
En effet une démonstration relativement simple montre l'existence d'une infinité de nombres premiers.
Cependant jusqu'à aujourd'hui personne n'a encore trouvé un moyen systématique de détérminer ces nombres premiers.
C'est sur ce fait que repose en effet certains systèmes de cryptographie tels la méthode RSA. Elle repose entièrement sur une "clé" qui est en fait un grand nombre premier que seul le décodeur de l'information connait.
Si quelqu'un parvenit à décrire de façon systématique les nombres premiers, il pourrait alors trouver la clé facilement et ferait sauter le système de cryptage RSA qui est présent un peu partout : Mot de passe, code de CB, et que sais-je encore.
Moralité, celui qui trouve la logique des nombres premiers fera bien avancer le scmilblick des mathématiques mais embètera aussi beaucoup les gens qui ont créé ce système de codage!
Et il gagnera aussi beaucoup d'argent
Salut,
pour la deuxième question, les algorithmes de recherche des nombres premiers n'est pas linéaire. J'entend par la que le temps mis pour calculer que 5 est nombre premier est beaucoup plus court que pour montrer qu'un nombre a 1 million de chiffres l'est... Et évidemment les nombres premiers actuellement trouvés comportent ENORMEMENT de chiffres, donc je pense que c'est plus une question de temps que de mémoire.
Principalement pour les algorithmes de cryptage (RSA notamment) qui s'appuient sur des produits de très grands nombres premiers. Il est relativement facile de déterminer si un nombre est premier (même très grand), mais il est beaucoup plus difficile de factoriser un nombre dont les facteurs premiers sont très grands.Envoyé par joshua_fr
Il existe énormément d'algorithmes de recherche évidemment. La concurrence se fait donc plutôt sur l'efficacité des algorithmes développé que sur l'accès aux super-calculateurs (et en passant, le mieux est de développer un algorithme qui puisse fonctionner sur une architecture parallèle pour pouvoir utiliser de nombreux procésseurs en même temps). Je crois d'ailleurs que les meilleurs algos aujourd'hui sont des algos stochastiques, qui ne garantissent même pas à 100% qu'un nombre est premier, ce qu'il faut donc vérifier ensuite.
Il y a également un challenge technologique, il se passe la même chose avec les décimales de Pi.
ce n'est pas plus bête que les courses de voitures, où les écuries rivalisent les unes avec les autres.
Mais ici, le moteur est le cerveau humain.
un nombre d'un million de chiffres tient facilement dans une barette de RAM classique (elles dépassent désormais le Go), suffit de décomposer le chiffre intelligemment
pour montrer qu'un chiffre n est premier, on le divise par les nombres compris entre 2 et
Donc il faut faire
dans, http://villemin.gerard.free.fr/Multimed/Puissanc.htm, le earth simulator fait du 4*
ia intérêt à se trouver des supers algorithmes!
ça c'est vraiment l'algo de base.pour montrer qu'un chiffre n est premier, on le divise par les nombres compris entre 2 et
Avec les algorithmes plus recherché, il faut moins de division parce que tout les nombres premiers sont stockés et on divise seulement par ceux qui sont inférieurs à la racine du nombre a tester. Du coup ca enlève pas mal de chiffre.un nombre d'un million de chiffres tient facilement dans une barette de RAM classique (elles dépassent désormais le Go), suffit de décomposer le chiffre intelligemment
pour montrer qu'un chiffre n est premier, on le divise par les nombres compris entre 2 et
Donc il faut faire
dans, http://villemin.gerard.free.fr/Multimed/Puissanc.htm, le earth simulator fait du 4*
ia intérêt à se trouver des supers algorithmes!
D'autres algorithmes sont probablement encore beaucoup plus rapides mais je les connais pas...
Bonjour.
Des indiens ont publié un de test de primalité non probabiliste et dont la complexité est polynomiale (en le nombre de chiffres) : http://www.cse.iitk.ac.in/news/primality.html . Ca avait fait la une de quelques journaux mathématiques.D'autres algorithmes sont probablement encore beaucoup plus rapides mais je les connais pas
D'autre part, étant donné un nombre premier, il me semble raisonnable de penser que chercher le premier nombre premier qui suit soit polynomial (en le nombre de chiffres).
Ce nouveau "plus grand nombre premier" (connu) est un nombre de Mersenne. Fermat a joué avec ces nombres et a fait quelques prédictions assez fausses. Un nombre de Mersenne est simple :
Au XIXème siècle, le Français Edouard Lucas a trouvé une méthode pour prouver qu'un nombre est premier SANS le diviser par les nombres premiers inférieurs. Grâce aux propriétés de séquences de nombres (du genre des nombres de Fibonacci :
Avec les grandes valeurs de q actuelles, les multiplications à effectuer sont nombreuses et très longues. On utilise la méthode FFT (Fast Fourier Transform), qui nécessite des calculs en nombres flottants.
Pourquoi rechercher de tels nombres ?
D'abord, on pense savoir qu'il y a une infinité de nombres de Mersenne premiers et qu'on en trouvera régulièrement. Ce qui n'est pas le cas par exemple des nombres de Fermat premiers (
Donc, régulièrement, on a l'espoir d'en trouver. Et effectivement, le GIMPS en trouve environ 1 par an, grâce à l'aide de milliers de bénévoles qui installent le logiciel prime95 sur leur PC (sous Windows ou Linux). (Les logiciels MLucas ou GLucas sont destinés à des machines plus grosses).
Mais, franchement, ces nombres de Mersenne premiers ne servent à rien de concret. Ils sont trop grands (presque 10 millions de chiffres).
Par contre, quelle joie d'en trouver un !
Du côté informatique, des scientifiques essaient constamment d'améliorer leur méthode de multiplication, ce qui peut servir pour des projets utiles, genre prévisions météo. Enfin, c'est aussi un bon moyen de vérifier la capacité des ordinateurs à BIEN calculer. C'est en effet un programme du genre de prime95 ou GLucas qui a permis de trouver un défaut de conception du microprocesseur d'Intel il y a quelques années.
Pour ma part, j'utilise le programme GLucas comme test pour un projet d'outil de trace d'applications multi-threadées avec NPTL sur Linux. Bull va aussi ajouter GLucas à l'ensemble des programmes utilisés pour vérifier que la chaîne de calcul de ses super-calculateurs NovaScale (à base de processeurs Itanium2) : compilateur C, système d'exploitation et hardware marche correctement : si le programme dit qu'un nombre connu comme premier ne l'est pas, c'est qu'une erreur s'est glissée quelque part !
Plus d'information à :
Le GIMPS
Le Forum du GIMPS
Tony
Pour les personnes intéressées, voici un peu d'histoire et de Maths :
Mersenne Numbers ou MathWorld C'est en Anglais, désolé, mais c'est très bien fait.
En français, il y a aussi : Mersenne
Tony
certes, mais il faut connaître parmi les
le calcul de
à comparer aux
Dernière modification par moijdikssékool ; 02/03/2005 à 23h52.
Trouver des nombres premiers très grand n'est pas vraiment difficile, et les divers record sont plus de l'ordre du "sport" que de l'utilité. On peut trouver en peu de temps des nombres premiers autours de 1000 chiffres grâce au test de Miller Rabin. Il est à noter que cet algorithme est probabiliste: il n'assure pas à 100% que le nombre est premier, mais avec une très grande probabilité(ajustable), ce qui suffit en pratique pour RSA. Le vrai défis actuellement est de factoriser des grand nombres: actuellement il est toujours difficile d'aller au dela de 100 chiffres.
Sauf que la méthode utilisé consiste justement à ne pas faire de multiplications classiques, car ce serait en O(n^2). Donc, pour de tels chiffres, je crains que cela ne dure plusieurs jours, voire beaucoup plus. On utilise plutôt une FFT.le calcul de
Tony
J'ai entendu dire que la conjecture de Poincaré aurait été démontrée et donc qu'on peut décrire les nombres premiers (ce qui fout en l'air les systèmes de cryptographie actuel)
Quelqu'un peut m'expliquer et développer?
C'est la conjecture de Rieman il me semble qui permet d'expliquer la répartition des nombres premiers. Malgré que non démontré (une démonstration est en cours de validation il me semble), lle est déja utilisé dans les algorithmes. La démonstration ne remet absolument pas en compte la cryptographie! Encore une fois, le problème de trouver des nombres premiers est quasi résolu, et de toute façon plus on en trouve, plus on est content pour la sécurité. C'est la factorisation qui est difficile, et dont un algorithme rapide remettrait en cause tous les cryptosystèmes à clef publique (RSA et cie).
Ah bon ? Effectivement, des algorithmes spécifiques et très rapides existent pour prouver avec certitude la primalité de certains type de nombres. Mais, pour un nombre quelconque, les outils de preuve de primalité sont encore assez lents et ne peuvent s'attaquer qu'à des nombres bien plus petits.
Tout à fait. D'ailleurs, sur le site du GIMPS apparaît aussi une information sur un nouveau facteur du nombre de Mersenne 2^971-1 (Environ 300 chiffres) A comparer avec M42 : 2^25964951-1 (Environ 8 millions de chiffres) !!! Voir :GIMPS.
Voir aussi le projet de recherche de facteurs des nombres de Fermat : Fermat Search .
Pour jouer avec ces nombres, il suffit de télécharger et d'installer le logiciel PARI/gp (Windows et Linux).
Ca dépend dans quel contexte on se place: moi je parlais de celui de la cryptographie. Dans ce domaine, on peut utiliser des tests probabilistes, et ces tests sont très rapide et marchent pour des nombres très grand (plus de mille chiffres), étant donné que pour l'instant les clefs font autours de 130 chiffres il me semble (ce sont donc des produits de 2 nombres premier d'environt 65 chiffres), on a une belle marge
quand je multiplie 123 par 123, j'effectue 3*3 opérations, et non 123*123
une FFT? du fourier?
Un article pas mal sur la factorisation de grands nombres : http://www.apprendre-en-ligne.net/cr...51_088_096.pdf
ça date de 98 mais c'est toujours bon à lire.
