Warning: Undefined array key "DOKU_PREFS" in /home/clients/a4e6fc1ce1761b72982b805de0f418c4/web/python/mesrecettespython/inc/common.php on line 2082
decomposition_en_facteurs_premiers [Les recettes Python de Tyrtamos]

Les recettes Python de Tyrtamos

Outils pour utilisateurs

Outils du site

Piste:
decomposition_en_facteurs_premiers

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
Prochaine révision 		Révision précédente
decomposition_en_facteurs_premiers [2008/07/02 17:25]
tyrtamos 		decomposition_en_facteurs_premiers [2009/01/09 12:54]
tyrtamos
Ligne 9: Ligne 9:
 Bien entendu, un nombre premier ne trouve que lui-même comme facteur premier! Bien entendu, un nombre premier ne trouve que lui-même comme facteur premier!
  
-Le principe du calcul est assez trivial, et consiste à faire des divisions entières systématiques avec divmod(). Cette fonction renvoie une liste de 2 valeurs: le résultat de la division entière et son reste. Si le reste est nul, c'est que la division est exacte, et on a trouvé un facteur de plus. On l'ajoute à la liste f, on remplace le n précédent par le résultat de cette division, et on recommence. La liste f contient à la fin tous les facteurs.+Le principe du calcul est assez trivial, et consiste à faire des divisions entières systématiques avec divmod(). Cette fonction renvoie une liste de 2 valeurs: le résultat de la division entière et son reste. Si le reste est nul, c'est que la division est exacte, et on a trouvé un facteur de plus. On l'ajoute à la liste F, on remplace le n précédent par le résultat de cette division, et on recommence. La liste F contient à la fin tous les facteurs.
  
 On utilise en plus une astuce pour gagner du temps: on commence par trouver tous les facteurs "2" (s'il y en a), ce qui permet après de n'essayer que les nombres impairs. Pour des valeurs de n importantes, on divise ainsi les essais par 2. On utilise en plus une astuce pour gagner du temps: on commence par trouver tous les facteurs "2" (s'il y en a), ce qui permet après de n'essayer que les nombres impairs. Pour des valeurs de n importantes, on divise ainsi les essais par 2.
  
-Les tentatives de division s'arrêtent à racine de n, parce que si on n'a pas trouvé de facteur avant, on n'en trouvera plus. Pour éviter l'utilisation de sqrt(), on fait le test sur i*i>n.+Les tentatives de division s'arrêtent à racine de n, parce que si on n'a pas trouvé de facteur avant, on n'en trouvera plus, et donc le n en question est premier (et on a donc fini la décomposition). Pour calculer la racine carrée de n, on utilise la fonction lsqrt() définie ici: [[http://python.jpvweb.com/mesrecettespython/racine_entiere]]. On aurait pu faire un test avec i*i>n, mais cela conduirait à faire la multiplication i*i pour chaque valeur de i, alors que la racine de n ne change que lorsque n change.
  
 Voici le code: Voici le code:
Ligne 23: Ligne 23:
 def facteurs(n): def facteurs(n):
     """facteurs(n): décomposition d'un nombre entier n en facteurs premiers"""     """facteurs(n): décomposition d'un nombre entier n en facteurs premiers"""
-    f=[]+    F = []
     if n==1:     if n==1:
-        return f+        return F
     # recherche de tous les facteurs 2 s'il y en a     # recherche de tous les facteurs 2 s'il y en a
     while n>=2:     while n>=2:
-        x=divmod(n,2) +        x,r = divmod(n,2) 
-        if x[1]==0: +        if r!=0:
-            f.append(2) +
-            n=x[0] +
-        else:+
             break             break
 +        F.append(2)
 +        n = x
     # recherche des facteurs 1er >2     # recherche des facteurs 1er >2
     i=3     i=3
-    while (i<=n): +    rn = lsqrt(n)+1 
-        if i*i>n: +    while i<=n: 
-            f.append(n)+        if i>rn: 
 +            F.append(n)
             break             break
-        x=divmod(n,i) +        x,r = divmod(n,i) 
-        if x[1]==0: +        if r==0: 
-            f.append(i) +            F.append(i) 
-            n=x[0]+            n=x 
 +            rn = lsqrt(n)+1
         else:         else:
-            i+=2 +            i += 2 
-    return f+    return F
  
 # exemple d'utilisation: # exemple d'utilisation:
Ligne 60: Ligne 61:
 Bien que passant par un calcul systématique "bête", cette fonction est rapide. Par exemple: Bien que passant par un calcul systématique "bête", cette fonction est rapide. Par exemple:
  
-facteurs(12345678901234567890) trouve [2, 3, 3, 5, 101, 3541, 3607, 3803, 27961] en moins d'un 1/10 de seconde (essayez donc de faire ça à la main...)+<code python> 
 +print facteurs(12345678901234567890) 
 +[2, 3, 3, 5, 101, 3541, 3607, 3803, 27961] 
 +</code> 
 + 
 +Résultat trouvé en moins d'un 1/10 de seconde (essayez donc de faire ça à la main...). 
 + 
 +La rapidité du calcul dépend de la quantité des facteurs et de leur taille. Le temps le plus long étant obtenu, pour une taille donnée,  avec un nombre premier, ou avec un nombre composé de 2 nombres premiers grands. Par exemple: 
 + 
 +<code python> 
 +print facteurs(6082717798076598743L) 
 +[1536921011, 3957729613L] 
 + 
 +print facteurs(4403961009416440783L) 
 +[1417259917, 3107377099L] 
 + 
 +print facteurs(1068903645797520007L) 
 +[589884577, 1812055591L] 
 + 
 +print facteurs(1036362964755146009L) 
 +[373148107, 2777350187L] 
 + 
 +print facteurs(433427761334691989L) 
 +[220147591, 1968805379L] 
 + 
 +print facteurs(2809239098183306821L) 
 +[725122477, 3874158073L] 
 +</code> 
 + 
 +Ce qui prend environ de 7 à 15 mn de calcul. 
 + 
 +Par contre, pour traiter des nombres de plusieurs centaines de chiffres comme on en trouve en cryptographie, il faudra nécessairement développer d'autres méthodes...
  
 \\ \\
Ligne 85: Ligne 117:
 \\ \\
 Vous pouvez tester la fonction facteurs(n) avec la Calculext ici: [[http://calculext.jpvweb.com]], mais soyez raisonnable: avec un nombre trop grand, vous risquez de dépasser le temps maxi de calcul autorisé sur le serveur. Vous pouvez tester la fonction facteurs(n) avec la Calculext ici: [[http://calculext.jpvweb.com]], mais soyez raisonnable: avec un nombre trop grand, vous risquez de dépasser le temps maxi de calcul autorisé sur le serveur.
 +
 +\\
 +Amusez-vous bien!
 +
 <html> <html>
 <head> <head>
decomposition_en_facteurs_premiers.txt · Dernière modification: 2009/01/09 12:54 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
CC Attribution-Noncommercial-Share Alike 4.0 International Donate Powered by PHP Valid HTML5 Valid CSS Driven by DokuWiki