Outils pour utilisateurs

Outils du site


factorisation_pollardrho

Factorisation par l'algorithme de Pollard rho

Objectif

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.

Code de base

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.

Test sur des nombres composés de 2 facteurs premiers

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:

  • que la décomposition est rapide: 2/10000 sec. en moyenne pour des nombres de 7 chiffres à décomposer,
  • qu'une décomposition “non triviale” (=différente de [n, 1]) est obtenue dans plus de 99% des cas (taux d'échec < 9/1000),
  • qu'aucune décomposition erronée (x1*x2 différent de n) n'est obtenue.

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

Test sur 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:

  • n = le nombre à décomposer
  • x1 et x2 = la décomposition trouvée
  • le temps moyen d'exécution de chaque décomposition
  • le temps mini
  • le temps maxi
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é)

Décomposition d'un nombre quelconque en facteurs premiers

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 :-D.

Amusez-vous bien!

factorisation_pollardrho.txt · Dernière modification: 2009/11/21 19:29 de tyrtamos

Outils de la page