CLEF RSA NSPIRE FACTORISEE !!!!!!!

→ **MyCalcs** profile · de **critor** » 09 Avr 2011, 14:41

Matériellement, oui.

→ **MyCalcs** profile · de **Chockosta** » 15 Avr 2011, 18:38

Arrêtez-moi si je dis des bêtises, mais...
Je viens de penser à un truc tout bête : pour trouver la clef, il faut environ 10³⁰⁰ opérations, c'est ça ?
Au niveau actuel du matériel, ça reviendrait donc à une dizaine d'années sur un bon ordi familial, non ?

Ma suggestion serait de faire participer la communauté.
Il faudrait, sur le portail, lancer un concours de celui qui trouvera la clef RSA le premier, et qui gagnera, allez, une Nspire, pour que ce soit bien motivant.
L'idée serait de faire un bot (genre en C, pour quelque chose de bien rapide) qu'on laisse tourner pendant 3h et qui teste quelques millions de possibilités. Un script (batch ?) envoie ensuite les possibilités testées sur TI-Bank, enfin dans une base de données, qui serait récupérée à chaque nouveau lancement du bot.
Il fadra automatiser tout ça, pour que ce soit accessible au tout-venant et pas décourageant, qui n'aura qu'un double-clic à faire.

Avec la bande passante de TI-Bank, il serait assez facile d'obtenir un bon millier de testeurs, voir même 5000, et le gain serait faramineux.

Bon, je dis peut-être n'importe quoi, mais ça me fait rêver...

→ **MyCalcs** profile · de **critor** » 15 Avr 2011, 18:43

Chockosta a écrit:Arrêtez-moi si je dis des bêtises, mais...
Je viens de penser à un truc tout bête : pour trouver la clef, il faut environ 10³⁰⁰ opérations, c'est ça ?
Au niveau actuel du matériel, ça reviendrait donc à une dizaine d'années sur un bon ordi familial, non ?

Je t'arrête...

J'ai certes parlé d'une 10aine d'années, mais pas dans ce sens là.
Dans une 10aine d'années, un bon groupe de bons ordinateurs devrait être capable de factoriser la clef en quelques semaines/mois.

Si on lance la recherche dès maintenant, ce sera loin d'être terminé dans 10 ans.

→ **MyCalcs** profile · de **Lionel Debroux** » 15 Avr 2011, 18:44

Les ordres de grandeur font que c'est complètement inimaginable par TF (il faut plus d'essais que ce qu'il y a de particules élémentaires dans l'univers...), et actuellement impensable avec le meilleur algorithme connu, puisque les implémentations ouvertes de cet algorithme sont un cran en-dessous de l'état de l'art (factorisation de RSA-768), qui est lui-même en-dessous de ce qu'il faudrait pour factoriser RSA-1024.
La factorisation de RSA-1024 est estimée environ 3 ordres de grandeur plus difficile que la factorisation de RSA-768, qui est elle-même entre 3 et 4 ordres de grandeur plus difficile que la factorisation de RSA-512 (celle-ci étant considérée comme une trivialité, puisqu'un ordinateur portable haut de gamme de 2011 le fait en moins d'un mois). Des dizaines de milliers de téra-octets de données brutes, une matrice presque carrée de dimension plusieurs milliards d'éléments * plusieurs milliards d'éléments.

Il y a deux douzaines de pages là -dessus sur Omnimaga, dans plusieurs topics. Des gens ont récemment essayé de réimplémenter absolument n'importe comment (avec un langage inadapté, le C#, et un algorithme stupide, qui fait de lourds tests de pseudo-primalité pour les diviseurs...) le programme C de TF que Tribal et moi avions fait sur Omnimaga, résultant en une performance horrible.

→ **MyCalcs** profile · de **Chockosta** » 15 Avr 2011, 18:47

Bon, très bien, ce n'était qu'un simple rêve...

Un seul moyen pour un horizon proche : un bon ami chez TI !
Enfin, un ex de chez TI, car je ne sais pas s'il va y rester bien longtemps...

ici · de **Loulou 54** » 15 Avr 2011, 19:39

Chockosta a écrit:Ma suggestion serait de faire participer la communauté.
Il faudrait, sur le portail, lancer un concours de celui qui trouvera la clef RSA le premier, et qui gagnera, allez, une Nspire, pour que ce soit bien motivant.

hihi j'avais aussi pensé à ça !

→ **MyCalcs** profile · de **Lionel Debroux** » 15 Avr 2011, 19:53

Le programme est déjà fait. Mais ça serait du gaspillage de temps CPU, vu que même en y mettant beaucoup d'ordinateurs pendant longtemps, on dépasserait difficilement 10^20 divisions, soit une partie infime de l'espace de recherche...

→ **MyCalcs** profile · de **Naruto`kun** » 16 Avr 2011, 09:35

et pourquoi pas utiliser les gpu? (notament avec ati stream et cuda)
j'avais testé un logiciel pour trouver des hash md5 (a titre purement expérimental) et sur mon quadcore de 3ghz, j'avais 100 milliards de hash a la seconde, alors que sur mon gpu (ati 4870) j'avais 20 000 milliards de hash a la seconde.... sa parrais toujours pas concevable, sachant que ma cg a maintenant deux ans (et donc qu'ils on fait de grand progrés depuis, et j'en parle méme pas avec du crosfire ou du sli...)? (je parle en communautaire, bien évidement)

Mes programmes · de **Levak** » 16 Avr 2011, 09:42

QuadSLI _o/

→ **MyCalcs** profile · de **Lionel Debroux** » 16 Avr 2011, 09:48

Il n'y a aucune implémentation du Number Field Sieve sur GPGPU (et pas vraiment d'implémentation de morceaux du NFS comme les diverses variantes de QS); les GPGPU peuvent faire des divisions de grands nombres (dizaines à centaines de millions de bits) par de petits nombres (mais 1) il est possible que les nombres d'entrée doivent avoir des formes spéciales et 2) des diviseurs de moins de 100 bits sont beaucoup trop petits, il nous faudrait environ 512 bits.
End of story

: