Crible algébrique

En théorie des nombres, l'algorithme du crible du corps de nombres généralisé (GNFS) obtient la décomposition d'un entier en produit de facteurs premiers. C'est à l'heure actuelle (2018) le plus efficace algorithme connu pour obtenir cette décomposition, lorsque le nombre considéré est assez grand, c'est-à-dire au-delà d'environ 10¹⁰⁰, et ne possède pas de structure remarquable. Cette efficacité est due pour partie à l'utilisation d'une méthode de crible et pour partie à l'utilisation d'algorithmes efficaces pour certaines opérations (comme la manipulation de matrices creuses). La complexité algorithmique du crible de corps de nombres n'est pas prouvée, elle n'est qu'heuristique. Cette estimation est utilisée par les organismes de standardisation tels que le NIST pour fixer des tailles des clés RSA à un niveau de sécurité donné.

De manière remarquable, l'algorithme permet également (au prix de modifications simples) de calculer des logarithmes discrets dans les corps finis, avec la même complexité. C'est à l'heure actuelle (2018) l'algorithme le plus efficace connu dans les corps finis de caractéristique première très grande. En revanche, l'algorithme du crible du corps de nombres n'est pas applicable au calcul du logarithme discret dans un groupe abstrait générique, ce qui est une des motivations derrières la cryptographie sur les courbes elliptiques.

Pour ces raisons, l'algorithme est responsable aujourd'hui de nombreux records de factorisation (et de calculs de logarithmes discret) et joue un rôle important en cryptographie. Enfin, quoique de manière plus anecdotique, il intervient également dans le contexte plus large de la sécurité informatique, par exemple dans l'attaque Logjam dont il est un composant essentiel : les auteurs ont montré comment intercepter une communication TLS 1.2, une des étapes consistant à calculer au moyen du crible du corps de nombres un logarithme discret dans un corps de 512 bits en moins d'une minute.

Histoire

L'algorithme du crible du corps de nombres est une des techniques de factorisation développées progressivement au cours du 20^e siècle.

Il fut proposé initialement dans une lettre de John Pollard à Arjen Lenstra et Andrew Odlyzko datée de 1988, comme une amélioration possible du crible quadratique. L'ayant testé sur le septième nombre de Fermat (factorisé pour la première fois en 1970), l'algorithme est étendu puis publié par Lenstra, Lenstra, Manasse et Pollard en 1990 dans une version « restreinte » à certains types d'entiers. Cette première version était tout de même suffisante pour factoriser pour la première fois le neuvième nombre de Fermat avec les ressources disponibles à l'époque. Des travaux successifs et les contributions de Joe Buhler et Carl Pomerance ont permis d'étendre l'algorithme à des entiers arbitraires. L'algorithme du crible du corps de nombres généralisé a atteint sa forme actuelle au courant des années 1990, sous l'impulsion entres autres de Peter Montgomery, mais il a continué à bénéficier depuis de l'amélioration des capacités de calcul des ordinateurs, et de la disponibilité accrue du calcul distribué.

L'algorithme fut simultanément adapté pour calculer des logarithmes discrets, où il reste aujourd'hui l'algorithme le plus efficace connu pour résoudre ce problème sur les corps finis de grande caractéristique. En petite caractéristique, plusieurs optimisations sont possibles, comme l'algorithme du crible de corps de fonctions (function field sieve) développé initialement par Adleman en 1994.

En 1995, Peter Shor présente un algorithme quantique dont la complexité asymptotique est très inférieure à celle du crible du corps de nombres, basé sur une approche radicalement différente ; toutefois un tel algorithme nécessite un calculateur quantique suffisamment grand pour fonctionner, ce qu'à l'heure actuelle (2018) on ne sait pas construire.

Principe d'opération

Principe général

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

• 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) sont souvent employés.

Phase de collecte

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

Principe du crible

Le crible du corps de nombres s'appuie sur la remarque suivante. Soit $f$un polynôme unitaire, à coefficients entiers, irréductible sur $\mathbb {Z}$. Notons $\alpha$une racine complexe de $f$. Supposons qu'il existe $m$tel que $f(m)=0{\bmod {n}}$, alors il existe un morphisme d'anneaux $\phi :\mathbb {Z} [\alpha ]\to \mathbb {Z} /(n)$défini par $\phi :\alpha \mapsto m$. En particulier, pour tout polynôme $g$à coefficients entiers, on a $\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 ${\mathcal {S}}$de polynômes tels que$$\prod _{g\in {\mathcal {S}}}g(\alpha )$$est un carré dans $\mathbb {Z} [\alpha ]$, notons-le $\beta ^{2}$, et que

$$\prod _{g\in {\mathcal {S}}}g(m)$$est un carré dans $\mathbb {Z} /(n)$, notons-le $y^{2}$. Alors on a trouvé une relation :

$$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 ${\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 $\mathbb {Z} [\alpha ]$. Avant de détailler cet aspect, donnons une manière de construire les polynômes $f$ et $g$intervenant dans l'équation.

Polynômes f et g

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

$$n=c_{d}m^{d}+c_{d-1}m^{d-1}+\cdots +c_{0}$$et on définit

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

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

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

Friabilité sur $\mathbb {Z} [\alpha ]$

Si $\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 $\beta$. Malheureusement, ce n'est en général pas le cas. Ceci dit, on dispose de l'application norme $N:\mathbb {Q} (\alpha )\to \mathbb {Q}$qui est multiplicative et dont les valeurs sur $\mathbb {Z} [\alpha ]$sont entières. En particulier, si $\prod _{(a,b)\in {\mathcal {S}}}(a-b\alpha )$est un carré dans $\mathbb {Z} [\alpha ]$, alors $\prod _{(a,b)\in {\mathcal {S}}}N(a-b\alpha )$est un carré dans $\mathbb {Z}$, 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 $u$de $\mathbb {Z} [\alpha ]$est « friable » lorsque $N(u)$est friable. La phase de collecte consiste donc à chercher des couples $(a,b)$tels que $g(\alpha )=a-b\alpha \in \mathbb {Z} [\alpha ]$est friable en ce sens.

Phase d'algèbre linéaire

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 $u=p_{1}^{e_{1}}p_{2}^{e_{2}}\cdots p_{k}^{e_{k}}$où ${\mathcal {P}}=\{p_{1},\cdots ,p_{k}\}=\{p~{\textrm {premier}},p<B\}$, par le vecteur de ses exposants : $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 $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.

Complexité de l'algorithme

L'analyse de la complexité de l'algorithme repose notamment sur l'estimation de la distribution des nombres friables. Ce problème a été étudié par de Bruijn, et Canfield-Erdös-Pomerance, qui montrent le résultat suivant :

« Un entier positif choisi au hasard plus petit que $L_{x}[r,\psi ]$est $L_{x}[s,\beta ]$-friable avec probabilité $L_{x}\left[r-s,-{\frac {\psi (r-s)}{\beta }}\right]$lorsque $x\to \infty$. »

Dans l'énoncé ci-dessus on utilise la notation L (introduite par Pomerance en 1982), et on note dans la suite $\pi (B)$le nombre d'entiers positifs premiers inférieurs à $B$. Une analyse globale donne alors une complexité :

$$\underbrace {\left(\pi (L_{n}[s,\beta ])+\omega \right)} _{\mathrm {nombre~de~relations~a~collecter} }\cdot \underbrace {L_{n}[r-s,\psi (r-s)/\beta ]} _{\mathrm {inverse~de~proba~de~friabilite} }\cdot \underbrace {S\left(L_{n}[r,\psi ],L_{n}[s,\beta ]\right)} _{\mathrm {cout~verification~friabilite} }+\underbrace {M\left(\pi (L_{n}[s,\beta ])\right)} _{\mathrm {cout~algebre~lineaire} }$$

L'utilisation des meilleurs algorithmes d'algèbre linéaire et l'amortissement du coût de $S$grâce au crible permettent, en optimisant tous les paramètres, d'estimer la probabilité totale de l'algorithme à $L_{n}\left[{\frac {1}{3}},{\sqrt[{3}]{\frac {64}{9}}}\right]$. Il est possible d'abaisser encore cette complexité au moins en principe en utilisant deux techniques dues à Coppersmith, mais les gains réels de ces modifications ne sont pas encore bien mesurés.

Adaptation au calcul de logarithme discret

De même que la méthode de Dixon, le crible du corps de nombres s'adapte bien au calcul de logarithmes discrets. En particulier, il s'agit du plus efficace algorithme classique connu pour résoudre ce problème dans les corps finis, où le crible du corps de nombres s'apparente à une forme de « calcul d'indice » .

Records obtenus au moyen de cet algorithme

Le crible du corps de nombres est derrière de nombreux records récents de factorisation et de calculs de logarithmes discrets.

Factorisation de nombres de forme générale

• 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.

Factorisation de nombres de forme particulière

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

Logarithmes discrets dans un corps de grande caractéristique

• 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.

• 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.
• 18 juin 2005, Antoine Joux et Reynald Lercier, logarithme discret modulo un premier sûr de 431 bits.

Voir aussi

• Crible du corps de fonctions
• Crible quadratique
• Crible linéaire
• Algorithme de Dixon
• Factorisation par courbes elliptiques