Méthode de factorisation de Fermat

En arithmétique modulaire, la méthode de factorisation de Fermat est un algorithme de décomposition en produit de facteurs premiers d'un entier naturel.

Intuition

L'intuition est la suivante. Tout entier naturel impair $N$ se décompose en la différence de deux carrés : $N = a 2 - b 2$ . Algébriquement, cette différence se factorise en $(a + b)(a - b)$ et, si ni $a + b$ ni $a - b$ n'est égal à 1, alors ce sont des facteurs non triviaux de $N$ .

Il existe une telle représentation pour tout nombre impair composé. Si $N = cd$ est une factorisation de $N$ , alors $N=\left({\frac {c+d}{2}}\right)^{2}-\left({\frac {c-d}{2}}\right)^{2}.$ Puisque $N$ est impair, $c$ et $d$ le sont aussi et ces « moitiés » sont des nombres entiers. Notons qu'un multiple de 4 donne aussi une différence de deux carrés, en posant $c$ et $d$ comme nombres pairs.

Dans sa forme la plus simple, la méthode de factorisation de Fermat peut être plus lente que la factorisation par essais de divisions. Néanmoins, la combinaisons des deux méthodes est plus efficace qu'uniquement l'une ou l'autre.

Méthode de base

On essaie différentes valeurs de $a$ , en espérant que $a 2 - N$ soit un carré $b 2$ . On peut utiliser qu'un carré ne peut se terminer que par 0, 1, 4, 5, 6 ou 9 dans le système décimal.

FactorFermat(N): // N doit être impair

A ← arrondi(sqrt(N))

Bsq ← A*A – N

tant que Bsq n'est pas un carré:

A ← A + 1

Bsq ← A*A – N // ou de façon équivalente : Bsq ← Bsq + 2*A + 1

fin tant que

retourner A – sqrt(Bsq) // ou A + sqrt(Bsq)

Analyse

Soit $N$ un entier possédant plus d'une factorisation ( $N$ possède plus de deux facteurs). La méthode de Fermat donne la factorisation de $N$ avec les plus petites valeurs de $a$ et de $b$ , c'est-à-dire que $a + b$ est le plus petit facteur supérieur à la racine carrée de $N$ . Donc, $a - b = N /(a + b)$ est le plus grand facteur n'excédant pas la racine carrée de $N$ . Si la méthode produit $N = 1 \times N$ , cela signifie que $N$ est un nombre premier.

Complexité

Pour $N = cd$ , soit $c$ le plus grand facteur plus petit que la racine carrée de $N$ et soit $a = (c + d)/2$ . Alors, le nombre d'opérations est approximativement ${\frac {c+d}{2}}-{\sqrt {N}}={\frac {({\sqrt {d}}-{\sqrt {c}})^{2}}{2}}={\frac {({\sqrt {N}}-c)^{2}}{2c}}.$

Si $N$ est premier (donc $c = 1$ ), l'algorithme prend O(N) opérations. C'est donc une façon très inefficace de démontrer la primalité d'un nombre. Par contre, si $N$ a un facteur suffisamment près de sa racine carrée, alors la méthode de Fermat est très efficace. Plus précisément, si $c$ diffère de moins que $(4 N) 1/4$ de $\sqrt N$ , la méthode ne prend qu'une seule opération. Cette analyse est indépendante de la grandeur de $N$ .

Exemple

Par exemple, pour factoriser $N = 5959$ ( $\sqrt N \approx 77,19$ ), on calcule :

A	78	79	80
Bsq	125	282	441

Le troisième essai produit un carré : $A = 80, B = 21$ et les facteurs sont $A - B = 59$ et $A + B = 101$ .

Améliorations importantes

Les méthodes de factorisation du crible quadratique et du crible général de corps de nombres (GNFS) sont basées en grande partie sur la méthode de factorisation de Fermat.

Méthode de factorisation de Lehman

La méthode de Fermat fonctionne optimalement lorsqu'un des facteurs est approximativement la racine carrée de $N$ . La question qui s'ensuit est : peut-on s'arranger pour que ce soit le cas ?

Si on connaît approximativement le quotient de deux facteurs, $d / c$ , alors on peut choisir un nombre rationnel, $v / u$ , proche de ce quotient. Posons $Nuv = cv \times du$ , donc les facteurs sont à peu près égaux : la méthode de Fermat appliquée à $Nuv$ les trouvera rapidement. Puis, on obtient $pgcd (N, cv) = c$ et $pgcd(N, du) = d$ (sauf si $c$ divise $u$ ou $d$ divise $v$ ).

En général, le quotient n'est pas connu, mais on peut essayer différentes valeurs de $u / v$ et essayer de factoriser chaque $Nuv$ résultant. Une méthode systématique est donnée par Russell Sherman Lehman[1]. Sa complexité calculatoire est de $O (N 1/3+ ε)$ , laquelle est avantageuse par rapport à celle pour la méthode des divisions successives, dont la complexité est en $O (N 1/2+ ε)$ .

Notes et références

(en) Cet article est partiellement ou en totalité issu de l’article de Wikipédia en anglais intitulé « Fermat's factorization method » (voir la liste des auteurs).

(en) R. Sherman Lehman, « Factoring Large Integers », Math. Comp., vol. 28, n^o 126,‎ avril 1974, p. 637-646 (lire en ligne).

Voir aussi

Articles connexes

Lien externe

(en) Eric W. Weisstein, « Fermat's Factorization Method », sur MathWorld

Portail de l’informatique
Portail de l'informatique théorique
Arithmétique et théorie des nombres

Cet article est issu de Wikipedia. Le texte est sous licence Creative Commons - Attribution - Partage dans les Mêmes. Des conditions supplémentaires peuvent s'appliquer aux fichiers multimédias.

[1] (en) R. Sherman Lehman, « Factoring Large Integers », Math. Comp., vol. 28, n^o 126,‎ avril 1974, p. 637-646 (lire en ligne).