Ci-dessous, les différences entre deux révisions de la page.
Les deux révisions précédentes Révision précédente | Dernière révision Les deux révisions suivantes | ||
factorisation_fermat [2009/01/12 12:23] tyrtamos |
factorisation_fermat [2009/01/12 13:19] tyrtamos |
||
---|---|---|---|
Ligne 15: | Ligne 15: | ||
* [[http:// | * [[http:// | ||
- | L' | + | 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 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' | ||
+ | |||
+ | 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:// | ||
+ | |||
+ | Voilà le code: | ||
+ | |||
+ | <code python> | ||
+ | def congcarres(n): | ||
+ | if n&1==0: | ||
+ | return [n>> | ||
+ | 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, | ||
+ | else: | ||
+ | k += 1 | ||
+ | </ | ||
+ | |||
+ | Ce code fonctionne (il trouve les facteurs), mais il est plus lent que l' | ||
\\ | \\ |