Êtes-vous un étudiant de l'EPFL à la recherche d'un projet de semestre?
Travaillez avec nous sur des projets en science des données et en visualisation, et déployez votre projet sous forme d'application sur Graph Search.
Concept
Crible algébrique
Résumé
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) l'algorithme le plus efficace connu pour obtenir cette décomposition, lorsque le nombre considéré est assez grand, c'est-à-dire au-delà d'environ 10100, 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è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.
L'algorithme du crible du corps de nombres est une des techniques de factorisation développées progressivement au cours du .
Source officielle
À propos de ce résultat
Cette page est générée automatiquement et peut contenir des informations qui ne sont pas correctes, complètes, à jour ou pertinentes par rapport à votre recherche. Il en va de même pour toutes les autres pages de ce site. Veillez à vérifier les informations auprès des sources officielles de l'EPFL.