Ci-dessous, les différences entre deux révisions de la page.
Les deux révisions précédentes Révision précédente | Dernière révision Les deux révisions suivantes | ||
factorisation_shor [2009/01/06 07:45] tyrtamos |
factorisation_shor [2009/01/06 08:10] 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 275: | Ligne 277: | ||
On a bien trouvé le résultat, mais en 102 secondes. | On a bien trouvé le résultat, mais en 102 secondes. | ||
- | Les limites " | + | Les limites " |
- | Et, curieusement, | + | 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' |