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

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 Les deux révisions suivantes
decomposition_en_facteurs_premiers [2008/07/02 17:25]
tyrtamos 		decomposition_en_facteurs_premiers [2009/01/09 12:38]
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 61: Ligne 62:
  
 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...) 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...)
 +
 +Autre exemple: factorisation d'un grand nombre composé de 2 grands nombres premiers (env. 15mn de calcul):
 +
 +<code python>
 +print facteurs(6082717798076598743)
 +[1536921011, 3957729613L]
 +</code>
 +
 +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 95:
 \\ \\
 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.
 +
 <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