# 2019/2020

• 2020-01-28
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-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-10
Développeurs LFANT (IMB)
Hacking session
• 2019-11-26
Alice Pellet-Mary (ÉNS de Lyon)
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-19
Maria Dostert (EPFL)
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
HDR defense: Cryptographie basée sur les corps quadratiques: cryptanalyse, primitives et protocoles
• 2019-11-05
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
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
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
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
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
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)
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.