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 1000² + 3² ou 972² + 235² 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 $4 k + 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 $4 k + 1$ sont souvent le produit de deux nombres premiers de la forme $4 k + 3$ (par exemple 3053 = 43 × 71) et donc ne peuvent pas être factorisés par la méthode d'Euler.

Bases théoriques

L'identité de Brahmagupta montre que le produit de deux sommes de deux carrés est une somme de deux carrés. La méthode d'Euler s'appuie sur cette identité : étant donné $n = a 2 + b 2 = c 2 + d 2$ , on peut exprimer $n$ comme produit de sommes de deux carrés.

On déduit premièrement que

a^{2}-c^{2}=d^{2}-b^{2}

et en factorisant des deux côtés

(a-c)(a+c)=(d-b)(d+b)

(1)

Soient $k = pgcd(a - c, d - b)$ et $h = pgcd(a + c, d + b)$ . Alors il existe des entiers $l, m, l', m'$ tels que :

$a-c=kl$ ,
$d-b=km$ ,
$\operatorname {pgcd} (l,m)=1$ ;
$a+c=hm'$ ,
$d+b=hl'$ ,
$\operatorname {pgcd} (l',m')=1$ .

En remplaçant cela dans l'équation (1), on obtient

klhm'=kmhl'

,

c'est-à-dire

lm'=l'm

.

En utilisant le fait que $(l, m)$ et $(l', m')$ sont des couples de nombres premiers entre eux, on trouve que

l=l'\ {\textrm {et}}\ m=m'

donc

a-c=kl,\,d-b=km,\,a+c=hm\ {\textrm {et}}\ d+b=hl

.

En appliquant l'identité de Brahmagupta, on obtient

\left(k^{2}+h^{2}\right)\left(l^{2}+m^{2}\right)=\left(kl-hm\right)^{2}+(km+hl)^{2}=\left((a-c)-(a+c)\right)^{2}+\left((d-b)+(d+b)\right)^{2}=(2c)^{2}+(2d)^{2}=4n

,

\left(k^{2}+h^{2}\right)\left(l^{2}+m^{2}\right)=(kl+hm)^{2}+(km-hl)^{2}=\left((a-c)+(a+c)\right)^{2}+\left((d-b)-(d+b)\right)^{2}=(2a)^{2}+(2b)^{2}=4n

.

On en déduit que les facteurs $k^{2}+h^{2}$ et $l^{2}+m^{2}$ sont tous deux pairs, ou bien que l'un des deux est divisible par 4. Dans le cas où ils sont tous les deux pairs, n se factorise de la façon suivante :

n=\left({\frac {k^{2}+h^{2}}{2}}\right)\left({\frac {l^{2}+m^{2}}{2}}\right)

.

Dans le cas où l'un des deux est divisible par 4 (supposons sans perte de généralité qu'il s'agisse de $k^{2}+h^{2}$ ), cela signifie que les deux carrés dont il est la somme sont eux-mêmes divisibles par 4. En effet, une somme de deux carrés ne peut être congrue à 0 modulo 4 que si ces deux carrés sont eux-mêmes congrus à 0 modulo 4, car un carré ne peut être congru qu'à 0 ou 1 modulo 4. On en déduit que k et h sont tous deux pairs. n se factorise donc de la façon suivante : $n=\left(\left({\frac {k}{2}}\right)^{2}+\left({\frac {h}{2}}\right)^{2}\right)(l^{2}+m^{2})$ .

Exemple

Puisque $1000009 = 1000 2 + 3 2 = 972 2 + 235 2$ ,

on déduit de la formule ci-dessus :

a = 1000	(A) a − c = 28	k = pgcd[A,C] = 4
b = 3	(B) a + c = 1972	h = pgcd[B,D] = 34
c = 972	(C) d − b = 232	l = 7
d = 235	(D) d + b = 238	m = 58

Ainsi,

{\begin{aligned}1000009&=\left[\left({\frac {4}{2}}\right)^{2}+\left({\frac {34}{2}}\right)^{2}\right]\left(7^{2}+58^{2}\right)\\&=\left(2^{2}+17^{2}\right)\left(7^{2}+58^{2}\right)\\&=(4+289)(49+3364)\\&=293\times 3413.\end{aligned}}

Article connexe

Méthode de factorisation de Fermat

Références

(en) Cet article est partiellement ou en totalité issu de l’article de Wikipédia en anglais intitulé « Euler's factorization method » (voir la liste des auteurs).
(en) Oystein Ore, Number Theory and Its History, New York, Dover, 1988, 370 p. (ISBN 978-0-486-65620-5 et 0-486-65620-9, lire en ligne), « Euler's Factorization Method », p. 59-64
(en) James McKee, « Turning Euler's Factoring Method into a Factoring Algorithm », Bull. London Math. Soc., vol. 4, n^o 28,‎ 1996, p. 351-355 (DOI 10.1112/blms/28.4.351, lire en ligne)

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

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.