2019/2020

• 2020-03-10
  Florent Jouve (IMB)
  Harmonie et disparités dans le théorème de Chebotarev

  Étant donné une extension galoisienne de corps de nombres L/K, le théorème de Chebotarev affirme l’équirépartition des éléments de Frobenius, relatifs aux idéaux premiers non ramifiés, dans les classes de conjugaison de Gal(L/K). On présentera une étude portant sur les variations du terme d’erreur dans le théorème de Chebotarev, lorsque L/K parcourt certaines familles d’extensions. On donnera une formule de transfert pour les fonctions classiques de décompte des nombres (ou idéaux) premiers permettant de ramener la situation à celle d’une extension des rationnels. On exposera enfin quelques conséquences à des problèmes de “type Linnik” et à l’analogue du phénomène de biais de Chebyshev dans les corps de nombres. L’exposé porte sur un travail commun avec D. Fiorilli.

• 2020-03-09
  Jean Kieffer (IMB)
  Codes géométriques
• 2020-02-18
  Alex Bartel (University of Glasgow)
  The ray class group of a "random" number field

  The Cohen–Lenstra–Martinet heuristics are a probabilistic model for the behaviour of class groups of number fields in natural families. In this talk, I will discuss a generalisation to ray class groups. About 5 years ago, Varma determined the average number of 3-torsion elements in the ray class group of K with respect to m, when m is a fixed rational modulus, and K runs through the family of imaginary quadratic or of real quadratic fields. Since then, Bhargava has been challenging the community to come up with a natural probabilistic model that would explain the numbers obtained by Varma, and to predict more general averages in more general families of number fields. As I will explain in my talk, there turns out to be a very simple-minded way of doing so, and also a much more conceptual one, and they both turn out to be equivalent. The more conceptual one involves an object that does not appear to have been treated in the literature before, but that is very natural: the Aralelov ray class group of a number field. This is joint work with Carlo Pagano.

• 2020-02-17
  Razvan Barbulescu (IMB)
  Equivalence entre le cryptosystem d'Alekhnovich et son problème sousjacent
  (in the Quantum study group)
• 2020-02-11
  Raphael Rieu-Helft (Université Paris-Sud)
  How to Get an Efficient yet Verified Arbitrary-Precision Integer Library

  We present a fully verified arbitrary-precision integer arithmetic library designed using the Why3 program verifier. It is intended as a verified replacement for the mpn layer of the state-of-the-art GNU Multi-Precision library (GMP).
  The formal verification is done using a mix of automated provers and user-provided proof annotations. We have verified the GMP algorithms for addition, subtraction, multiplication (schoolbook and Toom-2/2.5), schoolbook division, divide-and-conquer square root and modular exponentiation. The rest of the mpn API is work in progress. The main challenge is to preserve and verify all the GMP algorithmic tricks in order to get good performance.
  Our algorithms are implemented as WhyML functions. We use a dedicated memory model to write them in an imperative style very close to the C language. Such functions can then be extracted straightforwardly to efficient C code. For medium-sized integers (less than 1000 bits, or 100,000 for multiplication), the resulting library is performance-competitive with the generic, pure-C configuration of GMP.

• 2020-02-04
  Luca De Feo
  Verifiable Delayed Functions II
  (in the CIAO conference)
• 2020-02-04
  Benjamin Wesolowski (CNRS/IMB)
  Verifiable Delayed Functions I
  (in the CIAO conference)
• 2020-02-04
  Jean-Marc Couveignes (IMB)
  Paramétrisation de courbes par radicaux
  (in the CIAO conference)
• 2020-02-04
  Aude Le Gluher (LORIA)
  Une approche géométrique efficace pour le calcul d'espaces de Riemann-Roch : Algorithme et Complexité

  Le calcul effectif de bases d’espaces de Riemann-Roch intervient dans de nombreux domaines pratiques, notamment pour l’arithmétique dans les jacobiennes de courbes ou dans des codes correcteurs d’erreurs algébraico-géométriques. Nous proposons une variante probabiliste de l’algorithme de Brill et Noether décrit par Goppa pour le calcul d’une base de l’espace de Riemann-Roch $L(D)$ associé à un diviseur $D$ d’une courbe projective plane nodale $C$ sur un corps parfait $k$ suffisamment grand.
  On prouve que sa complexité (estimée par le nombre d’opérations arithmétiques dans le corps $k$ est en $O\big(\max\big(\deg(C)^{2\omega}, \deg(D^+)^{\omega}\big)\big)$ où $\omega > 2,38$ est la constante de l’algèbre linéaire et $D^+$ le plus petit diviseur effectif vérifiant $D^+ \geq D$. Cet algorithme probabiliste peut échouer mais sous quelques conditions, on prouve que sa probabilité d’échec est bornée par $O\big(\max\big(\deg(C)^4, \deg(D^+)^2\big)/|E|\big)$ où $E$ est un sous ensemble fini de $k$ dans lequel on peut choisir des éléments de $k$ uniformément aléatoirement.
  À notre connaissance cette borne sur la complexité est la meilleure obtenue jusqu’alors pour le calcul d’espaces de Riemann-Roch dans un cadre général. Dans le contexte du calcul de la loi de groupe dans la jacobienne d’une courbe lisse, notre borne améliore aussi la meilleure borne connue à ce jour, due à Khuri-Makdisi. Notre algorithme jouit également du fait que son efficacité repose sur deux blocs pour lesquels des algorithmes efficaces existent : algèbre linéaire et arithmétique des polynômes univariés. Nous avons implémenté cet algorithme en C++/NTL. Les résultats expérimentaux obtenus via cette implémentation semblent indiquer une amélioration des temps de calcul par rapport à l’implémentation dans le logiciel de calcul formel Magma (jusqu’à 200 fois plus rapide sur certaines instances sur de grands corps finis).

• 2020-02-04
  Aurel Page (Inria/IMB)
  Algèbres de quaternion
  (in the CIAO conference)
• 2020-02-03
  Cyril Bouvier
  Aspects arithmétiques de SIDH et CSIDH II
  (in the CIAO conference)
• 2020-02-03
  Laurent Imbert
  Aspects arithmétiques de SIDH et CSIDH I
  (in the CIAO conference)
• 2020-02-03
  Antonin Leroux
  Calcul rapide d'isogénies en genre 1
  (in the CIAO conference)
• 2020-02-03
  Benjamin Smith
  Graphe d'isogénies supersingulières et superspéciales en genre 2
  (in the CIAO conference)
• 2020-02-03
  Jean Kieffer (IMB)
  Calcul d'isogénies en genre 2
  (in the CIAO conference)
• 2020-02-03
  Damien Robert (Inria/IMB)
  Calcul d'isogénies sur des variétés abéliennes
  (in the CIAO conference)
• 2020-01-28
  Jacques Martinet (IMB)
  Réseaux, variétés abéliennes et courbes
  On expliquera d’abord comment la notion de variété abélienne complexe polarisée possède une version euclidienne dans laquelle on considère des triplets $(E,\Lambda,v)$ d’un espace euclidien $E$, d’un réseau $\Lambda$ de $E$ et d’un élément $v$ de $\mathrm{GL}(E)$ tel que $v^2=-\mathrm{Id}$ et $v(\Lambda)\subset\Lambda^*$.

  On s’intéressera à de telles données compatibles avec l’action d’un groupe $G\subset\mathrm{SO}(E)$, et l’on décrira plus précisément deux situations :

  $\bullet$ Action d’un groupe d’ordre 7 en dimension réelle $6$, une sorte d’appendice à l’article de Elkies paru dans The Eightfold Way (The beauty of Klein’s quartic curve), Cambridge University Press (1999); S. Levy ed.

  $\bullet$ Actions de groupes « pas trop petits » en dimension $4$ en relation avec les courbes de genre $2$.

  Dans tous les cas l’ingrédient important est le théorème de Torelli.

• 2020-01-27
  Xavier Caruso (IMB)
  Algorithme de Grover
  (in the Quantum study group)
• 2020-01-14
  Abdoulaye Maiga (IMB)
  Canonical Lift of Genus 2 Curves
  Let $\mathcal{A}/\mathbb{F}_q$ (with $q=p^n$) be an ordinary abelian variety, a classical result due to Lubin, Serre and Tate says that there exists a unique abelian variety $\tilde{\mathcal{A}}$ over $\mathbb{Z}_q$ such that the modulo $p$ reduction of $\tilde{\mathcal{A}}$ is $\mathcal{A}$ and $End(\tilde{\mathcal{A}})\cong End(\mathcal{A})$ as a ring. In 2000 T.Satoh introduced a point-counting algorithm on elliptic curves over $\mathbb{F}_q$ based on canonical lift. In fact the action of the lifted Verschiebung on the tangent space gives Frobenius eigenvalues and hence the characteristic polynomial of the ordinary elliptic curves over $\mathbb{F}_q$. We propose to extend the canonical lift algorithm introduced by T.Satoh to genus 2 curves over finite fields, using the modular polynomials in dimension 2. We first prove the Kronecker condition in dimension 2 case and then succeed to lift the endomorphism ring of $\mathcal{A}$ in dimension 2 case using a general lift algorithm of a $p$-torsion group of an ordinary abelian variety. These results provide an algorithm to compute the characteristic polynomial of a genus 2 curves in quasi-quadratic time complexity.
• 2019-12-17
  Xavier Caruso (IMB)
  Introduction à l'algorithmique quantique. Algorithme de factorisation de Shor
  (in the Quantum study group)
• 2019-12-10
  Développeurs LFANT (IMB)
  Hacking session
• 2019-11-26
  Alice Pellet-Mary (ÉNS de Lyon)
  An LLL Algorithm for Module Lattices
  A lattice is a discrete subgroup (i.e., $\mathbb Z$-module) of $\mathbb R^n$ (where $\mathbb Z$ and $\mathbb R$ are the sets of integers and real numbers). The LLL algorithm is a central algorithm to manipulate lattice bases. It takes as input a basis of a Euclidean lattice, and, within a polynomial number of operations, it outputs another basis of the same lattice but consisting of rather short vectors.

  On the cryptographic side, many algorithms based on lattices in fact use structured lattices, in order to improve the efficiency of the schemes. Most of the time, these structured lattices are $R$-modules of small dimension, where $R$ is the ring a integers of some number field. It is then tempting to try and adapt the LLL algorithm, which works over lattices (i.e., $\mathbb Z$-modules), to these $R$-modules.

  All the previous works trying to solve this question focused on rings of integers $R$ that were Euclidean, as the LLL algorithm over $\mathbb Z$ crucially rely on the Euclidean division. In this talk, I will describe the first LLL algorithm which works in any ring of integers $R$. This algorithm is heuristic and runs in quantum polynomial time if given access to an oracle solving the closest vector problem in a fixed lattice, depending only on the ring of integers R.

  This is a joint work with Changmin Lee, Damien Stehlé and Alexandre Wallet

• 2019-11-20
  Gilles Zemor (IMB)
  Cryptographie post-quantique à base de codes
  (in the Quantum study group)
• 2019-11-19
  Maria Dostert (EPFL)
  Exact Semidefinite Programming Bounds for Packing Problems
  Semidefinite Programming (SDP) is a powerful tool to obtain upper bounds for packing problems. For example, one can consider the kissing problem of the hemisphere in dimension 8 which asks for the maximal number of pairwise non-overlapping spheres which can simultaneously touch a central hemisphere in 8-dimensional Euclidean space. The E8 lattice gives a kissing configuration of 183 points. Moreover, using an SDP given by Bachoc and Vallentin one gets an upper bound of 182.99999999996523. Hence, the optimal value is 183. But how can we obtain the exact rational solution of the SDP based on the floating point results given by the SDP solver?

  In this talk, I will explain how we can determine the exact result of the SDP. Furthermore, we use these techniques to obtain exact results for the kissing problem of the hemisphere in dimension 8 as well as for other packing problems.

  Using the exact rational solution for the kissing problem of the hemisphere, we can prove that the optimal kissing configuration is unique up to isometry.

  This is a joint work with David de Laat and Philippe Moustrou.

• 2019-11-08
  Guilhem Castagnos (imb)
  HDR defense: Cryptographie basée sur les corps quadratiques: cryptanalyse, primitives et protocoles
• 2019-11-05
  Henri Cohen (imb)
  Apéry-Like recursions and modular forms
  Following Zagier and Beukers, we show that the sequences used by Apery in his proofs of the irrationality of zeta(2) and zeta(3) are special cases of more general sequences having surprisingly only integer values, and that many of these sequences can be parametrized by modular forms. Following Almkwist and Zudilin, we also explain that the degree three sequences used for zeta(3) and generalizations can be automatically obtained via a Clausen type hypergeometric identity from the degree two sequences used for zeta(2) and generalizations.
• 2019-10-29
  Développeurs LFANT (IMB)
  Hacking session
• 2019-10-22
  Développeurs LFANT (IMB)
  Hacking session
• 2019-10-15
  Gilles Zémor
  Cryptographie post-quantique à base de codes
  Nous nous proposons de faire un état de l’art et de discuter l’état actuel de la cryptologie basée sur les codes. Nous nous intéresserons à l’approche historique, le paradigme de McEliece, ainsi qu’à la méthodologie plus moderne, initiée par Alekhnovich, et inspirée de la cryptologie basée sur les réseaux suite aux travaux d’Ajtai et de Regev en particulier. Cette deuxième approche ne prétendait pas à l’origine déboucher sur des systèmes de chiffrement compétitifs, mais présentait l’avantage théorique d’avoir des preuves de sécurité bien identifiées et reconnues par la communauté de complexité algorithmique et de cryptologie théorique. Nous détaillerons les principes de ces preuves de sécurité qui ne sont pas accessibles de manière évidente dans la littérature. Nous montrerons également en quoi il y a aujourd’hui convergence des deux approches du chiffrement basé sur les codes.

  Nous parcourrons et ferons une synthèse des propositions actuelles à la compétition du NIST. Nous nous intéresserons également aux primitives de signature à base de codes, domaine sensiblement moins développé que le chiffrement.

• 2019-10-08
  Jared Asuncion (imb)
  Computing Hilbert class fields of quartic CM fields using Complex Multiplication
  The Hilbert class field $H_K(1)$ is the maximal unramified abelian extension of $K$. For imaginary quadratic number fields $K$, it can be generated using special values of certain analytic, modular functions. For quartic CM-fields $K$, the corresponding construction yields only a subfield of $H_K(1)$.

  Ray class fields are generalizations of Hilbert class fields. For a positive integer $m > 0$, the ray class field $H_K(m)$ is obtained by relaxing the ramification conditions for ideals of $\mathcal{O}_K$ dividing $m$.

  It turns out that there is a particular subfield $L(m)$ of $H_K(m)$ which can be generated using special values of higher-level modular functions and Stark’s conjectures. For some values of $m$, this $L(m)$ contains the Hilbert class field $H_K(1)$. Thus, we can compute the Hilbert class field as a subfield of $L(m)$. In this talk, we find an upper bound for such an integer $m$.

  If time permits, we will discuss how to compute the Hilbert class field as a subfield of this $L(m)$ when $m = 2$.

• 2019-10-01
  Damien Robert (imb)
  An overview of isogeny algorithms
  Let $A$ be an abelian variety and $K$ a finite subgroup. We will discuss several approaches to compute the isogeny $A \mapsto A/K$, starting from Vélu’s algorithm for elliptic curves, and then the isogeny theorem for theta functions, Couveignes and Ezome’s work on Jacobians of curves, and recent progress with David Lubicz.
• 2019-09-24
  Jean Kieffer (imb)
  Computing isogenies from modular equations in genus 2
  Given two elliptic curves such an isogeny of degree l exists between them, there is an algorithm, due to Elkies, that uses modular equations to compute this isogeny explicitly. It is an essential tool in the SEA point counting algorithm: using isogenies is superior to Schoof’s original idea of using endomorphisms. In this work, we present the analogue of Elkies’ algorithm for Jacobians of genus 2 curves, thus opening the way to using isogenies in higher genus point counting.
• 2019-09-17
  Fredrik Johansson (imb)
  Fungrim : The Mathematical Functions Grimoire
  Fungrim is a new, open source database of formulas and tables for mathematical functions. All formulas are represented in symbolic, computer-readable form and include explicit conditions for the variables.

  The immediate goal is to create a web-based special functions reference work that addresses some of the drawbacks of resources such as the NIST Digital Library of Mathematical Functions, the Wolfram Functions site, and Wikipedia. A potential longer-term ambition is to provide a software library for symbolic knowledge about special functions, usable by computer algebra systems and theorem proving software.

  This talk will discuss the motivation behind the project, design issues, and possible applications.

• 2019-09-10
  David Roe (MIT)
  The inverse Galois problem for p-adic fields
  We describe a method for counting the number of extensions of $\mathbb{Q}_p$ with a given Galois group $G$, founded upon the description of the absolute Galois group of $\mathbb{Q}_p$ due to Jannsen and Wingberg. Because this description is only known for odd $p$, our results do not apply to $\mathbb{Q}_2$. We report on the results of counting such extensions for $G$ of order up to $2000$ (except those divisible by 512), for $p = 3$, 5, 7, 11, 13. In particular, we highlight a relatively short list of minimal $G$ that do not arise as Galois groups. Motivated by this list, we prove two theorems about the inverse Galois problem for $\mathbb{Q}_p$: one giving a necessary condition for G to be realizable over $\mathbb{Q}_p$ and the other giving a sufficient condition.