Description
Cet exposé constitue un survol de méthodes récentes permettant de construire des tables de corps de nombres ainsi qu'une énumération asymptotique des corps de nombres ordonnés par leur discriminant. Les méthodes traditionnelles pour effectuer cela reposent sur la géométrie des nombres, pour l'essentiel sur un théorème dû à Hunter, complété par un résultat de Martinet pour traiter les extensions non primitives. De telles méthodes sont impraticables même pour les petits degrés, et déja pour le degré $ 3$ elles ne donnent pas un ordre de grandeur correct pour les corps de nombres.<br/> Différentes méthodes bien plus efficaces sont apparues dans les dernières années. Selon le cas, ces méthodes permettent de construire des tables de corps de nombres étendues, de construire des corps de nombres de grand degré ayant des propriétés particulières par exemple un discriminant particulièrement petit ou bien de compter exactement ou bien de manière asymptotique les corps de nombres ordonnés par la donnée de leur discriminant. La plupart de ces méthodes sont fondées sur des théories assez classiques mais dont l'aspect algorithmique ainsi que l'implantation n'ont été étudiées que récemment. La première de ces méthodes est fondée sur la théorie de Kummer et/ou la théorie du corps de classe (qui sont deux théories intimement liées de toute manière). Bien que principalement une théorie des extensions abéliennes, elle peut être utilisée pour des extension non abéliennes (mais résolubles), comme pour le groupe diédral ou pour les groupes $ A_4$ et $ S_4$. Cette méthode à été développée extensivement par l'auteur avec F. Diaz y Diaz et M. Olivier et les résultats ont été ou seront publiés dans une série de 18 articles.<br/> Pour ce qui est de la construction de tables, nous avons fait des tables extensives de corps octiques non primitifs contenant un sous-corps de degré $ 4$ (ceux contenant un sous-corps quadratique ayant été traité par C. Fieker), et nous avons calculé des corps de nombres totalement complexes de degré jusqu'à 80 ayant un petit discriminant, c'est-à-dire très près (souvent moins de 1%) de la borne donnée par GRH selon Odlyzko-Stark. Dans presque tous les cas, nous avons pu trouver une équation polynomiale explicite pour ces gros corps de nombres en utilisant de nouveaux outils algorithmiques développés en théorie de Kummer et en théorie du corps de classe. Pour ce qui est du comptage des discriminants, depuis le travail de S. Mäki, la situation est complètement explicite pour les groupes abéliens quand le corps de base est $ \mathbb{Q}$. Le travail de D. Wright donne en principe une réponse explicite (toujours dans le cas abélien) pour un corps de base arbitraire, mais dans la pratique, le calcul de l'une des constantes se revèle difficile. Dans le cas non abélien, peu de choses sont connues.<br/> Pour le cas abélien, notre principale contribution a été de donner une formule complètement explicite pour le cas des groupes cycliques d'ordre premier $ C_l$, et pour le groupe $ C_4$ et $ V_4=C_2 \times C_2$. Bien qu'utilisant des outils standards de la théorie algébrique des nombres, chacun des calculs nécessite du travail et un nombre de lemmes intermédiaires conséquent.<br/> Dans le cas non abélien, nous avons complètement résolu le problème du groupe diédral $ D_4$, à la fois en donnant des formules asymptotiques (pour un corps de base arbitraire), et en donnant des formules exactes sur $ \mathbb{Q}$ qui nous ont permis de compter exactement de tels corps de nombres jusqu'au discriminant $ 10^{17}$, avec ou sans condition de signature.<br/> Nous avons des résultats similaires sur $ \mathbb{Q}$ pour les groupes $ A_4$ et $ S_4$, qui nous ont permis de compter les corps de nombres $ A_4$ jusqu'au discriminant $ 10^{16}$ et $ S_4$ jusqu'à $ 10^7$. En particulier, nous avons fait une table complète des corps de nombres quartiques jusqu'au discriminant $ 10^7$ en valeur absolue (il serait facile d'aller plus loin mais nous avons été limité par la taille des disques). Malheureusement, contrairement aux autres cas, ces résultats exacts ne nous permettent pas de déduire des résultats asymptotiques, bien que le cas de $ A_4$ ne soit pas désespéré.<br/> Le deuxième genre de méthode très efficace pour effectuer les tâches décrites au début est fondé sur la théorie des espaces vectoriels préhomogènes, introduite par T. Shintani, dont une version simplifiée, applicable essentiellement seulement à $ \mathbb{Q}$ est la théorie des formes de degrés supérieurs. Le premier succès de ces méthodes a été la remarquable théorie de Davenport-Heilbronn qui permet une énumération asymptotique des extensions $ S_3$ sur $ \mathbb{Q}$ en comptant des formes cubiques binaires convenables. Plus récemment, cette théorie a été utilisée par K. Belabas pour compter exactement de tels corps de nombres.<br/> L'observation essentielle de Shintani, utilisée plus tard par Darskovsky-Wright pour étendre les résultats de Davenport-Heibronn à un corps de base arbitraire est que c'est une instance simple d'espace vectoriel préhomogène : la dimension de l'espace des formes cubiques primitives est égale à $ 3$, le même nombre de paramètres que le groupe $ SL_2(\mathbb{Z})$ qui agit naturellement sur lui. L'année dernière, des avancées ont été faites dans le cas bien plus difficile de $ S_4$. M. Bhargava a montré qu'il était possible d'obtenir une énumération asymptotique des extensions $ S_4$ de $ \mathbb{Q}$ en comptant des paires de formes quadratiques ternaires convenables. Il est clair que la même méthode donne un algorithme pour compter exactement de tels corps de nombres.<br/> Cela correspond aussi à un espace vectoriel préhomogène : la dimension de l'espace des paires primitives de formes quadratiques ternaires est égal à $ 11$, le même que le nombre de paramètres du groupe $ SL_3(\mathbb{Z}) \times SL_2(\mathbb{Z})$ qui agit naturellement dessus. Ainsi, des méthodes de type Shintani peuvent être utilisées, et A. Yuki a presque achevé une généralisation du travail de Datskovsky-Wright.
Prochains exposés
-
Présentations des nouveaux doctorants Capsule
Orateur : Alisée Lafontaine et Mathias Boucher - INRIA Rennes
2 nouveaux doctorants arrivent dans l'équipe Capsule et présenteront leurs thématiques de recherche. Alisée Lafontaine, encadrée par André Schrottenloher, présentera son stage de M2: "Quantum rebound attacks on double-block length hash functions" Mathias Boucher, encadré par Yixin Shen, parlera de "quantum lattice sieving" -
Design of fast AES-based Universal Hash Functions and MACs
Orateur : Augustin Bariant - ANSSI
Ultra-fast AES round-based software cryptographic authentication/encryption primitives have recently seen important developments, fuelled by the authenticated encryption competition CAESAR and the prospect of future high-profile applications such as post-5G telecommunication technology security standards. In particular, Universal Hash Functions (UHF) are crucial primitives used as core components[…]-
Cryptography
-
-
Lie algebras and the security of cryptosystems based on classical varieties in disguise
Orateur : Mingjie Chen - KU Leuven
In 2006, de Graaf et al. proposed a strategy based on Lie algebras for finding a linear transformation in the projective linear group that connects two linearly equivalent projective varieties defined over the rational numbers. Their method succeeds for several families of “classical” varieties, such as Veronese varieties, which are known to have large automorphism groups. In this talk, we[…]-
Cryptography
-
-
Some applications of linear programming to Dilithium
Orateur : Paco AZEVEDO OLIVEIRA - Thales & UVSQ
Dilithium is a signature algorithm, considered post-quantum, and recently standardized under the name ML-DSA by NIST. Due to its security and performance, it is recommended in most use cases. During this presentation, I will outline the main ideas behind two studies, conducted in collaboration with Andersson Calle-Vierra, Benoît Cogliati, and Louis Goubin, which provide a better understanding of[…] -
Wagner’s Algorithm Provably Runs in Subexponential Time for SIS^∞
Orateur : Johanna Loyer - Inria Saclay
At CRYPTO 2015, Kirchner and Fouque claimed that a carefully tuned variant of the Blum-Kalai-Wasserman (BKW) algorithm (JACM 2003) should solve the Learning with Errors problem (LWE) in slightly subexponential time for modulus q = poly(n) and narrow error distribution, when given enough LWE samples. Taking a modular view, one may regard BKW as a combination of Wagner’s algorithm (CRYPTO 2002), run[…]-
Cryptography
-
-
CryptoVerif: a computationally-sound security protocol verifier
Orateur : Bruno Blanchet - Inria
CryptoVerif is a security protocol verifier sound in the computational model of cryptography. It produces proofs by sequences of games, like those done manually by cryptographers. It has an automatic proof strategy and can also be guided by the user. It provides a generic method for specifying security assumptions on many cryptographic primitives, and can prove secrecy, authentication, and[…]-
Cryptography
-