Deprecated: Array and string offset access syntax with curly braces is deprecated in /home/clients/a4e6fc1ce1761b72982b805de0f418c4/web/python/mesrecettespython/inc/init.php on line 563
decomposition_en_facteurs_premiers [Les recettes Python de Tyrtamos]

Outils pour utilisateurs

Outils du site


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
Révision précédente
decomposition_en_facteurs_premiers [2009/01/09 12:38]
tyrtamos
decomposition_en_facteurs_premiers [2009/01/09 12:54]
tyrtamos
Ligne 61: 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...).
  
-Autre exemple: factorisation d'un grand nombre composé de 2 grands ​nombres premiers ​(env15mn de calcul):+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 ​grandsPar exemple:
  
 <code python> <code python>
-print facteurs(6082717798076598743)+print facteurs(6082717798076598743L)
 [1536921011,​ 3957729613L] [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>​ </​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... 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 95: 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>​
decomposition_en_facteurs_premiers.txt · Dernière modification: 2009/01/09 12:54 par tyrtamos