Outils pour utilisateurs

Outils du site


factorisation_fermat

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_fermat [2009/01/12 12:23]
tyrtamos
factorisation_fermat [2010/10/28 15:02]
tyrtamos
Ligne 15: Ligne 15:
   * [[http://​mathworld.wolfram.com/​FermatsFactorizationMethod.html]]   * [[http://​mathworld.wolfram.com/​FermatsFactorizationMethod.html]]
  
-L'​algorithme étant simple: ​voir les liens pour la théorie!+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é ===== ===== Codage proposé =====
Ligne 133: Ligne 151:
  
 Au delà, ça se gâte un peu (et même beaucoup...). 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é.
  
 \\ \\
factorisation_fermat.txt · Dernière modification: 2010/10/28 15:02 par tyrtamos