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:42] tyrtamos |
factorisation_shor [2009/01/06 08:20] tyrtamos |
||
---|---|---|---|
Ligne 1: | Ligne 1: | ||
====== Une curiosité: factorisation par l' | ====== Une curiosité: factorisation par l' | ||
- | |||
- | //**En construction**// | ||
===== Problématique ===== | ===== Problématique ===== | ||
Ligne 170: | 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 246: | 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 272: | 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 291: | Ligne 307: | ||
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// | ||
+ | |||
+ | \\ | ||
+ | Amusez-vous bien! | ||
< | < |