Outils pour utilisateurs

Outils du site


factorisation_shor

Différences

Ci-dessous, les différences entre deux révisions de la page.

Lien vers cette vue comparative

Les deux révisions précédentes Révision précédente
factorisation_shor [2009/01/06 08:10]
tyrtamos
factorisation_shor [2009/01/06 08:20] (Version actuelle)
tyrtamos
Ligne 272: Ligne 272:
 calcul de n2 calcul de n2
 Solution: n1= 2087 n2= 2371 Solution: n1= 2087 n2= 2371
-2087 2371 4948277 ​4948277 102.754698033+2087 2371 4948277 102.754698033
 </​code>​ </​code>​
  
 On a bien trouvé le résultat, mais en 102 secondes. On a bien trouvé le résultat, mais en 102 secondes.
 +
 +Autre exemple:
 +
 +<code python>
 +Nombre à factoriser:
 +P= 5611561 (produit de  2621  et de  2141 )
 +=====> Essai avec a= 3948837
 +période r= 280340
 +calcul de a**(r//2)
 +calcul de n1
 +calcul de n2
 +Solution: n1= 2621 n2= 2141
 +2621 2141 5611561 4.17664580239
 +</​code>​
 +
 +Là, le bon résultat [2621, 2141] a été trouvé en 4 secondes avec un seul essai a=3948837 qui a donné la période r=280340.
  
 Les limites "​raisonnables"​ (quelques minutes?) correspondent à un produit de nombres à 12 ou 16 bits, ce qui est déjà pas mal. Les limites "​raisonnables"​ (quelques minutes?) correspondent à un produit de nombres à 12 ou 16 bits, ce qui est déjà pas mal.
  
-Et, curieusement,​ avec ces produits de nombres ​à 16 bits, le calcul de la période se passe plutôt bien, et c'est le calcul de %%a**(r//​2)%% qui dure trop de temps!+Et, curieusement,​ avec des nombres ​de cette taille, le calcul de la période se passe plutôt bien, et c'est le calcul de %%a**(r//​2)%% qui dure trop de temps!
  
 On est donc encore très loin de factoriser un nombre de 2048 bits (composé d'​environ 600 chiffres)... On est donc encore très loin de factoriser un nombre de 2048 bits (composé d'​environ 600 chiffres)...
Ligne 290: Ligne 306:
  
 En ce qui concerne le calcul de la période, si on n'a pas d'​ordinateur quantique sous la main (:-D), peut-être qu'une FFT appliquée à f(k) serait une bonne solution? En ce qui concerne le calcul de la période, si on n'a pas d'​ordinateur quantique sous la main (:-D), peut-être qu'une FFT appliquée à f(k) serait une bonne solution?
 +
 +En ce qui concerne le calcul de %%a**(r//​2)%%,​ il faut se rappeler que ça se fait avec des nombres très grands, et que le résultat est énorme. Pour prendre le dernier exemple, essayer donc de calculer %%3948837**(280340//​2)%%,​ et imaginez un peu ce que ça donnerait pour des nombres de plusieurs centaines de chiffres...
  
 \\ \\
factorisation_shor.txt · Dernière modification: 2009/01/06 08:20 par tyrtamos