méthode de factorisation d'Euler

La méthode de factorisation d'Euler est une technique de factorisation d'un nombre, du nom de Leonhard Euler, en l'écrivant comme une somme de deux carrés de deux manières différentes. Par exemple, le nombre 1 000 009 peut s'écrire 10002 + 32 ou 9722 + 2352 et la méthode de factorisation d'Euler donne 1 000 009 = 293 × 3413. L'idée que deux représentations distinctes d'un entier naturel impair peut conduire à une factorisation aurait été proposée par Marin Mersenne. Cependant, elle n'avait pas été exploitée, jusqu'à Euler, cent ans plus tard. L'utilisation la plus célèbre de la méthode, qui porte maintenant son nom, était de factoriser le nombre 1 000 009, qui était auparavant supposé premier. La méthode de factorisation d'Euler est plus efficace que celle de Fermat pour les entiers dont les facteurs ne sont pas proches, si l'on peut trouver raisonnablement facilement des représentations de nombres sous la forme de deux carrés. Le développement d'Euler a finalement permis une factorisation beaucoup plus efficace des nombres et, vers les années 1910, le développement de grandes tables allant jusqu'à environ dix millions[réf. nécessaire]. Les méthodes utilisées pour trouver des représentations de nombres sous la forme de sommes de deux carrés sont essentiellement les mêmes que pour trouver des différences de carrés dans la méthode de factorisation de Fermat. L'inconvénient de la méthode de factorisation d'Euler est qu'elle ne peut pas être appliquée à la factorisation d'un nombre entier n avec un facteur premier de la forme 4k + 3 à une puissance impaire dans la décomposition en facteurs premiers de n, car un tel nombre premier n'est jamais somme de deux carrés. (Voir le théorème des deux carrés de Fermat). Des nombres impairs de la forme 4k + 1 sont souvent le produit de deux nombres premiers de la forme 4k + 3 (par exemple 3053 = 43 × 71) et donc ne peuvent pas être factorisés par la méthode d'Euler.