# 2014/2015

• 2015-06-23
Multiplication réelle et polynômes modulaires
Soit $K=\mathbb{Q}(\sqrt{2})$ ou $\mathbb{Q}(\sqrt{5})$. Il existe deux invariants qu’on appelle invariants de Gundlach qui engendrent le corps des fonctions modulaires symétriques de Hilbert. Si $\beta$ est un élément totalement positif de $O_K$ de norme $p$, les $\beta$-polynômes modulaires paramétrisent les classes d’isomorphisme de variétés abé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. Nous décrivons un algorithme efficace pour calculer ces polynômes en transposant certains calculs sur l’espace de Siegel. Nous étendrons ces méthodes à des invariants dérivés des fonctions thêta.
• 2015-06-02
Optimised addition sequences for eta and theta functions
The main ingredient of complex multiplication algorithms for elliptic curves that compute class and modular polynomials via floating point approximations is the evaluation of Dedekind’s η- and of more general ϑ-functions. While algorithms are known that are asymptotically quasi-linear in the desired precision, in practice it is usually faster to evaluate lacunary power series. It has been observed experimentally that particularly short addition sequences exist for the specially structured exponents of η and ϑ. A leisurely stroll through classic number theory will provide us with proofs of this fact.

Joint work in progress with William Hart and Fredrik Johansson.

• 2015-05-26
Iuliana Ciocanea-Teodorescu (Leiden+IMB)
Algorithms for finite rings
We will discuss deterministic polynomial time algorithms designed to answer a series of fundamental questions about finite rings and finite modules. These include the module isomorphism problem, computing the minimum number of generators of a module and finding a “good” approximation for the Jacobson radical of a finite ring.
• 2015-05-12
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.
• 2015-05-05
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.
• 2015-04-14
• 2015-04-07
• 2015-03-31
• 2015-03-10
In this talk, we will design a linearly homomorphic encryption scheme whose security relies on the hardness of the decisional Diffie-Hellman (DDH) problem. Our approach requires some special features of the underlying group. In particular, its order is unknown and it contains a subgroup in which the discrete logarithm problem is tractable. Therefore, our instantiation holds in the class group of a non maximal order of an imaginary quadratic field. Its algebraic structure makes it possible to obtain such a linearly homomorphic scheme whose message space is the whole set of integers modulo a prime p and which supports an unbounded number of additions modulo p from the ciphertexts. A notable difference with previous works is that, for the first time, the security does not depend on the hardness of the factorization of integers. As a consequence, under some conditions, the prime p can be scaled to fit the application needs.

Joint work with Fabien Laguillaumie.

• 2015-03-03
Renate Scheidler (University Calgary)
Algebraic geometry codes are obtained from certain types of curves over finite fields. Since the length of such a code is determined by the number of rational points on the curve, it is desirable to use curves with as many rational points as possible. We investigate a certain class of Artin-Schreier curves with an unusually large number of automorphisms. Their automorphism group contains a large extraspecial subgroup. Precise knowledge of this subgroup makes it possible to compute the zeta functions of these curves. As a consequence, we obtain new 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, Padmavathi Srinivasan and Christelle Vincent.

• 2015-02-10
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.

• 2015-02-03
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-key cryptography. If $\G$ is an abelian group (written additively), then the Diffie–Hellman protocol in $\G$ is composed of four computations in the form $P \longmapsto [m]P = \underbrace{P + \cdots + P}_{m \text{ times}}$ for various points $P$ and integers $m$; optimising this scalar multiplication operation is therefore crucial.

In practice, the most efficient contemporary Diffie–Hellman implementations are based on elliptic curves, or Jacobians of genus 2 curves. 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 and speed up the protocol, identifying $P$ with $-P$ (formally, we are working 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 reference implementation 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 use particularly efficient formulae developed by the Chudnovskys, and popularized in cryptography by Gaudry.

Recent years have seen renewed interest in the Gallant–Lambert–Vanstone (GLV) technique for computing $[m]P$. Here, we suppose our elliptic curve (or our genus 2 Jacobian) has an efficiently computable non-integer endomorphism $\phi$, which when applied to elements of $\G$ acts like $[\lambda]$ (for some large eigenvalue $\lambda$). Suppose we want to compute $[m]P$: first we use the Euclidean algorithm 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 size of $m$. In practice, $a$ and $b$ have half the bitlength of $m$, which means that GLV and its variants can offer us a significant speedup.

In this talk, we will discuss the adaptation of GLV techniques to $x$-coordinate-only and Kummer surface systems. On the practical side, we will present some experimental results for a new elliptic-curve based implementation. On the more theoretical side, we will present some new formulae for Kummer surface systems with explicit real multiplication endomorphisms.

• 2015-01-27

The complex multiplication method is well-known for elliptic curves, where it may be used to construct curves used in primality proofs or to implement crytosystems, in particular pairing-based ones. A similar approach is possible for abelian surfaces, that are Jacobians of genus 2 curves, with considerable number theoretic complications. I describe an algorithm using complex floating point approximations with an asymptotically optimal running time, that is, quasi-linear in the size of the class polynomials produced as output. Our implementation has been used to carry out parallelised record computations and I present experimental data.

(joint work with Emmanuel Thomé)

• 2014-12-09
Alain Couvreur (INRIA & LIX, École Polytechnique)

Le schéma de McEliece est un schéma de chiffrement basé sur les codes correcteurs d’erreurs dont la sécurité repose sur la difficulté à décoder un code aléatoire. Parmi les différentes familles de codes algébriques proposées pour ce schéma, les codes de Goppa classiques sont les seuls à résister à toutes les attaques algébriques, et ce, depuis près de 35 ans. Dans cet exposé, je présenterai une attaque d’un genre nouveau, dite “par filtration” qui permet de retrouver la structure d’un code de Goppa “sauvage” (Wild Goppa code) construit à partir d’une extension de corps quadratique. Cette attaque consiste à utiliser des propriétés multiplicatives du code pour en calculer une filtration (i.e. une famille de sous-codes emboités) dont chaque élément est un code de Goppa classique.

Les propriétés algébriques de cette filtration permettent ensuite de retrouver entièrement la structure du code utilisé comme clé publique. Cette attaque a été implémentée en Magma et permet de casser en moins d’une heure des clés proposées par Bernstein, Lange et Peters dont la sécurité était estimée supérieure à 128 bits (Wild McEliece, SAC 2010). Depuis l’introduction du schéma de McEliece, c’est la première attaque polynomiale sur des codes de Goppa classiques n’ayant aucune symétrie apparente.

(Travail commun avec Ayoub Otmani et Jean-Pierre Tillich)

• 2014-12-02

A well-known result by Liouville shows that some elementary functions of a real or complex variable does not admit elementary antiderivatives, the usual example being $\exp(-x^2)$. In 1968, Risch gave an algorithm to decide if an elementary function admit an elementary antiderivative. Elementary functions can be defined in term of differentials fields which allow a natural definition over fields of finite characteristic. We discuss the problem of elementary antiderivative in this context, and we extent it to elementary solutions to linear differential equations.

• 2014-11-25
A Pari/GP package for computing L-functions.

Based on an idea of Pascal Molin, we describe a GP script for computing with L-functions of any reasonable degree. Most of the talk will be computer demonstrations of examples. The audience can bring their own favourite L-functions, as long as they are easy to implement and most importantly that their conductor be not too large. This will enable me to add to the examples that I will present, and/or find bugs.

• 2014-10-24
Euler systems from special cycles on unitary Shimura varieties and arithmetic applications

We construct a new Euler system from a collection of special 1-cycles on certain Shimura 3-folds associated to $\mathrm{U}(2,1) \times \mathrm{U}(1,1)$ and appearing in the context of the Gan–Gross–Prasad conjectures. We study and compare the action of the Hecke algebra and the Galois group on these cycles via distribution relations and congruence relations obtain adelically using Bruhat–Tits theory for the corresponding buildings. If time permits, we explain some potential arithmetic applications in the context of Selmer groups and the Bloch–Kato conjectures for Galois representations associated to automorphic forms on unitary groups.

• 2014-10-21
Isogeny graphs with maximal real multiplication

An isogeny graph is a graph whose vertices are principally polarized abelian varieties and whose edges are isogenies between these varieties. In his thesis, Kohel described the structure of isogeny graphs for elliptic curves and showed that one may compute the endomorphism ring of an elliptic curve defined over a finite field by using a depth first search algorithm in the graph. In dimension 2, the structure of isogeny graphs is less understood and existing algorithms for computing endomorphism rings are very expensive. We fully describe isogeny graphs of genus 2 jacobians, with maximal real multiplication. Over finite fields, we derive a depth first search algorithm for computing endomorphism rings locally at prime numbers, if the real multiplication is maximal. To the best of our knowledge, this is the first DFS-based algorithm in genus 2. This is joint work with Emmanuel Thomé.

• 2014-10-07
Calcul des polynômes modulaires en genre 2

Nous nous proposons dans un premier temps de décrire les travaux de Régis Dupont (datant de 2006) quant au calcul des polynômes modulaires en genre 2. Ces polynômes dépendent des invariants d’Igusa, qui sont une généralisation de la fonction $j$ dans le genre 1, et permettent d’obtenir toutes les variétés abéliennes isogènes à une variété abélienne donnée. Dans un second temps, nous expliquerons comment généraliser ces polynômes à d’autres invariants, comment les calculer et décrirons certaines de leurs propriétés, notamment le lien entre le dénominateur d’un coefficient du polynôme modulaire et les surfaces de Humbert.

• 2014-09-30
Chloe Martindale (University of Leiden / IMB)

We describe an algorithm for computing an analogue of the modular polynomial for elliptic curves, for principally polarised (p.p.) abelian varieties with real multiplication (RM). Given a p.p. abelian variety with RM by $\mathcal{O}_{F}$, where $\mathcal{O}_{F}$ is the maximal order in a totally real number field $F$, for any totally positive prime $\mu$ in $\mathcal{O}_{F}$, one can find a “$\mu$-isogenous” p.p. abelian variety with RM by $\mathcal{O}_{F}$. We describe an algorithm to compute a birational model for an algebraic variety which parametrises $\mu$-isogeny classes of p.p. abelian varieties with RM by $\mathcal{O}_{F}$.

This is work supervised by Marco Streng.

• 2014-09-23
Yuri Bilu and Bill Allombert (imb)


In 1998 Yves André proved that a non-special (the notion will be defined during the talk) irreducible plane curve ${F(x_1,x_2)=0}$ may have only finitely many CM-points. This was the first non-trivial contribution to the celebrated André-Oort conjecture.

Relying on recent ideas of Lars Kühne, we obtain a very explicit version of this result for straight lines defined over $\Q$: with obvious’’ exceptions, a CM-point cannot belong to such a line. Kühne himself proved this for the line ${x_1+x_2=1}$.

I will talk briefly about software aspects, and give a summary of two topics covered in my thesis: rigorous high-precision computation of the Hurwitz zeta function, and asymptotically fast provable computation of the integer partition function $p(n)$.