Outils pour utilisateurs
factorisation_fermat
Warning: Undefined array key -1 in /home/clients/a4e6fc1ce1761b72982b805de0f418c4/web/python/mesrecettespython/inc/html.php on line 1458
Différences
Ci-dessous, les différences entre deux révisions de la page.
| 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:16] tyrtamos |
factorisation_fermat [2010/10/28 15:02] 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 24: | Ligne 42: | ||
| def fermat(n): | def fermat(n): | ||
| if n&1==0: | if n&1==0: | ||
| - | return [n>> | + | return [n>> |
| x = lsqrt(n) | x = lsqrt(n) | ||
| if x*x==n: | if x*x==n: | ||
| - | return [x, x] | + | return [x, x] # si n est déjà un carré parfait, retourner la solution |
| - | x += 1 | + | x += 1 # car on veut la valeur entière immédiatement supérieure à la racine carrée réelle |
| while True: | while True: | ||
| y2 = x*x-n | y2 = x*x-n | ||
| y = lsqrt(y2) | y = lsqrt(y2) | ||
| if y*y==y2: | if y*y==y2: | ||
| - | break | + | break # si y2 est un carré parfait, on a trouvé un " |
| else: | else: | ||
| x += 1 | x += 1 | ||
| 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' | ||
| \\ | \\ | ||
factorisation_fermat.txt · Dernière modification: 2010/10/28 15:02 de tyrtamos
Outils de la page
Sauf mention contraire, le contenu de ce wiki est placé sous les termes de la licence suivante : CC Attribution-Noncommercial-Share Alike 4.0 International
