IMB > Recherche > Séminaires

Séminaire de Théorie Algorithmique des Nombres

Responsables : Xavier Caruso et Aurel Page

Page du séminaire

  • Le 28 janvier 2020 à 10:00
  • Salle 385
    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éepossè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 The beauty of the Klein quartic ;

    $\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.


  • Le 4 février 2020 à 10:00
  • Salle 385
    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 courbesou 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 pourle 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(max(deg(C)^(2 omega), deg(D+)^omega)) où omega > 2,38 estla constante de l’algèbre linéaire et D+ le plus petit diviseur effectif vérifiant D+ >= D. Cet algorithme probabiliste peut échouer mais sous quelques conditions,on prouve que sa probabilité d’échec est bornée par O(max(deg(C)^4, deg(D+)^2)/|E|) où E est un sous ensemble fini de k dans lequel on peut choisir des élémentsde k uniformément aléatoirement.

    A 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 lecontexte 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 etarithmé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 semblentindiquer 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 certainesinstances sur de grands corps finis).


  • Le 11 février 2020 à 10:00
  • Salle 385
    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 arithmeticlibrary designed using the Why3 program verifier. It is intended as averified replacement for the mpn layer of the state-of-the-art GNUMulti-Precision library (GMP).

    The formal verification is done using a mix of automated provers anduser-provided proof annotations. We have verified the GMP algorithmsfor addition, subtraction, multiplication (schoolbook and Toom-2/2.5),schoolbook division, divide-and-conquer square root and modularexponentiation. The rest of the mpn API is work in progress. Themain challenge is to preserve and verify all the GMP algorithmic tricksin order to get good performance.

    Our algorithms are implemented as WhyML functions. We use a dedicatedmemory model to write them in an imperative style very close to the Clanguage. Such functions can then be extracted straightforwardly toefficient C code. For medium-sized integers (less than 1000 bits, or100,000 for multiplication), the resulting library isperformance-competitive with the generic, pure-C configuration of GMP.


  • Le 18 février 2020 à 10:00
  • Salle 385
    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.

    Afficher 2016 - 2015 - antérieurs