Partage
  • Partager sur Facebook
  • Partager sur Twitter

Grands nombres premiers

Méthode naïve

    2 juin 2019 à 4:21:47

    Bonjour,

    Il est facile d'écrire un algorithme pour vérifier si un entier naturel est un nombre premier si celui-ci n'est pas trop grand.

    Mais comment fait-on pour savoir avec certitude si un très grand nombre est premier?

    • Partager sur Facebook
    • Partager sur Twitter

    Le Tout est souvent plus grand que la somme de ses parties.

      2 juin 2019 à 11:44:42

      Salut,

      Tu peux regarder la page Wikipédia sur les tests de primalité. Dans certains cas, on utilise des méthodes probabilistes (Miller-Rabin par exemple) et donc on n'a pas la réponse avec une certitude absolue. Il existe des algorithmes non probabilistes en temps polynomial (en la taille du nombre) comme le test AKS et ses variantes.

      • Partager sur Facebook
      • Partager sur Twitter
      Tutoriel Ruby - Bon tutoriel C - Tutoriel SDL 2 - Python avancé - Faîtes un zeste, devenez des zesteurs
        2 juin 2019 à 11:55:58

        une multitude tests ont été développés avec les moyens de calcul de plus en plus performants. Il y a énormément de  liens sur le sujet sur le net. La compréhension de certains algorithme peut demander des connaissances relativement avancées en arithmétique voire au delà ( tests basés sur les fonctions elliptiques, utilisation de la transformée de Fourier rapide etc...)  

        Les algorithmes les plus efficaces en temps de calcul ne donnent pas nécessairement une certitude sur la primalité mais  une probabilité très faible d'erreur, probabilité que on peut rendre aussi faible que on veut pour certains ( qui se paie évidemment en temps de calcul).  

        Un test très classique est celui de Miller- Rabin qui est un  raffinement du petit théorème de Fermat  \(a^{p-1}\equiv 1 mod(p)\) diminuant  significativement le risque que \(p\) vérifie Fermat sans être premier.   Mais ce test ne garantie pas à 100% que le nombre testé est premier .

        Il existe un test déterministe relativement efficace pour dire si un nombre de Mersenne \( 2^n -1\) est premier , utilisant la transformée de Fourier rapide. C'est pourquoi la presque totalité des derniers grands nombres premiers prouvés sont des nombres de Mersenne. Le dernier exhibé date de fin 2018. cf article wiki sur le sujet: https://fr.wikipedia.org/wiki/Plus_grand_nombre_premier_connu 

        • Partager sur Facebook
        • Partager sur Twitter
        tout ce qui est simple est faux, tout ce qui est compliqué est inutilisable
          2 juin 2019 à 13:16:40

          L'univers des nombres premiers est un univers complexe. Il y a des tas de gens très sérieux qui travaillent sur le sujet, qui trouvent des résultats, des petits résultats, peu exploitables par le commun des matheux.

          Et il y a aussi des tas de gens qui travaillent sur le sujet et qui sont convaincus d'avoir des tas de preuves sur tel ou tel sujet, mais qui en fait n'ont ren du tout. Tous les pseudos mathématiciens qui se croient compétents mais qui ne savent pas ce qu'est une démonstration vont écrire un jour ou l'autre un truc sur les nombres premiers.

          Donc, attention quand tu lis des choses sur le net sur le sujet, il y a à boire et à manger. 

          Ceci dit, les liens donnés par mes amis sont des liens très fiables.

          • Partager sur Facebook
          • Partager sur Twitter
            2 juin 2019 à 17:28:52

            Bonjour,

            Je vous remercie pour ces explications et et ces références.

            Je ne connais rien en encryptage mais je me demandais comment ils font pour s'assurer que leur clé est bien un nombre premier.

            Ce que j'en comprend, ils prennent une chance ...

            • Partager sur Facebook
            • Partager sur Twitter

            Le Tout est souvent plus grand que la somme de ses parties.

            Grands nombres premiers

            × Après avoir cliqué sur "Répondre" vous serez invité à vous connecter pour que votre message soit publié.
            • Editeur
            • Markdown