Crible algébrique | EPFL Graph Search

Ê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 GraphSearch.

Découvrez-en plus sur les applications Graph.

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 .

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

Publications associées (13)

Personnes associées (6)

Unités associées (1)

Concepts associés (19)

Cours associés (3)

Séances de cours associées (17)

This paper reports on the number field sieve computation of a 768-bit prime field discrete logarithm, describes the different parameter optimizations and resulting algorithmic changes compared to the

Springer International Publishing Ag2017

The RSA cryptosystem introduced in 1977 by Ron Rivest, Adi Shamir and Len Adleman is the most commonly deployed public-key cryptosystem. Elliptic curve cryptography (ECC) introduced in the mid 80's by

EPFL2015

, , ,

We show how the cofactorization step, a compute-intensive part of the relation collection phase of the number field sieve (NFS), can be farmed out to a graphics processing unit. Our implementation on

Springer-Verlag Berlin2014

Factorisation entière: Sieve Quadratic

Couvre la méthode Quadratic Sieve pour la factorisation entière, soulignant l'importance de choisir les bons paramètres pour la factorisation efficace.

Sieving de poudre de céramique atomisée avec 50 Micron Sieve

Explore le traitement des matériaux céramiques, le moulage par glissement, l'écoulement des poudres, le tamisage des poudres atomisées, la stabilité de la suspension et la mesure du volume de sédimentation.

Granulation de la suspension céramique par atomisation

Explore la granulation de la suspension céramique par l'atomisation et les processus connexes tels que le moulage par glissement et les mesures de densité.

L'algorithme du crible quadratique est un algorithme de factorisation fondé sur l'arithmétique modulaire. C'est en pratique le plus rapide après le crible général des corps de nombres, lequel est cependant bien plus compliqué, et n'est plus performant que pour factoriser un nombre entier d'au moins cent chiffres. Le crible quadratique est un algorithme de factorisation non spécialisé, c'est-à-dire que son temps d'exécution dépend uniquement de la taille de l'entier à factoriser, et non de propriétés particulières de celui-ci.

La notation L est un analogue aux notations de Landau en notation asymptotique. Cette notation a été introduite par Carl Pomerance en 1982 pour comparer différents algorithmes de factorisation et a été généralisée à deux paramètres par Arjen Lenstra et Hendrik Lenstra. Elle est principalement utilisée en théorie algorithmique des nombres, où elle permet de donner une échelle entre les différents algorithmes exponentiels.

The goal of the course is to introduce basic notions from public key cryptography (PKC) as well as basic number-theoretic methods and algorithms for cryptanalysis of protocols and schemes based on PKC

This course introduces the basics of cryptography. We review several types of cryptographic primitives, when it is safe to use them and how to select the appropriate security parameters. We detail how