Outils pour utilisateurs
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.
| Les deux révisions précédentes Révision précédente Prochaine révision | Révision précédente | ||
|
factorisation_shor [2009/01/06 07:45] tyrtamos |
factorisation_shor [2009/01/06 08:20] tyrtamos |
||
|---|---|---|---|
| Ligne 168: | Ligne 168: | ||
| </ | </ | ||
| - | La fonction a échoué sur une première valeur de a = 5811, puis sur a = 3859 et a réussi avec a = 30757 au bout de 2/100 ème de seconde. | + | La fonction a échoué sur une première valeur de a = 5811, puis sur a = 3859 et a réussi avec a = 30757 (au bout de 2/100 ème de seconde). |
| - | Cette dernière valeur de a a permis de trouver une période r=3870, qui a fournit les 2 solutions n1= 181 et n2= 173 (dont le produit est bien 31313). | + | Cette dernière valeur de "a" |
| - | Si on recommence, on voit que le temps d' | + | Si on recommence |
| Essayez par exemple le code d' | Essayez par exemple le code d' | ||
| Ligne 244: | Ligne 244: | ||
| Le principe est assez simple: | Le principe est assez simple: | ||
| - | on commence par calculer les 10000 premières valeurs de la fonction f = pow(a,k,P) pour k=0 à (imax-1)=9999. Bien sûr, si on trouve un f=1 avant d' | + | on commence par calculer les 10000 premières valeurs de la fonction f = pow(a,k,P) pour k=0 à (imax-1)=9999. |
| + | |||
| + | Bien sûr, si on trouve un f=1 avant d' | ||
| Si ce n'est pas le cas, on va calculer la fonction pour un certain nombre de k commençant à imax, se terminant à P, par pas de " | Si ce n'est pas le cas, on va calculer la fonction pour un certain nombre de k commençant à imax, se terminant à P, par pas de " | ||
| Ligne 270: | Ligne 272: | ||
| calcul de n2 | calcul de n2 | ||
| Solution: n1= 2087 n2= 2371 | Solution: n1= 2087 n2= 2371 | ||
| - | 2087 2371 4948277 | + | 2087 2371 4948277 102.754698033 |
| </ | </ | ||
| On a bien trouvé le résultat, mais en 102 secondes. | On a bien trouvé le résultat, mais en 102 secondes. | ||
| - | Les limites " | + | Autre exemple: |
| - | Et, curieusement, avec ces produit de nombres à 16 bits, le calcul de la période se passe plutôt bien, et c'est le calcul de %%a**(r// | + | <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 | ||
| + | </ | ||
| + | |||
| + | Là, le bon résultat [2621, 2141] a été trouvé en 4 secondes | ||
| + | |||
| + | Les limites " | ||
| + | |||
| + | Et, curieusement, | ||
| On est donc encore très loin de factoriser un nombre de 2048 bits (composé d' | On est donc encore très loin de factoriser un nombre de 2048 bits (composé d' | ||
| Ligne 288: | Ligne 306: | ||
| En ce qui concerne le calcul de la période, si on n'a pas d' | En ce qui concerne le calcul de la période, si on n'a pas d' | ||
| + | |||
| + | En ce qui concerne le calcul de %%a**(r// | ||
| \\ | \\ | ||
factorisation_shor.txt · Dernière modification: 2009/01/06 08:20 de tyrtamos
Outils de la page
Sauf mention contraire, le contenu de ce wiki est placé sous les termes de la licence suivante : CC Attribution-Noncommercial-Share Alike 4.0 International
