Factorisation de Fermat

La factorisation de Fermat est une méthode de factorisation d'un entier naturel $ N $ impair et composé (non premier). Elle repose sur l'identité algébrique de la différence de deux carrés : $$ N = a^2 - b^2 = (a + b)(a - b) $$

L'objectif est de trouver deux entiers $ a $ et $ b $ tels que $ a^2 - N $ soit un carré parfait $ b $.

Lorsque c'est le cas, cette écriture fournit immédiatement deux facteurs non triviaux de $ N $, à savoir $ c = (a+b) $ et $ d = (a-b) $

La factorisation de Fermat est particulièrement efficace lorsque $ N $ possède deux facteurs $ c $ et $ d $ proches l'un de l'autre, c'est-à-dire lorsque $ c \pm \epsilon_1 \approx d \pm \epsilon_2 \approx \sqrt{N} $.

Dans ce cas, la différence $ a^2 - N $ devient rapidement un carré parfait.

En revanche, lorsque $ N $ est premier ou lorsque ses facteurs sont très éloignés de $ \sqrt{N} $, la méthode devient peu performante et nettement moins efficace que d'autres algorithmes de factorisation.

L'algorithme de factorisation de Fermat applique les étapes suivantes :

1 - Initialiser $ A $ à la plus petite valeur entière telle que $ A \ge \sqrt{N} $

2 - Calculer $ B^2 = A^2 - N $

3 - Tester si $ B^2 $ est un carré parfait

4 - Si oui, alors $ N = (A+B)(A-B) $ et terminer. Sinon, incrémenter $ A $ de 1 et répéter le calcul à l'étape 2

La complexité de la factorisation de Fermat dépend de l'écart entre les facteurs de $ N $.

— Cas favorable : si $ N = c \times d $ avec $ c \approx d \approx \sqrt{N} $, le nombre d'itérations est faible, souvent proportionnel à $ |d - c| $.

— Pire cas : si $ N $ est premier, l'algorithme doit tester tous les entier jusqu'à $ \sqrt{N} $, rendant la méthode impraticable pour les grands nombres.

Voici un code source et une implémentation Python :

// Pseudo code

function fermat_factorization(N) {

if N is even {

return (2, N / 2)

}

A ← ceil(sqrt(N))

while true {

B2 ← A^2 - N

if B2 is a perfect square {

B ← sqrt(B2)

return (A - B, A + B)

}

A ← A + 1

}

}



// Python

import math

def fermat_factorization(N):

A = math.isqrt(N)

while True:

B2 = A * A - N

B = math.isqrt(B2)

if B * B == B2:

return (A - B, A + B)

A += 1