2013/2014
- 2014-07-10Kamal Khuri Makdisi (American University of Beirut)On divisor group arithmetic for typical divisors on curves
Cet exposé portera sur l’utilisation des algorithmes de calcul dans les Jacobiennes présentés dans http://arxiv.org/abs/math/0409209 dans le cas générique (avec des diviseurs de degrés plus petits), et présentera des critères concrets suffisants pour certifier que le résultat du calcul est bon.
- 2014-07-08Kamal Khuri Makdisi (American University of Beirut)Moduli interpretation of Eisenstein series
Talk based on the preprint http://arxiv.org/abs/0903.1439
- 2014-06-03Gaëtan Bisson (University of French Polynesia)On polarised class groups of orders in quartic CM-fields
We give an explicit characterisation of pairs of orders in a quartic CM-field that admit the same polarised ideal class group structure. This generalises a simpler result for imaginary quadratic fields. We give applications to computing endomorphism rings of abelian surfaces over finite fields, and extending a completeness result of Murabayashi and Umegaki to a list of abelian surfaces over the rationals with complex multiplication by arbitrary orders. This is joint work with Marco Streng.
- 2014-05-20Alina Dudeanu (EPFL)
We present an algorithm for computing isogenies of prime degree between Jacobians of smooth curves of genus two defined over finite fields. We aim at applying this algorithm to problems that are encountered in curve-based cryptography. In the genus one case, one of the goals is to construct with high probability by using random walks an isogeny between two arbitrary classes of isomorphic curves that belong to the same isogeny class. Another goal is to study the random self reducibility of the Discrete Logarithm Problem for isomorphism classes within the same isogeny class and extend the Weil descent attack to a larger family of curves. We could hope for similar positive results in the genus two case if given the proper input for the isogeny computation algorithm, we are able to obtain fast enough, both the isogeny map and the target isogenous Jacobian (unique up to an isomorphism).
- 2014-05-13Henri Cohen (imb)The aim of this talk is to give a number of very useful recipes for numerical computations to high accuracy (typically from $38$ to $1000$ decimal digits) for definite integration, summation, and extrapolation. Many of these methods are fundamental in experimental number theory.
- 2014-04-08Monique Thonnat (Inria Bordeaux Sud-Ouest)Visite de la directrice du centre Inria Bordeaux
- 2014-04-01Amalia Pizarro-Madariaga (Valparaíso)Estimations for the Artin conductor
In this talk, I will show two methods to improve Odlyzko’s lower bound for the Artin conductor. We will begin by translating Odlyzko’s methods to the language of explicit formulas, which yields an initial improvement on Odlyzko’s bound.
Then we introduce a technique to take advantage of the contribution of the primes to further improve the lower bounds.
- 2014-03-31Oriol Serra (UPC, Barcelone)Algebraic Removal Lemma
The removal lemma is a combinatorial result which, in its simpler form, says that a graph with $n$ vertices and $o(n^3)$ triangles can be made triangle free by deleting $o(n^2)$ edges. It was used by Ruzsa and Szemerédi to provide a simple proof of Roth’s theorem on $3$-term arithmetic progressions in dense sets of integers. An analogous algebraic statement was formulated by Green in terms of solutions of linear equations in abelian groups. In the talk I will report on some contributions made jointly with Dan Král’ and Lluís Vena to this algebraic version for linear systems in abelian groups and some consequences in arithmetic Ramsey theory. The latter include a version of Szemerédi theorem on arithmetic progressions in dense sets of finite abelian groups.
- 2014-03-24Emmanuel Thomé (Nancy)Un algorithme quasi-polynomial de calcul de logarithme discret en petite caractéristiqueThe difficulty of computing discrete logarithms in fields $\mathbb F_{q^k}$ depends on the relative sizes of $k$ and $q$. Until recently all the cases had a sub-exponential complexity of type $L(1/3)$, similar to the factorization problem. In 2013, Joux designed a new algorithm with a complexity of $L(1/4+\epsilon)$ in small characteristic. In the same spirit, we propose another heuristic algorithm that provides a quasi-polynomial complexity when $q$ is of size at most comparable with $k$. By quasi-polynomial, we mean a runtime of $n^{O(\log n)}$ where $n$ is the bit-size of the input. For larger values of $q$ that stay below the limit $L_{q^k}(1/3)$, our algorithm loses its quasi-polynomial nature, but still surpasses the Function Field Sieve.
- 2014-03-21Bertrand Maury (Paris-Sud)Arbre bronchique infini et entiers dyadiques
$ \newcommand{\Z}{\mathbb{Z}} $ L’écoulement de l’air dans l’arbre bronchique peut, en première approximation, être décrit par des équations discrètes écrites sur un arbre abstrait résistif, qui respecte la structure dyadique de l’arbre réel.
Ce système, qui implique les pressions définies aux noeuds du réseau ainsi que les flux qui traversent les arêtes, a la structure d’un problème de Darcy (qui décrit les écoulements en milieu poreux) ou, en éliminant les flux, d’un problème de Laplace (discret) sur la pression. Ventiler consiste à exercer une pression aux niveau des feuilles de l’arbres, pour récupérer des flux en retour, ce qui prend la structure d’un problème dit de Dirichlet-Neuman. Du fait de la régularité de la progression des caractéristiques géométriques au fil des générations, établi par des mesures expérimentales, il est tentant de faire tendre le nombre de générations, égal à 23 dans la réalité, vers l’infini (d’extrapoler l’arbre réel en quelque sorte), pour construire un objet idéalisé respectant la structure des phénomènes auxquels on s’intéresse.
Se pose alors, parmi d’autres, la question de la définition d’un champ de pression sur l’espace des bouts de cet arbre.
Nous préciserons comment l’identification de la génération $n$ à $\Z/2^n\Z$, et de l’espace des bouts à la limite projective de ces ensembles, ie. l’anneau des entiers dyadiques $\Z_2$, permet de donner une structure naturelle à cet arbre résistif infini. En particulier, la tranformée de Fourier sur $\Z_2$ permet de caractériser la régularité des champs de pression aux bouts de l’arbre. De plus, l’opérateur de “ventilation” (qui à un champ de pression associe l’ensemble des flux correspondants) prend sous certaines hypothèses la forme d’un simple opérateur de convolution.
(Travail en collaboration avec F. Bernicot et D. Salort)
- 2014-03-18Pınar Kılıçer (Leiden+IMB)
The Gauss class number one problem for imaginary quadratic fields is equivalent to finding all elliptic curves over the rationals with complex multiplication. I will quickly explain the relation between the class number one problem and the elliptic curves over the rationals. Then I will give the analogue of the class number one problem for genus-2 curves with CM and sketch its solution.
- 2014-03-04John Boxall (Caen)
Pendant cet exposé, nous proposerons des heuristiques concernant la distribution asymptotique des variétés abéliennes sur les corps primaires adaptées à la cryptographie à couplage. Il s’agit d’un travail en commun avec David Gruenewald.
- 2014-02-20Eduardo Friedman (Universidad de Chile)Cône de Shintani et degré topologique
- 2014-02-14Nicolas Delfosse (Montreal)Une introduction au calcul quantique tolérant aux fautes
Alors que les composants classiques sont suffisamment fiables, chaque manipulation d’un bit quantique a une probabilité non négligeable d’introduire une erreur. Ceci rend l’application d’une porte quantique délicate. Je présenterai différentes techniques permettant de transformer un circuit quantique en un circuit quantique tolérant aux fautes.
- 2014-02-04Marc Munsch (IMB)Moments des fonctions thêta
Pour $\chi$ un caractère de Dirichlet modulo $q$, on définit sa fonction thêta associée $\theta(x,\chi):=\sum_{n\geq 1}\chi(n)e^{-\frac{\pi n^2x}{q}}$. Elle intervient habituellement dans la preuve de l’équation fonctionnelle de $L(s,\chi)$. Le calcul de l’asymptotique des moments des fonctions $L$ est un problème classique de théorie analytique des nombres étudié notamment afin de montrer que $L(1/2,\chi)\neq 0$ pour “beaucoup” de caractères. Il est conjecturé de façon analogue que $\theta(1,\chi)\neq 0$. De rares contre-exemples ont été découverts par H. Cohen et D. Zagier mais la conjecture reste ouverte dans le cas d’un module premier. On étudie les moments des fonctions thêta dans deux familles de caractères:
- Les caractères modulo $p$ un nombre premier.
- Les caractères réels primitifs de conducteur $0 < D \leq X$.
Cela nous permet d’en déduire des résultats de non-annulation pour la fonction thêta allant dans le sens de la conjecture.
(Rattrapage de l’exposé au séminaire de théorie des nombres pour les participants aux ateliers Pari/GP.)
- 2014-01-30Hartmut Monien (Physikalisches Institut der Universität Bonn)Calculating rational coverings for subgroups of ${\rm PSL}_{2}\left(\mathbb{Z}\right)$ efficiently
A powerful tool for investigating these non-congruence subgroups was introduced by Kulkarni in 1991 and is now known as Farey symbols. With the help of the Farey symbols it is possible to substantially extend methods from analytic number theory. We will discuss three methods. The first is a generalisation of a numerical algorithm originally due to Hejhal. The second approach is based on a series of papers by Rademacher and Zuckerman which turned out to be very useful in the recent studies of the properties of Mock modular forms. A third surprisingly simple and powerful method was recently discovered by us. We will present some interesting non-congruence subgroups with interesting Galois groups.
- 2014-01-28Hartmut Monien (Physikalisches Institut der Universität Bonn)Zeta values, random matrix theory and Euler-MacLaurin summation
Gaussian quadrature is a well known technique for approximating integrals. In this talk we generalise these ideas to infinite sums in general. For a broad class of functions the error of Gaussian summation is exponentially small as a function of the number of summation points. The corresponding new orthogonal polynomials have interesting asymptotic properties, which are connected to Hankel determinants of Zeta values. We will present a random matrix theory which allows to connect the asymptotics of these determinants to a Riemann-Hilbert problem and explain its connection to the Euler-MacLaurin summation.
- 2014-01-21Barinder Banwait (imb)Local-Global for Isogenies on Elliptic Curves
If an elliptic curve $E$ over a number field $K$ admits a $K$-rational $l$-isogeny, for prime $l$, then its base-change to every completion will certainly have a rational $l$-isogeny. But what about the converse? That is, do isogenies on elliptic curves over number fields satisfy a local-global principle? The answer is no: as shown by Andrew Sutherland; there is (precisely one) elliptic curve over $\mathbb{Q}$ which fails this principle. In this talk I’ll discuss my (incomplete) work in finding all such failures over all quadratic fields.
- 2014-01-09Frédérique Oggier (NTU, Singapour)Le codage pour le stockage distribué de données
- 2013-12-13Soline Renner (imb)High-Order Masking by Using Coding Theory and its Application to AES
To guarantee that some implementation of a cryptographic scheme is secure against side channel analysis, one needs to formally prove its leakage resilience. A relatively recent trend is to apply methods pertaining to the field of Multi-Party Computation: in particular this means applying secret sharing techniques to design masking countermeasures. It is known besides that there is a strong connection between secret sharing schemes and error-correcting codes, namely every linear code gives rise to a linear secret sharing scheme. However, the schemes mostly used in practice are the so-called Boolean masking and Shamir’s secret sharing scheme and it is widely thought that they are the most adapted to masking techniques because they correspond to MDS codes that are in some sense optimal. We present alternative masking techniques that rely on {\em non-MDS} linear codes: these codes are non-binary but have an underlying binary structure which is that of a \textit{self-orthogonal binary} code. Their being non-MDS is compensated by the fact that the distributed multiplication procedure is more efficient than with MDS codes due to an efficient encoding process and that the distributed computation of squares comes at almost no cost.
In protecting AES against high-order side channel analysis, this approach is more efficient than methods using Shamir’s secret sharing scheme and competitive with Boolean masking.
- 2013-12-10Bill Allombert (imb)Minimums de formes quadratiques
$ \newcommand{\Disc}[1]{ \Delta_{#1} } $ Soit f une forme quadratique à coefficients entiers à deux variables, à discriminant positif non carré. On note $\min{f}$ le minimum de $f$ sur $\mathbb{Z}^2-\{0,0\}$.
Les formes $f$ vérifiant $\Disc{f} < 9\min{f}^2$ sont décrites par les nombres de Markoff qui sont les entiers $m$ tel que l’équation $x^2+y^2+m^2=3xym$ admet une solution entière. Elles vérifient $\Disc{f} = 9\min{f}^2-4$.
Dans cet exposé, pour tout nombre de Markoff $m$, nous associons aux solutions de l’équation $x^2+y^2-m^2=3xym$ des formes vérifiant $\Disc{f} = 9\min{f}^2+4m^2$. Expérimentalement ce sont les formes tel que $\Disc{f}/\min{f}^2$ est le plus proche de $9$ par excès.
Ces problèmes sont liées à des questions d’approximation de nombres quadratiques réels par des rationnels, de fractions continues, de minorations de normes d’idéaux représentant des classes d’idéaux dans des ordres quadratique réels, et à certains sous-groupes de $\mathrm{SL}_2(\mathbb{Z})$.
- 2013-11-29Renaud Coulangeon (imb)Théorie de Bass-Serre des graphes de groupes et application au calcul de la présentation du groupe d'unité d'une algèbre semi-simple (2).
- 2013-11-22Mate Matolcsi (Budapest)Maximal cliques in Paley graphs
For infinitely many primes $p = 4k + 1$ we give a slightly improved upper bound for the maximal cardinality of a subset $B$ of $Z_p$ such that the difference set $B - B$ contains only quadratic residues. Namely, instead of the “trivial” bound $|B| <= \sqrt{p}$ we prove $|B| <= \sqrt{p} - 1$, under suitable conditions on $p$. The new bound is valid for approximately three quarters of the primes $p = 4k + 1$. Joint result with C. Bachoc and I. Z. Ruzsa.
- 2013-11-22Renaud Coulangeon (imb)Théorie de Bass-Serre des graphes de groupes et application au calcul de la présentation du groupe d'unité d'une algèbre semi-simple (1).
- 2013-11-12Damien RobertOn isogenies and polarisations.
Let $(A,L)$ be a polarised abelian variety, and $K$ a finite kernel of $A$. A natural question is how one can compute the isogeny $f: A \mapsto A/K$. When $A$ is an elliptic curve, Vélu’s formulas give an explicit form of the isogeny $f$. In this talk, we describe how the theory of theta functions allows to generalize Vélu’s formulas to abelian varieties. When $K$ is not a maximal isotropic kernel, for instance when $K$ is cyclic, the algorithm uses the action of the symmetric endomorphisms (under the Rosatti involution) on the Néron-Séveri group.
This is a joint work with Gaëtan Bisson, Romain Cosset, Alina Dudeanu, Dimitar Jetchev and David Lubicz.
- 2013-11-05Renaud Coulangeon (imb)Algorithmes de Voronoi et groupes d'unités
On présentera certains aspects d’un travail en cours avec Gabriele Nebe (RWTH Aachen), sur le calcul du groupe des unités d’un ordre maximal d’une algèbre semi-simple sur Q. Les méthodes utilisées reposent sur une combinaison de la théorie de Bass-Serre des “graphes de groupes” et de différents avatars de l’algorithme de Voronoi pour les formes quadratiques. L’exposé portera plus particulièrement sur la description d’un algorithme pour le calcul des classes de conjugaison des sous-groupes finis maximaux d’un tel groupe d’unités.
- 2013-10-25Gilles ZémorGraphes sur des surfaces et codes quantiques
- 2013-10-04Sylvia BianchiPolyhedra associated with identifying codes
- 2013-09-24Hamish Ivey-Law (imb)
Abstract: We will consider a type of Riemann-Roch problem for divisors on certain algebraic surfaces. Specifically we consider algebraic surfaces arising as the square or the symmetric square of a hyperelliptic curve of genus at least two over an (almost) arbitrary field. The main results are a decomposition of the spaces of global sections of certain divisors on such surfaces and explicit formulæ for the dimensions of the spaces of sections of these divisors. We conclude by presenting an algorithm which generates a basis for the space of global sections of such a divisor.
Résumé: Nous considérerons un type de problème de Riemann-Roch pour les diviseurs sur certaines surfaces algébriques. Plus précisément, nous analysons les surfaces algébriques qui émanent d’un produit ou d’un produit symétrique d’une courbe hyperelliptique de genre supérieur à un sur un corps (presque) arbitraire. Les résultats principaux sont une décomposition des espaces de sections globales de certains diviseurs sur telles surfaces et des formules explicites qui décrivent les dimensions des espaces de sections de ces diviseurs. Pour conclure nous présenterons un algorithme qui produit une base pour l’espace de sections globales d’un tel diviseur.
- 2013-09-13Henri Cohen (imb)Calculs sur les fonctions L
Je vais exposer un certain nombre de méthodes pour “calculer” sur les fonctions L, en particulier celles de degré $>= 3$. Je parlerai des différentes méthodes pour calculer efficacement leurs coefficients de Dirichlet, et j’introduirai les “motifs hypergéométriques”, qui fournissent très facilement des fonctions L de degré supérieur. Je parlerai ensuite des méthodes analytiques: transformées de Mellin inverses, équations fonctionnelles approchées, formules explicites de Weil.
Je terminerai par deux applications remarquables: la conjecture paramodulaire de Brumer-Kramer qui généralise très précisément aux surfaces abéliennes le théorème de modularité de Wiles, et les calculs extensifs de formes de Maass pour $\mathrm{SL}_n(Z)$ pour $n=2$, $3$, et $4$ effectués par Farmer et al.
- 2013-09-10Friedrich Panitz (Paderborn)An algorithm to enumerate quartic fields, after Bhargava.