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.
Journal Nombre de 307 chiffres factorisé
24
mai
2007
# ouah
Posté par Snarky . Évalué à 10.
Où même mieux, l'intérêt de factoriser ce nombre :)
[^] # Re: ouah
Posté par 태 (site web personnel) . Évalué à 8.
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 ouah (site web personnel) . Évalué à 9.
> 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 Sébastien B. . Évalué à 7.
Comment ai je pu passer à coté de ça si lontemps ?
[^] # Re: ouah
Posté par Bastien Leblanc (site web personnel) . Évalué à 1.
[^] # Re: ouah
Posté par Spyhawk . Évalué à 9.
Faut continuer vraiment l'explication ? :D
[^] # Re: ouah
Posté par chl (site web personnel) . Évalué à 6.
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 jcs (site web personnel) . Évalué à 10.
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 nats . Évalué à 5.
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 khivapia . Évalué à 1.
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 nats . Évalué à 2.
A quand le PrimeX (Le divX du nombre premier :p).
Hop, hop, hop ->[\o/]
[^] # Re: ouah
Posté par davux (site web personnel) . Évalué à 4.
Ahem... Le tatillonage consistait justement à dire qu'un nombre premier ça ne se factorise pas :D
[^] # Re: ouah
Posté par nats . Évalué à 2.
Je file me pendre de ce pas -_-'
Il manque un "semi-" devant premiers ^^
[^] # lieu
Posté par tfeserver tfe (site web personnel) . Évalué à -2.
# précision
Posté par cowboy . Évalué à 10.
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 desertpingouin . Évalué à -2.
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 Nicolas Schoonbroodt . Évalué à 7.
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 M . Évalué à 2.
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 Nicolas Schoonbroodt . Évalué à 6.
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 chl (site web personnel) . Évalué à 5.
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 pipo_molo . Évalué à 3.
[^] # Re: Moi je le fais à la main
Posté par Dring . Évalué à 8.
[^] # Re: Moi je le fais à la main
Posté par ouah (site web personnel) . Évalué à 7.
>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 Sébastien B. . Évalué à 5.
Je sais quel est la réponse, c'est 42 !
[^] # Re: Pff...
Posté par Spyhawk . Évalué à 4.
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 plagiats . Évalué à 1.
[^] # Re: Pff...
Posté par fleny68 . Évalué à 2.
TuxMath est maintenant là-bas: http://alioth.debian.org/projects/tux4kids/
[^] # Re: Pff...
Posté par Alex . Évalué à 10.
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 fleny68 . Évalué à 0.
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.