Répondre à la discussion
Affichage des résultats 1 à 22 sur 22

nombre premier



  1. #1
    joshua_fr

    nombre premier


    ------

    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?

    -----

  2. Publicité
  3. #2
    kron

    Re : nombre premier

    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.
    Life is music !

  4. #3
    GuYem

    Re : nombre premier

    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
    Bravo jolie Ln, tu as trouvé : l'armée de l'air c'est là où on peut te tenir par la main.

  5. #4
    Evil.Saien

    Re : nombre premier

    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.
    Mon psychiatre, pour quinze mille francs, il m'a débarrassé de ce que j'avais : quinze mille francs

  6. A voir en vidéo sur Futura
  7. #5
    matthias

    Re : nombre premier

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

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

  8. #6
    Bobby
    Invité

    Re : nombre premier

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

  9. Publicité
  10. #7
    Azrem

    Re : nombre premier

    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.

  11. #8
    moijdikssékool

    Re : nombre premier

    Citation 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!

  12. #9
    matthias

    Re : nombre premier

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

  13. #10
    Evil.Saien

    Re : nombre premier

    Citation 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...
    Mon psychiatre, pour quinze mille francs, il m'a débarrassé de ce que j'avais : quinze mille francs

  14. #11
    hedron

    Re : nombre premier

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

  15. #12
    T.Rex

    Nombre de Mersenne premier

    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

  16. Publicité
  17. #13
    T.Rex

    Re : nombre premier

    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

  18. #14
    moijdikssékool

    Re : nombre premier

    Citation Envoyé par Matthias
    ça c'est vraiment l'algo de base
    certes, mais il faut connaître parmi les premiers nombres, les nombres premiers!

    Citation 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...
    Dernière modification par moijdikssékool ; 02/03/2005 à 22h52.

  19. #15
    Eric78

    Re : nombre premier

    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.
    Pour un TPE sur la cryptographie ou les trous noirs, allez voir mon profil.

  20. #16
    T.Rex

    Re : nombre premier

    Citation 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

  21. #17
    chrisgir

    Re : nombre premier

    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?

  22. #18
    Eric78

    Re : nombre premier

    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).
    Pour un TPE sur la cryptographie ou les trous noirs, allez voir mon profil.

  23. Publicité
  24. #19
    T.Rex

    Primalité et Factorisation

    Citation Envoyé par Eric78
    Encore une fois, le problème de trouver des nombres premiers est quasi résolu ...
    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.
    Citation Envoyé par Eric78
    C'est la factorisation qui est difficile, et dont un algorithme rapide remettrait en cause tous les cryptosystèmes à clef publique (RSA et cie).
    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).

  25. #20
    Eric78

    Re : Primalité et Factorisation

    Citation Envoyé par T.Rex
    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.
    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 (c'est pour ca que j'ai dit que le problème était résolus) Maintenant d'un point de vue mathématique, on ne peut se satisfaire de tests probabilistes, mais il existe un "nouveau" (quelque années déja) test déterministe: http://www.cse.iitk.ac.in/news/primality.html qui fonctionne avec de très grands nombres aussi.
    Pour un TPE sur la cryptographie ou les trous noirs, allez voir mon profil.

  26. #21
    moijdikssékool

    Re : nombre premier

    Citation Envoyé par T.rex
    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.
    quand je multiplie 123 par 123, j'effectue 3*3 opérations, et non 123*123

    une FFT? du fourier?

  27. #22
    matthias

    Re : nombre premier

    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.

Discussions similaires

  1. nombre premier et nombre impair
    Par nélli dans le forum Mathématiques du supérieur
    Réponses: 11
    Dernier message: 08/01/2016, 17h49
  2. Nombre Premier
    Par BOBYJOE dans le forum Mathématiques du collège et du lycée
    Réponses: 4
    Dernier message: 30/09/2007, 09h38
  3. nombre premier
    Par Lainé Jean Lhermite dans le forum Mathématiques du collège et du lycée
    Réponses: 2
    Dernier message: 28/04/2007, 08h55
  4. nombre premier
    Par akdim dans le forum Mathématiques du supérieur
    Réponses: 4
    Dernier message: 25/07/2005, 00h02