Outils pour utilisateurs

Outils du site


factorisation_fermat

Ceci est une ancienne révision du document !


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 [n2, 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é: <code python> 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] </code> 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: <code python> 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®: print “solution triviale” break </code> 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: <code python> 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®: print “solution triviale” break </code> Ce code utilise un générateur de nombres premiers très simple: <code python> def genpremier(nbits): while True: n = random.randint(2, 2**nbits-1) if estpremier(n): return n </code> 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: <code> 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 </code> 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: <code> 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 </code> 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: <code python> 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 </code> 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! <html> <head> <style type=“text/css”> <!– body {background-image:url(fondcorps.jpg);} –> </style> </head> <body> </body> </html>
factorisation_fermat.1231762798.txt.gz · Dernière modification: 2009/01/12 13:19 par tyrtamos

Outils de la page