Méthode de factorisation de Fermat

L'intuition est la suivante. Tout entier naturel impair N se décompose en la différence de deux carrés : N = a² – b². 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 ${\displaystyle 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 combinaison des deux méthodes est plus efficace qu'uniquement l'une ou l'autre.

On essaie différentes valeurs de a, en espérant que a² – N soit un carré b². 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 ← partie entière supérieure(√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 – √(Bsq) // ou A + √(Bsq)

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 × N, cela signifie que N est un nombre premier.

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'itérations est approximativement ${\displaystyle {\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 fait O(N) ité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 (4N)^1/4 de √N, la méthode ne fait qu'une seule itération. Cette analyse est indépendante de la grandeur de N.

Par exemple, pour factoriser N = 5959 (√N ≈ 77,19), on calcule :

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