Différences

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

--- factorisation_shor [2009/01/06 07:45]
tyrtamos
+++ factorisation_shor [2009/01/06 08:10]
tyrtamos
@@ Ligne 168: / Ligne 168: @@
 </code>
-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" 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).
-Si on recommence, on voit que le temps d'exécution change pas mal en fonction de la pertinence du choix du "a". Quelquefois, la réponse est quasi immédiate, d'autre fois, cela peut dépasser la dizaine de seconde pour des valeurs de cette taille.
+Si on recommence avec d'autres valeurs, on voit que le temps d'exécution change pas mal en fonction de la pertinence du choix du "a". Quelquefois, la réponse est quasi immédiate, d'autre fois, cela peut dépasser la dizaine de seconde pour des valeurs de cette taille.
 Essayez par exemple le code d'essai suivant:
@@ Ligne 244: / Ligne 244: @@
 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'arriver au bout, on renvoie la valeur de r=k car on l'a trouvé!
+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'arriver au bout, on renvoie la valeur de r=k car on l'a trouvé!
 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 "pas". Ce pas est fixé a priori à %%(P-imax)//10000%%, mais il ne doit pas être inférieur à 1.
@@ Ligne 275: / Ligne 277: @@
 On a bien trouvé le résultat, mais en 102 secondes.
-Les limites "raisonnables" (quelques minutes) correspondent à un produit de nombres à 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 produit 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 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!
 On est donc encore très loin de factoriser un nombre de 2048 bits (composé d'environ 600 chiffres)...

Les recettes Python de Tyrtamos

Outils pour utilisateurs

Outils du site

Différences

Outils de la page