Algorithmes de factorisation
Le crible quadratique et le crible du corps de nombres sont deux des algorithmes de factorisation d'entiers les plus employés. Ils reposent sur l'idée suivante, due à l'arithméticien français Pierre de Fermat : si on trouve deux entiers $x$ et $y,$ non égaux, non opposés, tels que $x^2\equiv y^2\ [n]$ alors $(x-y)(x+y)\equiv 0\ [n]$, et $\textrm{pgcd}(x+y,n)$ ou $\textrm{pgcd}(x-y,n)$ donne un diviseur non trivial de $n.$
Il reste à trouver de tels nombres $x$ et $y.$ Considérons $x$ un entier juste supérieur à $\sqrt n$. Alors $x^2$ est juste supérieur à $n,$ et $x^2\equiv a\ [n]$ avec $a$ petit. Il est donc facile de factoriser $a,$ et avec un peu de chances, en essayant plusieurs $x,$ on peut espérer trouver un $a$ tel que $a=y^2.$ Et alors c'est fini!
Exemple : Soit à factoriser $n=3337.$ Sa racine carrée vaut un peu plus que $57$. On teste :
- $58^2\equiv 27=3^3\ [3337]$ : ne convient pas.
- $59^2\equiv 144=12^2\ [3337]$ : convient!
Alors, $\textrm{pgcd}(59+12,3337)=71$ donne un diviseur non trivial de $n.$ Le second facteur premier est $49.$
Bien sûr, dans le cas général, en prenant des $x$ juste plus grands que $\sqrt n$, il n'est pas sûr que l'on tombe dans le cas précédent. Mais on peut combiner plusieurs équations : si $x_1^2\equiv a_1\ [n]$, $x_2^2\equiv a_2\ [n],\dots$ $x_p^2 \equiv a_p\ [n],$ et si $a_1\cdots a_p\equiv y^2\ [n]$, en posant $x=x_1\cdots x_p,$ on retrouve $x^2\equiv y^2\ [n].$
Exemple : Soit à factoriser $n=180121,$ dont la racine carrée vaut un peu plus que $424.$ En faisant des essais successifs avec les entiers juste supérieurs à $424,$ on trouve :
- $425^2\equiv 2^3\cdot 3^2\times 7 [n]$
- $439^2\equiv 2^3\cdot 3^2\cdot 5^2\times 7\ [n]$
d'où $(425\times 439)^2\equiv(2^3\times 3^2\times 5\times 7)^2\ [n],$ et $\textrm{pgcd}(n,425×439-2^33^25 7)=281$ donne un diviseur non trivial de $n.$