Encore plus de Nombres Premiers

Posté par  (site web personnel) . Modéré par Pascal Terjan.
Étiquettes : aucune
0
10
août
2002
Sécurité
Tout le monde sait à quoi sert les nombres premiers : factoriser.
Et à quoi peut bien servir de factoriser ? A casser du chiffre (je sais ça sert pas qu'à ça, mais bon).

Or une équipe indienne annonce avoir trouver une méthode infaillible pour dire si un nombre est premier ou non. L'avantage est que les chances d'erreur sont de 0%, par contre il semble que l'algo qui en découle rende la recherche un peu plus lente. Ce qu'ils cherchent les trois gars d'la bas, c'est rendre plus rapide leur algo ... Si ça vous interresse ou que vous êtes une bête en math.... suivez les liens.

Dijkstra est mort, mais la relève est là !

Je vous conseille le document qui pourrait être compris dès la seconde ..... semaine de lecture.

N.B. : un nombre premier c'est un nombre uniquement divisible par 1 ou par lui même (ex: 1, 2, 3, 5, 7, 11, 13, 17, 19, etc...)

NdM: l'interet et la nouveauté de leur algorithme sont qu'il est en temps polynomial !

Aller plus loin

  • # Putain, toujours à ramener ma fraise!

    Posté par  . Évalué à 10.

    Désolé d'être aussi rigide (mais je suis un matheux, ça explique), mais 1 n'est pas premier (et donc la définition donnée n'est pas bonne). Je sais, c'est une histoire de culture, il y en a peut être qui ont vraiment eu cette définition là, encore que j'en doute. Le consensus m'a l'air d'être assez établi, du moins en France.
    Ca change peut être pas grand chose (un nombre change de status), mais c'est une simplification pour l'arithmétique (ça évite d'avoir des énoncé avec des "sauf pour n=1") et ç'est génant sinon, parce q'on aime mieux avoir l'énoncé "tout nombre non nul a une décomposition UNIQUE en facteurs premiers aux inversibles près" que tout nombre non nul est décomposables en produits de facteurs premiers. Parmi les décompositions, il y en a une de plus petite longueur (à définir!), elle estt unique aux inversibles près".
    Et pour tout dire, je complique vachement. Dans un anneau, un inversible ne peut pas être premier. C'est comme ça.

    • [^] # Re: Putain, toujours à ramener ma fraise!

      Posté par  (Mastodon) . Évalué à 1.

      Je ne suis pas mathématicien, mais j'ai un problème avec ce que tu dis. Moi, on m'a donné un théorème qui dit que tout nombre naturel peut se factoriser en un produit de nombres premiers. Comment tu factorises 1 si 1 n'est pas premier ?

    • [^] # Re: Putain, toujours à ramener ma fraise!

      Posté par  (site web personnel) . Évalué à 6.

      Moi je reste souple(tm) ;^)

      En fait je ne comprends pas a quoi ca sert...

      Pour un nombre, etre divisible uniquement pas lui meme (et 1 bien sur) c'est une propriete assez interressante, et je comprends vaguement pourquoi on remarque cette 'propriete', ca defini un ensemble de nombre. bref ca peut servir

      Par contre, je ne pige pas a quoi sert d'exclure '1' ? (hormis le fait de gagner du temps a l'ennoncer du bac...) Quel resultat concret ca implique ?

      Je demande tout ca parce que les maths je les oublier apres la terminal, alors bon...

      • [^] # Re: Putain, toujours à ramener ma fraise!

        Posté par  . Évalué à -7.

        Ouais, et la grammaire aussi

        • [^] # ROOOOH!

          Posté par  . Évalué à 0.

          Mais il faut reconnaître ... et l'othographe aussi ... ;)

      • [^] # Re: Putain, toujours à ramener ma fraise!

        Posté par  . Évalué à 10.

        C'est pour l'unicité de la décomposition :

        6 = 2 * 3
        et si 1 était premier on aurait :
        6 = 2*3 = 1*2*3 = 1*1*2*3 ...
        du coup on pourrait pas dire qu'un entier naturel non nul se décompose de façon unique à l'ordre près en produit de nombres premiers.

      • [^] # Re: Putain, toujours à ramener ma fraise!

        Posté par  (site web personnel) . Évalué à -7.

        Et l'orthographe aussi !

        Jellyroll

      • [^] # Re: Putain, toujours à ramener ma fraise!

        Posté par  . Évalué à 2.

        Ben les maths, ce n'est pas quelque chose de souple, justement, c'est une science ou la rigueur est de mise. Et effectivement, selon la définition des nombres premiers, 1 n'est PAS un nombre premier, c'est comme ça, qu'on pige ou pas à quoi ça sert d'exclure ce nombre.

        « rester souple », ça se traduit, sur une copie notée, par une inscription rageuse en rouge: « manque de rigueur ! » :)

  • # en pratique..

    Posté par  . Évalué à 10.

    L'avantage est que les chances d'erreur sont de 0%
    Il faut quand meme noter qu'avec les algos probabilistes qu'on utilisait avant, l'erreur était de l'ordre de 10^-10.. donc en pratique, comme le dit l'article, ca ne change pas grand chose.. (Par "en pratique", j'entends pour la crypto par exemple)

  • # Compléments

    Posté par  (site web personnel) . Évalué à 10.

    Les tests les plus utilisés pour tester la primalité d'un nombre sont les tests de Fermat et de Miller-Rabin. Ce sont des tests probabilistiques qui prouvent qu'un nombre n'est pas premier ou qui supposent avec une certaine probabilité qu'un nombre est premier. Ces tests se basent sur le théorème de Fermat qui dit :

    si p est premier et 1<=a<n alors a^(n-1) = 1 mod p

    plus d'infos sur
    http://www.utm.edu/research/primes/prove/index.html(...)

    Autre précision, tester la primalité d'un nombre sert aussi à créer des pairs de clés publiques/privés pour le RSA, DSA... par exemple.

    • [^] # Re: Compléments

      Posté par  . Évalué à 1.

      Je dis peut-être une anerie (surement même, vu mon niveau en maths), mais j'ai du mal à imaginer qu'on parle de preuve pour une méthode probabiliste .

      "Je vous prouve que A , sauf si je me trompe mais y'a peu de chance alors on va dire que je me trompe pas."

      • [^] # Re: Compléments

        Posté par  (site web personnel) . Évalué à 10.

        Désolé pour le néologisme. On dit par sûr probabiliste pour ce qui se rapporte à la théorie des probabilités.

        Par contre on peut parler de preuve. En effet, ces algos fonctionnent par itérations. On effectue N fois un test sur un nombre p. Si un de ces N tests retourne la valeur faux alors p n'est pas premier. En revanche si les N tests sont vrais alors p est peut-être premier. Cela s'explique par le fait que le théorème de Fermat est une implacation et non pas une équivalence donc :

        p premier => tous les tests sont vrais

        comme on a : si A=>B alors !B=>!A ; un test est faux => p n'est pas premier. Mais la réciproque est fausse. En revanche on peut prouver que la proposition p est premier est vraie avec une certaine probabilité.

        • [^] # Re: Compléments

          Posté par  (site web personnel) . Évalué à 10.

          Si un de ces N tests retourne la valeur faux alors p n'est pas premier.
          D'ailleurs, en pratique, dès le premier échec, on arrête le test car on est certain que le nombre testé n'est pas premier (cf. ce que tu mets sur l'implication et la logique)

          ... par le fait que le théorème de Fermat est une implacation ...
          En toute rigueur, il s'agit du petit théorème de Fermat.

          Mais la réciproque est fausse. En revanche on peut prouver que la proposition p est premier est vraie avec une certaine probabilité.
          FAUX (sauf en logique flou et d'une manère plus générale avec les logiques pour lesquelles les valeurs possibles d'un théorème ne sont pas que vrai ou faux - logiques dites multimodales mais je ne suis pas certain du terme)

          Dans le cas de Miller-Rabin (voir http://www.security-labs.org/index.php3?page=5(...)) on part de l'hypothèse qu'un entier n impair est fortement pseudo-premier par rapport à b pour au plus 25% des nombres b (0<b<n). Cela signifie que si n et b ne sont pas fortement pseudo-premiers, alors n n'est pas premier.

          Ainsi, pour chaque b testé, on a une probabilité de 0.25 que n soit composite. Si on répète le test p fois, la probabilité que n soit composite descend alors à 0.25^p

          Bref, tout cela pour dire que les tests probabilistes donnent comme information une probabilité pour qu'un nombre soit composite.

      • [^] # Re: Compléments

        Posté par  (site web personnel) . Évalué à 10.

        Non, tu n'as pas bien compris. Ce que l'on prouve, c'est qu'un nombre n'est pas premier.
        Par contre, on n'a qu'une probabilité pour affirmer qu'un nombre est premier. Ce n'est pas symétrique.

        Apparemment, le nouvel algorithme proposé permettrait de prouver qu'un nombre est premier, et donc de manière non probabiliste. Et en temps polynomial, ce qui est surprenant.

  • # La rédaction de cette news est une honte

    Posté par  (site web personnel) . Évalué à 1.

    Cet article de recherche est très intéressant et novateur dans le domaine, je l'avais d'ailleurs lu en voyant passer le lien sur /.

    Malheuresement, les modéros devraient plus faire attention lorsqu'il passe une news : dans le cas présent, la news est très bonne mais la rédaction est "nulle à chier" (si je peux me permettre). L'auteur ne maitrise clairement pas le sujet (erreurs relevées dans les commentaires) et oublient un point essentiel de l'article : la résolution en temps polynomial (d'ailleurs le modéro a été obligé de l'ajouter).

    SVP, les modéros, sur les articles de recherche, si vous jugez la news intéressante et que vous la comprenez bien, n'hésitez pas à la réécrire entièremment quand la rédaction est aussi nulle.

Suivre le flux des commentaires

Note : les commentaires appartiennent à celles et ceux qui les ont postés. Nous n’en sommes pas responsables.