En théorie des nombres, l'algorithme du crible du corps de nombres généraliséAussi connu sous son nom anglais, generalised number field sieve, ou son acronyme : GNFS.Parfois appelé de manière moins précise « crible algébrique » ou « crible sur les corps de nombres », plus rarement « crible de corps de nombres ». (GNFS) obtient la décomposition d'un entier en produit de facteurs premiers. C'est à l'heure actuelle (2018) l'algorithme le plus efficace connu pour obtenir cette décomposition, lorsque le nombre considéré est assez grandIl existe un algorithme quantique asymptotiquement strictement plus efficace : l'algorithme de Shor. Cependant il n'est pas possible à l'heure actuelle d'exécuter cet algorithme pour de grands nombres., c'est-à-dire au-delà d'environ 10100, et ne possède pas de structure remarquableLorsqu'on s'intéresse à des nombres de forme particulière, comme les nombres de Fermat ou de Mersenne, une version spécialisée de l'algorithme est plus efficace.. 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'heuristiqueElle s'appuie notamment sur des hypothèses de répartition uniforme qui sont étayées par l'expérience mais pour lesquelles il n'y a pas de justification théorique.. 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 grandeIl existe des algorithmes plus efficaces pour les corps finis de petite caractéristique, en particulier les corps binaires , tels que le crible du corps de fonctions.. 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ère 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 discrets) 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 .
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 entre 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 principalesComme indiqué par (Lenstra 2017), ce découpage en deux phases a été identifié par Morrison et Brillhart dès 1975. :
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 l'entier positif que l'on cherche à factoriser, et on suppose que n'est pas la puissance d'un nombre premier (cette précaution n'est pas un renoncement : dans le cas contraire où 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 un polynôme unitaire, à coefficients entiers, irréductible sur . Notons une racine complexe de . Supposons qu'il existe tel que , alors il existe un morphisme d'anneaux défini par . En particulier, pour tout polynôme à coefficients entiers, on a . Voici comment cette remarque participe à la recherche de congruences de carrés : si on a trouvé une collection de polynômes tels que est un carré dans , notons-le , et que
est un carré dans , notons-le . Alors on a trouvé une relation :
Pour trouver , 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 . Avant de détailler cet aspect, donnons une manière de construire les polynômes et intervenant dans l'équation.
Polynômes f et g Pour construire le polynôme de la section précédente, on peut utiliser ceci : prenons un entier tel que et posons . En écrivant l'entier en base , on obtient
et on définit
On vérifie aisément que est unitaire, et que par construction, donc . Si n'est pas irréductible, on peut le décomposer en facteurs irréductibles de manière efficaceSi la factorisation de n'est pas triviale on obtient directement une factorisation de ..
Pour construire les polynômes , posons de manière heuristique pour deux entiers premiers entre eux avec .
Friabilité sur ℤ[α] Si é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 . Malheureusement, ce n'est en général pas le cas. Cela dit, on dispose de l'application norme qui est multiplicative et dont les valeurs sur sont entièresDans le détail, si on note les conjugués complexes de , alors
ce qui montre que la norme de est un polynôme en à coefficients entiers.. En particulier, si est un carré dans , alors est un carré dans La réciproque n'est en général pas vraie : par exemple on a dans , donc est un carré, alors que n'en est pas un., 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 de est « friable » lorsque est friable. La phase de collecte consiste donc à chercher des couples tels que 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 où , par le vecteur de ses exposants : . 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 ), 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 est -friable avec probabilité lorsque . »
Dans l'énoncé ci-dessus on utilise la notation L (introduite par Pomerance en 1982), et on note dans la suite le nombre d'entiers positifs premiers inférieurs à . Une analyse globale donne alors une complexitéVoir (Lenstra 2017, Section 5.2.3). :
L'utilisation des meilleurs algorithmes d'algèbre linéaire et l'amortissement du coût de grâce au crible permettent, en optimisant tous les paramètres, d'estimer la probabilité totale de l'algorithme à Voir (Lenstra 2017, Section 5.5.3).. 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ésVoir (Lenstra 2017, Section 5.5.4)..
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
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 bitsEmmanuel Thomé, “795-bit factoring and discrete logarithms,” December 2, 2019..