Responsables : Elena Berardini, Léo Poyeton.
Étant donné une période w d'une variété abélienne A (définie sur un corps de nombres k), un théorème de Wüstholz affirme que le plus petit sous-espace vectoriel de l'espace tangent à A, défini sur une clôture algébrique de k, contenant w, est l'espace tangent d'une sous-variété abélienne A_w. Un théorème des périodes donne une majoration du degré de A_w, degré relatif à un plongement projectif de A. Les premières bornes ont été obtenues par Masser et Wüstholz dans les années 90. Ces énoncés permettent d'estimer le degré de l'isogénie minimale entre deux courbes elliptiques isogènes.
Dans cet exposé, nous présenterons de nouveaux résultats qui améliorent les bornes connues jusqu'alors. Il s'agit d'un travail en commun avec Gaël Rémond.
On apprend à l'école comment ajouter ou multiplier deux entiers. La division euclidienne et son application au calcul du PGCD viennent ensuite, et, plus tard, la multiplication des polynômes, puis des matrices. Pour chacun de ces problèmes, la méthode apprise à l'école est la plus facile à expliquer et la plus commode lorsque l'on traite des données de petite taille. Mais, d'un point de vue asymptotique, la méthode naïve n'est pas la meilleure, sauf pour l'addition. Pour multiplier deux nombres entiers, par exemple, il existe des algorithmes quasi-optimaux, c'est-à-dire des méthodes de calcul qui ne demandent pas (beaucoup) plus de temps qu'il n'en faut pour écrire le résultat. On ne peut donc espérer de meilleurs algorithmes. Ces méthodes de multiplication rapide utilisent la transformée de Fourier discrète. Inventées dans les années 1970, elles se sont répandues grâce à la micro-informatique et aux logiciels de calcul formel. Quant à la multiplication des matrices, Strassen et d'autres ont proposé depuis 1969 des méthodes théoriquement plus rapides que la méthode standard; mais on ignore s'il existe des algorithmes optimaux: multiplier deux matrices est aujourd'hui bien plus lent que de recopier le résultat. Majorer le rang du tenseur de multiplication des matrices est une question importante et difficile. Cohn et Umans on récemment reformulé cette question en termes de combinatoire et de représentations de groupes finis.
Dans la première partie de mon exposé je présenterai quelques uns de ces problèmes importants de complexité algébrique.
Je présenterai ensuite un travail commun avec Reynald Lercier, qui donne un algorithme quasi-optimal pour produire des polynômes irréductibles sur un corps fini, à l'aide de la théorie de Kummer des courbes elliptiques. La même question pour les entiers premiers reste ouverte.
Nous décrivons un algorithme de calcul de couplages utilisant les fonctions thêta. Puis nous revisitons divers techniques d'accélération de ces calculs (couplage de Ate, couplage optimal). Un bénéfice de notre approche est sa généralité puisqu'elle permet de calculer très naturellement des couplages sur toutes les variétés abéliennes. Nous obtenons aussi des gains de performance.
Travail commun avec Damien Robert
Considérons les groupes de Bianchi: Ce sont PSL_2(A) avec A l'anneau d'entiers d'un corps quadratique imaginaire. Un modèle pour leur espace classifiant pour actions propres, est l'espace hyperbolique à trois dimensions, sur lequel ils agissent comme mouvements engendrés par des translations et des rotations.
Un programme en Pari/GP qui vient d'être réalisé, nous permet d'obtenir des domaines fondamentaux pour cette action; et nous soutient dans les calculs de la K-homologie équivariante des groupes de Bianchi par une suite spectrale.
Baum et Connes construisent un homomorphisme de la K-homologie équivariante d'un groupe à la K-théorie de sa C^*-algèbre réduite; et postulent qu'il soit un isomorphisme.
Leur conjecture est vérifiée pour les groupes de Bianchi, ce qui nous permet d'obtenir cette dernière K-théorie des opérateurs, qui ne serait pas accessible directement pour les groupes de Bianchi.
The ``learning with errors'' (LWE) problem is to distinguish random linear equations, which have been perturbed by a small amount of noise, from truly uniform ones. The problem has been shown to be as hard as worst-case lattice problems, and in recent years it has served as the foundation for a plethora of cryptographic applications.
Unfortunately, these applications are rather inefficient due to an inherent quadratic overhead in the use of LWE. After a short introduction to the area, we will discuss recent work on making LWE and its applications truly efficient by exploiting extra algebraic structure. Namely, we will define the ring-LWE problem, and prove that it too enjoys very strong hardness guarantees. We will mention some recent cryptographic applications in this line of work.
Based on joint work with Vadim Lyubashevsky and Chris Peikert.
In this talk, we will discuss the following problem posed by Makoto Matsumoto and Akio Tamagawa concerning monodromic fullness of hyperbolic curves.
For a hyperbolic curve X over a number field, are the following three conditions equivalent?
(A) For any prime number l, X is quasi-l-monodromically full.
(B) There exists a prime number l such that X is l-monodromically full.
(C) X is l-monodromically full for all but finitely many prime numbers l.
The property of being (quasi-)monodromically full may be regarded as an analogue for hyperbolic curves of the property of not admitting complex multiplication for elliptic curves, and the above equivalence may be regarded as an analogue for hyperbolic curves of the following result concerning the Galois representation on the Tate module of an elliptic curve over a number field proven by Jean-Pierre Serre.
For an elliptic curve E over a number field, the following four conditions are equivalent:
(0) E does not admit complex multiplication.
(1) For any prime number l, the image of the l-adic Galois representation associated to E is open.
(2) There exists a prime number l such that the l-adic Galois representation associated to E is surjective.
(3) The l-adic Galois representation associated to E is surjective for all but finitely many prime numbers l.
In this talk, I will present some results concerning the above problem in the case where the given hyperbolic curve is of genus zero. In particular, I will give an example of a hyperbolic curve of type (0,4) over a number field which satisfies (C) but does not satisfy (A).
In english : The use of pairings in cryptology has allowed to implement powerful protocols like Identity Based Encryption in an efficient way. To date, the only cryptographically secure known pairings come from Abelian Varieties. Miller's algorithm allows to compute pairings efficiently on Jacobians of hyperelliptic curves. In a paper with David Lubicz, we described an algorithm using theta functions to compute the Weil and Tate pairing on any abelian variety.
Since theta coordinates are faster than Mumford coordinates for hyperelliptic of genus 2 curves, this algorithm is particularly interesting in this case. However for cryptographic applications of pairings, one can use faster pairings derived from the Tate pairing (optimal ate). In this talk, we will describe our pairing algorithm, and how we can adapt it to the case of the ate and optimal ate pairing.
Pirillo et Varricchio ont posé en 1994 la question suivante : existe-t-il une suite d'entiers bornée telle que deux blocs consécutifs de même longueur n'aient jamais la même somme ? Ce problème fait partie des problèmes d'évitabilité de motifs dans les mots infinis, le motif à éviter étant ici appelé carré additif. Il est encore ouvert à ce jour.
Nous considérons dans cet exposé le cas des cubes additifs, c'est à dire du motif formé non pas de deux mais de trois blocs consécutifs de même longueur et de même somme. Nous montrons au moyen d'une construction explicite qu'il est évitable sur un alphabet à 4 éléments. Nous nous demandons ensuite dans quelle mesure une construction similaire serait possible pour les carrés additifs (dans l'hypothèse où la réponse à la question de Pirillo et Varricchio serait positive).
Travail en collaboration avec J. Currie, L. Schaeffer et J. Shallit. http://arxiv.org/abs/1106.5204
Dans ce travail, en collaboration avec Jean-Marc Couveignes, nous nous intéressons aux corps des modules et de définition de certaines variétés. Plus précisément, on souhaite trouver des exemples de variétés qui ne sont pas définies sur leur corps des modules. Partant du fait que de telles obstructions à la descente existent dans la catégorie des revêtements de courbes, nous produisons d'autres exemples dans certaines catégories de surfaces puis dans la catégorie des courbes lisses.
Soient G un groupe fini et A un ensemble de générateurs de A. Le diamètre diam(Gamma(G,A)) du graphe de Cayley Gamma(G,A) est le l minimal tel que chaque élément de G peut être écrit comme un produit de longueur <=l d'éléments de A et A^{-1}. La question est : comment borner diam(G):= max_A diam(Gamma(G,A)) ?
Il a été conjecturé durant longtemps que le diamètre du groupe symétrique sur $n$ lettres est borné par une puissance de n, mais la meilleure borne connue était exponentielle en sqrt(n log n). Nous avons prouvé une borne quasi polynomiale :
diam(G) = exp(O(log n)^4 log log n) = exp((log log |G|)^O(1)).
Par des résultats standard, ceci implique la même borne pour tous les groupes de permutations transitifs.
Travail commun avec A. Seress.
Un résultat célèbre de Faltings peut être reformulé pour les courbes elliptiques comme suit : Soit K un corps de nombres, et soit E une courbe elliptique sur K. Soit S un ensemble d'idéaux premiers de l'anneau des entiers de K de densité un et de bonne réduction pour E. Alors la classe de K-isogénie de E est déterminée par la fonction qui à un idéal premier p dans S associe la taille #E (k_p) du groupe des points de E sur le corps résiduel.
Nous prouvons qu'il suffit de regarder les nombres premiers qui divisent la taille. Nous avons également remplacé E(k_p) par l'image du groupe de Mordell-Weil via la réduction modulo p, et résolu le problème analogue pour une large classe de variétés abéliennes. Il s'agit d'un travail en commun avec Chris Hall.
NTRUEncrypt, proposé en 1996 par Hoffstein, Pipher et Silverman, est le schéma de chiffrement asymétrique le plus efficace, parmi ceux dont la sécurité repose sur la difficulté de problèmes portant sur les réseaux euclidiens. Malheureusement, depuis sa création, sa sécurité a régulièrement été mise en doute. Nous montrerons comment modifier NTRUEncrypt pour qu'il admette une preuve de sécurité contre les attaques à clair choisi, sous l'hypothèse qu'il est difficile de trouver des vecteurs courts dans des réseaux correspondant à des idéaux arbitraires des anneaux d'entiers de corps cyclotomiques. La preuve repose sur les travaux récents de [Lyubashevsky et al., Eurocrypt'10] sur la difficulté du problème Ring-LWE. Notre principale contribution est de démontrer que si les polynômes de petites hauteurs correspondant à la clé secrète sont tirés suivant une loi Gaussienne discrète, alors la distribution de la clé publique, qui est leur quotient modulo un entier, est statistiquement proche de la loi uniforme sur son domaine.
Travail en commun avec Ron Steinfeld
Le titre, peut-être un peu facétieux, est choisi pour souligner le fait que la conjecture de Littlewood classique, en Approximation Diophantienne simultanée, ainsi que la conjecture mixte (mêlant approximation et divisibilité), proviennent de problèmes extrêmement simples, qui deviennent difficiles, voire insolubles, en renforçant simplement une condition. Sous ce titre, je proposerai un "survey" de résultats récents de divers auteurs sur ces problèmes, ainsi que sur la conjecture duale de la conjecture de Littlewood.