IMB > Recherche > Séminaires

Séminaire de Théorie Algorithmique des Nombres

Responsable : Damien Robert

Page du séminaire

  • Le 27 janvier 2015 à 10:00
  • Salle 385
    Andreas Enge (imb)
    Class polynomials for abelian surfaces

    The complex multiplication method is well-known for elliptic curves, whereit may be used to construct curves used in primality proofs or to implementcrytosystems, in particular pairing-based ones. A similar approach ispossible for abelian surfaces, that are Jacobians of genus 2 curves,with considerable number theoretic complications. I describe an algorithmusing complex floating point approximations with an asymptotically optimalrunning time, that is, quasi-linear in the size of the class polynomialsproduced as output. Our implementation has been used to carry outparallelised record computations and I present experimental data.

    (joint work with Emmanuel Thomé)

  • Le 27 janvier 2015 à 10:00
  • Salle 385
    Andreas Enge (imb)
    Class polynomials for abelian surfaces

    The complex multiplication method is well-known for elliptic curves, whereit may be used to construct curves used in primality proofs or to implementcrytosystems, in particular pairing-based ones. A similar approach ispossible for abelian surfaces, that are Jacobians of genus 2 curves,with considerable number theoretic complications. I describe an algorithmusing complex floating point approximations with an asymptotically optimalrunning time, that is, quasi-linear in the size of the class polynomialsproduced as output. Our implementation has been used to carry outparallelised record computations and I present experimental data.

    (joint work with Emmanuel Thomé)

  • Le 3 février 2015 à 10:30
  • Salle 385
    Benjamin Smith (INRIA & LIX, École Polytechnique)
    Arithmetic Geometry and Key Exchange : Compact Diffie--Hellman with Efficient Endomorphisms

    $\newcommand{\G}{{\mathcal{G}}}$Diffie?Hellman key exchange is a fundamental primitive in public-keycryptography. If \(\G\) is an abelian group (written additively), thenthe Diffie?Hellman protocol in \(\G\) is composed of four computationsin the form\[ P \longmapsto [m]P = \underbrace{P + \cdots + P}_{m \text{ times}}\]for various points \(P\) and integers \(m\); optimising thisscalar multiplication operation is therefore crucial.

    In practice, the most efficient contemporary Diffie?Hellmanimplementations are based on elliptic curves, or Jacobians of genus 2curves. But in these groups, computing \(-P\) is extremely efficient,so we can use the fact that \([m]\left(\pm P\right) = \pm([m]P)\) to simplify andspeed up the protocol, identifying \(P\) with \(-P\) (formally, we areworking in the quotient set \(\G/\langle\pm1\rangle\)).These ``compact?? systems offer significant savings in both space(which translates into slightly shorter keys) and computing time(through simpler pseudo-group law formulae).In the elliptic curve context, this amounts to using only\(x\)-coordinates of points and Montgomery?s pseudo-group law.Bernstein?s Curve25519 software, which has become a de facto referenceimplementation of Diffie?Hellman at the 128-bit security level,is a practical example of these techniques in practice.The genus 2 analogue is Kummer surface arithmetic, where we can useparticularly efficient formulae developed by the Chudnovskys, andpopularized in cryptography by Gaudry.

    Recent years have seen renewed interest in theGallant?Lambert?Vanstone (GLV) technique for computing \([m]P\).Here, we suppose our elliptic curve (or our genus 2 Jacobian) has anefficiently computable non-integer endomorphism \(\phi\), which whenapplied to elements of \(\G\) acts like \([\lambda]\) (for some largeeigenvalue \(\lambda\)).Suppose we want to compute \([m]P\): first we use the Euclideanalgorithm to compute much smaller integers \(a\) and \(b\) such that\(a + b\lambda \equiv m \pmod{\#\G}\), and then we compute\[ [m]P = [a]P + [b]\phi(P) \ .\]The running time of the multiexponentiation depends on the size of \(a\)and \(b\), while traditional scalar multiplication depends on the sizeof \(m\). In practice, \(a\) and \(b\) have half the bitlength of\(m\), which means that GLV and its variants can offer us a significantspeedup.

    In this talk, we will discuss the adaptation of GLV techniques to\(x\)-coordinate-only and Kummer surface systems. On the practicalside, we will present some experimental results for a new elliptic-curvebased implementation. On the more theoretical side, we will presentsome new formulae for Kummer surface systems with explicit realmultiplication endomorphisms.

  • Le 10 février 2015 à 10:00
  • Salle 385
    Eduardo Friedman (Universidad de Chile)
    Co-volume of high-rank subgroups of the units of a number field
    Since Zimmert's work in the early 1980's the co-volume (essentially a regulator) of units is known to grow exponentially with the unit-rank. At the other end of the rank scale, Lehmer's 1933 conjecture predicts a strong lower bound for the height of a subgroup of rank 1 of the units. Rodriguez-Villegas made a conjecture that interpolates between these two and applies to any subgroup of the units. We will sketch a recent analytic proof of this conjecture in the case of high-rank subgroups.

    This is joint work with Ted Chinburg, Ben McReynolds, Matt Stover and James Sundstrom.

  • Le 3 mars 2015 à 10:00
  • Salle 385
    Renate Scheidler (University Calgary)
    A family of Artin-Schreier curves with many automorphisms
    Algebraic geometry codes are obtained from certain types of curves overfinite fields. Since the length of such a code is determined by thenumber of rational points on the curve, it is desirable to use curveswith as many rational points as possible. We investigate a certainclass of Artin-Schreier curves with an unusually large number ofautomorphisms. Their automorphism group contains a large extraspecialsubgroup. Precise knowledge of this subgroup makes it possible tocompute the zeta functions of these curves. As a consequence, we obtainnew examples of curves that attain the provably maximal (or minimal)number of points over an appropriate field of definition.

    This is joint work with Irene Bouw, Wei Ho, Beth Malmskog, PadmavathiSrinivasan and Christelle Vincent.

  • Le 10 mars 2015 à 10:00
  • Salle 385
    Guilhem Castagnos (imb)
    Linearly Homomorphic Encryption from DDH
    In this talk, we will design a linearly homomorphic encryption schemewhose security relies on the hardness of the decisional Diffie-Hellman(DDH) problem. Our approach requires some special features of theunderlying group. In particular, its order is unknown and it contains asubgroup in which the discrete logarithm problem is tractable.Therefore, our instantiation holds in the class group of a non maximalorder of an imaginary quadratic field. Its algebraic structure makes itpossible to obtain such a linearly homomorphic scheme whose messagespace is the whole set of integers modulo a prime p and which supportsan unbounded number of additions modulo p from the ciphertexts. Anotable difference with previous works is that, for the first time, thesecurity does not depend on the hardness of the factorization ofintegers. As a consequence, under some conditions, the prime p can bescaled to fit the application needs.

    Joint work with Fabien Laguillaumie.

  • Le 31 mars 2015 à 10:00
  • Salle 385
    Karim Belabas (imb)
    Modular symbols and p-adic L functions I

  • Le 7 avril 2015 à 10:00
  • Salle 385
    Karim Belabas (imb)
    Modular symbols and p-adic L functions II

  • Le 14 avril 2015 à 10:00
  • Salle 385
    Karim Belabas (imb)
    Modular symbols and p-adic L functions III

  • Le 5 mai 2015 à 10:00
  • Salle 385
    Damien Robert (imb)
    Arithmetic on Abelian and Kummer varieties I
    The first talk will review the arithmetic of different models of elliptic curves and on the Kummer line. We will also review Mumford coordinates for Jacobian of hyperelliptic curves and introduce theta functions for general abelian varieties.
  • Le 12 mai 2015 à 10:00
  • Salle 385
    Damien Robert (imb)
    Arithmetic on Abelian and Kummer varieties II
    The second talk will focus on the arithmetic of theta functions of level 2 and 4 and their use for Abelian and Kummer varieties cryptography.
  • Le 26 mai 2015 à 10:00
  • Salle 385
    Iuliana Ciocanea-Teodorescu (Leiden+IMB)
    Algorithms for finite rings
    We will discuss deterministic polynomial time algorithms designed toanswer a series of fundamental questions about finite rings and finitemodules. These include the module isomorphism problem, computing theminimum number of generators of a module and finding a ?good?approximation for the Jacobson radical of a finite ring.
  • Le 2 juin 2015 à 10:00
  • Salle 385
    Andreas Enge (imb)
    Optimised addition sequences for eta and theta functions
    The main ingredient of complex multiplication algorithms for ellipticcurves that compute class and modular polynomials via floating pointapproximations is the evaluation of Dedekind?s ?- and of more general?-functions. While algorithms are known that are asymptoticallyquasi-linear in the desired precision, in practice it is usually fasterto evaluate lacunary power series. It has been observed experimentallythat particularly short addition sequences exist for the speciallystructured exponents of ? and ?. A leisurely stroll through classicnumber theory will provide us with proofs of this fact.

    Joint work in progress with William Hart and Fredrik Johansson.

  • Le 23 juin 2015 à 10:00
  • Salle 385
    Enea Milio (imb)
    Multiplication réelle et polynômes modulaires
    Soit $K=\mathbb{Q}(\sqrt{2})$ ou $\mathbb{Q}(\sqrt{5})$. Il existe deuxinvariants qu?on appelle invariants de Gundlach qui engendrent le corpsdes fonctions modulaires symétriques de Hilbert. Si $\beta$ est unélément totalement positif de $O_K$ de norme $p$, les $\beta$-polynômesmodulaires paramétrisent les classes d?isomorphisme de variétésabéliennes principalement polarisées ayant multiplication réelle par$O_K$ et munis d?une $\beta$-isogénie ou d?une $\beta^c$-isogénie. Nousdécrivons un algorithme efficace pour calculer ces polynômes entransposant certains calculs sur l?espace de Siegel. Nous étendrons cesméthodes à des invariants dérivés des fonctions thêta.
  • Le 8 septembre 2015 à 10:00
  • Salle 385
    Cyril Bouvier
    Algorithms for integer factorization and discrete logarithms computation
    In this talk, I will present some results obtained during my Ph.D oninteger factorization and discrete logarithm computation in finitefields. First, I will present the ECM algorithm for integerfactorization and a new method to analyze the elliptic curves used inthis algorithm by studying the Galois properties of divisionpolynomials. Then, I will talk about the NFS algorithm for integerfactorization and in particular the polynomial selection step for whichI will propose improvements of existing algorithms. Finally, I willtalk about a common step of the NFS algorithm for integer factorizationand the NFS-DL and FFS algorithms for discrete logarithm computations:the filtering step. I will explain this step thoroughly and present animprovement for which I will study the impact using data from severalcomputations of discrete logarithms and factorizations.
  • Le 22 septembre 2015 à 11:00
  • Salle 385
    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 basedprotocols and describe some countermeasures. I will particularly showthat the point blinding countermeasure does not provide a completeprotection to Miller?s algorithm which is the main tool for pairings.
  • Le 6 octobre 2015 à 11:00
  • Salle 385
    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 integresur $K$ et $\ell$ un nombre premier impair different de lacarcteristique de $K$. Notons $W$ l?ensemble des classes d?equivalencelineaire de diviseurs effectifs de degre 1 sur $C$. Nous nousinteressons aux sections globales d?un faisceau de $O_C$-modules sur lajacobienne $J_C$ de C. Plus precisement nous allons construitre unebase de l?espace des fonctions $f$ sur $J_C$ tels que le diviseur$div(f)+\ell W$ est un diviseur effectif sur $J_C$.
  • Le 13 octobre 2015 à 11:00
  • Salle 385
    Fredrik Johansson (imb)
    Computing transcendental functions with error bounds
    In this talk, I will give an overview of work I?ve done in the lastyear on computing various transcendental functions in intervalarithmetic. The first notable result is a large (order of magnitude)speed improvement for elementary functions. The second project concernsgeneralized hypergeometric functions (including the incomplete gammafunction, Bessel functions, and others). This is still a work inprogress, and some significant problems remain, particularly the taskof computing useful enclosures when the inputs are large, inexactcomplex numbers. Finally, I have a fairly complete implementation ofthe classical Jacobi theta functions, elliptic functions and modularforms. I will describe an optimization for theta series, following upthe results presented earlier by Andreas Enge (2015-06-02), and discussthe application of computing class polynomials.
  • Le 24 novembre 2015 à 11:00
  • Salle 385
    Julien Keuffer (Morpho)
    The SEA algorithm in PARI/GP
    The Schoof-Elkies-Atkin (SEA) algorithm is currently the most efficientalgorithm for counting the number of points of an elliptic curve definedover a finite field of large characteristic. The main idea of thisalgorithm is to use the relation between the order of the curve and thetrace of the Frobenius endomorphism and then to compute this trace modulosmall primes. Using the CRT and the Hasse-Weil bound leads to find theexact value of the trace. The implementation of SEA in PARI/GP is basedon Reynald Lercier?s thesis, published in 1997. Many improvements havebeen proposed since. In this talk, I will present two algorithms(respectively published by Gaudry and Morain and by Mihailescu, Morainand Schost) to compute the trace in the so-called Elkies case, theirimplementations in PARI and comparisons I made during my master?sinternship in the French Network and Information Security Agency.
  • Le 3 décembre 2015 à 10:00
  • Salle 385
    David Kohel (Université d'Aix-Marseille)
    Characterization of Sato-Tate distributions by character theory
    We describe the generalized Sato-Tate group attached to an abelianvariety and introduce an approach to characterize it through thecharacter theory of compact Lie groups. We illustrate the method withexamples of generic curves of low genus, with Sato-Tate group$\mathrm{USp}(2g)$; special curves which yield proper subgroups, and afamily of Katz giving rise to Galois representations in$\mathrm{SO}(2g+1)$.

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

  • Le 15 décembre 2015 à 11:00
  • Salle 385
    Bill Allombert (imb)
    Les aspect combinatoires des fonctions L d'Artin.

  • Le 26 janvier 2016 à 11:00
  • Salle 1
    Bernadette Perrin-Riou (Université Paris-Sud)
    Présentation de WIMS (WWW Interactive Multipurpose Server)

  • Le 9 février 2016 à 11:00
  • Salle 385
    Павел Соломатин (imb)
    L-functions of Genus Two Abelian Coverings of Elliptic Curves over Finite Fields
    Initially motivated by the relations between Anabelian Geometry andArtin’s L-functions of the associated Galois-representations, here westudy the list of zeta-functions of genus two abelian coverings ofelliptic curves over finite fields. Our goal is to provide a completedescription of such a list.
  • Le 1er mars 2016 à 11:00
  • Salle 385
    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 forfactoring large integers that are free of small prime factors. The goalof the polynomial selection, the first stage of this algorithm, is tocompute a pair of integer polynomials. Montgomery proposed a method forgenerating two nonlinear polynomials which relies on the constructionof small modular geometric progressions. In this talk, I will presenttheoretical and practical improvements to Montgomery’s method thatallow us to generate pairs of a quadratic and a cubic polynomials andpairs of two cubic polynomials for larger integer that was previouslypossible.Joint work with Nicholas Coxon.
  • Le 8 mars 2016 à 11:00
  • Salle 385
    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 peutdéfinir un régulateur associé au groupe de Mordell-Weil des pointsrationnels $A(K)$, lequel joue un rôle important dans la forme forte dela conjecture de Birch et Swinnerton-Dyer. Si l’on suppose vraie laconjecture de Lang et Silverman, on montre alors que ce régulateurvérifie la propriété de finitude suivante : il n’y a qu’un nombre fini devariétés abéliennes simples de dimension fixée $g$, définie sur $K$, derang non nul et de régulateur borné. On montre de plus (dans le courantde la preuve) une inégalité inconditionnelle entre la hauteur deFaltings de $A$, les premiers de mauvaise réduction de $A$ et le rang deMordell-Weil de $A$. L’exposé commencera par une introduction présentantun résultat similaire et inconditionnel pour les régulateurs defamilles de corps de nombres.
  • Le 15 mars 2016 à 11:00
  • Salle 385
    Bill Allombert (imb)
    Survey on computing isogeny between elliptic curves.
    We present methods to compute isogenies between elliptic curves, and weapply them to the computation of the isogenies matrix of an ellipticcurve defined over the rational and to the Schoof Elkies Atkinalgorithm for counting point on elliptic curves defined over a finitefield.
  • Le 22 mars 2016 à 11:00
  • Salle 385
    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 desrapports de puissances de theta constantes avec les coordonnées affinesdes points de ramification d’une courbe hyperelliptique. A partir desannées 80, plusieurs auteurs, ayant des préoccupations centrés sur laphysique, ont montré des généralisations de ces formules au cas descourbes superelliptiques. Plus récemment, Shau Zemel et Hershel Farkasont écrit un livre en utilisant des arguments essentiellementalgé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 extensionsrésolubles de $k(x)$ et quelles obstructions peuvent survenir.
  • Le 5 avril 2016 à 11:00
  • Salle 385
    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.

  • Le 10 mai 2016 à 11:00
  • Salle 385
    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, enl’isolant dans la torsion de la jacobienne d’une courbe modulaire. Cecipermet notamment de calculer les coefficients a(p) de la forme en tempspolynomial 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 aclassical newform may be efficiently computed, by isolating it amongthe l-torsion of a modular jacobian. This yields a way of computing thecoefficient a(p) of the form in time polynomial in log p, which makesit the most efficient methodknown as of today.

  • Le 17 mai 2016 à 11:00
  • Salle 385
    Nicolas Mascot (University of Warwick)
    Certification de représentations galoisiennes modulaires / Certifying modular Galois representations
    Nous verrons comment les calculs de représentations galoisiennesprésentés dans l’exposé précédent peuvent être certifiés, en s’appuyantsur la conjecture de modularité de Serre et des calculs explicites decohomologie des groupes.

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

  • Le 7 juin 2016 à 10:00
  • Salle 385
    Jared Asuncion (IMB)
    Tower decomposition of Hilbert class fields

  • Le 11 octobre 2016 à 14:00
  • Salle 385
    Enea Milio (Inria Nancy Grand Est)
    Une implantation en genre 2 de 'Computing functions on Jacobians and their quotients' de Jean-Marc Couveignes et Tony Ezome
    Cet article explique comment définir et évaluer des fonctions sur desJacobiennes de courbes de genre $g$ et sur des quotients de tellesJacobiennes par des sous-groupes isotropes maximaux de la$\ell$-torsion, pour $\ell>2$ premier. Pour le cas spécifique du genre2, il est bien connu qu’à partir d’une courbe hyperelliptique $C$ etd’un sous-groupe isotrope maximal $V$, le quotient $\mathrm{Jac}(C)/V$est la Jacobienne d’une courbe hyperelliptique $C’$,$(\ell,\ell)$-isogène à $C$. L’application de $C$ vers$\mathrm{Jac}(D)$ peut être décrite avec des fractions rationnelles dedegré en $O(\ell)$. L’article donne une méthode pour calculer $C’$ etces fractions. Pour notre exposé, nous nous proposons d’exposer lecontenu de ce papier et de parler de l’implantation que nous avonsfaite en genre 2.
  • Le 18 octobre 2016 à 10:00
  • Salle 385
    Gregor Seiler (ETH Zurich)
    Computing ray class fields of imaginary quadratic fields

  • Le 8 novembre 2016 à 10:00
  • Salle 385
    Aurélien Focqué
    Algorithmes BMSS et Lercier Sirvent pour SEA dans PARI

  • Le 22 novembre 2016 à 10:00
  • Salle 385
    Razvan Barbulescu
    A brief history of pairings
    Pairings are a relatively new cryptographic tool which have been theobject of many arithmetic works. In the last few years some of thepairings have become obsolete because of the progress on the underlyingproblem of discrete logarithm in finite fields. We propose ourselves tomake a list of pairings constructions, to explain their advantages butalso their weaknesses. The sporadic curves are vulnerable to the Logjamattack and have never been a popular choice. The small characteristiccurves allow a very good arithmetic but are the target of aquasi-polynomial algorithm. The pairings where the characteristic has alow Hamming weight, which eliminate the cost of modular reductions,have been the object of special attacks. When the embedding degree iscomposite the one can use the tower field arithmetic but there are alsotower field attacks.
  • Le 17 janvier 2017 à 10:00
  • Salle 385
    Damien Stehlé (ENS Lyon)
    Tuple lattice sieving
    Lattice sieving is asymptotically the fastest approach for solving the shortest vector problem (SVP) on Euclidean lattices. All known sieving algorithms for solving SVP require space which (heuristically) grows as $2^{0.2075n+o(n)}$, where n is the lattice dimension. In high dimensions, the memory requirement becomes a limiting factor for running these algorithms, making them uncompetitive with enumeration algorithms, despite their superior asymptotic time complexity. We generalize sieving algorithms to solve SVP with less memory. We consider reductions of tuples of vectors rather than pairs of vectors as existing sieve algorithms do. For triples, we estimate that the space requirement scales as $2^{0.1887n+o(n)}$. The naive algorithm for this triple sieve runs in time $2^{0.5661n+o(n)}$. With appropriate filtering of pairs, we reduce the time complexity to $2^{0.4812n+o(n)}$ while keeping the same space complexity. We further analyze the effects of using larger tuples for reduction, and conjecture how this provides a continuous tradeoff between the memory-intensive sieving and the asymptotically slower enumeration. Joint work with Shi Bai, Thijs Laarhoven
  • Le 14 mars 2017 à 10:00
  • Salle 385
    Cécile Pierrot (Centrum Wiskunde & Informatica, Amsterdam)
    Nearly sparse linear algebra
    Linear algebra is a widely used tool both in mathematics and computerscience, and cryptography is no exception to this rule. Yet, itintroduces some particularities, such as dealing with linear systemsthat are often sparse, or, in other words, linear systems inside whicha lot of coefficients are equal to zero. We propose to enlarge thisnotion to nearly sparse matrices, characterized by the concatenationof a sparse matrix and some dense columns, and to design an algorithmto solve this kind of problems. Motivated by discrete logarithmscomputations on medium and high characteristic finite fields, theNearly Sparse Linear Algebra bridges the gap between classical denselinear algebra problems and sparse linear algebra ones, for whichspecific methods have already been established. Our algorithmparticularly applies on one of the three phases of NFS (Number FieldSieve) which precisely consists in finding a non trivial element ofthe kernel of a nearly sparse matrix.

    This is a joint work with Antoine Joux.

  • Le 23 mai 2017 à 10:00
  • Salle 385
    Christophe Petit (Oxford)
    Post-quantum cryptography from supersingular isogeny problems?
    We review existing cryptographic schemes based on the hardness ofcomputing isogenies between supersingular isogenies, and present someattacks against them. In particular, we present new techniques toaccelerate the resolution of isogeny problems when the action of theisogeny on a large torsion subgroup is known, and we discuss the impactof these techniques on the supersingular key exchange protocol ofJao-de Feo.
  • Le 30 mai 2017 à 10:00
  • Salle 385
    Benjamin Wesolowski (EPFL)
    Isogeny graphs of ordinary abelian varieties
    Fix a prime number $\ell$. Graphs of isogenies of degree a power of$\ell$ are well-understood for elliptic curves, but not forhigher-dimensional abelian varieties. We study the case of absolutelysimple ordinary abelian varieties over a finite field. We analysegraphs of so-called $\mathfrak l$-isogenies, resolving that, inarbitrary dimension, their structure is similar, but not identical, tothe ``volcanoes’’ occurring as graphs of isogenies of elliptic curves.Specializing to the case of principally polarizable abelian surfaces,we then exploit this structure to describe graphs of a particular classof isogenies known as $(\ell, \ell)$-isogenies. These results lead tonew, provable algorithms to navigate in isogeny graphs, withconsequences for the CM-method in genus 2, for computing explicitisogenies, and for the random self-reducibility of the discretelogarithm problem in genus 2 cryptography.
  • Le 6 juin 2017 à 10:00
  • Salle 385
    Guilhem Castagnos (imb)
    Encryption Switching Protocols Revisited: Switching modulo p
    Last year, Couteau, Peters and Pointcheval introduced a new primitivecalled encryption switching protocols, allowing to switch ciphertextsbetween two encryption schemes. If such an ESP is built with twoschemes that are respectively additively and multiplicativelyhomomorphic, it naturally gives rise to a secure 2-party computationprotocol. It is thus perfectly suited for evaluating functions, suchas multivariate polynomials, given as arithmetic circuits. Couteau etal. built an ESP to switch between Elgamal and Paillier encryptionswhich do n ot naturally fit well together. Consequently, they had todesign a clever variant of Elgamal over Z/nZ with a costly shareddecryption. In this talk, we first present a conceptually simplegeneric construction for encryption switching protocols. We then givean efficient instantiation of our generic approach that uses twowell-suited protocols, namely a variant of Elgamal in Z/pZ and theCastagnos-Laguillaumie encryption defined over class groups of quadratic fields which is additively homomorphic over Z/pZ. Among otheradvantages, this allows to perform all computations modulo a prime pinstead of an RSA modulus. Overall, our solution leads to significantreductions in the number of rounds as well as the number of bitsexchanged by the parties during the interactive protocols. We also showhow to extend its security to the malici ous setting.

    Joint work with Laurent Imbert and Fabien Laguillaumie.

  • Le 13 juin 2017 à 10:00
  • Salle 385
    Bernhard Schmidt (Nanyang Technological University, Singapore)
    The Anti-Field-Descent Method
    A circulant Hadamard matrix of order $v$ is a matrix of the form\[H=\begin{pmatrix}a_1 & a_2 & \cdots & a_v \a_v & a_1 & \cdots & a_{v-1} \\cdots & \cdots & \cdots &\cdots \a_2 & a_3 & \cdots & a_1 \\end{pmatrix}\]with $a_i=\pm 1$ such that any two rows of $H$ are orthogonal withrespect to the standard inner product. It is conjectured that there isno circulant Hadamard matrix of order larger than $4$.

    One way to study circulant Hadamard matrices is the so-called``field-descent method’’. The essential fact behind this method is thatcertain cyclotomic integers necessarily are contained in relativelysmall fields and thus must have relatively small complex modulus. Inthis talk, I will present a method which reveals a complementaryphenomenon: certain cyclotomic integers cannot be contained in relativelysmall fields and thus must have relatively large complex modulus. Thismethod provides new necessary conditions for the existence of circulantHadamard matrices.

    This is joint work with K. H. Leung.

  • Le 17 octobre 2017 à 10:00
  • Salle 385
    Fredrik Johansson (imb)
    Numerics of classical elliptic functions, elliptic integrals and modular forms
    We review methods for validated arbitrary-precision numericalcomputation of elliptic functions and their inverses (the complete andincomplete elliptic integrals), as well as the closely related Jacobitheta functions and $\mathrm{SL}_2(\mathbb{Z})$ modular forms. A general strategy consists of two stages:first, using functional equations to reduce the functionarguments to a smaller domain; second, evaluation of a suitable truncatedseries expansion. For elliptic functions and modular forms, one exploitsperiodicity and modular transformations for argument reduction, afterwhich the rapidly convergent series expansions of Jacobi theta functionscan be employed. For elliptic integrals, a comprehensive strategypioneered by B. Carlson consists of using symmetric forms to unify andsimplify both the argument reduction formulas and the series expansions(which involve multivariate hypergeometric functions). Among otheraspects, we discuss error bounds as well as strategies for argumentreduction and series evaluation that reduce the computational complexity.The functions have been implemented in arbitrary-precision complexinterval arithmetic as part of the Arb library.
  • Le 24 octobre 2017 à 10:00
  • Salle 385
    José Manuel Rodriguez Caballero (Labri)
    Context-free languages in Algebraic Geometry and Number Theory.
    Kassel and Reutenauer computed the zeta function of the Hilbert schemeof n points on a two-dimensional torus and showed it satisfies severalnumber-theoretical properties via modular forms. Classifying thesingularities of this rational function into zeros and poles, we definea word which contains a lot of number-theoretical information about n(the above-mentioned number of points). This nontrivial connectionbetween natural numbers and words can be used to define many classicalsubsets of natural numbers in terms of rational and context-freelanguages (e.g. the set of semi-perimeters of Pythagorean triangles,the set of numbers such that any partition into consecutive parts hasan odd number of parts). Also, some arithmetical functions can bedescribed in way (e.g. the Erdös-Nicolas function, the number of middledivisors). Finally, this approach provides a new technique to provenumber-theoretical results just using relationships among context-freelanguages.
  • Le 14 novembre 2017 à 10:00
  • Salle 385
    Jean Kieffer (ENS Paris)
    Accélération du protocole d'échange de clés de Couveignes-Rostovtsev-Stolbunov
    Ce protocole d’échange de clés est fondé sur la théorie de lamultiplication complexe: un ordre dans un corps quadratique imaginaireagit sur un ensemble de courbes elliptiques ordinaires isogènes définiessur un corps fini. Pour instancier le protocole, on est amené à calculerdes isogénies de différents degrés entre ces courbes à l’aide desalgorithmes développés pour le comptage de points. Ce cryptosystème peutêtre accéléré par un bon choix de courbe elliptique initiale, notammentpar la présence de points de torsion rationnels, et l’on présente uneméthode de recherche de telles courbes.
  • Le 20 novembre 2017 à 14:00
  • Salle 385
    Christian Klein
    Computational approach to compact Riemann surfaces
    A purely numerical approach to compact Riemann surfaces starting fromplane algebraic curves is presented. The critical points of the algebraiccurve are computed via a two-dimensional Newton iteration. The startingvalues for this iteration are obtained from the resultants with respect toboth coordinates of the algebraic curve and a suitable pairing of theirzeros. A set of generators of the fundamental group for the complement ofthese critical points in the complex plane is constructed from circlesaround these points and connecting lines obtained from a minimal spanningtree. The monodromies are computed by solving the de ning equation of thealgebraic curve on collocation points along these contours and byanalytically continuing the roots. The collocation points are chosen tocorrespond to Chebychev collocation points for an ensuing Clenshaw–Curtisintegration of the holomorphic differentials which gives the periods ofthe Riemann surface with spectral accuracy. At the singularities of thealgebraic curve, Puiseux expansions computed by contour integration on thecircles around the singularities are used to identify the holomorphicdifferentials. The Abel map is also computed with the Clenshaw–Curtisalgorithm and contour integrals. As an application of the code, solutionsto the Kadomtsev–Petviashvili equation are computed on non-hyperellipticRiemann surfaces.
  • Le 28 novembre 2017 à 10:00
  • Salle 385
    Frank Vallentin
    Coloring the Voronoi tessellation of lattices
    We define the chromatic number of a lattice: It is the least number ofcolors one needs to color the interiors of the cells of the Voronoitesselation of a lattice so that no two cells sharing a facet are ofthe same color. We compute the chromatic number of the irreducible rootlattices and for this we apply a generalization of the Hoffman bound.
  • Le 9 janvier 2018 à 10:00
  • Salle 385
    Fredrik Johansson (imb)
    Numerical integration in complex interval arithmetic
    We present a new implementation of validated arbitrary-precisionnumerical evaluation of definite integrals $\int_a^b f(x) dx$,available in the Arb library. The code uses a version of the Petrasalgorithm, which combines adaptive subdivision with Gauss-Legendre (GL)quadrature, evaluating the integrand on complex intervals surroundingthe path of integration to obtain rigorous error bounds. The first partof the talk discusses the general algorithm and its performance forinteresting families of integrals. The second part, which is based onjoint work with Marc Mezzarobba, discusses the fast computation of GLquadrature nodes with rigorous error bounds. It is well known that GLquadrature achieves a nearly optimal rate of convergence for analyticintegrands with singularities well isolated from the path ofintegration, but due to the cost of generating GL quadrature nodes, themore slowly converging Clenshaw-Curtis and double exponentialquadrature rules have often been favored when an accuracy of severalhundreds or thousands of digits is required. We consider the asymptoticand practical aspects of this problem. An order-of-magnitude speedup isobtained over previous code for computing GL nodes with simultaneoushigh degree and precision, which makes GL quadrature viable even atvery high precision.
  • Le 22 janvier 2018 à 10:00
  • Salle 2
    Philippe Moustrou (IMB)
    On the Density of Sets Avoiding Parallelohedron Distance 1
    Let $\Vert \cdot \Vert$ be a norm on $\mathbb{R}^n$. We consider theso-called unit distance graph $G$ associated with $\Vert \cdot \Vert$:the vertices of $G$ are the points of $\mathbb{R}^n$, and the edgesconnect the pairs $\{x,y\}$ satisfying $\Vert x-y\Vert=1$. We define$m_1\left(\mathbb{R}^n,\Vert \cdot \Vert\right)$ as the supremum of thedensities achieved by independent sets of $G$. The number $m_1$ wasintroduced by Larman and Rogers (1972) as a tool to study themeasurable chromatic number $\chi_m(\mathbb{R}^n)$ of $\mathbb{R}^n$for the Euclidean norm.

    The best known estimates for $\chi_m(\mathbb{R}^n)$ and$m_1\left(\mathbb{R}^n,\Vert \cdot \Vert\right)$ present relations withEuclidean lattices, in particular with the sphere packing problem.

    The determination of $m_1\left(\mathbb{R}^n,\Vert \cdot \Vert\right)$for the Euclidean norm is still a difficult question. We study thisproblem for norms whose unit ball is a convex polytope. More precisely,if the unit ball corresponding with $\Vert \cdot \Vert$ tiles$\mathbb{R}^n$ by translation, for instance if it is the Voronoiregion of a lattice, then it is easy to see that$m_1\left(\mathbb{R}^n,\Vert \cdot \Vert\right)\geq \frac{1}{2^n}$.

    C. Bachoc and S. Robins conjectured that equality always holds. We showthat this conjecture is true for $n=2$ and for some families of Voronoiregions of lattices in higher dimensions.

  • Le 30 janvier 2018 à 10:00
  • Salle 385
    Jared Asuncion (IMB)
    The elliptic curve primality proving (ECPP) algorithm not only proves(or disproves) the primality of an integer $N$ but also provides, if$N$ is prime, a primality certificate which one can verify quickly. Inthis talk, we recall the steps of ECPP and discuss its implementationin PARI/GP.
  • Le 6 mars 2018 à 10:00
  • Salle 385
    Takashi Fukuda (Nihon University)
    Class number calculation for special number fields
    I will talk about TC (an interpreter of multiprecision C language whichI developed), Weber’s problem, Coates’ conjecture and an algorithm ofcalculating p-class group of abelian number fields. I also present myproject trying to implement an algorithm mentioned above to PARI/GPduring my stay at IMB.
  • Le 20 mars 2018 à 10:00
  • Salle 385
    Tristan Vaccon (Université de Limoges)
    Sur les équations différentielles $p$-adiques à variables séparables
    Les trois dernières décennies ont vu le développement de méthodes etalgorithmes $p$-adiques, notamment :
    • la factorisation de polynômes rationnels par lemme de Hensel ;
    • les algorithmes de comptage de points de Kedlaya et Lauder, reposant surdes résultats avancés de géométrie arithmétique ;
    • le calcul d’isogénies entre courbes elliptiques.

    Dans toutes ces méthodes et algorithmes, on passe par des calculs surles nombres $p$-adiques, et le problème de la gestion de la précision yest crucial. Avec Xavier Caruso et David Roe, nous avons développé uneméthode, dite de précision différentielle, pour étudier et gérer laprécision $p$-adique.

    Dans cet exposé, nous nous intéresserons à l’application de cetteméthode pour l’étude du calcul d’isogénies entre courbes elliptiquesvia la résolution de certaines équations différentielles $p$-adiques àvariables séparables. Il s’agit d’un travail en commun avec PierreLairez de 2016 qui ne traite que du cas $p>2$. Nous présenterons aussidans cet exposé quelques avancées récentes lorsque $p=2$.

  • Le 3 avril 2018 à 10:00
  • Salle 385
    Alex Bartel (Glasgow University)
    Cohen-Martinet heuristics revisited
    In the early 1990s Henri Cohen and Jacques Martinet offered aprobabilistic model that explains the behaviour of ideal class groupsof number fields in natural families, generalising earlier work byCohen and Lenstra. There is a lot of numerical evidence for thecorrectness of the model, but very few theorems. In joint work withHendrik Lenstra we revisit the Cohen-Martinet heuristics and, amongother things, disprove them in two different ways, but also lendadditional support for the expectation that they are “basically true”.In this talk I will explain one of these disproofs, and will proposepossible corrections.
  • Le 24 avril 2018 à 10:00
  • Salle 385
    Damien Robert (imb)
    Huang's proposal for trilinear maps
    In a recent paper, Huang proposed atrilinear map involving abelian varieties over finite fields. In this talkwe present his approach.

    We will first begin the talk with a review of the standard pairingsconstructions on an abelian variety.

  • Le 22 mai 2018 à 10:00
  • Salle 385
    Jean Kieffer (ENS Paris)
    Étude et implémentation de l’algorithme de Schoof–Elkies–Atkin

  • Le 12 juin 2018 à 10:00
  • Salle 385
    Xavier Caruso (Université de Rennes)
    Variations autour d'un théorème de Christol
    Un célèbre théorème de Christol affirme qu’une série à coefficientsdans $\mathbb{Z}/p\mathbb{Z}$ est algébrique sur$\mathbb{Z}/p\mathbb{Z}(x)$ si et seulement si la suite de sescoefficients est $p$-automatique.

    L’objectif de cet exposé sera de raconter de jolies mathématiques enlien de ce théorème. Je commencerai par esquisser deux démonstrations“classiques” de ce résultat, puis montrerai comment les combiner pourobtenir une variante effective du théorème de Christol. Je présenteraiensuite une application de ce résultat à une question de naturealgorithmique.

    Si le temps le permet, je discuterai également les liens entre théorèmede Christol et équations différentielles p-adiques et montrerai commentutiliser ce nouvel ingrédient pour accélérer l’algorithme précédent.

    (Travail en commun avec A. Bostan, G. Christol et Ph. Dumas.)

  • Le 5 juillet 2018 à 10:00
  • Salle 385
    Jean-François Biasse (University of South Florida)
    Fast multiquadratic S-unit computation and application to the calculation of class groups
    Let $L=Q(√d_1, … ,√d_n)$ be a real multiquadratic field and S be a setof prime ideals of L that does not contain any divisors of 2. In thispaper, we present a heuristic algorithm for the computation of theS-class group and the S-unit group that runs in time$Poly(log(∆),Size(S)) e^{Õ(√ln d)}$ where $d=max_{i≤n} d_i$ and ∆ is thediscriminant of L. We use this method to compute the ideal class groupof the maximal order $O_L$ of L in time $Poly(log(∆)) e^{Õ(√log d)}$. When$log(d)≤log(log(∆))^c$ for some constant $c < 2$, these methods run inpolynomial time. We implemented our algorithm using Sage 7.5.1.
  • Le 18 septembre 2018 à 10:30
  • Salle 385
    Aurel Page et Pascal Molin
    Mini groupe de travail: calcul des caractères de Hecke

  • Le 6 novembre 2018 à 10:00
  • Salle 385
    Elie Eid (Université de Rennes)
    Calcul d'isogénies en genre 2
    Étant donné une courbe algébrique $C$ de genre $2$ définie sur un corpsfini $K$ de caractéristique impaire et un sous-groupe isotrope maximal$\mathcal{V}$ (pour le couplage de commutateur) de l’ensemble despoints de $l$-torsion où $l$ est un entier (premier) impair, noussavons que le quotient de la jacobienne $J_K(C)$ de $C$ par$\mathcal{V}$ est une variété abélienne de dimension 2 et donc lajacobienne d’une courbe $D$ de genre $2$.

    La surjection canonique \[ \pi_l \: : J_K(C) \longrightarrow J_K(D) =J_K(C) / \mathcal{V}\] est une $(l,l)$-isogénie de noyau $\mathcal{V}$.

    Dans cet exposé, on s’intéresse à l’algorithme de Couveignes et Ezomepour trouver l’équation de la courbe $D$ à partir de sa kummerconstruite à l’aide de fonctions définies sur la jacobienne de lacourbe de départ et son quotient, ainsi que les équations quidéfinissent l’isogénie $\pi_l$.

  • Le 27 novembre 2018 à 10:00
  • Salle 385
    Ida Tucker

    Afficher 2016 - 2015 - antérieurs