Outils pour utilisateurs

Outils du site


factorisation_shor

Warning: Undefined array key -1 in /home/clients/a4e6fc1ce1761b72982b805de0f418c4/web/python/mesrecettespython/inc/html.php on line 1458

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 de tyrtamos