IMB > Recherche > Séminaires

Séminaire de Théorie Algorithmique des Nombres

Responsable : Damien Robert

Page du séminaire

  • Le 22 avril 2008
  • Salle de Conference
    Karim Belabas
    Calcul de valeurs de fonctions L complexes I

  • Le 13 mai 2008
  • Salle de Conference
    Karim Belabas
    Calcul de valeurs de fonctions L complexes II

  • Le 29 mai 2008
  • Salle de Conference
    Pascal Molin
    Intégration numérique de fonctions analytiques

  • Le 3 juin 2008
  • Salle de Conference
    Henri Cohen
    Fractions continues pour la fonction Gamma incomplète I

  • Le 10 juin 2008
  • Salle de Conference
    Henri Cohen
    Fractions continues pour la fonction Gamma incomplète II

  • Le 30 septembre 2008
  • Salle de Conference
    Eduardo Friedman Santiago de Chile
    Lower bounds for regulators of number fields

  • Le 7 octobre 2008
  • Salle de Conference
    Henri Cohen
    Réciprocité cubique et équation de Mordell

  • Le 13 janvier 2009
  • Salle de Conference
    Eduardo Friedman Santiago de Chile
    Barnes' multiple Gamma and zeta functions\nand their application to totally real fields I

  • Le 20 janvier 2009
  • Salle de Conference
    Eduardo Friedman Santiago de Chile
    Barnes' multiple Gamma and zeta functions\nand their application to totally real fields II

  • Le 22 janvier 2009
  • Salle de Conference
    Eduardo Friedman Santiago de Chile
    Barnes' multiple Gamma and zeta functions\nand their application to totally real fields III

  • Le 3 février 2009
  • Salle de Conference
    Eduardo Friedman Santiago de Chile
    Barnes' multiple Gamma and zeta functions\nand their application to totally real fields IV

  • Le 4 mai 2009
  • Salle de Conference
    Jean-Paul Cerri
    Corps euclidiens: introduction

  • Le 12 mai 2009
  • Salle de Conference
    Jean-Paul Cerri
    Corps euclidiens: algorithmique. I

  • Le 19 mai 2009
  • Salle de Conference
    Jean-Paul Cerri
    Corps euclidiens: algorithmique. II

  • Le 19 juin 2009
  • Salle de Conference
    Luca de Feo Palaiseau
    Calcul d'isogénies en petite caractéristique
    Nous nous intéressons au problème de calculer explicitement une isogénieentre courbes elliptiques. Lorsque le degré de l'isogénie est inférieur à lacaractéristique du corps de base, les algorithmes CCR et de Atkin permettentun calcul aisé. Le cas où la caractéristique est inférieure au degré cherchéest beaucoup plus délicat à traiter et a donné lieu à de nombreuxalgorithmes. En nous appuyant sur les travaux récents d'É. Schost et del'orateur (Fast Arithmetics in Artin-Schreier Towers over Finite Fields. Toappear in ISSAC'09. ACM, 2009), nous présentons ici une version rapide del'algorithme de Couveignes (Computing l-isogenies using the p-torsion. inANTS' II, 59-65. Springer, 1996) et nous comparons les performances aveccelles des autres algorithmes connus.
  • Le 15 septembre 2009
  • Salle de Conference
    Andreas Enge
    Comptes rendus de SAC et ECC à Calgary

  • Le 22 septembre 2009
  • Salle de Conference
    Karim Belabas
    Programmer avec la bibliothèque Pari pour les nuls

  • Le 29 septembre 2009
  • Salle de Conference
    Karim Belabas
    The Cohen-Lenstra heuristics for finite Abelian groups\n(d'après Johannes Lengler)

  • Le 6 octobre 2009
  • Salle de Conference
    Jean-François Biasse
    An L(1/3) algorithm for ideal class group and regulator computation in\ncertain number fields
    We present an analysis of the complexity of the computation of the classgroup structure of a certain class of number fields. Our approach slightlydiffers from the one of Buchmann who proved that the complexity wasbounded by L(1/2) when the discrminant tends to infinity with a fixeddegree of the extension. We achieve the subexponential complexity L(1/3)when both the discriminant and the degree of the extension tend toinfinity using techniques due to Enge and Gaudry in the context ofalgebraic curves over finite fields.
  • Le 3 novembre 2009
  • Salle de Conference
    Henri Cohen
    Quelques calculs de sommes de Kloosterman et de fonctions L associées\naux variétés de Calabi-Yau. I

  • Le 6 novembre 2009
  • Salle de Conference
    Andreas Enge
    Invariants de classes (presque) sans réciprocité de Shimura
    Un invariant de classes est une valeur spéciale d'une fonction modulaire quiengendre algébriquement le corps de classes de Hilbert d'un corps quadratiqueimaginaire. Il peut être utilisé pour obtenir des courbes elliptiques àmultiplication complexe et donc à cardinal connu d'avance sur un corps fini,ce qui trouve des applications en cryptographie et pour les preuves deprimalité. Classiquement, la loi de réciprocité de Shimura est utilisée pourdémontrer qu'une valeur est invariant de classes et pour déterminer sesconjuguées algébriques, ce qui demande des calculs fastidieux au cas par cas.Schertz a donné une approche élégante qui encapsule la loi de réciprocité etpermet d'obtenir des preuves faciles pour des fonctions modulaires pour$Gamma^0(N)$ ayant un développement en $q$ rationnel. En même temps, il enrésulte une caractérisation facilement implantable des conjuguées.Dans le cadre du résultat de Schertz, je présente une généralisation auxfonctions multipliées par des racines de l'unité et donne une application àl'invariant de classes de Ramanujan.
  • Le 10 novembre 2009
  • Salle de Conference
    Henri Cohen
    Quelques calculs de sommes de Kloosterman et de fonctions L associées\naux variétés de Calabi-Yau. II

  • Le 17 novembre 2009
  • Salle de Conference
    Marco Streng Leiden
    Abelian surfaces admitting an (l,l)-endomorphism
    We give a classification of all principally polarized abeliansurfaces that admit an (l,l)-isogeny to themselves. We make theclassification explicit in the simplest cases l=1 and l=2 and show howto compute all abelian surfaces that occur.This research was done during an internship of the speaker at MicrosoftResearch (MSR). It is joint work with Reinier Bröker (MSR, currentlyBrown University) and Kristin Lauter (MSR).
  • Le 20 novembre 2009
  • Salle de Conference
    Gaëtan Bisson Nancy
    Calcul des anneaux d'endomorphismes des variétés abéliennes\nsur les corps finis
    Les anneaux d'endomorphismes des courbes elliptiques (et, plus généralement,des variétés abéliennes) définies sur les corps finis sont d'importantsobjets,autant pour leur rôle dans la « méthode CM » (pour construire des variétésde cardinal donné) que pour leur pertinence en cryptographie.Nous présenterons une méthode permettant de les calculer en tempssous-exponentiel en la taille du corps de base, étant ainsi (en pratiquecomme en théorie) plus rapide que les précédentes ; elle exploite l'actiondu groupe de classe sur le graphe d'isogénie, empruntant quelques idéesaux travaux de Kohel. Dans le cas elliptique, il s'agit de travaux communsavec Andrew Sutherland ; dans le cas général, ce sont des travaux en cours.
  • Le 24 novembre 2009
  • Salle de Conference
    Andreas Enge
    Multiplication complexe de courbes elliptiques:\napplications cryptologiques

  • Le 8 décembre 2009
  • Salle de Conference
    Andreas Enge
    Multiplication complexe de courbes elliptiques:\nconstruction de courbes à petit degré de plongement

  • Le 15 décembre 2009
  • Salle de Conference
    Andreas Enge
    Multiplication complexe de courbes elliptiques:\nalgorithmes à base d'approximations flottantes,\ncomplexité et implantation

  • Le 12 janvier 2010
  • Salle de Conference
    Pascal Molin
    Méthode des trapèzes et fonctions méromorphes I
    Intégration numérique par la méthode des fonctionsà décroissance doublement exponentielle, applicationau calcul de valeurs spéciales de fonctions L
  • Le 19 janvier 2010
  • Salle de Conference
    Pascal Molin
    Méthode des trapèzes et fonctions méromorphes II

  • Le 26 janvier 2010
  • Salle de Conference
    Henri Cohen
    Recherche de bons exemples pour la conjecture ABC et la conjecture\nde Hall I (d'apres Elkies et Calvo-Herranz-Saez)

  • Le 2 février 2010
  • Salle de Conference
    Henri Cohen
    Recherche de bons exemples pour la conjecture ABC et la conjecture\nde Hall II (d'apres Elkies et Calvo-Herranz-Saez)

  • Le 11 février 2010
  • Salle de Conference
    Damien Robert Nancy
    Calcul de pairings avec les fonctions thétas
    Dans cet exposé je rappellerai brièvement les définitions des classes depairings usuelles sur les variétés abéliennes (Weil, Tate, commutatorpairing).Je donnerai ensuite un algorithme pour calculer ces pairings grâce auxfonctions thétas, différent de l'algorithme usuel dû à Miller.
  • Le 12 février 2010
  • Salle de Conference
    Damien Robert Nancy
    Computing isogenies between abelian varieties
    Isogenies are an essential tool in Elliptic Curves cryptography,where they are used in a wide variety of area: fast point counting,complex multiplication methods... Vélu's formulas give an efficient methodfor computing such isogenies, but there were no known formulas for computingisogenies for hyperelliptic curves of higher genus, except in particuliarcases. In this talk, we will show how the framework of theta structures,developped by Mumford in 1967, allows us to give a generalization of Vélu'sformulas for any abelian variety. This is a joint work with David Lubicz.
  • Le 16 février 2010
  • Salle de Conference
    Eduardo Friedman Santiago de Chile
    Special values of Dirichlet series and Zeta integrals\nassociated to polynomials

  • Le 2 mars 2010
  • Salle de Conference
    Pieter Rozenhart
    Reduction theory of binary forms over polynomial rings I

  • Le 9 mars 2010
  • Salle de Conference
    Pieter Rozenhart
    Reduction theory of binary forms over polynomial rings II

  • Le 16 mars 2010
  • Salle de Conference
    Henri Cohen
    Sommes de Gauss, sommes de Jacobi, et comptage de points sur des\nhypersurfaces quasi-diagonales I

  • Le 23 mars 2010
  • Salle de Conference
    Henri Cohen
    Sommes de Gauss, sommes de Jacobi, et comptage de points sur des\nhypersurfaces quasi-diagonales II

  • Le 30 mars 2010
  • Salle de Conference
    Henri Cohen
    Sommes de Gauss, sommes de Jacobi, et comptage de points sur des\nhypersurfaces quasi-diagonales III

  • Le 6 avril 2010
  • Salle de Conference
    Loïc Grenié Bologna
    Comment vérifier si deux représentations galoisiennes ont la\nmême semi-simplifiée
    Soient deux représentations galoisiennes \sigma et \taunon-ramifiées hors d'un ensemble fini de places S. Nous décrirons danscet exposé comment calculer un ensemble fini de places tel que si lestraces des deux représentations sont égales en ces places alors les deuxreprésentations ont la même fonction L.
  • Le 18 mai 2010
  • Salle de Conference
    Andreas Enge
    The queen of mathematics in communication security
    Number theory and arithmetic geometry have found surprising applicationsto cryptology, the science of protecting communication from maliciousintruders. In particular, abelian varieties of low dimension currentlyprovide the most performing public key cryptosystems. After giving abrief and self-contained introduction to modern cryptography, Idiscuss some of John Tate's results on abelian varieties and how theyrelate to the design of secure systems.
  • Le 8 juin 2010
  • Salle de Conference
    Pierre Lezowski
    Algorithme de détermination d'euclidianité et applications I
    Il y a peu, Jean-Paul Cerri a développé un algorithme permettant decalculer le minimum euclidien d'un corps de nombres et les points où il estatteint. L'algorithme n'avait été exploité que dans le cas totalement réelet nécessitait un travail «à la main» en parallèle. Nous l'avons récemmentétendu aux corps de nombres quelconques et nous avons quasiment automatiséla méthode de calcul. Nous étudierons en détail quelques étapes importantesde cette procédure avant de présenter des applications plus ou moinsdirectes de l'algorithme.
  • Le 15 juin 2010
  • Salle de Conference
    Pierre Lezowski
    Algorithme de détermination d'euclidianité et applications II

  • Le 9 septembre 2010
  • Salle de Conference
    Jean-François Biasse
    Subexponential algorithms for number fields

  • Le 17 septembre 2010
  • Salle de Conference
    Henri Cohen
    Fonctions L de motifs hypergéométriques I

  • Le 24 septembre 2010
  • Salle de Conference
    Michael Drmota Wien
    An asymptotic analysis of Cuckoo hashing
    The aim of this talk is to present a recent hash algorithm, which iscalled Cuckoo Hashing, and to provide a precise asymptotic analysis.Cuckoo Hashing has been introduced by Pagh and Rodler in 2001 and has(by construction) constant worst case search time and alsoa very good performance in conflict resolution.The analysis of standard Cuckoo Hashing that we present hererests on a generating function approach to the so called Cuckoo Graph, arandom bipartite graph. With help of double saddle point methods(and related techniques) it will be shown that the probability that theconstruction of a hash table succeeds, is asymptotically1-c(?)/m+O(1/m2) for some explicit c(?), where mdenotesthe size of each of the two tables, n=m(1-?) is the number ofkeys and0 < ? < 1. Further we show that the expected running time islinear.The talk is based on joint work with Reinhard Kutzelnigg.
  • Le 1er octobre 2010
  • Salle de Conference
    Vincent Verneuil
    Scalar multiplication on smart cards and side-channel analysis
    Scalarmultiplication is the main operation of Elliptic Curve Cryptography. Itsimplementation on smart cards in an industrial context requires much effortin order to satisfy performance and security goals. Indeed short timingexecution are required in many applications and must be achieved given thepower and memory constraints of the smart cards. On the other hand the wellknown side- channel analysis can threaten the secrets manipulated by thecard, such as secret scalars. Therefore numerous studies have proposedsolutions for speeding-up the elliptic curve scalar multiplication andcounterfeiting side-channel attacks. Not all of these solutions fit to theindustrial smart card context however.
  • Le 7 octobre 2010
  • Salle de Conference
    Paul Zimmermann Nancy
    Peut-on calculer sur ordinateur?
    Les calculs que l'on peut faire sur ordinateur se divisent en deuxgrandes classes: les calculs 'exacts' (entiers, entiers modulo n,rationnels, ...) et les calculs 'inexacts' (nombres à virgule fixe ouflottante, nombres p-adiques, ...) On s'intéresse plus particulièrement danscette leçon aux nombres à virgule flottante, aussi appelés 'nombresflottants'. Les calculs flottants étant inexacts, peut-on en tirer uneinformation rigoureuse, que l'on peut utiliser dans la preuve d'un théorème?Par exemple, comment prouver π < 22/7 à l'aide d'un ordinateur?Peut-on obtenir dix décimales significatives de l'intégrale entre x=17 etx=42 de la fonction exp(-x2) log(x)?On commencera par rappeler quelques 'catastrophes' dues à une mauvaiseprise en compte des erreurs inhérentes au calcul flottant.On évoquera ensuite plusieurs méthodologies qui permettent d'obtenirune information rigoureuse sur le résultat d'un calcul flottant (arrondicorrect, arithmétique d'intervalles, modèle RealRAM, ...) et on indiqueraquelques outils logiciels qui implantent ces méthodologies.Enfin, on illustrera la leçon par l'exemple du calcul de la deuxième décimalede la constante de Masser-Gramain (travail en cours avec GuillaumeMelquiond).
  • Le 12 octobre 2010
  • Salle de Conference
    Manuel Charlemagne Dublin
    The security of the discrete logarithm problem (DLP) in the\ncontext of pairings
    When applying pairings in cryptographic protocols, it isimportant to ensure that the hardness of the DLP and ECDLP areequivalent in order to satisfy some given security requirementswithout compromising the efficiency of the computation. In this talkwe explain how to achieve proper security levels and we also considerthe less obvious problem of the minimum embedding field.
  • Le 12 octobre 2010
  • Salle de Conference
    Manuel Charlemagne Dublin
    The security of the discrete logarithm problem (DLP) in the\ncontext of pairings
    When applying pairings in cryptographic protocols, it isimportant to ensure that the hardness of the DLP and ECDLP areequivalent in order to satisfy some given security requirementswithout compromising the efficiency of the computation. In this talkwe explain how to achieve proper security levels and we also considerthe less obvious problem of the minimum embedding field.
  • Le 15 octobre 2010
  • Salle de Conference
    Pascal Molin
    Intégration numérique et calculs de fonctions L

  • Le 22 octobre 2010
  • Salle de Conference
    Henri Cohen
    Fonctions L de motifs hypergéométriques II

  • Le 19 novembre 2010
  • Salle de Conference
    Pieter Rozenhart
    Computing quadratic function fields with high 3-rank via cubic field\ntabulation

  • Le 26 novembre 2010
  • Salle de Conference
    Andreas Enge
    HQFRU HIDXW LODYR LUODE RQQHF OHI
    Peut-on considérer la cryptologie, étymologiquement : la science dusecret, comme une science à part entière? Sans doute que la réponse àcette question aurait été différente selon qu'elle ait été posée àl'Antiquité, durant la 2nde guerre mondiale ou encore hier...

    En effet, la cryptologie est à la fois un art ancien et une sciencenouvelle. Outil au service des puissants de ce monde très tôt, cen'est un thème de recherche scientifique académique que depuis lesannées 1970.

    Nous allons nous intéresser plus particulièrement à la cryptographie,cette science de transformation des messages qui sert à en assurerla confidentialité, l'authenticité et l'intégrité. Elle estnaturellement présente dans notre quotidien sans même que nous nous enrendions compte. Mais vous le découvrirez, en coulisses: c'est unequête vers les meilleurs niveaux de sécurité et les frontières sontsans cesse repoussées!
  • Le 26 novembre 2010
  • Salle de Conference
    Andreas Enge
    HQFRU HIDXW LODYR LUODE RQQHF OHI
    Peut-on considérer la cryptologie, étymologiquement : la science dusecret, comme une science à part entière? Sans doute que la réponse àcette question aurait été différente selon qu'elle ait été posée àl'Antiquité, durant la 2nde guerre mondiale ou encore hier...

    En effet, la cryptologie est à la fois un art ancien et une sciencenouvelle. Outil au service des puissants de ce monde très tôt, cen'est un thème de recherche scientifique académique que depuis lesannées 1970.

    Nous allons nous intéresser plus particulièrement à la cryptographie,cette science de transformation des messages qui sert à en assurerla confidentialité, l'authenticité et l'intégrité. Elle estnaturellement présente dans notre quotidien sans même que nous nous enrendions compte. Mais vous le découvrirez, en coulisses: c'est unequête vers les meilleurs niveaux de sécurité et les frontières sontsans cesse repoussées!
  • Le 6 décembre 2010
  • Salle de Conference
    Bill Allombert
    Calcul de groupes d'inertie

  • Le 6 décembre 2010
  • Salle de Conference
    Bill Allombert
    Calcul de groupes d'inertie

  • Le 7 décembre 2010
  • Salle de Conference
    Julien Blondeau Besançon
    Relèvement de représentations avec conditions en p

  • Le 7 décembre 2010
  • Salle de Conference
    Julien Blondeau Besançon
    Relèvement de représentations avec conditions en p

  • Le 7 décembre 2010
  • Salle de Conference
    Julien Blondeau Besançon
    Relèvement de représentations avec conditions en p

  • Le 7 décembre 2010
  • Salle de Conference
    Julien Blondeau Besançon
    Relèvement de représentations avec conditions en p

  • Le 8 décembre 2010
  • Salle de Conference
    Damien Robert
    Variétés abéliennes, fonctions théta, applications I

  • Le 8 décembre 2010
  • Salle de Conference
    Damien Robert
    Variétés abéliennes, fonctions théta, applications I

  • Le 8 décembre 2010
  • Salle de Conference
    Damien Robert
    Variétés abéliennes, fonctions théta, applications I

  • Le 8 décembre 2010
  • Salle de Conference
    Damien Robert
    Variétés abéliennes, fonctions théta, applications I

  • Le 9 décembre 2010
  • Salle de Conference
    Pierre Parent
    Points rationnels de courbes modulaires I:\nestimations analytiques en grand niveau

  • Le 9 décembre 2010
  • Salle de Conference
    Pierre Parent
    Points rationnels de courbes modulaires I:\nestimations analytiques en grand niveau

  • Le 9 décembre 2010
  • Salle de Conference
    Pierre Parent
    Points rationnels de courbes modulaires I:\nestimations analytiques en grand niveau

  • Le 9 décembre 2010
  • Salle de Conference
    Pierre Parent
    Points rationnels de courbes modulaires I:\nestimations analytiques en grand niveau

  • Le 10 décembre 2010
  • Salle de Conference
    Andreas Enge
    Polynômes de classes par restes chinois

  • Le 10 décembre 2010
  • Salle de Conference
    Andreas Enge
    Polynômes de classes par restes chinois

  • Le 10 décembre 2010
  • Salle de Conference
    Andreas Enge
    Polynômes de classes par restes chinois

  • Le 17 décembre 2010
  • Salle de Conference
    Vincent Verneuil
    Scalar multiplication on smart cards and side-channel analysis, le\nretour

  • Le 17 décembre 2010
  • Salle de Conference
    Vincent Verneuil
    Scalar multiplication on smart cards and side-channel analysis, le\nretour

  • Le 27 janvier 2011
  • Salle de Conference
    Adrien Poteaux Paris 6
    Calculs rapides modulo un ensemble triangulaire et\napplications
    Soient F un corps parfait, et Y=(Y_1,…,Y_n) desindeterminees sur F. Un ensemble triangulaire (unitaire et endimension 0) T=(T_1,…,T_n) est une famille de polynomes deF[Y] telle que pour tout i, T_i ∈ F[Y_1,...,Y_i] estunitaire et reduit modulo . Ledegré de T est le produit deg(T_1,Y_1)*...*deg(T_n,Y_n).Ces objets permettent de resoudre de nombreuxproblemes pour les systemes d'equations polynomiales.Cet exposé s'intéresse à la complexite de diversesoperations modulo un ensemble triangulaire: la multiplication,l'inversion (quand cela est possible), calculer la norme de A ∈F[Y]/, le probleme de composition modulaire(i.e. calculer F(G_1(\Y),...,G_m(Y)) mod ) et leprobleme transpose de projection des puissances, et enfin leprobleme de changement d'ordre (sous certaines conditions).Nous decrirons pour ces problemes des algorithmes ayant unecomplexite binaire quasi-lineaire en la taille du probleme quandF est un corps fini, ce qui ameliore les algorithmes existantsquand le nombre de variables n'est pas borné par une constante.Enfin, nous illustrerons brièvement une application de cesalgorithmes dans le cas du problème de comptage de points descourbes elliptiques.
  • Le 3 février 2011
  • Salle de Conference
    Bill Allombert
    Calcul de points rationnels sur une courbe elliptique par la méthode\n de Silverman-Cremona-Delaunay.
    Soit E une courbe elliptique de rang analytique 1. La méthode de Silverman-Cremona-Delaunay permet de calculer explicitement un point rationnel sur E à l'aide du théorème de Gross-Zagier sur la hauteur des points de Heegner. L'éfficacité de la méthode dépend du choix de nombreux paramètres (choix d'une tordue quadratique de E, choix de représentants du groupe de classes sous l'action de certains groupes, etc.). Nous discutons de l'optimisation de ces paramètres, qui elle-même doit être faite efficacement.
  • Le 10 février 2011
  • Salle de Conference
    Jean-Marc Couveignes
    Géométrie des tangentes d'inflexion d'une cubique plane et\n les pseudo-paramétrisations qui s'en déduisent

  • Le 17 février 2011
  • Salle de Conference
    Nicolas Mascot
    Algorithmique pour les jacobiennes de courbes:\n algorithmes classiques et méthodes de Khuri-Maksidi

  • Le 24 février 2011
  • Salle de Conference
    Christophe Ritzenthaler
    Couplages sur les courbes d'Edwards et formules d'addition complètes
    Le modèle d'Edwards x2+y2 =1+dx2y2 des courbes elliptiques a connu un engouement important de la part de la communauté cryptographique, en particulier grâce à sa propriété de 'complétude'. Celle-ci exprime le fait qu'il existe une loi d'addition sur la courbe, valide pour tout couple de points rationnels dès lors que d n'est pas un carré dans le corps (alors que pour le modèle de Weierstrass, on utilise classiquement des expressions différentes suivant les cas ? points distincts, doublement, addition du neutre...). Nous montrerons qu'une telle propriété peut se généraliser aux variétés abéliennes de toute dimension. Nous utiliserons pour cela la description des lois d'addition en termes de sections d'un certain fibré en droites. Ce travail est en collaboration avec Christophe Arène et David Kohel. Nous montrerons également comment on peut calculer efficacement le couplage de Tate sur le modèle d'Edwards (travail en collaboration avec Christophe Arène, Tanja Lange et Michael Naehring). Pour cela nous donnerons une description géométrique de la loi d'addition.
  • Le 3 mars 2011
  • Salle de Conference
    Martin Weimann
    Factorisation torique des polynômes bivariés
    La plupart des algorithmes rapides actuels de factorisation des polynômes bivariés considèrent le degré total comme principal invariant. Quand le polynôme est creux, le degré se révèle être cependant un pauvre indicateur de complexité et on voudrait considérer des invariants plus fins. Dans cet exposé, je m'intéresse au polytope de Newton. Je prouve l'existence d'un algorithme déterministe qui, étant donné f ? Q[x, y]générique relativement à son polytope, et étant donnée la factorisation univariée de certains polynômes de facettes, calcule la factorisation rationnelle de f en petit temps polynomial en le volume du polytope. Quand le polynôme est suffisament creux, l'algorithme améliore considérablement les algorithmes denses les plus rapides (Chèze-Lecerf, Gao, Belabas-Van Hoeij-etc). La stratégie est de décomposer la courbe définie par f dans une compactification torique adéquate du plan affine. La preuve s'appuie alors sur un théorème d'extension des fibrés en droite, la théorie des résidus, la cohomologie des variétés toriques, et le critère d'irréductibilité de Ruppert.
  • Le 10 mars 2011
  • Salle de Conference
    Karim Belabas
    Termes restes dans le théorème de Davenport-Heilbronn I

  • Le 17 mars 2011
  • Salle de Conference
    Karim Belabas
    Termes restes dans le théorème de Davenport-Heilbronn II

  • Le 31 mars 2011
  • Salle de Conference
    Karim Belabas
    Termes restes dans le théorème de Davenport-Heilbronn III

  • Le 14 avril 2011
  • Salle de Conference
    Vanessa Vitse Versailles
    Attaques par recouvrement et décomposition du logarithme discret sur\n courbes elliptiques.
    On présente dans cet exposé une méthode combinant la descente de Weil et les méthodes de calcul d'indices, qui permet d'attaquer le problème du logarithme discret sur courbes elliptiques définies sur des extensions de degré composé. En particulier, on donnera un exemple concret d'attaque du DLP pour un sous-groupe de taille 130 bits d'une courbe définie sur Fp6, a priori résistant à toute autre attaqueconnue.
  • Le 28 avril 2011
  • Salle de Conference
    Jérémie Le Borgne Rennes
    Algorithmique des phi-modules pour les représentations\n galoisiennes p-adiques
    Je présenterai quelques problèmes algorithmiques liés à l'étude des représentations galoisiennes p-adiques. J'expliquerai la correspondance entre certaines représentations p-adiques et des objets d'algèbre semi-linéaires appelés phi-modules. Je présenterai un algorithme polynomial pour déterminer certains invariants d'un phi- module, qui donnent des invariants équivalents sur la représentation associée, en particulier les poids de l'inertie modérée.
  • Le 5 mai 2011
  • Salle de Conference
    Andy Novocin Lyon
    L1 a new quasi-linear LLL algorithm
    The LLL lattice reduction algorithm of 1982 has proven to be useful in a wide variety of fields. It can be used to approximately solve computationally difficult lattice-based problems, such as the shortest vector problem, in polynomial time. We present a new algorithm for lattice reduction which is the first algorithm to have a complexity bound which is both polynomial and quasi-linear bound in the bit-length of the input. To achieve this we present an independently interesting toolkit for analyzing incremental lattice reductions.
  • Le 19 mai 2011
  • Salle de Conference
    Lassina Dembelé Warwick
    Sur la conjecture de Gross
    Gross a conjecturé que pour tout premier p, il existe une extension finie de Q non-résoluble, non-ramifiée en dehors de p. (C'est maintenant un théorème.) Nous expliquerons comment les représentations galoisoisiennes associées aux formes de Hilbert mod p permettent une nouvelle approche de ce problème.
  • Le 26 mai 2011
  • Salle de Conference
    Jean-François Biasse Calgary
    Calcul du groupe de classes et des unités dans les corps de nombres
    Le calcul du groupe de classes, du régulateur et des unités fondamentales d'un corps de nombres est une tâche fondamentale en théorie des nombres. Ce problème est aussi utilisé dans l'élaboration et l'attaques de cryptosystèmes asymétriques. Dans cet exposé, nous nous intéresserons à une nouvelle variations de l'algorithme sous-exponentiel de Buchmann dans lequel les relations sont calculée à l'aide des techniques de lattice sieving tandis que les unités sont dérivées par des méthodes p-adiques. Les premiers résultats de ce projet de recherche en court montrent une nette amélioration pour les corps de petit degré (degré n plus petit que 10).
  • Le 7 septembre 2011
  • Salle de Conference
    Jérôme Milan
    Pairings implementation in the PARI computer algebra system
    Pairing-based cryptography has been one of the most active areas inasymmetric cryptology in the past two decades. They were initially introducedwith the destructive goal of transferring the resolution of the discretelogarithm problem from elliptic curves to finite fields. However, the lastdecade saw the explosion of the use of pairings with constructive objectivessuch as identity-based cryptography or short signatures, and a great amountof effort was invested to speed up their computations. In this presentation, I will report on the design of a PARI/GP module forcomputing pairings on elliptic curves over large characteristic fields. Thedefinition of the Tate, Weil and ate pairings will be recalled, together withthe notion of optimal pairing independently proposed by Hess and Vercauteren.Most pairings consist of the evaluation of a rational function followed by anexponentiation in a large finite field. We will explain both steps anddescribe some recent improvements found in the literature. The remainder ofthe talk will deal with our implementation in PARI/GP: available algorithms,weaknesses of our implementation, and benchmarks.
  • Le 23 septembre 2011
  • Salle de Conference
    Jean-Marc Couveignes
    Paramétrisation des cubiques planes à l'aide d'un radical\ncubique
    Étant donnée une cubique lisse projective plane C sur un corps K decaractéristique première à 6, on cherche des morphismes finisf : D?C où D est un revêtement radiciel de P1/K de degré 3. Ondit que f est une paramétrisation de C à l'aide d'un radical cubique. Cesparamétrisations présentent un intérêt cryptographique. Icart, Kammerer,Lercier, Renault and Farashahi en ont donné quelques exemples. J'expliqueraipourquoi ces paramétrisations correspondent à des courbes rationnelles dansle plan dual, ayant des propriétés remarquables d'intersection avec la duale? de C. De telles courbes se relèvent en des courbes rationnellessur le revêtement de degré 2 du plan dual ramifié le long de ?. Cerevêtement est une surface K3 de rang générique 19. L'étude de son groupede Néron-Séveri met de l'ordre dans les paramétrisations connues et permetd'en produire de nouvelles.

    Travail en commun avec Jean-Gabriel Kammerer.


  • Le 28 septembre 2011 à 15:00
  • Salle 385
    Peter Stevenhagen Leiden
    Radical extensions and primitive roots
    It follows from the work of Artin (1927, 1958) and Hooley (1967) that,under assumption of the generalized Riemann hypothesis, everynon-square rational number different from -1 is a primitive rootmodulo infinitely many primes.Moreover, the set of these primes has a natural density that canbe written as the product of a `naive density' and a somewhatcomplicated correction factor reflecting the entanglement of theradical extensions from which the density statement is obtained.We show how the correction factors arising in Artin's original primitiveroot problem and the many generalizations that have been studiedin the last few decades can be interpreted ascharacter sums describing the nature of the entanglement.The resulting description in terms of local contributionsis so transparent that it greatly facilitates explicitcomputations.

    This is joint work with Hendrik Lenstra and Pieter Moree.


  • Le 30 septembre 2011 à 14:00
  • Salle de conférences
    Damien Robert
    Couplages optimaux sur variétés abéliennes via les fonctions\nthêta
    L'utilisation de couplages en cryptographie a connu un grand essor cesdernières années, car elle permet la réalisation de protocoles comme lacryptographie basée sur l'identité, de manière efficace. Pour l'instant, lesseuls couplages cryptographiquement sûrs connus viennent des variétésabéliennes. L'algorithme de Miller permet de calculer efficacement lecouplage de Weil et de Tate sur les Jacobiennes de courbes hyperelliptiques.Une collaboration avec David Lubicz nous a permis de développer un algorithmepour calculer le couplage sur une variété abélienne par le biais desfonctions thêta. Pour des raisons d'efficacité, des modifications du couplagede Tate ont été développées dans le cadre des courbes elliptiques (couplagede ate optimal). Dans cet exposé, nous décrirons notre algorithme, et commentl'adapter aux couplages optimaux. Il s'agit d'une collaboration avec DavidLubicz.
  • Le 5 octobre 2011 à 15:00
  • Salle 385
    Michael Rubinstein Waterloo
    Conjectures, experiments, and algorithms concerning the moments\nof L(1/2,?d)
    I'll report on some extensive computations with MatthewAlderson in which wecomputed the values of L(1/2, ?d) for-5·1010?d? 1.3·1010in orderto test conjectures concerning the moments?|d| < XL(1/2, ?d)k.Specifically we wereinterested in testing the full asymptotics for the moments conjecturedby Conrey, Farmer, Keating,Rubinstein, and Snaith, as well as the conjecture of Diaconu,Goldfeld, and Hoffstein concerning additionallower terms in the moments. I'll also describe the algorithms we usedfor this large computation.
  • Le 13 octobre 2011 à 14:00
  • Salle de conférences
    Julio Brau
    Computing the image of Galois representations attached to elliptic curves
    I will discuss ongoing work on an algorithm that computes the full imageof the Galois representation attached to an elliptic curve.
  • Le 25 octobre 2011 à 15:00
  • Salle 385
    Bill Allombert
    Développement de Pari/Gp sous Git
    Une séance de travaux pratiques qui couvrira les sujets suivants:
    • les concepts de base du contrôle de version avec git;
    • comment rester à jour des derniers développements de pari/gp;
    • comment contribuer au développement.

  • Le 25 octobre 2011 à 15:00
  • Salle 385
    Bill Allombert
    Développement de Pari/Gp sous Git
    Une séance de travaux pratiques qui couvrira les sujets suivants:
    • les concepts de base du contrôle de version avec git;
    • comment rester à jour des derniers développements de pari/gp;
    • comment contribuer au développement.

  • Le 25 octobre 2011 à 15:00
  • Salle 385
    Bill Allombert
    Développement de Pari/Gp sous Git
    Une séance de travaux pratiques qui couvrira les sujets suivants:
    • les concepts de base du contrôle de version avec git;
    • comment rester à jour des derniers développements de pari/gp;
    • comment contribuer au développement.

  • Le 25 octobre 2011 à 15:00
  • Salle 385
    Bill Allombert
    Développement de Pari/Gp sous Git
    Une séance de travaux pratiques qui couvrira les sujets suivants:
    • les concepts de base du contrôle de version avec git;
    • comment rester à jour des derniers développements de pari/gp;
    • comment contribuer au développement.

  • Le 25 octobre 2011 à 15:00
  • Salle 385
    Bill Allombert
    Développement de Pari/Gp sous Git
    Une séance de travaux pratiques qui couvrira les sujets suivants:
    • les concepts de base du contrôle de version avec git;
    • comment rester à jour des derniers développements de pari/gp;
    • comment contribuer au développement.

  • Le 25 octobre 2011 à 15:00
  • Salle 385
    Bill Allombert
    Développement de Pari/Gp sous Git
    Une séance de travaux pratiques qui couvrira les sujets suivants:
    • les concepts de base du contrôle de version avec git;
    • comment rester à jour des derniers développements de pari/gp;
    • comment contribuer au développement.

  • Le 25 octobre 2011 à 15:00
  • Salle 385
    Bill Allombert
    Développement de Pari/Gp sous Git
    Une séance de travaux pratiques qui couvrira les sujets suivants:
    • les concepts de base du contrôle de version avec git;
    • comment rester à jour des derniers développements de pari/gp;
    • comment contribuer au développement.

  • Le 25 octobre 2011 à 15:00
  • Salle 385
    Bill Allombert
    Développement de Pari/Gp sous Git
    Une séance de travaux pratiques qui couvrira les sujets suivants:
    • les concepts de base du contrôle de version avec git;
    • comment rester à jour des derniers développements de pari/gp;
    • comment contribuer au développement.

  • Le 25 octobre 2011 à 15:00
  • Salle 385
    Bill Allombert
    Développement de Pari/Gp sous Git
    Une séance de travaux pratiques qui couvrira les sujets suivants:
    • les concepts de base du contrôle de version avec git;
    • comment rester à jour des derniers développements de pari/gp;
    • comment contribuer au développement.

  • Le 25 octobre 2011 à 15:00
  • Salle 385
    Bill Allombert
    Développement de Pari/Gp sous Git
    Une séance de travaux pratiques qui couvrira les sujets suivants:
    • les concepts de base du contrôle de version avec git;
    • comment rester à jour des derniers développements de pari/gp;
    • comment contribuer au développement.

  • Le 25 octobre 2011 à 15:00
  • Salle 385
    Bill Allombert
    Développement de Pari/Gp sous Git
    Une séance de travaux pratiques qui couvrira les sujets suivants:
    • les concepts de base du contrôle de version avec git;
    • comment rester à jour des derniers développements de pari/gp;
    • comment contribuer au développement.

  • Le 1er décembre 2011 à 14:00
  • Salle de conférences
    Athanasios Angelakis
    Isomorphic Absolute Galois Groups of Number Fields
    By the Neukirch-Uchida theorem, two number fields K and K' areisomorphic if and only if their absolute Galois groups are.It is possible for non-isomorphic number fields to have isomorphicabsolute abelian Galois groups. In the case of imaginary quadratic fields,class field theory enables us to describe these abelian Galois groups andto construct examples where they are isomorphic.
  • Le 2 février 2012 à 15:30
  • Salle 2
    Vincent Verneuil
    Square Always Exponentiation
    Embedded exponentiation techniques have become a keyconcern for security and efficiency in hardware devices using public keycryptography. An exponentiation is basically a sequence of multiplicationsand squarings, but this sequence may reveal exponent bits to anattacker on an unprotected implementation. Although this subject hasbeen covered for years, we present in this paper new exponentiationalgorithms based on trading multiplications for squarings. Our methodcircumvents attacks aimed at distinguishing squarings from multiplicationsat a lower cost than previous techniques. Last but not least, wepresent new algorithms using two parallel squaring blocks which providethe fastest exponentiation to our knowledge.
  • Le 24 février 2012 à 10:00
  • Salle 385
    Jean-Marc Couveignes
    Logarithmes discrets elliptiques par recouvrement I

  • Le 8 mars 2012 à 11:00
  • Salle 1
    Jean-Marc Couveignes
    Logarithmes discrets elliptiques par recouvrement II

  • Le 12 mars 2012 à 11:00
  • Salle 385
    Vasily Golyshev
    Searching for congruences of Galois representations
    The famous theorem of Ramanujan states thatΔ= q Π (1-qi)24= Σ ai qihas the congruence propertyap = p11+1 mod 691for any prime p. In modern language, it says that thetwo-dimensional modular representation Φ that corresponds toΔ is congruent to an extension of a character by a charactermod 691:Φ = char + char mod 691 at the level of semisimplifications.Another example of such behavior, albeit of a different nature, is anelliptic curve X0(11):the existence of a 5-torsion rational pointon it leads to the congruence ap=1+p mod 5.

    We are interested in 4-dimensional Galois representations Ψ ofweight 3 that arise in Calabi-Yau threefolds. An intuition says that aphenomenon of bi-congruence may exist, namely, for certain Ψ therewould be a pair of moduli(N1, N2) and two rank 2 GaloisrepresentationsΦ1, Φ2such that, at the level ofsemisimplifications, or trace functions,Ψ = Φ1 + char + charmod N1 andΨ = Φ2 +char + charmod N2.

    We will discuss computational approaches to the problem of theexistence of Calabi-Yau Galois representations with bi-congruences.


  • Le 22 mars 2012 à 13:30
  • Salle 385
    Henri Cohen
    Lacunarité des quotients η

  • Le 29 mars 2012 à 13:30
  • Salle 385
    Marco Streng Warwick
    Smaller class invariants for quartic CM-fields
    The theory of complex multiplication allows one to construct ellipticcurves with a given number of points. The idea is to construct a curveover a finite field by starting with a special curve E incharacteristic 0, and taking the reduction of E modulo a prime number.

    Instead of writing down equations for the curve E, one only needs theminimal polynomial of its j-invariant, called a Hilbert classpolynomial. The coefficients of these polynomials tend to be verylarge, so in practice, one replaces the j-invariant by alternativeclass invariants.Such smaller class invariants can be found andstudied using an explicit version of Shimura's reciprocity law.

    The theory of complex multiplication has been generalized to curves ofhigher genus, but up to now, no class invariants were known in thishigher-dimensional setting. I will show how to find smaller classinvariants using a higher-dimensional version of Shimura's reciprocitylaw.


  • Le 12 avril 2012 à 13:30
  • Salle de conférences
    Gaëtan Bisson Sydney
    Un algorithme à la Pollard pour le problème du sac à dos
    Soit S une suite finie d'éléments d'un groupe fini G noté multiplicativement ; le problème du sac à dos consiste à trouver unesous-suite de S dont le produit vaut un élément donné z de G. Pourcertains groupes particuliers comme G=Z/nZ, on connait des méthodes trèsefficaces pour le résoudre ; cependant, aucun algorithme générique nepeut résoudre ce problème en moins de O(sqrt(#G)) opérations.

    Une approche de type « pas de bébé, pas de géant » atteint cettecomplexité en temps mais requiert un espace mémoire de taillecomparable. La première partie de cet exposé présentera une adaptationd'idées de Pollard à ce contexte afin d'obtenir un algorithme similairemais au coût mémoire négligeable. Ensuite, j'en présenterai certainesapplications, notamment au calcul d'isogénies entre deux courbeselliptiques.

    Ces travaux sont conjoints avec Andrew V. Sutherland.


  • Le 10 mai 2012 à 13:30
  • Salle de conférences
    Damien Robert
    Polynômes de classes en genre 2 par la méthode des restes chinois

  • Le 24 mai 2012 à 11:00
  • Salle 385
    Pierre Lezowski
    Corps de quaternions euclidiens
    Soient K un corps de nombres, F un corps de quaternions sur K et O unordre de F. Nous présenterons des techniques pour étudierl'euclidianité de O, par rapport à la norme ou un stathme quelconque.En nous appuyant sur la construction de Motzkin, nous étudierons lecas particulier où F est totalement défini quand K est le corps desrationnels ou un corps quadratique.

    Il s'agit d'un travail en commun avec Jean-Paul Cerri et Jérôme Chaubert.


  • Le 2 juillet 2012 à 15:00
  • Salle 385
    Bernhard Schmidt Singapore
    Values and ideals in combinatorial problems
    The absolute value of complex numbers is surprisingly useful in theinvestigation of certain combinatorial problems. The connection usually arisesfromembedding ?nite cyclic groups into the complex numbers by sending the groupelements to roots of unity. The absolute value of the resulting sums of rootsof unity, i.e., cyclotomic integers, usually is known explicitly, which allows theapplication of two powerful tools: the ideal theory of algebraic numbers and?size arguments? involving the absolute value of complex numbers. We willpresent some highlights of this approach including recent progress on circulantHadamard matrices, Barker sequences, and the structure of circulant weighingmatrices.
  • Le 11 septembre 2012 à 10:00
  • Salle 385
    Enea Milio Montpellier
    Techniques de criblage pour la factorisation et le calcul de logarithmes\n discrets
    Aujourd'hui, les meilleurs algorithmes pour résoudre les problèmesde la factorisation (NFS) et du logarithme discret (NFS-DL) dans le groupemultiplicatif d'un corps fini utilisent la notion de crible sur un corps denombres (number field sieve). Nous nous proposons de décrire lesdifférents aspects de ces algorithmes.
  • Le 18 septembre 2012 à 10:00
  • Salle 385
    Karim Belabas
    Calcul de résidus de la fonction zeta

  • Le 25 septembre 2012 à 10:00
  • Salle 385
    Fabien Pazuki
    Décompositions en hauteurs locales sur les courbes elliptiques I
    Le but de l'exposé est de donner un éclairage sur destravaux de Cremona, Prickett et Siksek concernant le calcul degénérateurs du groupe de Mordell-Weil. On révisera le cadre théoriquepuis on abordera les aspects pratiques de leurs articles. On discuteraenfin des généralisations futures.
  • Le 2 octobre 2012 à 10:00
  • Salle 385
    Fabien Pazuki
    Décompositions en hauteurs locales sur les courbes elliptiques II

  • Le 9 octobre 2012 à 10:00
  • Salle 385
    Fernando Mario
    Packings of bodies in Euclidean space
    Given a finite list of convex bodies in Euclidean space, a packing is a union of nonoverlapping translated copies of the bodies given. A natural question concerning packings is how dense they can be made, that is, what is the maximum fraction of space that can be covered by a packing of some given bodies? I wil show how harmonic analysis and semidefinite programming can be used to give upper bounds for the maximum density of a packing of bodies. In particular I will discuss the case of binary sphere packings, when one considers packings of spheres of two different sizes, and show how the computer can be used to find upper bounds for the densities of such packings. This is joint work with David de Laat and Frank Vallentin.
  • Le 16 octobre 2012 à 10:00
  • Salle 385
    Karim Belabas
    Tomographie arithmétique

  • Le 23 octobre 2012 à 10:00
  • Salle 385
    Henri Cohen
    Comptage des corps cubiques et quartiques

  • Le 30 octobre 2012 à 10:00
  • Salle 385
    Luca De Feo
    Towards Quantum-Resistant Cryptosystems from Supersingular Elliptic Curve Isogenies
    Il est bien connu que certains graphes de courbes elliptiques isogènesont une structure de graphe de Ramanujan, ce qui garantit des bonnespropriétés de mixage pour les marches aléatoires. Cette observation aété utilisée à plusieurs reprises pour construire des cryptosystèmesbasés sur la difficulté supposée de calculer une isogénie entre deuxcourbes elliptiques données.

    Parmi ces protocoles, nous nous intéressons particulièrement àl'échange de clef de Rostovstev et Stolbunov: il s'agitessentiellement d'un protocole de Diffie-Helman basé sur l'action dugroupe des classes sur un graphe d'isogénies ordinaires. Ce protocoleest peu efficace et présente un intérêt purement théorique; lesauteurs ont suggéré qu'il pourrait être utilisée dans un contextepost-quantique, cependant Childs, Jao et Soukharev ont montré qu'ilest attaquable en temps sous-exponentiel quantique à cause de sastructure abélienne.

    Dans ce travail, en commun avec David Jao et Jérôme Plût, nousproposons un noveau protocole à la Diffie-Helman basé sur des marchesdans des graphes d'isogénies supersingulières. La similitude avec leprotocole de Rostovstev et Stolbunov est seulement superficielle: dansnotre cas il n'y a pas de structure abélienne agissant sur le graphe,ce qui nous oblige à passer de l'information supplémentaire pourréaliser l'échange. Cependant il ne semble pas y avoir de moyend'utiliser cette information supplémentaire pour attaquer leprotocole, et l'absence d'une structure abélienne défie toute attaquequantique. La séparation la plus significative entre notreconstruction et les échanges de Diffie-Helman est réalisée par unprotocole Zero-Knowledge que nous construisons au dessus de nosprimitives, et dont l'équivalent abélien est trivialement cassé.

    Notre protocole, déjà dans une implantation naïve en Magma, estsensiblement plus performant que celui de Rostovstev et Stolbunov. Sonoptimisation est aussi intéressante que le protocole lui même; eneffet une étude fine de la combinatoire du calcul d'isogénies seréduit naturellement à des problèmes d'optimisation pour des arbresbinaires (infinis) avec poids. En combinant cette étude avec destechniques classiques en arithmétique des courbes elliptiques, nousobtenons une implantation mixte en Sage/Cython/C 1000 fois plus rapideque le protocole de Rostovstev et Stolbunov et avec des performancescomparables à celles de nombreux protocoles à base de couplages.


  • Le 20 novembre 2012 à 10:00
  • Salle 385
    Bill Allombert
    Comptage de points sur les courbes elliptiques en petite caractéristique

    La version de Harley de l'algorithme de Satoh permet de compter les points sur une courbe elliptique ordinaire sur $\mathbb{F}_p$ en temps $\tilde{O}_p(n^2)$ pour tout $p$. Nous montrons qu?il est possible d?obtenir une complexité en $\tilde{O}(p^2 n^2)$ et nous proposons une implantation dans PARI/GP.


  • Le 27 novembre 2012 à 10:00
  • Salle 385
    Jacques Martinet imb
    Le calcul des maxima locaux de l'invariant B-M d'un réseau est-il algorithmique?

    Soit $E$ un espace euclidien de dimension $n$. L?invariantd?Hermite d?un réseau $\Lambda \subset E$ est$\Gamma(\Lambda)=\frac{\min\Lambda}{\det(\Lambda)}$.

    On s?intéresse à $\Gamma?(\Lambda):=(\Gamma(\Lambda)\Gamma(\Lambda^*))^{1/2}$,dont l?introduction a été motivée par les classes jumelles de Zimmert, et àses maxima sur l?espace des réseaux, dont la classification n?a été faiteque jusqu?à la dimension~$4$. On considérera aussi un problème voisin nonrésolu à partir de $n=4$. Les ordinateurs ne connaissant pas les réseaux,les questions abordées doivent être traduites en termes de matricessymétriques.

    La méthode proposée repose sur une décomposition de l?espace des réseaux enclasses minimales, correspondant à la décomposition cellulaire del?espace des formes quadratiques définies positive, connue jusqu?à ladimension $7$($n=5$: Batut; $n=6,7$: Elbaz-Vincent?Gangl?Soulé).


  • Le 8 janvier 2013 à 10:00
  • IMB: Salle 385
    Philippe Jaming imb
    Problème de la phase dans le cadre discret

    Nous étudions le problème de reconstruire une fonction à partir du modulede sa transformée de Fourier (discrète) et d?informations a priori sur lafonction. Par exemple, dans le cas où la fonction est la fonctioncaractéristique d?un ensemble $A$, on veut reconstruire $A$ à partir del?ensemble de différences $A-A$.


  • Le 22 janvier 2013 à 10:00
  • Salle 385
    Hamish Ivey-Law imb
    Arithmetic on Jacobians of relative curves

  • Le 29 janvier 2013 à 10:00
  • Salle 385
    Nicolas Mascot imb
    Calcul de représentations galoisiennes modulaires

    Je décrirai un algorithme permettant de calculer les représentationsgaloisiennes associées à une forme modulaire parabolique propre, etj?étudierai un problème associé, à savoir le calcul des coefficients deFourier de cette forme modulo un petit nombre premier.


  • Le 5 février 2013 à 10:00
  • Salle 385
    Sorina Ionica (ENS Paris)
    Algorithms for isogeny graphs

    The CRT method for computing class polynomials in genus 2 relies onalgorithms for traveling in the isogeny graph and endomorphism ringcomputation. Using Galois cohomology, we relate the endomorphism ringstructure to certain properties of the $\ell$-Tate pairing, such asnon-degeneracy on subgroups of the $\ell$-torsion giving kernels ofisogenies of principally polarized abelian varieties in the $\ell$-isogenygraph. In genus 2, we present an efficient method to check whether thejacobian has locally maximal endomorphism ring at $\ell$. In view ofapplication to the CRT method for class polynomials, we derive an algorithmto compute horizontal $\ell$-isogenies starting from a jacobian with maximalendomorphism ring.


  • Le 19 février 2013 à 10:00
  • Salle 385
    Tony Ezome (Université de Masuku ? Franceville, Gabon)
    A faster pseudo-primality test

  • Le 26 février 2013 à 10:00
  • Salle 385
    Marie-Françoise Roy (Rennes)
    Algorithme diviser pour régner pour les cartes routières

    Complexity of deciding connectivity in semi-algebraic sets: recent results and future research directions

    The number of connected components of a real algebraic set is $O(d)^k$ which is polynomial in the degree $d$ and singly exponential in the number of variables $k$. The first algorithm with elementary recursive complexity for counting the connected components is Collins?s cylindrical decomposition, with complexity doubly exponential in $k$. Canny?s roadmap gives a singly exponential complexity, its best variants have complexity $d^{0(k^2)}$. The talk will report on recent results based on work of Safey/Schost and Basu/Roy/Safey/Schost improving Canny?s roadmap using a baby step giant step strategy and obtaining complexity $d^{0(k \sqrt(k))}$. A challenging research direction is to use a divide and conquer strategy to get an exponent quasi linear in $k$.


  • Le 5 mars 2013 à 09:30
  • IMB: Salle 385
    Paul Dorbec (Labri)
    A propos de domination dans les graphes.

    Au cours de cet exposé, nous verrons les bases de la domination dansles graphes et quelques pistes de recherches actuelles. Nous parleronsen particulier de la conjecture de Vizing, de dominants parfaits(codes couvrants), et de différentes autre variantes de la domination.


  • Le 19 mars 2013 à 10:00
  • Salle 385
    Claus Diem (Leipzig)
    Systèmes linéaires spéciaux sur courbes et le problème du logarithme discret

  • Le 9 avril 2013 à 10:00
  • Salle 385
    Pierre Lezowski (imb)
    Groupe de classe d'Arakelov

  • Le 16 avril 2013 à 10:00
  • IMB: Salle 385
    Ralf Klasing (Labri)
    Identifying coDes in Evolving grAphs (IDEA).

    In this talk, we will give an overview of the ANR project ?IdentifyingcoDes in Evolving grAphs (IDEA)?. In particular, we will present someof the results obtained in the project, and we will outline somepotential directions of future research.


  • Le 23 avril 2013 à 10:00
  • Salle 385
    Pierre Chrétien (imb)
    Calcul de corps de classe de rayon de courbes de genre $g \neq 0$.

    Soit $K/\F_q$ un corps de fonctions d?une variable et $S$ un ensemblenon vide de places $\F_q$-rationnelles de $K$.Le $S$-corps de classes de Hilbert de $K$ est la plus grande extensionabélienne non ramifiée de $K$ dans laquelle se décomposent complètementles places de $S$.On décrira une méthode efficace de calcul du $S$-corps de classes deHilbert pour $K$ de genre non nul, basée sur l?étude de sesautomorphismes sur $\F_q$.On illustrera cette méthode par le calcul de $S$-corps de classes deHilbert de courbes de Deligne-Lusztig ainsi que certains de leurs$S$-corps de classes de rayons.


  • Le 14 mai 2013 à 10:00
  • Salle 385
    Maike Massierer (University of Basel)
    Point Compression for the Trace Zero Variety

    The hardness of the (hyper)elliptic curve discrete logarithm problemover extension fields lies in the trace zero variety. A compactrepresentation of the points of this abelian variety, computed by apoint compression algorithm, is needed in order to accurately assessthe hardness of the discrete logarithm problem there. Such algorithmshave been proposed by Lange and Silverberg. We present a newrepresentation that is optimal in size, compatible with the structureof the variety, and allows efficient point compression anddecompression.


  • Le 28 mai 2013 à 10:00
  • IMB: Salle 385
    Achill Schürmann (Universität Rostock)
    Exploiting Symmetries in Polyhedral Computations

    Many important problems in mathematics and its applications are modeledusing linear constraints respectively polyhedra. Standard modeling oftenyields polyhedra having many symmetries. However, standard algorithms donot take advantage of them, and even worse, they often work particularlypoorly on symmetric problems. In this talk we give an overview aboutongoing work on new symmetry exploiting techniques for three fundamentaltask in polyhedral computations: the representation conversion problem,integer linear programming, and lattice point counting.

    Initial proof-of-concept results show that affine symmetries can beexploited quite well in certain situations. In order to apply these newtechniques on a broader scale new theoretical grounds have to be broken.


  • Le 11 juin 2013 à 10:00
  • Salle 385
    Henri Cohen (imb)
    A first package for modular forms in Pari/GP

  • Le 18 juin 2013 à 10:00
  • IMB: Salle 385
    Sinai Robins (Nanyang Technological University (Singapore))
    Cone theta functions and what they tell us about the\nirrationality of spherical polytope volumes.

    This is joint work with Winfried Kohnen and Amanda Folsom.


  • Le 10 septembre 2013 à 10:00
  • Salle 385
    Friedrich Panitz (Paderborn)
    An algorithm to enumerate quartic fields, after Bhargava.

  • Le 24 septembre 2013 à 10:00
  • Salle 385
    Hamish Ivey-Law (imb)
    The Riemann-Roch problem for divisors on two classes of surfaces

    Abstract: We will consider a type of Riemann-Roch problem fordivisors on certain algebraic surfaces. Specifically we consideralgebraic surfaces arising as the square or the symmetric squareof a hyperelliptic curve of genus at least two over an (almost)arbitrary field. The main results are a decomposition of thespaces of global sections of certain divisors on such surfacesand explicit formulæ for the dimensions of the spaces of sectionsof these divisors. We conclude by presenting an algorithm whichgenerates a basis for the space of global sections of such adivisor.

    Résumé: Nous considérerons un type de problème de Riemann-Rochpour les diviseurs sur certaines surfaces algébriques. Plusprécisément, nous analysons les surfaces algébriques qui émanentd?un produit ou d?un produit symétrique d?une courbehyperelliptique de genre supérieur à un sur un corps (presque)arbitraire. Les résultats principaux sont une décomposition desespaces de sections globales de certains diviseurs sur tellessurfaces et des formules explicites qui décrivent les dimensionsdes espaces de sections de ces diviseurs. Pour conclure nousprésenterons un algorithme qui produit une base pour l?espace desections globales d?un tel diviseur.


  • Le 4 octobre 2013 à 14:00
  • LaBRI: Salle 178
    Sylvia Bianchi ()
    Polyhedra associated with identifying codes

  • Le 25 octobre 2013 à 14:00
  • LaBRI: Salle 178
    Gilles Zémor ()
    Graphes sur des surfaces et codes quantiques

  • Le 5 novembre 2013 à 10:00
  • IMB: Salle 385
    Renaud 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?unealgèbre semi-simple sur Q. Les méthodes utilisées reposent sur unecombinaison de la théorie de Bass-Serre des ?graphes de groupes? et dedifférents avatars de l?algorithme de Voronoi pour les formesquadratiques. L?exposé portera plus particulièrement sur la descriptiond?un algorithme pour le calcul des classes de conjugaison des sous-groupesfinis maximaux d?un tel groupe d?unités.


  • Le 22 novembre 2013 à 13:00
  • IMB: Salle 385
    Renaud Coulangeon (imb)
    Théorie de Bass-Serre des graphes de groupes et application au calcul de\nla présentation du groupe d'unité d'une algèbre semi-simple (1).

  • Le 22 novembre 2013 à 13:00
  • IMB: Salle 385
    Renaud Coulangeon (imb)
    Théorie de Bass-Serre des graphes de groupes et application au calcul de\nla présentation du groupe d'unité d'une algèbre semi-simple (1).

  • Le 29 novembre 2013 à 13:00
  • IMB: Salle 385
    Renaud Coulangeon (imb)
    Théorie de Bass-Serre des graphes de groupes et application au calcul de\nla présentation du groupe d'unité d'une algèbre semi-simple (2).

  • Le 10 décembre 2013 à 10:00
  • Salle 385
    Bill 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 lesnombres 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 auxsolutions 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 telque $\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 nombresquadratiques réels par des rationnels, de fractions continues, deminorations de normes d?idéaux représentant des classes d?idéaux dans desordres quadratique réels, et à certains sous-groupes de $\mathrm{SL}_2(\mathbb{Z})$.


  • Le 21 janvier 2014 à 10:00
  • Salle 385
    Barinder 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 willcertainly have a rational $l$-isogeny. But what about the converse? Thatis, do isogenies on elliptic curves over number fields satisfy alocal-global principle? The answer is no: as shown by Andrew Sutherland;there is (precisely one) elliptic curve over $\mathbb{Q}$ which failsthis principle. In this talk I?ll discuss my (incomplete) work infinding all such failures over all quadratic fields.


  • Le 28 janvier 2014 à 10:00
  • Salle 385
    Hartmut Monien (Physikalisches Institut der Universität Bonn)
    Zeta values, random matrix theory and Euler-MacLaurin summation

    Gaussian quadrature is a well known technique for approximatingintegrals. In this talk we generalise these ideas to infinite sumsin general. For a broad class of functions the error of Gaussian summationis exponentially small as a function of the number of summation points. Thecorresponding new orthogonal polynomials have interesting asymptoticproperties, which are connected to Hankel determinants of Zeta values. Wewill present a random matrix theory which allows to connect theasymptotics of these determinants to a Riemann-Hilbert problem andexplain its connection to the Euler-MacLaurin summation.


  • Le 30 janvier 2014 à 09:30
  • Salle 385
    Hartmut 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 wasintroduced by Kulkarni in 1991 and is now known as Farey symbols. Withthe help of the Farey symbols it is possible to substantially extendmethods from analytic number theory. We will discuss three methods. Thefirst is a generalisation of a numerical algorithm originally due toHejhal. The second approach is based on a series of papers by Rademacherand Zuckerman which turned out to be very useful in the recent studies ofthe properties of Mock modular forms. A third surprisingly simple andpowerful method was recently discovered by us. We will present someinteresting non-congruence subgroups with interesting Galois groups.


  • Le 4 février 2014 à 10:00
  • Salle 385
    Marc Munsch (IMB)
    Moments des fonctions thêta

    Pour $\chi$ un caractère de Dirichlet modulo $q$, on définit sa fonctionthêta associée $\theta(x,\chi):=\sum_{n\geq 1}\chi(n)e^{-\frac{\pin^2x}{q}}$. Elle intervient habituellement dans la preuve de l?équationfonctionnelle de $L(s,\chi)$. Le calcul de l?asymptotique des moments desfonctions $L$ est un problème classique de théorie analytique des nombresétudié notamment afin de montrer que $L(1/2,\chi)eq 0$ pour ?beaucoup? decaractères. Il est conjecturé de façon analogue que $\theta(1,\chi)eq 0$.De rares contre-exemples ont été découverts par H. Cohen et D. Zagier maisla conjecture reste ouverte dans le cas d?un module premier. On étudie lesmoments 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.)


  • Le 20 février 2014 à 15:00
  • Salle 385
    Eduardo Friedman (Universidad de Chile)
    Cône de Shintani et degré topologique

  • Le 4 mars 2014 à 10:00
  • Salle 385
    John Boxall (Caen)
    Heuristiques sur les variétés abéliennes adaptées à la cryptographie à couplage

    Pendant cet exposé, nous proposerons des heuristiques concernant ladistribution asymptotique des variétés abéliennes sur les corps primairesadaptées à la cryptographie à couplage. Il s?agit d?un travail en communavec David Gruenewald.


  • Le 18 mars 2014 à 10:00
  • Salle 385
    P?nar K?l?çer (Leiden+IMB)
    The class number one problem for genus-2 curves

    The Gauss class number one problem for imaginary quadratic fields isequivalent to finding all elliptic curves over the rationals with complexmultiplication. I will quickly explain the relation between the classnumber one problem and the elliptic curves over the rationals. Then Iwill give the analogue of the class number one problem for genus-2 curveswith CM and sketch its solution.


  • Le 21 mars 2014 à 10:00
  • Salle 385
    Bertrand 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èreapproximation, être décrit par des équations discrètes écrites sur un arbreabstrait 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 ainsique les flux qui traversent les arêtes, a la structure d?un problème deDarcy (qui décrit les écoulements en milieu poreux) ou, en éliminant lesflux, 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érerdes flux en retour, ce qui prend la structure d?un problème dit deDirichlet-Neuman. Du fait de la régularité de la progression descaractéristiques géométriques au fil des générations, établi par desmesures expérimentales, il est tentant de faire tendre le nombre degénérations, égal à 23 dans la réalité, vers l?infini (d?extrapolerl?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 depression sur l?espace des bouts de cet arbre.

    Nous préciserons comment l?identification de la génération $n$ à $\Z/2^n\Z$, etde l?espace des bouts à la limite projective de ces ensembles, ie. l?anneaudes entiers dyadiques $\Z_2$, permet de donner une structure naturelle à cetarbre 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 del?arbre. De plus, l?opérateur de ?ventilation? (qui à un champ de pressionassocie l?ensemble des flux correspondants) prend sous certaines hypothèsesla forme d?un simple opérateur de convolution.

    (Travail en collaboration avec F. Bernicot et D. Salort)


  • Le 24 mars 2014 à 10:00
  • Salle 385
    Emmanuel Thomé (Nancy)
    Un algorithme quasi-polynomial de calcul de logarithme discret en petite\n caractéristique
    The difficulty of computing discrete logarithms in fields $\mathbb F_{q^k}$depends on the relative sizes of $k$ and $q$. Until recently all thecases had a sub-exponential complexity of type $L(1/3)$, similar to thefactorization problem. In 2013, Joux designed a new algorithm with acomplexity of $L(1/4+\epsilon)$ in small characteristic. In the samespirit, we propose another heuristic algorithm that provides aquasi-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 belowthe limit $L_{q^k}(1/3)$, our algorithm loses its quasi-polynomialnature, but still surpasses the Function Field Sieve.
  • Le 1er avril 2014 à 10:00
  • Salle 385
    Amalia Pizarro-Madariaga (Valparaíso)
    Estimations for the Artin conductor

    In this talk, I will show two methods to improve Odlyzko?s lower boundfor the Artin conductor. We will begin by translating Odlyzko?s methodsto the language of explicit formulas, which yields an initial improvementon Odlyzko?s bound.

    Then we introduce a technique to take advantage of the contribution ofthe primes to further improve the lower bounds.


  • Le 8 avril 2014 à 09:00
  • Salle 385
    Monique Thonnat (Inria Bordeaux Sud-Ouest)
    Visite de la directrice du centre Inria Bordeaux

  • Le 13 mai 2014 à 10:00
  • Salle 385
    Henri Cohen (imb)
    Numerical recipes for multiprecision computations
    The aim of this talk is to give a number of very useful recipes fornumerical 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.
  • Le 20 mai 2014 à 10:00
  • Salle 385
    Alina Dudeanu (EPFL)
    Computing a Velu type formula for rational cyclic isogenies between\nisomorphism classes of Jacobians of genus two curves that are defined over a\nfinite field.

    We present an algorithm for computing isogenies of prime degreebetween Jacobians of smooth curves of genus two defined over finite fields. Weaim at applying this algorithm to problems that are encountered in curve-basedcryptography. In the genus one case, one of the goals is to construct with highprobability by using random walks an isogeny between two arbitrary classes ofisomorphic curves that belong to the same isogeny class. Another goal is tostudy the random self reducibility of the Discrete Logarithm Problem forisomorphism classes within the same isogeny class and extend the Weil descentattack to a larger family of curves. We could hope for similar positive resultsin the genus two case if given the proper input for the isogeny computationalgorithm, we are able to obtain fast enough, both the isogeny map and thetarget isogenous Jacobian (unique up to an isomorphism).


  • Le 3 juin 2014 à 10:00
  • Salle 385
    Gaetan 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 quarticCM-field that admit the same polarised ideal class group structure. Thisgeneralises a simpler result for imaginary quadratic fields. We giveapplications to computing endomorphism rings of abelian surfaces overfinite fields, and extending a completeness result of Murabayashi andUmegaki to a list of abelian surfaces over the rationals withcomplex multiplication by arbitrary orders.This is joint work with Marco Streng.


  • Le 8 juillet 2014 à 11:00
  • Salle 1
    Kamal Khuri Makdisi (American University of Beirut)
    Moduli interpretation of Eisenstein series

    Talk based on the preprint http://arxiv.org/abs/0903.1439


  • Le 10 juillet 2014 à 16:00
  • Salle 1
    Kamal 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 dansles 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), etprésentera des critères concrets suffisants pour certifier que lerésultat du calcul est bon.


  • Le 16 septembre 2014 à 10:00
  • Salle 385
    Fredrik Johansson (imb)
    Reliable multiprecision arithmetic for number theory

    Many calculations involving real or complex numbers can be doneprovably correctly by combining mathematical error bounds with arigorous error propagation scheme (interval arithmetic or ballarithmetic). An ongoing research subject is to develop efficientalgorithms and software implementations in this setting.

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


  • Le 23 septembre 2014 à 11:00
  • Salle 385
    Yuri Bilu and Bill Allombert (imb)
    Points CM sur les droites

    $\newcommand{\C}{{\mathbb{C}}}\newcommand{\Q}{{\mathbb{Q}}}\renewcommand{\Im}{{\mathrm{Im}}}$Let $\tau$ be an imaginary quadratic number with ${\Im\tau>0}$ and let$j$ denote the $j$-invariant function. According to the classicaltheory of Complex Multiplication, the complex number $j(\tau)$ is analgebraic integer. A CM-point in $\C^2$ is a point of the form$(j(\tau_1),j(\tau_2))$, where both $\tau_1$ and $\tau_2$ are imaginaryquadratic numbers.

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

    Relying on recent ideas of Lars Kühne, we obtain a very explicitversion 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}$.

    This is a joint work with Amalia Pizarro-Madariaga.


  • Le 30 septembre 2014 à 10:00
  • Salle 385
    Chloe Martindale (University of Leiden / IMB)
    An algorithm for computing Hilbert modular varieties

    We describe an algorithm for computing an analogue of the modularpolynomial for elliptic curves, for principally polarised (p.p.)abelian varieties with real multiplication (RM). Given a p.p. abelianvariety with RM by $\mathcal{O}_{F}$, where $\mathcal{O}_{F}$ is themaximal order in a totally real number field $F$, for any totallypositive 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 algebraicvariety which parametrises $\mu$-isogeny classes of p.p. abelianvarieties with RM by $\mathcal{O}_{F}$.

    This is work supervised by Marco Streng.


  • Le 7 octobre 2014 à 10:00
  • Salle 385
    Enea Milio (imb)
    Calcul des polynômes modulaires en genre 2

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


  • Le 21 octobre 2014 à 10:00
  • Salle 385
    Sorina Ionica (imb)
    Isogeny graphs with maximal real multiplication

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


  • Le 25 novembre 2014 à 10:00
  • Salle 385
    Henri Cohen (imb)
    A Pari/GP package for computing L-functions.

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


  • Le 2 décembre 2014 à 10:00
  • Salle 385
    Bill Allombert (imb)
    Symbolic integration in finite characteristic

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


  • Le 9 décembre 2014 à 10:00
  • Salle 385
    Alain Couvreur (INRIA & LIX, École Polytechnique)
    Une attaque polynomiale du schéma de McEliece basé sur les codes de Goppa 'sauvages'.

    Le schéma de McEliece est un schéma de chiffrement basé sur lescodes correcteurs d?erreurs dont la sécurité repose sur la difficulté àdécoder un code aléatoire. Parmi les différentes familles de codesalgébriques proposées pour ce schéma, les codes de Goppa classiques sontles seuls à résister à toutes les attaques algébriques, et ce, depuis prèsde 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 deGoppa ?sauvage? (Wild Goppa code) construit à partir d?une extension decorps quadratique. Cette attaque consiste à utiliser des propriétésmultiplicatives du code pour en calculer une filtration (i.e. une famillede sous-codes emboités) dont chaque élément est un code de Goppaclassique.

    Les propriétés algébriques de cette filtration permettent ensuite deretrouver entièrement la structure du code utilisé comme clé publique.Cette attaque a été implémentée en Magma et permet de casser en moinsd?une heure des clés proposées par Bernstein, Lange et Peters dont lasé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 attaquepolynomiale sur des codes de Goppa classiques n?ayant aucune symétrieapparente.

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


  • Le 9 décembre 2014 à 10:00
  • Salle 385
    Alain Couvreur (INRIA & LIX, École Polytechnique)
    Une attaque polynomiale du schéma de McEliece basé sur les codes de Goppa 'sauvages'.

    Le schéma de McEliece est un schéma de chiffrement basé sur lescodes correcteurs d?erreurs dont la sécurité repose sur la difficulté àdécoder un code aléatoire. Parmi les différentes familles de codesalgébriques proposées pour ce schéma, les codes de Goppa classiques sontles seuls à résister à toutes les attaques algébriques, et ce, depuis prèsde 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 deGoppa ?sauvage? (Wild Goppa code) construit à partir d?une extension decorps quadratique. Cette attaque consiste à utiliser des propriétésmultiplicatives du code pour en calculer une filtration (i.e. une famillede sous-codes emboités) dont chaque élément est un code de Goppaclassique.

    Les propriétés algébriques de cette filtration permettent ensuite deretrouver entièrement la structure du code utilisé comme clé publique.Cette attaque a été implémentée en Magma et permet de casser en moinsd?une heure des clés proposées par Bernstein, Lange et Peters dont lasé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 attaquepolynomiale sur des codes de Goppa classiques n?ayant aucune symétrieapparente.

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


  • 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.

    Afficher 2016 - 2015 - antérieurs