nombre premier

[joshua_fr]

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?

[kron]

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.

[GuYem]

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

[Evil.Saien]

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.

[matthias]

Envoyé par joshua_fr

1- Pourquoi se taroder la tête à savoir quel est le plus grand nombre premier? Ça va servir à quoi exactement?

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

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?

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.

Envoyé par joshua_fr

1- Pourquoi se taroder la tête à savoir quel est le plus grand nombre premier? Ça va servir à quoi exactement?

Il y a également un challenge technologique, il se passe la même chose avec les décimales de Pi.

[Azrem]

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.

[moijdikssékool]

Envoyé par Evil

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

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 divisions
dans, http://villemin.gerard.free.fr/Multimed/Puissanc.htm, le earth simulator fait du 4* bit/s. Si une division prend Xopérations bit à bit, il faudrait donc X/4* sec, c'est à dire (en supposant que X est d'ordre 10, ce qui est faux parcequ'il s'agit de diviser de très grand nombres...) qu'il faut années

ia intérêt à se trouver des supers algorithmes!

[matthias]

Envoyé par moijdikssékool

pour montrer qu'un chiffre n est premier, on le divise par les nombres compris entre 2 et

ça c'est vraiment l'algo de base.

[Evil.Saien]

Envoyé par moijdikssékool

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 divisions
dans, http://villemin.gerard.free.fr/Multimed/Puissanc.htm, le earth simulator fait du 4* bit/s. Si une division prend Xopérations bit à bit, il faudrait donc X/4* sec, c'est à dire (en supposant que X est d'ordre 10, ce qui est faux parcequ'il s'agit de diviser de très grand nombres...) qu'il faut années

ia intérêt à se trouver des supers algorithmes!

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.
D'autres algorithmes sont probablement encore beaucoup plus rapides mais je les connais pas...

[hedron]

Bonjour.

D'autres algorithmes sont probablement encore beaucoup plus rapides mais je les connais pas

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'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).

[T.Rex]

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 : , où q doit être premier. Historiquement, c'est l'un des plus vieux types de nombres étudiés car ils sont liés aux nombres parfaits (nombres égaux à la somme de leurs diviseurs : . Il est assez facile de prouver que les nombres parfaits pairs sont construits à partir des nombres de Mersenne premiers : .
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 : ), il a pu prouver (en partie) qu'un nombre de Mersenne est premier si la condition suivante est remplie : soit la suite : , le nombre est premier si et seulement si le terme est divisible par . Pour réduire la taille des calculs, les opérations sont effectuées modulo le nombre Mq. Une preuve complète sera apportée au début du XXème siècle par D. Lehmer. D'où le nom du test : LLT (Lucas-Lehmer Test). Le test est simple, mais la preuve du test prends une bonne quinzaine de pages ....
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 () pour lesquels on n'en connaît que 5 : 3, 5, 17, 257, 65537, et dont on pense que leur nombre est fini.
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

[T.Rex]

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

[moijdikssékool]

Envoyé par Matthias

ça c'est vraiment l'algo de base

certes, mais il faut connaître parmi les premiers nombres, les nombres premiers!

Envoyé par T-rex

Pour réduire la taille des calculs, les opérations sont effectuées modulo le nombre Mq

est de l'ordre de grandeur de Mq (10millions de chiffres) au bout de ( = Mq) à peu près de 10.000.000 itérations de n
le calcul de prend alors (produit de 2 chiffres identiques de 10.000.000 de chiffres) 10.000.000*10.000.000 = 100.000.000.000.000 opérations de multiplication élémentaire de 2 chiffres, le double pour partir de So et arriver à Sq. Sur mon ordi, ca devrait prendre plusieurs dizaines de minutes. Sur un super pc (10^13 pour les gros ordis à comparer à mon piteux 10^9), il te bouffe ca en quelques centièmes de secondes

à comparer aux années...

[Eric78]

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.

[T.Rex]

Envoyé par moijdikssékool

le calcul de prend alors (produit de 2 chiffres identiques de 10.000.000 de chiffres) 10.000.000*10.000.000 = 100.000.000.000.000 opérations de multiplication élémentaire de 2 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.

Tony

[chrisgir]

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?

[Eric78]

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).