La décomposition en facteur d'un nombre entier très grand est toujours un problème, et c'est là-dessus que repose la sécurité de la plupart des systèmes de cryptage actuels.
On a vu (autre page de ce site) que la recherche de la décomposition par division successives est assez longue.
On va étudier ici la méthode de Pollard rho qui est beaucoup plus efficace tout en restant très simple à coder.
Références: il y a de nombreux sites qui en parlent, ce qui me permettra de ne pas répéter la théorie. Citons au moins:
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.
Voilà le code minimum:
def pollardrho(n): """Factorisation d'un nombre entier décomposable (méth. de rho pollard)""" f = lambda z: z*z+1 x, y, d = 2, 2, 1 while d==1: x = f(x) % n y = f(f(y)) % n d = pgcd(x-y, n) return d
En principe, on ne lance cette fonction que sur des nombres décomposables (=non-premiers), mais en fait, si le nombre est premier, ce n'est pas grave, parce que cette fonction renverra une décomposition triviale [n, 1] sans se bloquer.
Le problème, c'est que, même avec des nombres décomposables (=non-premiers), cette fonction pourra renvoyer une décomposition triviale [n, 1]. C'est à dire que l'algorithme peut échouer dans la décomposition. On verra si c'est important par la suite, et comment contourner cet inconvénient.
On peut se rattraper un peu si la décomposition ne s'est pas faite, en modifiant la fonction interne f(z): mettre x*x+c au lieu de x*x+1, et essayer successivement c=1, 2, … mais il faudra bien limiter le nombre d'essais, parce qu'il y a des cas dans lesquels ça bouclera trop longtemps.
Voilà donc un 2ème codage de base dans lequel on a simplement ajouté une boucle pour tester plusieurs valeurs de c. On peut d'ailleurs changer la valeur maxi de c (cmax) à l'appel:
def pollardrho(n, cmax=11): """Factorisation d'un nombre entier décomposable (méth. de rho pollard)""" x, y, d = 2, 2, 1 for c in xrange(1, cmax): f = lambda z: z*z + c while d == 1: x = f(x) % n y = f(f(y)) % n d = pgcd(x-y, n) if d != n: return [d, n//d] # ici, on a trouvé une décomposition non triviale return [d, n//d] # ici, il est possible que la décomposition ait échoué
Mais, finalement, on ne gagne pas grand chose avec ce nouveau code. Des valeurs de c>1 ne sont essayées que pour des nombres de faible taille (disons n < 10 chiffres), et il arrive assez souvent qu'un essai avec c>1 entraine en fait toutes les autres valeurs jusqu'à cmax sans qu'une décomposition non triviale ne soit trouvée.
Ce qui fait que j'utiliserai le 1er code (le plus simple) pour la suite.
On va utiliser une fonction pour fabriquer des nombres premiers au hasard. Par exemple:
from random import randint def genpremier(n1, n2): """génère un nombre premier entre n1 et n2 (bornes comprises)""" while True: n = randint(n1, n2) if estpremier(n): return n
On utilise un test de primalité estpremier(n) efficace sur les grands nombres, par exemple le test de Miller-Rabin (voir autre page de ce site)
Et voilà mon code de test:
tps = 0 # compteur de temps d'exécution k = 0 # compteur de boucles d = 0 # compteur d'échecs de décomposition while True: k += 1 a = genpremier(2, 9999) b = genpremier(2, 9999) n = a*b print n, a, b, t = clock() x1, x2 = pollardrho(n) tps += clock()-t if x1==n: # échec de la décomposition d += 1 print x1, x2, tps/k, 1.0*d/k if x1*x2 != n: print "erreur:", x1, x2, x1*x2, n break
Et voilà des exemples de résultats:
6070369 7853 773 773 7853 0.000207891978866 0.00876761141196 29538581 9949 2969 9949 2969 0.000207887574668 0.00876740587932 65578103 7247 9049 9049 7247 0.000207886184694 0.00876720035631 36287057 8363 4339 4339 8363 0.000207885697166 0.00876699484294 24116513 7757 3109 3109 7757 0.000207890759165 0.00876678933921 3260627 5651 577 577 5651 0.000207887519423 0.00876658384511 19051531 4583 4157 4583 4157 0.000207887492079 0.00876637836064 1337131 229 5839 229 5839 0.000207885660146 0.00876617288581 1108339 953 1163 1163 953 0.000207885506528 0.0087659674206
On peut laisser tourner ce programme de test pendant plusieurs heures, et constater:
Faisons grimper maintenant la taille des nombres à décomposer, en prenant pour n une multiplication de 2 nombres premiers du genre: genpremier(100000, 999999) pour 6 chiffres (donc n à 12 chiffres).
On constate que le taux de décompositions triviales diminue quand la taille du nombre à décomposer augmente, et reste < 1/1000 au delà de n à 12 chiffres. Ce qui fait plus de 99.9% de décompositions réussies.
Pour n à 12 chiffres: temps d'exécution moyen = 0.0036 sec. (avec une décomposition par division: 0.076 sec.)
Pour n à 14 chiffres: temps d'exécution moyen = 0.013 sec. (avec une décomposition par division: 0.62 sec.)
Pour n à 16 chiffres: temps d'exécution moyen = 0.048 sec. (avec une décomposition par division: 5 sec.)
Pour n à 18 chiffres: temps d'exécution moyen = 0.18 sec. (avec une décomposition par division: trop long)
Pour n à 20 chiffres: temps d'exécution moyen = 0.63 sec. (— idem —)
Pour n à 22 chiffres: temps d'exécution moyen = 2 sec. (— idem —)
Pour n à 24 chiffres: temps d'exécution moyen = 5 sec. (— idem —)
Il faut avoir conscience de la taille des nombres dans ce dernier cas:
131876058687340818200393 = 847540519127 * 155598529759 117594665193949490693507 = 247823395231 * 474509943197 368620440437049313142309 = 893143981519 * 412722302411 419982641209049360891749 = 639442040443 * 656795478943 647544964476895816984781 = 774077746367 * 836537373043 327757218529543533906677 = 508254008653 * 644868929609
Finalement, cet algorithme se débrouille pas mal. Il permet la décomposition de nombres beaucoup plus grands qu'avec la méthode des divisions, et échoue rarement (<1/1000 au delà de 12 chiffres).
Voyons ce qu'il donne avec des nombres composés quelconques
On va tester la fonction de décomposition avec des nombres au hasard, mais on va exclure les nombres premiers: ils seraient responsables d'un accroissement anormal des temps d'exécution, alors même que nous disposons de tests de primalité rapide.
Essayons avec des nombres de 24 chiffres créés comme suit:
n = 2 while estpremier(n): n = randint(100000000000000000000000, 999999999999999999999999)
Voici un exemple de sortie. Dans l'ordre des colonnes:
489580399980411391898701 7 69940057140058770271243 0.0222322287958 3.4645966025e-06 12.7344201901 0.0 876773648620972672266057 3 292257882873657557422019 0.0222305008733 3.4645966025e-06 12.7344201901 0.0 997442969276261073587131 11 90676633570569188507921 0.022228773818 3.4645966025e-06 12.7344201901 0.0 958991205044005776613127 11617 82550676168030109031 0.0222272180857 3.4645966025e-06 12.7344201901 0.0 961958186090139713862109 1300112398093 739903863313 0.0224876796903 3.4645966025e-06 12.7344201901 0.0 703522462385485452529642 2 351761231192742726264821 0.0224859328124 3.4645966025e-06 12.7344201901 0.0 291321724040479551020151 3 97107241346826517006717 0.0224841861461 3.4645966025e-06 12.7344201901 0.0 330313979034090142894356 3 110104659678030047631452 0.022482439482 3.4645966025e-06 12.7344201901 0.0 937773643255662298898887 23 40772767098072273865169 0.0224806952128 3.4645966025e-06 12.7344201901 0.0 670433872417372699443272 8 83804234052171587430409 0.0224789493007 3.4645966025e-06 12.7344201901 0.0 821668200651088820674182 3 273889400217029606891394 0.0224772034206 3.4645966025e-06 12.7344201901 0.0 777310274531628758443373 271 2868303596057670695363 0.0224754648087 3.4645966025e-06 12.7344201901 0.0 903232910941487885036437 246238121 3668127856374797 0.0224780981226 3.4645966025e-06 12.7344201901 0.0 887417153093754350276758 2 443708576546877175138379 0.0224763529844 3.4645966025e-06 12.7344201901 0.0 110077084496369002984039 313 351683976026738028703 0.0224746105986 3.4645966025e-06 12.7344201901 0.0
On constate que le temps moyen d'exécution est très bon (env. 2.2/100 sec.). C'est normal: dans la grande majorité des cas, le nombre tiré au hasard a des petits facteurs.
On constate aussi une très grande différence entre le temps mini 3.5 10-6 sec. et le temps maxi = 12.7 sec ! Il est clair que le temps maxi correspond à une décomposition dans laquelle les 2 facteurs sont de taille semblable (par exemple: 961958186090139713862109 = 1300112398093 * 739903863313). Mais il est possible que l'algorithme lui-même réagisse différemment à certains nombres (non analysé)
Maintenant, je ne veux pas seulement une décomposition en 2 facteurs, mais je veux la décomposition complète en facteurs premiers.
Exemple:
949283752047438225793061 = [313L, 467L, 1471573L, 4413193994467L]
Il va donc falloir que j'ajoute une fonction d'entrée qui fera appel à la fonction de décomposition autant qu'il le faudra jusqu'à n'obtenir que des facteurs premiers.
Il va falloir aussi que j'ajoute une décomposition par division, parce que je sais maintenant que l'algorithme de Pollard Rho échoue de temps en temps. C'est rare (1/1000), mais ça existe.
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 (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.
############################################################################## def lrac(x): """Racine carrée entière d'un nb entier x (méth. de Héron d'Alexandrie)""" r1 = 1 while True: r2 = (r1+x//r1)//2 if abs(r1-r2) < 2: if r1*r1 <= x and (r1+1)*(r1+1) > x: return r1 r1 = r2 ############################################################################## def pgcd(a,b): """Calcul du 'Plus Grand Commun Diviseur' de a et b entiers (Euclide)""" while b: a, b = b, a%b return a ############################################################################## def facteursdiv2(n): """Décomposition par division de n (entier) en 2 facteurs quelconques""" pp = [2, 3, 5, 7, 11] racn = lrac(n)+1 # lrac(n) = racine carrée entière de n for p in pp: if p>racn: return [n, 1] # n est premier if n%p == 0: return [p, n//p] # on a trouvé une décomposition p = pp[-1] + 2 while p <= racn: if n%p == 0: return [p, n//p] # on a trouvé une décomposition p += 2 # si on arrive ici, n est premier return [n, 1] ############################################################################# def pollardrho(n): """Factorisation d'un nombre entier décomposable (méth. rho de pollard)""" f = lambda z: z*z+1 x, y, d = 2, 2, 1 while d==1: x = f(x) % n y = f(f(y)) % n d = pgcd(x-y, n) return [d, n//d] ############################################################################## def factpremiers(n): """liste des facteurs premiers de n, avec la fonction 'a, b = decomp(n)' """ R = [] # liste des facteurs premiers trouvés P = [n] # pile de calcul while P!=[]: x = P.pop(-1) # lecture et dépilage de la dernière valeur empilée if estpremier(x): R.append(x) # on a trouvé un facteur 1er => on ajoute à la liste else: a, b = pollardrho(x) # on calcule une nouvelle décomposition if a==1 or b==1: # echec: x n'est pas 1er mais sa decomposition ne se fait pas # on essaie une décomposition par division a, b = facteursdiv2(x) P.append(a) # on empile a P.append(b) # on empile b R.sort() return R
Et voilà des exemples d'application avec des nombres quelconques tirés au hasard (y compris premiers) de 24 chiffres:
n = randint(100000000000000000000000, 999999999999999999999999)
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]
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 .
Amusez-vous bien!