Crible algébrique

À l'instar du crible quadratique dont il est une amélioration, l'algorithme du crible du corps de nombres fonctionne en deux phases principales[Note 7] - [11] :

• Une phase de collecte, hautement parallélisable, pendant laquelle l'algorithme recherche des nombres friables modulo l'entier n à factoriser. C'est au cours de cette étape que la technique de crible est utilisée, s'appuyant sur les propriétés des corps de nombres pour sélectionner efficacement des candidats. Les nombres retenus à l'issue de cette première phase se décomposent tous en produits de puissances d'une base de facteurs (en général premiers). L'efficacité du crible du corps de nombres est surtout due à cette technique de crible, qui permet de trouver des nombres friables plus rapidement que d'autres approches telles que le crible quadratique.
• Une phase d'algèbre linéaire, difficilement parallélisable, au cours de laquelle l'algorithme construit un élément du noyau d'une grande matrice creuse. Les lignes de cette matrice correspondent aux puissances (modulo 2) de chaque facteur de la base apparaissant dans les nombres collectés dans la phase précédente. Le vecteur du noyau ainsi obtenu permet de déterminer une congruence de carrés, qui donne immédiatement une factorisation de n.

Cette seconde phase n'est pas spécifique au crible du corps de nombres, mais nécessite des algorithmes capables de manipuler des matrices de grande taille. L'algorithme de Lanczos par blocs ou celui de Wiedemann (dû à Coppersmith[12] - [13]) sont souvent employés.

On note ${\displaystyle n}$ l'entier positif que l'on cherche à factoriser, et on suppose que ${\displaystyle n}$ n'est pas la puissance d'un nombre premier (cette précaution n'est pas un renoncement : dans le cas contraire où ${\displaystyle n=p^{k}}$ il est aisé de factoriser en calculant des racines).

Le crible du corps de nombres s'appuie sur la remarque suivante. Soit ${\displaystyle f}$ un polynôme unitaire, à coefficients entiers, irréductible sur ${\displaystyle \mathbb {Z} }$. Notons ${\displaystyle \alpha }$ une racine complexe de ${\displaystyle f}$. Supposons qu'il existe ${\displaystyle m}$ tel que ${\displaystyle f(m)=0{\bmod {n}}}$, alors il existe un morphisme d'anneaux ${\displaystyle \phi$ :\mathbb {Z} [\alpha ]\to \mathbb {Z} /(n)} défini par ${\displaystyle \phi$ :\alpha \mapsto m} . En particulier, pour tout polynôme ${\displaystyle g}$ à coefficients entiers, on a ${\displaystyle \phi (g(\alpha ))=g(m){\bmod {n}}}$. Voici comment cette remarque participe à la recherche de congruences de carrés : si on a trouvé une collection ${\displaystyle {\mathcal {S}}}$ de polynômes tels que

$${\displaystyle \prod _{g\in {\mathcal {S}}}g(\alpha )}$$

est un carré dans ${\displaystyle \mathbb {Z} [\alpha ]}$, notons-le ${\displaystyle \beta ^{2}}$, et que

$${\displaystyle \prod _{g\in {\mathcal {S}}}g(m)}$$

est un carré dans ${\displaystyle \mathbb {Z} /(n)}$, notons-le ${\displaystyle y^{2}}$. Alors on a trouvé une relation :

$${\displaystyle x^{2}=\phi (\beta )^{2}=\phi (\beta ^{2})=\phi \left(\prod _{g\in {\mathcal {S}}}g(\alpha )\right)=\prod _{g\in {\mathcal {S}}}g(m)=y^{2}{\bmod {n}}}$$

Pour trouver ${\displaystyle {\mathcal {S}}}$, on va à l'instar du crible quadratique ou de la méthode de Dixon, chercher des nombres friables. Seulement, pour cela, il faut d'abord définir une notion de friabilité sur ${\displaystyle \mathbb {Z} [\alpha ]}$. Avant de détailler cet aspect, donnons une manière de construire les polynômes ${\displaystyle f}$ et ${\displaystyle g}$ intervenant dans l'équation.

Pour construire le polynôme ${\displaystyle f}$ de la section précédente, on peut utiliser ceci : prenons ${\displaystyle d}$ un entier tel que ${\displaystyle n>2^{d^{2}}}$ et posons ${\displaystyle m=\lfloor n^{1/d}\rfloor }$. En écrivant l'entier ${\displaystyle n}$en base ${\displaystyle m}$, on obtient

$${\displaystyle n=c_{d}m^{d}+c_{d-1}m^{d-1}+\cdots +c_{0}}$$

et on définit

$${\displaystyle f(t)=c_{d}t^{d}+c_{d-1}t^{d-1}+\cdots +c_{0}}$$

On vérifie aisément que ${\displaystyle f}$ est unitaire, et que ${\displaystyle f(m)=n}$ par construction, donc ${\displaystyle f(m)=0{\bmod {n}}}$. Si ${\displaystyle f}$ n'est pas irréductible, on peut le décomposer en facteurs irréductibles de manière efficace[Note 8].

Pour construire les polynômes ${\displaystyle g}$, posons de manière heuristique ${\displaystyle g(t)=a-bt}$ pour ${\displaystyle a,b}$ deux entiers premiers entre eux avec ${\displaystyle 0<b,|a|<B}$.

Si ${\displaystyle \mathbb {Z} [\alpha ]}$ était un anneau factoriel, on pourrait simplement décomposer ses éléments en facteurs premiers et chercher les entiers friables de l'anneau pour trouver ${\displaystyle \beta }$. Malheureusement, ce n'est en général pas le cas. Cela dit, on dispose de l'application norme ${\displaystyle N:\mathbb {Q} (\alpha )\to \mathbb {Q} }$ qui est multiplicative et dont les valeurs sur ${\displaystyle \mathbb {Z} [\alpha ]}$ sont entières[Note 9]. En particulier, si ${\displaystyle \prod _{(a,b)\in {\mathcal {S}}}(a-b\alpha )}$est un carré dans ${\displaystyle \mathbb {Z} [\alpha ]}$, alors ${\displaystyle \prod _{(a,b)\in {\mathcal {S}}}N(a-b\alpha )}$ est un carré dans ${\displaystyle \mathbb {Z} }$[Note 10], et plus généralement un élément qui se décompose en de nombreux facteurs aura une norme qui se décompose elle-même en de nombreux facteurs.

On dira qu'un élément ${\displaystyle u}$ de ${\displaystyle \mathbb {Z} [\alpha ]}$ est « friable » lorsque ${\displaystyle N(u)}$ est friable. La phase de collecte consiste donc à chercher des couples ${\displaystyle (a,b)}$ tels que ${\displaystyle g(\alpha )=a-b\alpha \in \mathbb {Z} [\alpha ]}$ est friable en ce sens.

La phase d'algèbre linéaire consiste, une fois que l'on dispose de suffisamment de relations entre nombres friables, à construire une congruence de carrés. Pour cela, on représente un nombre friable sur la base de friabilité, c'est-à-dire ${\displaystyle u=p_{1}^{e_{1}}p_{2}^{e_{2}}\cdots p_{k}^{e_{k}}}$où ${\displaystyle {\mathcal {P}}=\{p_{1},\cdots ,p_{k}\}=\{p~{\textrm {premier}},p<B\}}$, par le vecteur de ses exposants : ${\displaystyle v(u)={\begin{pmatrix}e_{1}&e_{2}&\cdots &e_{k}\end{pmatrix}}}$. Ensemble, tous les nombres collectés forment une matrice, dont on cherche un élément du noyau modulo 2, c'est-à-dire une combinaison linéaire des lignes telle que le vecteur obtenu ait des coefficients pairs.

Cette combinaison linéaire d'exposants correspond à un produit entre les nombres collectés : d'un côté, il s'agit de carrés (donc leur produit est encore un carré modulo ${\displaystyle n}$), et de l'autre, il s'agit de nombres dont le produit a des exposants pairs dans la base de friabilité, c'est-à-dire encore des carrés. On a bien une congruence de carrés.

• 2 Décembre 2019, Fabrice Boudot, Pierrick Gaudry, Aurore Guillevic, Nadia Heninger, Emmanuel Thomé, et Paul Zimmermann, factorisation du nombre RSA RSA-240, d'une taille de 795 bits[20].

• 6 janvier 2010, Thorsten Kleinjung, Kazumaro Aoki, Jens Franke, Arjen Lenstra, Emmanuel Thomé, Joppe Bos, Pierrick Gaudry, Alexander Kruppa, Peter Montgomery, Dag Arne Osvik, Herman te Riele, Andrey Timofeev et Paul Zimmermann, factorisation du nombre RSA RSA-768, d'une taille de 768 bits[21].

• 4 août 2012, Greg Childers, factorisation du nombre de Mersenne 2¹⁰⁶¹ − 1 d'une taille de 1061 bits[22].

• 2 Décembre 2019, Fabrice Boudot, Pierrick Gaudry, Aurore Guillevic, Nadia Heninger, Emmanuel Thomé, et Paul Zimmermann, logarithme discret modulo un premier sûr de 795 bits[20].

• 16 juin 2016, Thorsten Kleinjung, Claus Diem, Arjen K. Lenstra, Christine Priplata et Colin Stahlke, logarithme discret modulo un premier sûr de 768 bits[23].

• 11 juin 2014, Cyril Bouvier, Pierrick Gaudry, Laurent Imbert, Hamza Jeljeli et Emmanuel Thomé, logarithme discret modulo un premier sûr de 596 bits.
• 5 février 2007, Thorsten Kleinjung, logarithme discret modulo un premier sûr de 530 bits[24].
• 18 juin 2005, Antoine Joux et Reynald Lercier, logarithme discret modulo un premier sûr de 431 bits.