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

Les recettes Python de Tyrtamos

Outils pour utilisateurs

Outils du site

Piste:
factorisation_pollardrho

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
factorisation_pollardrho [2009/11/21 18:03]
tyrtamos 		factorisation_pollardrho [2009/11/21 19:29]
tyrtamos
Ligne 1: Ligne 1:
 ====== Factorisation par l'algorithme de Pollard rho ====== ====== Factorisation par l'algorithme de Pollard rho ======
- 
-//**En construction!**// 
  
 ===== Objectif ===== ===== Objectif =====
Ligne 14: Ligne 12:
  
   * [[http://fr.wikipedia.org/wiki/Algorithme_rho_de_Pollard]]   * [[http://fr.wikipedia.org/wiki/Algorithme_rho_de_Pollard]]
 +
 +  * [[http://www.loria.fr/~sur/enseignement/coursCalea/coursCalea4_FSur.pdf]]
  
 Mais en fait, mon objectif n'est pas de "casser" le cryptage RSA (!), mais d'obtenir un outil de décomposition en facteurs premiers de nombres les plus grands possibles pour intégration dans une calculatrice. Mais en fait, mon objectif n'est pas de "casser" le cryptage RSA (!), mais d'obtenir un outil de décomposition en facteurs premiers de nombres les plus grands possibles pour intégration dans une calculatrice.
Ligne 215: Ligne 215:
 La fonction d'entrée (factpremiers(n)) est amusante à programmer: on a une pile initialisée à n, et une liste pour les résultats. Dans une boucle, on prend le dernier élément de la pile. Si c'est un nombre 1er, on le met dans la liste résultat. Sinon, on demande la décomposition. Si la décomposition n'a pas été obtenue, on essaie la méthode par division. Sinon, on empile les 2 éléments de décomposition et on recommence jusqu'à ce que la pile soit vide. La fonction d'entrée (factpremiers(n)) est amusante à programmer: on a une pile initialisée à n, et une liste pour les résultats. Dans une boucle, on prend le dernier élément de la pile. Si c'est un nombre 1er, on le met dans la liste résultat. Sinon, on demande la décomposition. Si la décomposition n'a pas été obtenue, on essaie la méthode par division. Sinon, on empile les 2 éléments de décomposition et on recommence jusqu'à ce que la pile soit vide.
  
-Voilà le code complet (les commentaires suivent). la seule fonction externe au code ci-dessous est la fonction estpremier(n): voir le test de Miller-Rabin sur ce site.+Voilà le code complet (il est auto-commenté). la seule fonction externe au code ci-dessous est la fonction estpremier(n): voir le test de Miller-Rabin sur ce site.
  
 <code python> <code python>
Ligne 286: Ligne 286:
 </code> </code>
  
 +Et voilà des exemples d'application avec des nombres quelconques tirés au hasard (y compris premiers) de 24 chiffres:
 +
 +<code python>
 +n = randint(100000000000000000000000, 999999999999999999999999)
 +</code>
 +
 +<code>
 +449946525836240730011144 [2L, 2, 2, 22739L, 2473429602424472987L]
 +723631393653923846443861 [723631393653923846443861L]
 +100761461480650516552474 [2L, 13L, 418031L, 7150123L, 1296579373L]
 +309621299363859380750381 [19L, 491L, 7366397L, 4505475319937L]
 +470982819479871720893314 [2L, 401L, 8966899L, 65492024992843L]
 +659285903932670502433034 [2L, 43L, 419927L, 18255828184441097L]
 +440521626857087271425673 [3L, 181L, 811273714285611917911L]
 +184558454917472165131677 [3L, 17798911649L, 3456362174591L]
 +542761678115984315317635 [3L, 3L, 3L, 5L, 91247281L, 44061114269621L]
 +705972276260517746239783 [43L, 1151L, 333337L, 42791779280963L]
 +182994624593879036449624 [2L, 2, 2, 137L, 439L, 380332342487652421L]
 +</code>
 +
 +Avec un temps d'exécution moyen de 0.13 sec., un temps mini de 3.5/1000 sec., et un temps maxi de 16.5 sec. 
 +
 +Je vais donc considérer que j'ai atteins mon but: cette fonction est parfaitement utilisable dans une calculatrice pour décomposer en facteur premier un nombre quelconque jusqu'à 24 chiffres, et même au delà avec un peu de chance.
 +
 +Mais ce n'est pas encore avec ça que je vais craquer les codes RSA :-D.
 +
 +
 +Amusez-vous bien!
  
 <html> <html>
factorisation_pollardrho.txt · Dernière modification: 2009/11/21 19:29 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