2015/2016

• 2016-06-07
  Hugo Labrande (Loria et Université de Calgary)
  Computing Theta functions in quasi-linear time
  The genus g function Theta : $\mathbb{C}^g x \mathfrak{H}_g -> \mathbb{C}$ has numerous applications in mathematics, from number theory to non-linear differential equations; in particular, its connection with the Abel-Jacobi map on complex elliptic and hyperelliptic curves has important applications. A connection between some values of this function (the theta-constants) and the arithmetico-geometric mean of Gauss (and its generalization in genus $g$, the Borchardt mean) yields an algorithm to compute any $P$ digits of the theta-constants in roughly $\mathrm{log} P$ multiplication of $P$-bit numbers, which is quasi-optimal. We provide a generalization of this connection using general tau-duplication formulas; with some care, this allows us to devise an algorithm to compute $P$ digits of Theta in the same quasi-linear time in $P$. We also report on an implementation in genus 1 and 2, which beats the naive algorithm for precisions as low as a few thousand digits. This is joint work with Emmanuel Thomé.
• 2016-06-07
  Jared Asuncion (IMB)
  Tower decomposition of Hilbert class fields
• 2016-05-17
  Nicolas Mascot (University of Warwick)
  Certification de représentations galoisiennes modulaires / Certifying modular Galois representations
  Nous verrons comment les calculs de représentations galoisiennes présentés dans l’exposé précédent peuvent être certifiés, en s’appuyant sur la conjecture de modularité de Serre et des calculs explicites de cohomologie des groupes.

  We will show how the Galois representation computations presented in last week’s talk may be certified, thanks to Serre’s modularity conjecture and explicit group cohomology computations.

• 2016-05-10
  Nicolas Mascot (University of Warwick)
  Calcul de représentations galoisiennes modulaires / Computing modular Galois representations
  Nous verrons comment la représentation galoisienne modulo l associée à une forme modulaire classique peut être calculée efficacement, en l’isolant dans la torsion de la jacobienne d’une courbe modulaire. Ceci permet notamment de calculer les coefficients a(p) de la forme en temps polynomial en log p, ce qui en fait la méthode la plus efficace connue à ce jour.

  We will explain how the mod l Galois representation attached to a classical newform may be efficiently computed, by isolating it among the l-torsion of a modular jacobian. This yields a way of computing the coefficient a(p) of the form in time polynomial in log p, which makes it the most efficient methodknown as of today.

• 2016-04-05
  Benjamin Matschke (IMB)
  A database of rational elliptic curves with given bad reduction
  In this talk we present a database of rational elliptic curves with good reduction outside certain finite sets of primes, including the set {2, 3, 5, 7, 11}, and all sets whose product is at most 1000.

  In fact this is a biproduct of a larger project, in which we construct practical algorithms to solve S-unit, Mordell, cubic Thue, cubic Thue–Mahler, as well as generalized Ramanujan–Nagell equations, and to compute S-integral points on rational elliptic curves with given Mordell–Weil basis. Our algorithms rely on new height bounds, which we obtained using the method of Faltings (Arakelov, Parshin, Szpiro) combined with the Shimura–Taniyama conjecture (without relying on linear forms in logarithms), as well as several improved and new sieves. In addition we used the resulting data to motivate several conjectures and questions, such as Baker’s explicit abc-conjecture, and a new conjecture on the number of S-integral points of rational elliptic curves.

  This is joint work with Rafael von Känel.

• 2016-03-22
  Alexandre Le Meur (Université de Rennes)
  Formules de Thomae généralisées aux cas des extensions galoisiennes résolubles de $\mathbb{P}^1$.
  D’un point de vue classique, les formules de Thomae relient des rapports de puissances de theta constantes avec les coordonnées affines des points de ramification d’une courbe hyperelliptique. A partir des années 80, plusieurs auteurs, ayant des préoccupations centrés sur la physique, ont montré des généralisations de ces formules au cas des courbes superelliptiques. Plus récemment, Shau Zemel et Hershel Farkas ont écrit un livre en utilisant des arguments essentiellement algébriques. D’un point de vue arithmétique, ces courbes correspondent à des extensions galoisiennes cycliques d’un corps de fonctions $k(x)$. Nous montrerons comment généraliser ces formules au cas des extensions résolubles de $k(x)$ et quelles obstructions peuvent survenir.
• 2016-03-15
  Bill Allombert (imb)
  Survey on computing isogeny between elliptic curves.
  We present methods to compute isogenies between elliptic curves, and we apply them to the computation of the isogenies matrix of an elliptic curve defined over the rational and to the Schoof Elkies Atkin algorithm for counting point on elliptic curves defined over a finite field.
• 2016-03-08
  Fabien Pazuki (IMB et Université de Copenhague)
  Régulateurs de corps de nombres et de variétés abéliennes et propriété de Northcott.
  Soit $A$ une variété abélienne définie sur un corps de nombres $K$. On peut définir un régulateur associé au groupe de Mordell-Weil des points rationnels $A(K)$, lequel joue un rôle important dans la forme forte de la conjecture de Birch et Swinnerton-Dyer. Si l’on suppose vraie la conjecture de Lang et Silverman, on montre alors que ce régulateur vérifie la propriété de finitude suivante : il n’y a qu’un nombre fini de variétés abéliennes simples de dimension fixée $g$, définie sur $K$, de rang non nul et de régulateur borné. On montre de plus (dans le courant de la preuve) une inégalité inconditionnelle entre la hauteur de Faltings de $A$, les premiers de mauvaise réduction de $A$ et le rang de Mordell-Weil de $A$. L’exposé commencera par une introduction présentant un résultat similaire et inconditionnel pour les régulateurs de familles de corps de nombres.
• 2016-03-01
  Cyril Bouvier (imb)
  Nonlinear polynomial selection for the number field sieve: improving Montgomery's method
  The number field sieve is the most efficient known algorithm for factoring large integers that are free of small prime factors. The goal of the polynomial selection, the first stage of this algorithm, is to compute a pair of integer polynomials. Montgomery proposed a method for generating two nonlinear polynomials which relies on the construction of small modular geometric progressions. In this talk, I will present theoretical and practical improvements to Montgomery’s method that allow us to generate pairs of a quadratic and a cubic polynomials and pairs of two cubic polynomials for larger integer that was previously possible. Joint work with Nicholas Coxon.
• 2016-02-09
  Павел Соломатин (imb)
  L-functions of Genus Two Abelian Coverings of Elliptic Curves over Finite Fields
  Initially motivated by the relations between Anabelian Geometry and Artin’s L-functions of the associated Galois-representations, here we study the list of zeta-functions of genus two abelian coverings of elliptic curves over finite fields. Our goal is to provide a complete description of such a list.
• 2016-01-26
  Bernadette Perrin-Riou (Université Paris-Sud)
  Présentation de WIMS (WWW Interactive Multipurpose Server)
• 2015-12-15
  Bill Allombert (imb)
  Les aspect combinatoires des fonctions L d'Artin.
• 2015-12-03
  Enea Milio (imb)
  Calcul de polynômes modulaires en dimension 2
  (doctoral defense)
• 2015-12-03
  David Kohel (Université d'Aix-Marseille)
  Characterization of Sato-Tate distributions by character theory
  We describe the generalized Sato-Tate group attached to an abelian variety and introduce an approach to characterize it through the character theory of compact Lie groups. We illustrate the method with examples of generic curves of low genus, with Sato-Tate group $\mathrm{USp}(2g)$; special curves which yield proper subgroups, and a family of Katz giving rise to Galois representations in $\mathrm{SO}(2g+1)$.

  This is joint work with Gilles Lachaud and Yih-Dar Shieh.

• 2015-11-24
  Julien Keuffer (Morpho)
  The SEA algorithm in PARI/GP
  The Schoof-Elkies-Atkin (SEA) algorithm is currently the most efficient algorithm for counting the number of points of an elliptic curve defined over a finite field of large characteristic. The main idea of this algorithm is to use the relation between the order of the curve and the trace of the Frobenius endomorphism and then to compute this trace modulo small primes. Using the CRT and the Hasse-Weil bound leads to find the exact value of the trace. The implementation of SEA in PARI/GP is based on Reynald Lercier’s thesis, published in 1997. Many improvements have been proposed since. In this talk, I will present two algorithms (respectively published by Gaudry and Morain and by Mihailescu, Morain and Schost) to compute the trace in the so-called Elkies case, their implementations in PARI and comparisons I made during my master’s internship in the French Network and Information Security Agency.
• 2015-10-13
  Fredrik Johansson (imb)
  Computing transcendental functions with error bounds
  In this talk, I will give an overview of work I’ve done in the last year on computing various transcendental functions in interval arithmetic. The first notable result is a large (order of magnitude) speed improvement for elementary functions. The second project concerns generalized hypergeometric functions (including the incomplete gamma function, Bessel functions, and others). This is still a work in progress, and some significant problems remain, particularly the task of computing useful enclosures when the inputs are large, inexact complex numbers. Finally, I have a fairly complete implementation of the classical Jacobi theta functions, elliptic functions and modular forms. I will describe an optimization for theta series, following up the results presented earlier by Andreas Enge (2015-06-02), and discuss the application of computing class polynomials.
• 2015-10-06
  Tony Ezome (Université des Sciences et Techniques de Masuku, Franceville)
  Constructions et evaluations de fonctions sur les varietes jacobiennes et leur quotients.
  Soient $K$ un corps fini, $C$ une courbe projective absolument integre sur $K$ et $\ell$ un nombre premier impair different de la carcteristique de $K$. Notons $W$ l’ensemble des classes d’equivalence lineaire de diviseurs effectifs de degre 1 sur $C$. Nous nous interessons aux sections globales d’un faisceau de $O_C$-modules sur la jacobienne $J_C$ de C. Plus precisement nous allons construitre une base de l’espace des fonctions $f$ sur $J_C$ tels que le diviseur $div(f)+\ell W$ est un diviseur effectif sur $J_C$.
• 2015-09-22
  Abdoul Aziz Ciss (Ecole Polytechnique de Thiès, Sénégal)
  Faster Ate Pairing Computation on Selmer Elliptic Curves
• 2015-09-22
  Emmanuel Fouotsa (École Normale Supérieure de l'Université de Bamenda)
  Analysis of the Efficiency of the point blinding countermeasure against fault attack in Miller's algorithm.
  In this talk, I will present fault attacks against pairing based protocols and describe some countermeasures. I will particularly show that the point blinding countermeasure does not provide a complete protection to Miller’s algorithm which is the main tool for pairings.
• 2015-09-08
  Cyril Bouvier (imb)
  Algorithms for integer factorization and discrete logarithms computation
  In this talk, I will present some results obtained during my Ph.D on integer factorization and discrete logarithm computation in finite fields. First, I will present the ECM algorithm for integer factorization and a new method to analyze the elliptic curves used in this algorithm by studying the Galois properties of division polynomials. Then, I will talk about the NFS algorithm for integer factorization and in particular the polynomial selection step for which I will propose improvements of existing algorithms. Finally, I will talk about a common step of the NFS algorithm for integer factorization and the NFS-DL and FFS algorithms for discrete logarithm computations: the filtering step. I will explain this step thoroughly and present an improvement for which I will study the impact using data from several computations of discrete logarithms and factorizations.