Si si, tu as fait avancer le débat :
ton post est juste et on est près de la conclusion : (si ce n'est que la complexité de factorisation d'un nombre n'est pas, a priori, polynômiale mais bien non polynômiale ;-) ) si n est de taille t le temps de factorisation de n est de l'ordre de e^t.
(pour ceux qui en veulent un peu plus : voir un exemple de complexité pour le meilleur algo connu sur http://fr.wikipedia.org/wiki/Crible_général_de_corps_de_nombres_(GNFS) sachant que log(n) est peu ou prou le nombre de bits de n)
Id est : augmenter la taille d'un bit multiplie le temps de calcul par une constante.
On va dire que cette constante est 2 (ça serait plus, avec la complexité précédente, un peu plus de 1/3*64/9*1 soit e^2.37 = 10,7 voir plus bas) :
Alors augmenter la taille de 256 bits à 2048 multiplie le temps de calcul par 2^(2048-256) > 10^306 ! Soit plus, bien plus de 10^306 heures avec un PC actuel s'il met une heure pour calculer une factorisation de 256 bits.
Un PC actuel fait 1 GigaFlop mettons (1 GHz, bon c'est pas tout à fait vrai pour les flottants, et de toutes façons la factorisation ne fait appel qu'à des entiers, mais bon on calcule à la louche, hein ;-) )
1PetaFlop/1GigaFlop = 10^15Flop/10^9Flop = 10^6 ; le Blue Gene mettra 10^6 fois moins de temps que le PC de base pour faire la décomposition de la clef RSA, soit 10^300 heures !
(à titre de comparaison 1 an fait un peu moins de 10^4 heures... ça fait pas beaucoup à côté ! )
Bon évidemment c'est sous réserve que personne ne trouve entre temps d'algo plus rapide/de vice dans le principe/ne construise d'ordinateur quantique
Explication du 2.37 : en gros il faut a*e^{(64/9t)^{1/3}} opérations pour un nombre de logarithme t (la constante a vient du grand O, et on néglige la variation du log(log(n))) ; si t->t+1 (on augmente la taille de n, égale ici à son logarithme, de 1) on passe au temps a*e^{ (64/9 (t+1))}{1/3}} à peu près égal (développement limité à l'ordre 1 du terme à a*e^{(64/9t)^{1/3}+(1/3)*(64/9)*1} si t grand devant 1. d'où une multiplication du temps par e^(1/3)*(64/9)*1 d'où le résultat)
Note : résultats bien entendu non garantis ;-) à vérifier si quelqu'un passe par là ?
[^] # Re: .
Posté par khivapia . En réponse au journal BlueGene/P...enfin le petaflop !. Évalué à 6.
ton post est juste et on est près de la conclusion : (si ce n'est que la complexité de factorisation d'un nombre n'est pas, a priori, polynômiale mais bien non polynômiale ;-) ) si n est de taille t le temps de factorisation de n est de l'ordre de e^t.
(pour ceux qui en veulent un peu plus : voir un exemple de complexité pour le meilleur algo connu sur http://fr.wikipedia.org/wiki/Crible_général_de_corps_de_nombres_(GNFS) sachant que log(n) est peu ou prou le nombre de bits de n)
Id est : augmenter la taille d'un bit multiplie le temps de calcul par une constante.
On va dire que cette constante est 2 (ça serait plus, avec la complexité précédente, un peu plus de 1/3*64/9*1 soit e^2.37 = 10,7 voir plus bas) :
Alors augmenter la taille de 256 bits à 2048 multiplie le temps de calcul par 2^(2048-256) > 10^306 ! Soit plus, bien plus de 10^306 heures avec un PC actuel s'il met une heure pour calculer une factorisation de 256 bits.
Un PC actuel fait 1 GigaFlop mettons (1 GHz, bon c'est pas tout à fait vrai pour les flottants, et de toutes façons la factorisation ne fait appel qu'à des entiers, mais bon on calcule à la louche, hein ;-) )
1PetaFlop/1GigaFlop = 10^15Flop/10^9Flop = 10^6 ; le Blue Gene mettra 10^6 fois moins de temps que le PC de base pour faire la décomposition de la clef RSA, soit 10^300 heures !
(à titre de comparaison 1 an fait un peu moins de 10^4 heures... ça fait pas beaucoup à côté ! )
Bon évidemment c'est sous réserve que personne ne trouve entre temps d'algo plus rapide/de vice dans le principe/ne construise d'ordinateur quantique
Explication du 2.37 : en gros il faut a*e^{(64/9t)^{1/3}} opérations pour un nombre de logarithme t (la constante a vient du grand O, et on néglige la variation du log(log(n))) ; si t->t+1 (on augmente la taille de n, égale ici à son logarithme, de 1) on passe au temps a*e^{ (64/9 (t+1))}{1/3}} à peu près égal (développement limité à l'ordre 1 du terme à a*e^{(64/9t)^{1/3}+(1/3)*(64/9)*1} si t grand devant 1. d'où une multiplication du temps par e^(1/3)*(64/9)*1 d'où le résultat)
Note : résultats bien entendu non garantis ;-) à vérifier si quelqu'un passe par là ?