Journal Nombre de 307 chiffres factorisé

Posté par  (site web personnel) .
Étiquettes :
0
24
mai
2007
Une équipe de chercheurs de l'EPFL en Suisse, de NTT au Japon et de l'Université de Bonn en Allemagne a annoncé le 21 mai avoir factorisé un nombre de 307 chiffres (dans le cas présent, 1017 bits). Onze mois de calcul ont été nécessaires.

A noter qu'il ne s'agit pas d'un nombre du challenges RSA (dont le plus grand factorisé à ce jour est de 200 chiffres) mais d'un des facteurs du nombre de Mersenne 2^1039-1.

La factorisation a été faite grâce à l'algorithme "special number field sieve" (SNFS). La puisssance de calcul nécessaire à cette factorisation correspond à environ 95 ans de calcul sur un Pentium-D 3-GHz.

  • # ouah

    Posté par  . Évalué à 10.

    Un lien ? Une source ? Le nombre ? Le résultat ?
    Où même mieux, l'intérêt de factoriser ce nombre :)

    • [^] # Re: ouah

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

      Pour compléter un tout petit peu : http://www.loria.fr/~zimmerma/records/factor.html page de records de factorisation.

      Un lien vers la source : http://www.crypto-world.com/announcements/m1039.txt du journal.

      Le nombre a été donné dans le journal : 2^1039-1. Mais en fait, 5080711 était un facteur connu, donc ils ont "seulement" factorisé (2^1039-1)/5080711...

    • [^] # Re: ouah

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

      > Un lien ? Une source ? Le nombre ? Le résultat ?
      > Où même mieux, l'intérêt de factoriser ce nombre :)

      Quelques infos supplémentaires:

      [1] [EN] L'annnonce sur FactorWorld
      http://www.crypto-world.com/announcements/m1039.txt
      (ainsi que l'a déjà posté Ernest H)

      [2] [FR] La news sur le site de l'EPFL
      http://actualites.epfl.ch/presseinfo-com?id=439

      [3] [EN] Les nombres de Mersenne
      http://mathworld.wolfram.com/MersenneNumber.html

      [4] [DE] La news sur le site de l'Uni de Bonn
      http://www1.uni-bonn.de/pressDB/jsp/pressemitteilungsdetails(...)

      La solution:

      1159420574072573064369807148876894640753899791702
      0177249868683535388224838599667566080006095408005
      1794720539932612302048744028604353028619141014409
      3453512334712739679888502263075752809379166028555
      1055004258107711761776100941379707879738061870084
      3777718682868088984471282200293520180607475545154
      1370711023817

      =

      5585366661993629126074920465831594496864652701848
      8637648010052346319853288374753
      ×
      2075818194644238276457048137035946951629397080073
      9520988120838703792729090324679382343143884144834
      8825340533447691122230281583276965253760914101891
      0524199389933410971162435896206597216748116174900
      4803659735573409253205425523689

      --
      "La poésie se fait dans un lit comme l'amour. Ses draps défaits
      sont l'aurore des choses.", André Breton

      • [^] # Re: ouah

        Posté par  . Évalué à 7.

        Yahouuu mais c'est magnifique tout ça !
        Comment ai je pu passer à coté de ça si lontemps ?

    • [^] # Re: ouah

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

      +1 quel est l'intérêt final?

      • [^] # Re: ouah

        Posté par  . Évalué à 9.

        L'algorithme RSA (entre autres) est basé sur la factorisation de 2 grands nombres premiers.

        Faut continuer vraiment l'explication ? :D

        • [^] # Re: ouah

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

          Faut continuer vraiment l'explication ? :D

          Vu qu'il n'a pas l'air très renseigné, dis lui quand même que presque toutes les transactions sécurisées se basent sur RSA, genre lorsqu'il utilise sa CB pour acheter un truc. J'pense que là il va comprendre l'interêt de savoir factoriser :)

        • [^] # Re: ouah

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

          L'algorithme RSA (entre autres) est basé sur la factorisation de 2 grands nombres premiers.


          Non, les nombres premiers ne se factorisent pas (puisqu'ils sont premiers). RSA est basé sur le fait que la factorisation d'un grand nombre en un produit de 2 facteurs premiers est un problème difficile. Oui je sais je suis tatillon :-)

          • [^] # Re: ouah

            Posté par  . Évalué à 5.

            Pour une fois je suis d'accord avec le tatillonage!
            C'est pas être tatillon c'est la base même de RSA ^^
            L'intéret de factoriser des nombres premiers et de simplifier les algorithme de "cassage" de clés RSA.
            Seulement il est d'un complexe de trouver des nombres premiers trés grand (Pas forcément complexe en fait, mais trés couteux en temps),
            Le fait de stocker ces exemples factorisés permet de ne pas refaire le même calcul plus tard :)
            http://pages-perso.esil.univmed.fr/~bruasse.a//factorisation(...) <= pour pas mal d'informations :)

            • [^] # Re: ouah

              Posté par  . Évalué à 1.

              Le fait de stocker ces exemples factorisés permet de ne pas refaire le même calcul plus tard :)


              c'est très difficile de stocker ce genre de choses : Pi(256)>10^74 autrement dit : le nombre de nombres premiers de longueur inférieure à 256 bits (et 1024 bits est actuellement fortement recommandé pour les nombres premiers dans les clefs RSA) est supérieur à 10^74 ! !

              ce qui pose deux problèmes ; comment construire une telle base de données ? (surtout qu'il n'y a que plus ou moins10^80 atomes dans l'univers... ;-) ) et comment y accéder de façon intelligente ?

              Bref même en ne gardant que les nombres premiers solides d'exactement 256 bits dans le cas plus haut il est imposible de les stocker tous !

              • [^] # Re: ouah

                Posté par  . Évalué à 2.

                J'avoue ne pas avoir pensé à ca, mais stocker ceux qui sont calculables "rapidement" peut peut-être réduire significativement la taille de cette "base de données".
                A quand le PrimeX (Le divX du nombre premier :p).
                Hop, hop, hop ->[\o/]

            • [^] # Re: ouah

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

              Pour une fois je suis d'accord avec le tatillonage!
              C'est pas être tatillon c'est la base même de RSA ^^
              L'intéret de factoriser des nombres premiers et de simplifier [...]


              Ahem... Le tatillonage consistait justement à dire qu'un nombre premier ça ne se factorise pas :D

              • [^] # Re: ouah

                Posté par  . Évalué à 2.

                Et merde!! honte à moi j'ai osé dire ca....
                Je file me pendre de ce pas -_-'
                Il manque un "semi-" devant premiers ^^

    • [^] # lieu

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

      en suisse ;) c'est marqué voyons.

  • # précision

    Posté par  . Évalué à 10.

    Ce n'est pas une factorisation standard au sens "factorisation du produit de deux nombres premiers aléatoires de taille équivalente" mais bien la factorisation d'un nombre particulier ce qui permet d'utiliser un polynome spécial (d'où le S et non un G comme général) qui permet d'accélerer grandement le crible (sieving en anglais).
    Je vous invite à voir http://en.wikipedia.org/wiki/SNFS et http://fr.wikipedia.org/wiki/Algorithme_de_factorisation_par_crible_sur_les_corps_de_nombres_sp%C3%A9cialis%C3%A9 (beaucoup moins complet) et leurs pendants sur le GNFS.

  • # Ah

    Posté par  . Évalué à -2.

    C'est quand je lis un journal comme ca que je me dis que finalement, un bon petit post sur sarkozy, c'est tellement passionnant.
    Mais il fallait bien la geek touch pour remettre tout le monde de cette longue plage politique.

  • # Moi je le fais à la main

    Posté par  . Évalué à 7.

    Je sais factoriser plusieurs nombres de 307 chiffres à la main.
    Par exemple, 10^307, 2*10^307, 3*10^307, mais j'en connais plein d'autres. (bon, je pourrais faire des erreurs, mais en me concentrant, j'y arriverais probablement)

    • [^] # Re: Moi je le fais à la main

      Posté par  . Évalué à 2.

      Ben fait le!



      PS : on parle bien sur de décomposition en nombre premier (oui l'auteur du journal a tres mal traduit le interger factorization, mais il suffit d'aller faire un tour sur wikipedia pour s'en convaincre).

      • [^] # Re: Moi je le fais à la main

        Posté par  . Évalué à 6.

        10^307 : 2x5x2x5x2x5x2x5x2x5x2x5x2x5x2x5x2x5x2x5x2x5x2x5x2x5x2x5x2x5x2x5x2x5x2x5x2x5x2x5x2x5x2x5x2x5x2x5x2x5x2x5x2x5x2x5x2x5x2x5x2x5x2x5x2x5x2x5x2x5x2x5x2x5x2x5x2x5x2x5x2x5x2x5x2x5x2x5x2x5x2x5x2x5x2x5x2x5x2x5x2x5x2x5x2x5x2x5x2x5x2x5x2x5x2x5x2x5x2x5x2x5x2x5x2x5x2x5x2x5x2x5x2x5x2x5x2x5x2x5x2x5x2x5x2x5x2x5x2x5x2x5x2x5x2x5x2x5x2x5x2x5x2x5x2x5x2x5x2x5x2x5x2x5x2x5x2x5x2x5x2x5x2x5x2x5x2x5x2x5x2x5x2x5x2x5x2x5x2x5x2x5x2x5x2x5x2x5x2x5x2x5x2x5x2x5x2x5x2x5x2x5x2x5x2x5x2x5x2x5x2x5x2x5x2x5x2x5x2x5x2x5x2x5x2x5x2x5x2x5x2x5x2x5x2x5x2x5x2x5x2x5x2x5x2x5x2x5x2x5x2x5x2x5x2x5x2x5x2x5x2x5x2x5x2x5x2x5x2x5x2x5x2x5x2x5x2x5x2x5x2x5x2x5x2x5x2x5x2x5x2x5x2x5x2x5x2x5x2x5x2x5x2x5x2x5x2x5x2x5x2x5x2x5x2x5x2x5x2x5x2x5x2x5x2x5x2x5x2x5x2x5x2x5x2x5x2x5x2x5x2x5x2x5x2x5x2x5x2x5x2x5x2x5x2x5x2x5x2x5x2x5x2x5x2x5x2x5x2x5x2x5x2x5x2x5x2x5x2x5x2x5x2x5x2x5x2x5x2x5x2x5x2x5x2x5x2x5x2x5x2x5x2x5x2x5x2x5x2x5x2x5x2x5x2x5x2x5x2x5x2x5x2x5x2x5x2x5x2x5x2x5x2x5x2x5x2x5x2x5x2x5x2x5x2x5x2x5x2x5x2x5x2x5x2x5x2x5x2x5x2x5x2x5x2x5x2x5x2x5x2x5x2x5x2x5x2x5x2x5x2x5x2x5x2x5x2x5x2x5x2x5x2x5x2x5x2x5x2x5x2x5x2x5x2x5x2x5x2x5x2x5x2x5x2x5x2x5x2x5x2x5x2x5x2x5x2x5x2x5x2x5x2x5x2x5x2x5x2x5x2x5x2x5x2x5x2x5x2x5x2x5x2x5x2x5x2x5x2x5x2x5x2x5x2x5x2x5x2x5x2x5x2x5x2x5x2x5x2x5x2x5x2x5x2x5x2x5x2x5x2x5x2x5

        2x10^307 :
        2x2x5x2x5x2x5x2x5x2x5x2x5x2x5x2x5x2x5x2x5x2x5x2x5x2x5x2x5x2x5x2x5x2x5x2x5x2x5x2x5x2x5x2x5x2x5x2x5x2x5x2x5x2x5x2x5x2x5x2x5x2x5x2x5x2x5x2x5x2x5x2x5x2x5x2x5x2x5x2x5x2x5x2x5x2x5x2x5x2x5x2x5x2x5x2x5x2x5x2x5x2x5x2x5x2x5x2x5x2x5x2x5x2x5x2x5x2x5x2x5x2x5x2x5x2x5x2x5x2x5x2x5x2x5x2x5x2x5x2x5x2x5x2x5x2x5x2x5x2x5x2x5x2x5x2x5x2x5x2x5x2x5x2x5x2x5x2x5x2x5x2x5x2x5x2x5x2x5x2x5x2x5x2x5x2x5x2x5x2x5x2x5x2x5x2x5x2x5x2x5x2x5x2x5x2x5x2x5x2x5x2x5x2x5x2x5x2x5x2x5x2x5x2x5x2x5x2x5x2x5x2x5x2x5x2x5x2x5x2x5x2x5x2x5x2x5x2x5x2x5x2x5x2x5x2x5x2x5x2x5x2x5x2x5x2x5x2x5x2x5x2x5x2x5x2x5x2x5x2x5x2x5x2x5x2x5x2x5x2x5x2x5x2x5x2x5x2x5x2x5x2x5x2x5x2x5x2x5x2x5x2x5x2x5x2x5x2x5x2x5x2x5x2x5x2x5x2x5x2x5x2x5x2x5x2x5x2x5x2x5x2x5x2x5x2x5x2x5x2x5x2x5x2x5x2x5x2x5x2x5x2x5x2x5x2x5x2x5x2x5x2x5x2x5x2x5x2x5x2x5x2x5x2x5x2x5x2x5x2x5x2x5x2x5x2x5x2x5x2x5x2x5x2x5x2x5x2x5x2x5x2x5x2x5x2x5x2x5x2x5x2x5x2x5x2x5x2x5x2x5x2x5x2x5x2x5x2x5x2x5x2x5x2x5x2x5x2x5x2x5x2x5x2x5x2x5x2x5x2x5x2x5x2x5x2x5x2x5x2x5x2x5x2x5x2x5x2x5x2x5x2x5x2x5x2x5x2x5x2x5x2x5x2x5x2x5x2x5x2x5x2x5x2x5x2x5x2x5x2x5x2x5x2x5x2x5x2x5x2x5x2x5x2x5x2x5x2x5x2x5x2x5x2x5x2x5x2x5x2x5x2x5x2x5x2x5x2x5x2x5x2x5x2x5x2x5x2x5x2x5x2x5x2x5x2x5x2x5x2x5x2x5x2x5x2x5x2x5x2x5x2x5x2x5x2x5x2x5x2x5x2x5x2x5x2x5x2x5x2x5x2x5x2x5x2x5x2x5x2x5x2x5x2x5

        3x10^307 :
        3x2x5x2x5x2x5x2x5x2x5x2x5x2x5x2x5x2x5x2x5x2x5x2x5x2x5x2x5x2x5x2x5x2x5x2x5x2x5x2x5x2x5x2x5x2x5x2x5x2x5x2x5x2x5x2x5x2x5x2x5x2x5x2x5x2x5x2x5x2x5x2x5x2x5x2x5x2x5x2x5x2x5x2x5x2x5x2x5x2x5x2x5x2x5x2x5x2x5x2x5x2x5x2x5x2x5x2x5x2x5x2x5x2x5x2x5x2x5x2x5x2x5x2x5x2x5x2x5x2x5x2x5x2x5x2x5x2x5x2x5x2x5x2x5x2x5x2x5x2x5x2x5x2x5x2x5x2x5x2x5x2x5x2x5x2x5x2x5x2x5x2x5x2x5x2x5x2x5x2x5x2x5x2x5x2x5x2x5x2x5x2x5x2x5x2x5x2x5x2x5x2x5x2x5x2x5x2x5x2x5x2x5x2x5x2x5x2x5x2x5x2x5x2x5x2x5x2x5x2x5x2x5x2x5x2x5x2x5x2x5x2x5x2x5x2x5x2x5x2x5x2x5x2x5x2x5x2x5x2x5x2x5x2x5x2x5x2x5x2x5x2x5x2x5x2x5x2x5x2x5x2x5x2x5x2x5x2x5x2x5x2x5x2x5x2x5x2x5x2x5x2x5x2x5x2x5x2x5x2x5x2x5x2x5x2x5x2x5x2x5x2x5x2x5x2x5x2x5x2x5x2x5x2x5x2x5x2x5x2x5x2x5x2x5x2x5x2x5x2x5x2x5x2x5x2x5x2x5x2x5x2x5x2x5x2x5x2x5x2x5x2x5x2x5x2x5x2x5x2x5x2x5x2x5x2x5x2x5x2x5x2x5x2x5x2x5x2x5x2x5x2x5x2x5x2x5x2x5x2x5x2x5x2x5x2x5x2x5x2x5x2x5x2x5x2x5x2x5x2x5x2x5x2x5x2x5x2x5x2x5x2x5x2x5x2x5x2x5x2x5x2x5x2x5x2x5x2x5x2x5x2x5x2x5x2x5x2x5x2x5x2x5x2x5x2x5x2x5x2x5x2x5x2x5x2x5x2x5x2x5x2x5x2x5x2x5x2x5x2x5x2x5x2x5x2x5x2x5x2x5x2x5x2x5x2x5x2x5x2x5x2x5x2x5x2x5x2x5x2x5x2x5x2x5x2x5x2x5x2x5x2x5x2x5x2x5x2x5x2x5x2x5x2x5x2x5x2x5x2x5x2x5x2x5x2x5x2x5x2x5x2x5x2x5x2x5x2x5x2x5x2x5x2x5x2x5x2x5x2x5x2x5x2x5x2x5x2x5x2x5x2x5x2x5x2x5x2x5x2x5x2x5x2x5

        Tiens, il y a un bug dans kate qui affiche que le curseur est dans la colonne 1,228, alors qu'il est sensé être affiché 1228, en français localisé.

        • [^] # Re: Moi je le fais à la main

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

          10^307 : 2x5x...x2x5

          2x10^307 :
          2x2x5x...x2x5

          3x10^307 :
          3x2x5x...x2x5

          Pourquoi ne pas aussi utiliser les exposants dans tes factorisations ?
          10^307 = 2^307x5^307
          2x10^307 = 2^308x5^307
          3x10^307 = 2^307x3x5^307

    • [^] # Re: Moi je le fais à la main

      Posté par  . Évalué à 3.

      En deux facteurs premiers ? Je veux voir !

    • [^] # Re: Moi je le fais à la main

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

      >Je sais factoriser plusieurs nombres de 307 chiffres à la main.
      >Par exemple, 10^307, 2*10^307, 3*10^307, mais j'en connais
      >plein d'autres. (bon, je pourrais faire des erreurs, mais en me
      >concentrant, j'y arriverais probablement)

      Pas sûr vu que ces nombres ont déjà tous 308 chiffres :)

  • # Pff...

    Posté par  . Évalué à 5.

    C'est n'importe quoi, tout ça pour avoir un résultat faux...
    Je sais quel est la réponse, c'est 42 !

    • [^] # Re: Pff...

      Posté par  . Évalué à 4.

      Pas du tout !

      La réponse est 6x9, puisqu'ici on cherche la factorisation et non le nombre lui-même :D

      • [^] # Nous dirons même plus

        Posté par  . Évalué à 1.

        2x3x3x3 ?

      • [^] # Re: Pff...

        Posté par  . Évalué à 2.

        J'ai un peu de mal à croire que 6x9 fasse 42. Puis je te recommander TuxMath pour t'entrainer un peu?

        TuxMath est maintenant là-bas: http://alioth.debian.org/projects/tux4kids/

        • [^] # Re: Pff...

          Posté par  . Évalué à 10.

          J'ai un peu de mal à croire que 6x9 fasse 42.

          Mon dieu certains ne savent toujours pas ça...
          toute l'éducation à refaire :
          http://fr.wikipedia.org/wiki/La_Grande_Question_sur_la_Vie,_(...)

          • [^] # Re: Pff...

            Posté par  . Évalué à 0.

            À la fin de la première série radiophonique, de la série télévisée et du livre Le Dernier Restaurant avant la fin du monde, le deuxième de la « trilogie en cinq volumes »

            Ah ben voilà. J'ai lu que le premier de la trilogie en cinq volumes. Tout s'explique.

            Il faudra coriiger TuxMath.

Suivre le flux des commentaires

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