Outils pour utilisateurs

Outils du site


factorisation_fermat

Factorisation par l'algorithme de Fermat (congruence de carrés)

Généralités

Factoriser un nombre entier n, c'est trouver au moins 2 nombres n1 et n2 tels que n1*n2 = n.

Le fait de pouvoir factoriser rapidement un nombre n très grand est un enjeu important pour la cryptographie: si quelqu'un y arrive, c'est toute la sécurité des cryptages de type RSA (clé publique / clé privée) qui est remise en cause!

On va parler ici de la méthode de Fermat, non pas qu'elle soit particulièrement performante, mais parce qu'elle est à la base de nombreuses méthodes très efficaces: on a intérêt à bien la comprendre pour aborder les suivantes!

Références (il y en a beaucoup d'autres):

Voilà le principe (voir les liens pour la théorie!):

Soit n à factoriser.

si on trouve 2 nombres x et y tels que (x*x - y*y) % n = 0, alors, comme (x*x-y*y) ⇒ (x+y)*(x-y), on a les 2 facteurs (x+y) et (x-y)!

On part de x = valeur supérieure de (racine de n)

On calcule y2 = x*x-n, puis sa racine carré y, et on teste si y2 pourrait être un carré parfait (y*y=y2).

Si oui, alors on a trouvé, et on retourne les 2 facteurs [x+y, x-y]

Si non, on essaye avec x = x+1

Dans le code, on élimine dès le départ 2 cas particuliers:

  • si n est pair, on renvoie la solution évidente [n//2, 2]
  • si n est un carré parfait, on renvoie la solution évidente [racine de n, racine de n]

Codage proposé

En application simple de la théorie, voilà le code proposé:

def fermat(n):
    if n&1==0:
        return [n>>1, 2]  # si n est pair, retourner la solution
    x = lsqrt(n)
    if x*x==n:
        return [x, x]  # si n est déjà un carré parfait, retourner la solution
    x += 1  # car on veut la valeur entière immédiatement supérieure à la racine carrée réelle
    while True:
        y2 = x*x-n
        y = lsqrt(y2)
        if y*y==y2:
            break  # si y2 est un carré parfait, on a trouvé un "bon" y qui va avec le x
        else:
            x += 1
    return [x-y, x+y]

On utilise ici la fonction lsqrt(x) qui calcule la racine carrée entière d'un nombre entier sans utiliser les flottants. Elle est décrite sur une autre page de ce site: http://python.jpvweb.com/mesrecettespython/racine_entiere.

Ce code retourne la liste des 2 facteurs trouvés. Si l'un des facteurs est 1, c'est que le nombre n était premier.

Utilisation et performances

Test de validité

J'ai fait tourner cette fonction des milliers de fois avec le code d'essai suivant:

while True:
    n = random.randint(100,1000)
 
    r1, r2 = fermat(n)
 
    r = r1*r2
    print n, r1, r2, r
    if r!=n:
        print "erreur"
        break
    if (r1==1 or r2==1) and not estpremier(r):
        print "solution triviale"
        break

Ce code utilise la fonction estpremier(x) décrite sur une autre page de ce site (http://python.jpvweb.com/mesrecettespython/est_premier) et qui renvoie True si le nombre est premier et False dans le cas contraire. Si le nombre est un entier très très grand, utilisez la méthode probabiliste de Miller-Rabin décrite sur la même page.

Test de performance

Puisqu'on est censé factoriser des entiers long composés d'entiers “premiers” eux-mêmes longs, testons avec le code suivant:

c = 0
t = 0
while True:
    c += 1
    n1 = genpremier(16)
    n2 = genpremier(16)
    n = n1*n2
 
    tps = time.clock()
    r1, r2 = fermat(n)
    t += time.clock()-tps
 
    r = r1*r2
    print n, r1, r2, r, tps/c
    if r!=n:
        print "erreur"
        break
    if (r1==1 or r2==1) and not estpremier(r):
        print "solution triviale"
        break

Ce code utilise un générateur de nombres premiers très simple:

def genpremier(nbits):
    while True:
        n = random.randint(2, 2**nbits-1)
        if estpremier(n):
            return n

Résultat: avec des produits de facteurs premiers de 16 bits, l'algorithme de Fermat trouve la décomposition en 15/100 seconde, ce qui n'est pas mal du tout!

Par exemple:

    n      n1    n2     n1*n2    temps de calcul
196350179 6763 29033 196350179 0.155932540904
1377352127 28789 47843 1377352127 0.155931107849
344349001 12227 28163 344349001 0.155924267883
523660211 19763 26497 523660211 0.155918367746
756900317 12853 58889 756900317 0.155909863646
1447054303 24923 58061 1447054303 0.155924434771
1418822893 33377 42509 1418822893 0.155924342057
816783713 24317 33589 816783713 0.155916571915

Mais, bien sûr, quand on augmente la taille des facteurs, la durée de calcul augmente rapidement.

Avec des nombres composés de facteurs premiers de 24 bits, ces facteurs sont trouvés en environ 2 minutes:

      n           n1      n2       n1*n2       temps de calcul
13916806570859 2851873 4879883 13916806570859 139.859221204
128861865840923 8556629 15059887 128861865840923 126.113548375
38634249620851 2843803 13585417 38634249620851 119.341574648
45192514318207 4356479 10373633 45192514318207 132.969813929
23881384824917 1919041 12444437 23881384824917 128.729607645

Au delà, ça se gâte un peu (et même beaucoup…).

Factorisation par congruence de carré simplifié

Pour mémoire, citons un codage de même principe que Fermat, mais avec une simplification.

Au lieu de chercher 2 nombres x et y tels que (x*x-y*y) % n =0, on va partir du fait que y=1.

On aura donc (x*x-1)%n=0. Donc, x*x = k*n+1, k étant un facteur entier de proportionnalité (k=1, 2, 3, …).

On va donc appliquer l'algorithme de Fermat modifié par ce choix. Mais si ça ne marche pas avec x = racine carrée de (k*n+1) avec k=1, il faudra essayer avec k = k+1.

Par ailleurs, les solutions ne seront plus (x+1) et (x-1), mais pgcd(x+1, n) et pgcd(x-1, n). La fonction permettant de calculer le PGCD sont à cette autre page du site: http://python.jpvweb.com/mesrecettespython/pgcd_ppcm.

Voilà le code:

def congcarres(n):
    if n&1==0:
        return [n>>1, 2]
    x = lsqrt(n)
    if x*x==n:
        return [x, x]
    k = 1
    while True:
        x2 = k*n+1
        x = lsqrt(x2)
        if x*x == x2:
            return [pgcd(x+1,n), pgcd(x-1,n)]
        else:
            k += 1

Ce code fonctionne (il trouve les facteurs), mais il est plus lent que l'algorithme de Fermat, et donc il n'est cité ici que pour la curiosité.


Amusez-vous bien!

factorisation_fermat.txt · Dernière modification: 2010/10/28 15:02 de tyrtamos

Outils de la page