Calculateur de Factorisation de Fermat

À propos de ce calculateur

La méthode de factorisation de Fermat exploite le fait que tout entier impair N peut s'écrire comme une différence de deux carrés, N = a² − b² = (a−b)(a+b). L'algorithme part de a = ⌈√N⌉ et augmente a de 1 à chaque étape, en vérifiant si a² − N est lui-même un carré parfait (b²) ; dès que c'est le cas, N se factorise immédiatement en (a−b)(a+b). Ce calculateur exécute cette boucle et montre chaque étape parcourue pour trouver les facteurs.

La méthode converge en très peu d'étapes lorsque les deux facteurs de N sont proches l'un de l'autre — sa principale faiblesse est aussi son usage réel le plus important : les étudiants en cryptographie et les chercheurs en sécurité utilisent la factorisation de Fermat pour montrer pourquoi les modules RSA doivent être construits à partir de nombres premiers éloignés l'un de l'autre, car des nombres premiers choisis trop proches rendent le module trivialement cassable. C'est aussi un exercice classique des cours de théorie des nombres pour illustrer le raisonnement par différence de carrés.