Le Laboratoire
Soutien à la recherche Accès à l’IMB Annuaire Organigramme
Recherche
Diffusion Logiciels Recherche Espace Entreprise Bibliothèque BMI
Evènements
Séminaires La semaine de l’IMB Manifestations Scientifiques
Actions Sociétales
Mission Parité Mission Environnement Mentorat Santé et sécurité International Researchers
Doctorant·es
Informatique
Site de la cellule Webmail FAQ Acheter du matériel Réserver du matériel Assistance (Help)
Intranet
IMB > Recherche > Séminaires

Séminaire de Théorie Algorithmique des Nombres

Responsables : Razvan Barbulescu et Wessel Van Woerden

Page du séminaire

  • Le 22 avril 2008
    • Séminaire de Théorie Algorithmique des Nombres
    Salle de Conference
    Karim Belabas
    Calcul de valeurs de fonctions L complexes I

  • Le 13 mai 2008
    • Séminaire de Théorie Algorithmique des Nombres
    Salle de Conference
    Karim Belabas
    Calcul de valeurs de fonctions L complexes II

  • Le 29 mai 2008
    • Séminaire de Théorie Algorithmique des Nombres
    Salle de Conference
    Pascal Molin
    Intégration numérique de fonctions analytiques

  • Le 3 juin 2008
    • Séminaire de Théorie Algorithmique des Nombres
    Salle de Conference
    Henri Cohen
    Fractions continues pour la fonction Gamma incomplète I

  • Le 10 juin 2008
    • Séminaire de Théorie Algorithmique des Nombres
    Salle de Conference
    Henri Cohen
    Fractions continues pour la fonction Gamma incomplète II

  • Le 30 septembre 2008
    • Séminaire de Théorie Algorithmique des Nombres
    Salle de Conference
    Eduardo Friedman Santiago de Chile
    Lower bounds for regulators of number fields

  • Le 7 octobre 2008
    • Séminaire de Théorie Algorithmique des Nombres
    Salle de Conference
    Henri Cohen
    Réciprocité cubique et équation de Mordell

  • Le 13 janvier 2009
    • Séminaire de Théorie Algorithmique des Nombres
    Salle de Conference
    Eduardo Friedman Santiago de Chile
    Barnes' multiple Gamma and zeta functions.and their application to totally real fields I

  • Le 20 janvier 2009
    • Séminaire de Théorie Algorithmique des Nombres
    Salle de Conference
    Eduardo Friedman Santiago de Chile
    Barnes' multiple Gamma and zeta functions.and their application to totally real fields II

  • Le 22 janvier 2009
    • Séminaire de Théorie Algorithmique des Nombres
    Salle de Conference
    Eduardo Friedman Santiago de Chile
    Barnes' multiple Gamma and zeta functions.and their application to totally real fields III

  • Le 3 février 2009
    • Séminaire de Théorie Algorithmique des Nombres
    Salle de Conference
    Eduardo Friedman Santiago de Chile
    Barnes' multiple Gamma and zeta functions.and their application to totally real fields IV

  • Le 4 mai 2009
    • Séminaire de Théorie Algorithmique des Nombres
    Salle de Conference
    Jean-Paul Cerri
    Corps euclidiens: introduction

  • Le 12 mai 2009
    • Séminaire de Théorie Algorithmique des Nombres
    Salle de Conference
    Jean-Paul Cerri
    Corps euclidiens: algorithmique. I

  • Le 19 mai 2009
    • Séminaire de Théorie Algorithmique des Nombres
    Salle de Conference
    Jean-Paul Cerri
    Corps euclidiens: algorithmique. II

  • Le 19 juin 2009
    • Séminaire de Théorie Algorithmique des Nombres
    Salle de Conference
    Luca de Feo Palaiseau
    Calcul d'isogénies en petite caractéristique

  • Le 15 septembre 2009
    • Séminaire de Théorie Algorithmique des Nombres
    Salle de Conference
    Andreas Enge
    Comptes rendus de SAC et ECC à Calgary

  • Le 22 septembre 2009
    • Séminaire de Théorie Algorithmique des Nombres
    Salle de Conference
    Karim Belabas
    Programmer avec la bibliothèque Pari pour les nuls

  • Le 29 septembre 2009
    • Séminaire de Théorie Algorithmique des Nombres
    Salle de Conference
    Karim Belabas
    The Cohen-Lenstra heuristics for finite Abelian groups.(d'après Johannes Lengler)

  • Le 6 octobre 2009
    • Séminaire de Théorie Algorithmique des Nombres
    Salle de Conference
    Jean-François Biasse
    An L(1/3) algorithm for ideal class group and regulator computation in.certain number fields

  • Le 3 novembre 2009
    • Séminaire de Théorie Algorithmique des Nombres
    Salle de Conference
    Henri Cohen
    Quelques calculs de sommes de Kloosterman et de fonctions L associées.aux variétés de Calabi-Yau. I

  • Le 6 novembre 2009
    • Séminaire de Théorie Algorithmique des Nombres
    Salle de Conference
    Andreas Enge
    Invariants de classes (presque) sans réciprocité de Shimura

  • Le 10 novembre 2009
    • Séminaire de Théorie Algorithmique des Nombres
    Salle de Conference
    Henri Cohen
    Quelques calculs de sommes de Kloosterman et de fonctions L associées.aux variétés de Calabi-Yau. II

  • Le 17 novembre 2009
    • Séminaire de Théorie Algorithmique des Nombres
    Salle de Conference
    Marco Streng Leiden
    Abelian surfaces admitting an (l,l)-endomorphism

  • Le 20 novembre 2009
    • Séminaire de Théorie Algorithmique des Nombres
    Salle de Conference
    Gaëtan Bisson Nancy
    Calcul des anneaux d'endomorphismes des variétés abéliennes.sur les corps finis

  • Le 24 novembre 2009
    • Séminaire de Théorie Algorithmique des Nombres
    Salle de Conference
    Andreas Enge
    Multiplication complexe de courbes elliptiques:.applications cryptologiques

  • Le 8 décembre 2009
    • Séminaire de Théorie Algorithmique des Nombres
    Salle de Conference
    Andreas Enge
    Multiplication complexe de courbes elliptiques:.construction de courbes à petit degré de plongement

  • Le 15 décembre 2009
    • Séminaire de Théorie Algorithmique des Nombres
    Salle de Conference
    Andreas Enge
    Multiplication complexe de courbes elliptiques:.algorithmes à base d'approximations flottantes,.complexité et implantation

  • Le 12 janvier 2010
    • Séminaire de Théorie Algorithmique des Nombres
    Salle de Conference
    Pascal Molin
    Méthode des trapèzes et fonctions méromorphes I

  • Le 19 janvier 2010
    • Séminaire de Théorie Algorithmique des Nombres
    Salle de Conference
    Pascal Molin
    Méthode des trapèzes et fonctions méromorphes II

  • Le 26 janvier 2010
    • Séminaire de Théorie Algorithmique des Nombres
    Salle de Conference
    Henri Cohen
    Recherche de bons exemples pour la conjecture ABC et la conjecture.de Hall I (d'apres Elkies et Calvo-Herranz-Saez)

  • Le 2 février 2010
    • Séminaire de Théorie Algorithmique des Nombres
    Salle de Conference
    Henri Cohen
    Recherche de bons exemples pour la conjecture ABC et la conjecture.de Hall II (d'apres Elkies et Calvo-Herranz-Saez)

  • Le 11 février 2010
    • Séminaire de Théorie Algorithmique des Nombres
    Salle de Conference
    Damien Robert Nancy
    Calcul de pairings avec les fonctions thétas

  • Le 12 février 2010
    • Séminaire de Théorie Algorithmique des Nombres
    Salle de Conference
    Damien Robert Nancy
    Computing isogenies between abelian varieties

  • Le 16 février 2010
    • Séminaire de Théorie Algorithmique des Nombres
    Salle de Conference
    Eduardo Friedman Santiago de Chile
    Special values of Dirichlet series and Zeta integrals.associated to polynomials

  • Le 2 mars 2010
    • Séminaire de Théorie Algorithmique des Nombres
    Salle de Conference
    Pieter Rozenhart
    Reduction theory of binary forms over polynomial rings I

  • Le 9 mars 2010
    • Séminaire de Théorie Algorithmique des Nombres
    Salle de Conference
    Pieter Rozenhart
    Reduction theory of binary forms over polynomial rings II

  • Le 16 mars 2010
    • Séminaire de Théorie Algorithmique des Nombres
    Salle de Conference
    Henri Cohen
    Sommes de Gauss, sommes de Jacobi, et comptage de points sur des.hypersurfaces quasi-diagonales I

  • Le 23 mars 2010
    • Séminaire de Théorie Algorithmique des Nombres
    Salle de Conference
    Henri Cohen
    Sommes de Gauss, sommes de Jacobi, et comptage de points sur des.hypersurfaces quasi-diagonales II

  • Le 30 mars 2010
    • Séminaire de Théorie Algorithmique des Nombres
    Salle de Conference
    Henri Cohen
    Sommes de Gauss, sommes de Jacobi, et comptage de points sur des.hypersurfaces quasi-diagonales III

  • Le 6 avril 2010
    • Séminaire de Théorie Algorithmique des Nombres
    Salle de Conference
    Loïc Grenié Bologna
    Comment vérifier si deux représentations galoisiennes ont la.même semi-simplifiée

  • Le 18 mai 2010
    • Séminaire de Théorie Algorithmique des Nombres
    Salle de Conference
    Andreas Enge
    The queen of mathematics in communication security

  • Le 8 juin 2010
    • Séminaire de Théorie Algorithmique des Nombres
    Salle de Conference
    Pierre Lezowski
    Algorithme de détermination d'euclidianité et applications I

  • Le 15 juin 2010
    • Séminaire de Théorie Algorithmique des Nombres
    Salle de Conference
    Pierre Lezowski
    Algorithme de détermination d'euclidianité et applications II

  • Le 9 septembre 2010
    • Séminaire de Théorie Algorithmique des Nombres
    Salle de Conference
    Jean-François Biasse
    Subexponential algorithms for number fields

  • Le 17 septembre 2010
    • Séminaire de Théorie Algorithmique des Nombres
    Salle de Conference
    Henri Cohen
    Fonctions L de motifs hypergéométriques I

  • Le 24 septembre 2010
    • Séminaire de Théorie Algorithmique des Nombres
    Salle de Conference
    Michael Drmota Wien
    An asymptotic analysis of Cuckoo hashing

  • Le 1er octobre 2010
    • Séminaire de Théorie Algorithmique des Nombres
    Salle de Conference
    Vincent Verneuil
    Scalar multiplication on smart cards and side-channel analysis

  • Le 7 octobre 2010
    • Séminaire de Théorie Algorithmique des Nombres
    Salle de Conference
    Paul Zimmermann Nancy
    Peut-on calculer sur ordinateur?

  • Le 12 octobre 2010
    • Séminaire de Théorie Algorithmique des Nombres
    Salle de Conference
    Manuel Charlemagne Dublin
    The security of the discrete logarithm problem (DLP) in the.context of pairings

  • Le 12 octobre 2010
    • Séminaire de Théorie Algorithmique des Nombres
    Salle de Conference
    Manuel Charlemagne Dublin
    The security of the discrete logarithm problem (DLP) in the.context of pairings

  • Le 15 octobre 2010
    • Séminaire de Théorie Algorithmique des Nombres
    Salle de Conference
    Pascal Molin
    Intégration numérique et calculs de fonctions L

  • Le 22 octobre 2010
    • Séminaire de Théorie Algorithmique des Nombres
    Salle de Conference
    Henri Cohen
    Fonctions L de motifs hypergéométriques II

  • Le 19 novembre 2010
    • Séminaire de Théorie Algorithmique des Nombres
    Salle de Conference
    Pieter Rozenhart
    Computing quadratic function fields with high 3-rank via cubic field.tabulation

  • Le 26 novembre 2010
    • Séminaire de Théorie Algorithmique des Nombres
    Salle de Conference
    Andreas Enge
    HQFRU HIDXW LODYR LUODE RQQHF OHI

  • Le 26 novembre 2010
    • Séminaire de Théorie Algorithmique des Nombres
    Salle de Conference
    Andreas Enge
    HQFRU HIDXW LODYR LUODE RQQHF OHI

  • Le 6 décembre 2010
    • Séminaire de Théorie Algorithmique des Nombres
    Salle de Conference
    Bill Allombert
    Calcul de groupes d'inertie

  • Le 6 décembre 2010
    • Séminaire de Théorie Algorithmique des Nombres
    Salle de Conference
    Bill Allombert
    Calcul de groupes d'inertie

  • Le 7 décembre 2010
    • Séminaire de Théorie Algorithmique des Nombres
    Salle de Conference
    Julien Blondeau Besançon
    Relèvement de représentations avec conditions en p

  • Le 7 décembre 2010
    • Séminaire de Théorie Algorithmique des Nombres
    Salle de Conference
    Julien Blondeau Besançon
    Relèvement de représentations avec conditions en p

  • Le 7 décembre 2010
    • Séminaire de Théorie Algorithmique des Nombres
    Salle de Conference
    Julien Blondeau Besançon
    Relèvement de représentations avec conditions en p

  • Le 7 décembre 2010
    • Séminaire de Théorie Algorithmique des Nombres
    Salle de Conference
    Julien Blondeau Besançon
    Relèvement de représentations avec conditions en p

  • Le 8 décembre 2010
    • Séminaire de Théorie Algorithmique des Nombres
    Salle de Conference
    Damien Robert
    Variétés abéliennes, fonctions théta, applications I

  • Le 8 décembre 2010
    • Séminaire de Théorie Algorithmique des Nombres
    Salle de Conference
    Damien Robert
    Variétés abéliennes, fonctions théta, applications I

  • Le 8 décembre 2010
    • Séminaire de Théorie Algorithmique des Nombres
    Salle de Conference
    Damien Robert
    Variétés abéliennes, fonctions théta, applications I

  • Le 8 décembre 2010
    • Séminaire de Théorie Algorithmique des Nombres
    Salle de Conference
    Damien Robert
    Variétés abéliennes, fonctions théta, applications I

  • Le 9 décembre 2010
    • Séminaire de Théorie Algorithmique des Nombres
    Salle de Conference
    Pierre Parent
    Points rationnels de courbes modulaires I:.estimations analytiques en grand niveau

  • Le 9 décembre 2010
    • Séminaire de Théorie Algorithmique des Nombres
    Salle de Conference
    Pierre Parent
    Points rationnels de courbes modulaires I:.estimations analytiques en grand niveau

  • Le 9 décembre 2010
    • Séminaire de Théorie Algorithmique des Nombres
    Salle de Conference
    Pierre Parent
    Points rationnels de courbes modulaires I:.estimations analytiques en grand niveau

  • Le 9 décembre 2010
    • Séminaire de Théorie Algorithmique des Nombres
    Salle de Conference
    Pierre Parent
    Points rationnels de courbes modulaires I:.estimations analytiques en grand niveau

  • Le 10 décembre 2010
    • Séminaire de Théorie Algorithmique des Nombres
    Salle de Conference
    Andreas Enge
    Polynômes de classes par restes chinois

  • Le 10 décembre 2010
    • Séminaire de Théorie Algorithmique des Nombres
    Salle de Conference
    Andreas Enge
    Polynômes de classes par restes chinois

  • Le 10 décembre 2010
    • Séminaire de Théorie Algorithmique des Nombres
    Salle de Conference
    Andreas Enge
    Polynômes de classes par restes chinois

  • Le 17 décembre 2010
    • Séminaire de Théorie Algorithmique des Nombres
    Salle de Conference
    Vincent Verneuil
    Scalar multiplication on smart cards and side-channel analysis, le.retour

  • Le 17 décembre 2010
    • Séminaire de Théorie Algorithmique des Nombres
    Salle de Conference
    Vincent Verneuil
    Scalar multiplication on smart cards and side-channel analysis, le.retour

  • Le 27 janvier 2011
    • Séminaire de Théorie Algorithmique des Nombres
    Salle de Conference
    Adrien Poteaux Paris 6
    Calculs rapides modulo un ensemble triangulaire et.applications

  • Le 3 février 2011
    • Séminaire de Théorie Algorithmique des Nombres
    Salle de Conference
    Bill Allombert
    Calcul de points rationnels sur une courbe elliptique par la méthode. de Silverman-Cremona-Delaunay.

  • Le 10 février 2011
    • Séminaire de Théorie Algorithmique des Nombres
    Salle de Conference
    Jean-Marc Couveignes
    Géométrie des tangentes d'inflexion d'une cubique plane et. les pseudo-paramétrisations qui s'en déduisent

  • Le 17 février 2011
    • Séminaire de Théorie Algorithmique des Nombres
    Salle de Conference
    Nicolas Mascot
    Algorithmique pour les jacobiennes de courbes:. algorithmes classiques et méthodes de Khuri-Maksidi

  • Le 24 février 2011
    • Séminaire de Théorie Algorithmique des Nombres
    Salle de Conference
    Christophe Ritzenthaler
    Couplages sur les courbes d'Edwards et formules d'addition complètes

  • Le 3 mars 2011
    • Séminaire de Théorie Algorithmique des Nombres
    Salle de Conference
    Martin Weimann
    Factorisation torique des polynômes bivariés

  • Le 10 mars 2011
    • Séminaire de Théorie Algorithmique des Nombres
    Salle de Conference
    Karim Belabas
    Termes restes dans le théorème de Davenport-Heilbronn I

  • Le 17 mars 2011
    • Séminaire de Théorie Algorithmique des Nombres
    Salle de Conference
    Karim Belabas
    Termes restes dans le théorème de Davenport-Heilbronn II

  • Le 31 mars 2011
    • Séminaire de Théorie Algorithmique des Nombres
    Salle de Conference
    Karim Belabas
    Termes restes dans le théorème de Davenport-Heilbronn III

  • Le 14 avril 2011
    • Séminaire de Théorie Algorithmique des Nombres
    Salle de Conference
    Vanessa Vitse Versailles
    Attaques par recouvrement et décomposition du logarithme discret sur. courbes elliptiques.

  • Le 28 avril 2011
    • Séminaire de Théorie Algorithmique des Nombres
    Salle de Conference
    Jérémie Le Borgne Rennes
    Algorithmique des phi-modules pour les représentations. galoisiennes p-adiques

  • Le 5 mai 2011
    • Séminaire de Théorie Algorithmique des Nombres
    Salle de Conference
    Andy Novocin Lyon
    L1 a new quasi-linear LLL algorithm

  • Le 19 mai 2011
    • Séminaire de Théorie Algorithmique des Nombres
    Salle de Conference
    Lassina Dembelé Warwick
    Sur la conjecture de Gross

  • Le 26 mai 2011
    • Séminaire de Théorie Algorithmique des Nombres
    Salle de Conference
    Jean-François Biasse Calgary
    Calcul du groupe de classes et des unités dans les corps de nombres

  • Le 7 septembre 2011
    • Séminaire de Théorie Algorithmique des Nombres
    Salle de Conference
    Jérôme Milan
    Pairings implementation in the PARI computer algebra system

  • Le 23 septembre 2011
    • Séminaire de Théorie Algorithmique des Nombres
    Salle de Conference
    Jean-Marc Couveignes
    Paramétrisation des cubiques planes à l'aide d'un radical.cubique

  • Le 28 septembre 2011 à 15:00
    • Séminaire de Théorie Algorithmique des Nombres
    Salle 385
    Peter Stevenhagen Leiden
    Radical extensions and primitive roots

  • Le 30 septembre 2011 à 14:00
    • Séminaire de Théorie Algorithmique des Nombres
    Salle de conférences
    Damien Robert
    Couplages optimaux sur variétés abéliennes via les fonctions.thêta

  • Le 5 octobre 2011 à 15:00
    • Séminaire de Théorie Algorithmique des Nombres
    Salle 385
    Michael Rubinstein Waterloo
    Conjectures, experiments, and algorithms concerning the moments.of L(1/2,?d)

  • Le 13 octobre 2011 à 14:00
    • Séminaire de Théorie Algorithmique des Nombres
    Salle de conférences
    Julio Brau
    Computing the image of Galois representations attached to elliptic curves

  • Le 25 octobre 2011 à 15:00
    • Séminaire de Théorie Algorithmique des Nombres
    Salle 385
    Bill Allombert
    Développement de Pari/Gp sous Git

  • Le 25 octobre 2011 à 15:00
    • Séminaire de Théorie Algorithmique des Nombres
    Salle 385
    Bill Allombert
    Développement de Pari/Gp sous Git

  • Le 25 octobre 2011 à 15:00
    • Séminaire de Théorie Algorithmique des Nombres
    Salle 385
    Bill Allombert
    Développement de Pari/Gp sous Git

  • Le 25 octobre 2011 à 15:00
    • Séminaire de Théorie Algorithmique des Nombres
    Salle 385
    Bill Allombert
    Développement de Pari/Gp sous Git

  • Le 25 octobre 2011 à 15:00
    • Séminaire de Théorie Algorithmique des Nombres
    Salle 385
    Bill Allombert
    Développement de Pari/Gp sous Git

  • Le 25 octobre 2011 à 15:00
    • Séminaire de Théorie Algorithmique des Nombres
    Salle 385
    Bill Allombert
    Développement de Pari/Gp sous Git

  • Le 25 octobre 2011 à 15:00
    • Séminaire de Théorie Algorithmique des Nombres
    Salle 385
    Bill Allombert
    Développement de Pari/Gp sous Git

  • Le 25 octobre 2011 à 15:00
    • Séminaire de Théorie Algorithmique des Nombres
    Salle 385
    Bill Allombert
    Développement de Pari/Gp sous Git

  • Le 25 octobre 2011 à 15:00
    • Séminaire de Théorie Algorithmique des Nombres
    Salle 385
    Bill Allombert
    Développement de Pari/Gp sous Git

  • Le 25 octobre 2011 à 15:00
    • Séminaire de Théorie Algorithmique des Nombres
    Salle 385
    Bill Allombert
    Développement de Pari/Gp sous Git

  • Le 25 octobre 2011 à 15:00
    • Séminaire de Théorie Algorithmique des Nombres
    Salle 385
    Bill Allombert
    Développement de Pari/Gp sous Git

  • Le 1er décembre 2011 à 14:00
    • Séminaire de Théorie Algorithmique des Nombres
    Salle de conférences
    Athanasios Angelakis
    Isomorphic Absolute Galois Groups of Number Fields

  • Le 2 février 2012 à 15:30
    • Séminaire de Théorie Algorithmique des Nombres
    Salle 2
    Vincent Verneuil
    Square Always Exponentiation

  • Le 24 février 2012 à 10:00
    • Séminaire de Théorie Algorithmique des Nombres
    Salle 385
    Jean-Marc Couveignes
    Logarithmes discrets elliptiques par recouvrement I

  • Le 8 mars 2012 à 11:00
    • Séminaire de Théorie Algorithmique des Nombres
    Salle 1
    Jean-Marc Couveignes
    Logarithmes discrets elliptiques par recouvrement II

  • Le 12 mars 2012 à 11:00
    • Séminaire de Théorie Algorithmique des Nombres
    Salle 385
    Vasily Golyshev
    Searching for congruences of Galois representations

  • Le 22 mars 2012 à 13:30
    • Séminaire de Théorie Algorithmique des Nombres
    Salle 385
    Henri Cohen
    Lacunarité des quotients η

  • Le 29 mars 2012 à 13:30
    • Séminaire de Théorie Algorithmique des Nombres
    Salle 385
    Marco Streng Warwick
    Smaller class invariants for quartic CM-fields

  • Le 12 avril 2012 à 13:30
    • Séminaire de Théorie Algorithmique des Nombres
    Salle de conférences
    Gaëtan Bisson Sydney
    Un algorithme à la Pollard pour le problème du sac à dos

  • Le 10 mai 2012 à 13:30
    • Séminaire de Théorie Algorithmique des Nombres
    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
    • Séminaire de Théorie Algorithmique des Nombres
    Salle 385
    Pierre Lezowski
    Corps de quaternions euclidiens

  • Le 2 juillet 2012 à 15:00
    • Séminaire de Théorie Algorithmique des Nombres
    Salle 385
    Bernhard Schmidt Singapore
    Values and ideals in combinatorial problems

  • Le 11 septembre 2012 à 10:00
    • Séminaire de Théorie Algorithmique des Nombres
    Salle 385
    Enea Milio Montpellier
    Techniques de criblage pour la factorisation et le calcul de logarithmes. discrets

  • Le 18 septembre 2012 à 10:00
    • Séminaire de Théorie Algorithmique des Nombres
    Salle 385
    Karim Belabas
    Calcul de résidus de la fonction zeta

  • Le 25 septembre 2012 à 10:00
    • Séminaire de Théorie Algorithmique des Nombres
    Salle 385
    Fabien Pazuki
    Décompositions en hauteurs locales sur les courbes elliptiques I

  • Le 2 octobre 2012 à 10:00
    • Séminaire de Théorie Algorithmique des Nombres
    Salle 385
    Fabien Pazuki
    Décompositions en hauteurs locales sur les courbes elliptiques II

  • Le 9 octobre 2012 à 10:00
    • Séminaire de Théorie Algorithmique des Nombres
    Salle 385
    Fernando Mario
    Packings of bodies in Euclidean space

  • Le 16 octobre 2012 à 10:00
    • Séminaire de Théorie Algorithmique des Nombres
    Salle 385
    Karim Belabas
    Tomographie arithmétique

  • Le 23 octobre 2012 à 10:00
    • Séminaire de Théorie Algorithmique des Nombres
    Salle 385
    Henri Cohen
    Comptage des corps cubiques et quartiques

  • Le 30 octobre 2012 à 10:00
    • Séminaire de Théorie Algorithmique des Nombres
    Salle 385
    Luca De Feo
    Towards Quantum-Resistant Cryptosystems from Supersingular Elliptic Curve Isogenies

  • Le 20 novembre 2012 à 10:00
    • Séminaire de Théorie Algorithmique des Nombres
    Salle 385
    Bill Allombert
    Comptage de points sur les courbes elliptiques en petite caractéristique

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

  • Le 8 janvier 2013 à 10:00
    • Séminaire de Théorie Algorithmique des Nombres
    IMB: Salle 385
    Philippe Jaming imb
    Problème de la phase dans le cadre discret

  • Le 22 janvier 2013 à 10:00
    • Séminaire de Théorie Algorithmique des Nombres
    Salle 385
    Hamish Ivey-Law imb
    Arithmetic on Jacobians of relative curves

  • Le 29 janvier 2013 à 10:00
    • Séminaire de Théorie Algorithmique des Nombres
    Salle 385
    Nicolas Mascot imb
    Calcul de représentations galoisiennes modulaires

  • Le 5 février 2013 à 10:00
    • Séminaire de Théorie Algorithmique des Nombres
    Salle 385
    Sorina Ionica ENS Paris
    Algorithms for isogeny graphs

  • Le 19 février 2013 à 10:00
    • Séminaire de Théorie Algorithmique des Nombres
    Salle 385
    Tony Ezome Université de Masuku ? Franceville\, Gabon
    A faster pseudo-primality test

  • Le 26 février 2013 à 10:00
    • Séminaire de Théorie Algorithmique des Nombres
    Salle 385
    Marie-Françoise Roy Rennes
    Algorithme diviser pour régner pour les cartes routières

  • Le 5 mars 2013 à 09:30
    • Séminaire de Théorie Algorithmique des Nombres
    IMB: Salle 385
    Paul Dorbec Labri
    A propos de domination dans les graphes.

  • Le 19 mars 2013 à 10:00
    • Séminaire de Théorie Algorithmique des Nombres
    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
    • Séminaire de Théorie Algorithmique des Nombres
    Salle 385
    Pierre Lezowski imb
    Groupe de classe d'Arakelov

  • Le 16 avril 2013 à 10:00
    • Séminaire de Théorie Algorithmique des Nombres
    IMB: Salle 385
    Ralf Klasing Labri
    Identifying coDes in Evolving grAphs (IDEA).

  • Le 23 avril 2013 à 10:00
    • Séminaire de Théorie Algorithmique des Nombres
    Salle 385
    Pierre Chrétien imb
    Calcul de corps de classe de rayon de courbes de genre $g \neq 0$.

  • Le 14 mai 2013 à 10:00
    • Séminaire de Théorie Algorithmique des Nombres
    Salle 385
    Maike Massierer University of Basel
    Point Compression for the Trace Zero Variety

  • Le 28 mai 2013 à 10:00
    • Séminaire de Théorie Algorithmique des Nombres
    IMB: Salle 385
    Achill Schürmann Universität Rostock
    Exploiting Symmetries in Polyhedral Computations

  • Le 11 juin 2013 à 10:00
    • Séminaire de Théorie Algorithmique des Nombres
    Salle 385
    Henri Cohen imb
    A first package for modular forms in Pari/GP

  • Le 18 juin 2013 à 10:00
    • Séminaire de Théorie Algorithmique des Nombres
    IMB: Salle 385
    Sinai Robins (Nanyang Technological University (Singapore))
    Cone theta functions and what they tell us about the.irrationality of spherical polytope volumes.

  • Le 10 septembre 2013 à 10:00
    • Séminaire de Théorie Algorithmique des Nombres
    Salle 385
    Friedrich Panitz Paderborn
    An algorithm to enumerate quartic fields, after Bhargava.

  • Le 24 septembre 2013 à 10:00
    • Séminaire de Théorie Algorithmique des Nombres
    Salle 385
    Hamish Ivey-Law imb
    The Riemann-Roch problem for divisors on two classes of surfaces

  • Le 4 octobre 2013 à 14:00
    • Séminaire de Théorie Algorithmique des Nombres
    LaBRI: Salle 178
    Sylvia Bianchi ()
    Polyhedra associated with identifying codes

  • Le 25 octobre 2013 à 14:00
    • Séminaire de Théorie Algorithmique des Nombres
    LaBRI: Salle 178
    Gilles Zémor ()
    Graphes sur des surfaces et codes quantiques

  • Le 5 novembre 2013 à 10:00
    • Séminaire de Théorie Algorithmique des Nombres
    IMB: Salle 385
    Renaud Coulangeon imb
    Algorithmes de Voronoi et groupes d'unités

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

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

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

  • Le 10 décembre 2013 à 10:00
    • Séminaire de Théorie Algorithmique des Nombres
    Salle 385
    Bill Allombert imb
    Minimums de formes quadratiques

  • Le 21 janvier 2014 à 10:00
    • Séminaire de Théorie Algorithmique des Nombres
    Salle 385
    Barinder Banwait imb
    Local-Global for Isogenies on Elliptic Curves

  • Le 28 janvier 2014 à 10:00
    • Séminaire de Théorie Algorithmique des Nombres
    Salle 385
    Hartmut Monien Physikalisches Institut der Universität Bonn
    Zeta values, random matrix theory and Euler-MacLaurin summation

  • Le 30 janvier 2014 à 09:30
    • Séminaire de Théorie Algorithmique des Nombres
    Salle 385
    Hartmut Monien Physikalisches Institut der Universität Bonn
    Calculating rational coverings for subgroups of ${\rm PSL}_{2}\left(\mathbb{Z}\right)$ efficiently

  • Le 4 février 2014 à 10:00
    • Séminaire de Théorie Algorithmique des Nombres
    Salle 385
    Marc Munsch IMB
    Moments des fonctions thêta

  • Le 20 février 2014 à 15:00
    • Séminaire de Théorie Algorithmique des Nombres
    Salle 385
    Eduardo Friedman Universidad de Chile
    Cône de Shintani et degré topologique

  • Le 4 mars 2014 à 10:00
    • Séminaire de Théorie Algorithmique des Nombres
    Salle 385
    John Boxall Caen
    Heuristiques sur les variétés abéliennes adaptées à la cryptographie à couplage

  • Le 18 mars 2014 à 10:00
    • Séminaire de Théorie Algorithmique des Nombres
    Salle 385
    P?nar K?l?çer Leiden+IMB
    The class number one problem for genus-2 curves

  • Le 21 mars 2014 à 10:00
    • Séminaire de Théorie Algorithmique des Nombres
    Salle 385
    Bertrand Maury Paris-Sud
    Arbre bronchique infini et entiers dyadiques

  • Le 24 mars 2014 à 10:00
    • Séminaire de Théorie Algorithmique des Nombres
    Salle 385
    Emmanuel Thomé Nancy
    Un algorithme quasi-polynomial de calcul de logarithme discret en petite. caractéristique

  • Le 1er avril 2014 à 10:00
    • Séminaire de Théorie Algorithmique des Nombres
    Salle 385
    Amalia Pizarro-Madariaga Valparaíso
    Estimations for the Artin conductor

  • Le 8 avril 2014 à 09:00
    • Séminaire de Théorie Algorithmique des Nombres
    Salle 385
    Monique Thonnat Inria Bordeaux Sud-Ouest
    Visite de la directrice du centre Inria Bordeaux

  • Le 13 mai 2014 à 10:00
    • Séminaire de Théorie Algorithmique des Nombres
    Salle 385
    Henri Cohen imb
    Numerical recipes for multiprecision computations

  • Le 20 mai 2014 à 10:00
    • Séminaire de Théorie Algorithmique des Nombres
    Salle 385
    Alina Dudeanu EPFL
    Computing a Velu type formula for rational cyclic isogenies between.isomorphism classes of Jacobians of genus two curves that are defined over a.finite field.

  • Le 3 juin 2014 à 10:00
    • Séminaire de Théorie Algorithmique des Nombres
    Salle 385
    Gaetan Bisson University of French Polynesia
    On polarised class groups of orders in quartic CM-fields

  • Le 8 juillet 2014 à 11:00
    • Séminaire de Théorie Algorithmique des Nombres
    Salle 1
    Kamal Khuri Makdisi American University of Beirut
    Moduli interpretation of Eisenstein series

  • Le 10 juillet 2014 à 16:00
    • Séminaire de Théorie Algorithmique des Nombres
    Salle 1
    Kamal Khuri Makdisi American University of Beirut
    On divisor group arithmetic for typical divisors on curves

  • Le 16 septembre 2014 à 10:00
    • Séminaire de Théorie Algorithmique des Nombres
    Salle 385
    Fredrik Johansson imb
    Reliable multiprecision arithmetic for number theory
    Many calculations involving real or complex numbers can be done provably correctly by combining mathematical error bounds with a rigorous error propagation scheme (interval arithmetic or ball arithmetic). An ongoing research subject is to develop efficient algorithms and software implementations in this setting.
  • Le 23 septembre 2014 à 11:00
    • Séminaire de Théorie Algorithmique des Nombres
    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 classical theory of Complex Multiplication, the complex number $j(\tau)$ is an algebraic 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 imaginary quadratic numbers.
  • Le 30 septembre 2014 à 10:00
    • Séminaire de Théorie Algorithmique des Nombres
    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 modular polynomial for elliptic curves, for principally polarised (p.p.) abelian varieties with real multiplication (RM). Given a p.p. abelian variety with RM by $\mathcal{O}_{F}$, where $\mathcal{O}_{F}$ is the maximal order in a totally real number field $F$, for any totally positive prime $\mu$ in $\mathcal{O}_{F}$, one can find a "$\mu$-isogenous" p.p. abelian variety with RM by $\mathcal{O}_{F}$. We describe an algorithm to compute a birational model for an algebraic variety which parametrises $\mu$-isogeny classes of p.p. abelian varieties with RM by $\mathcal{O}_{F}$.
  • Le 7 octobre 2014 à 10:00
    • Séminaire de Théorie Algorithmique des Nombres
    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 de Régis Dupont (datant de 2006) quant au calcul des polynômes modulaires en genre 2. Ces polynômes dépendent des invariants d'Igusa, qui sont une généralisation de la fonction $j$ dans le genre 1, et permettent d'obtenir toutes les variétés abéliennes isogènes à une variété abélienne donnée. Dans un second temps, nous expliquerons comment généraliser ces polynômes à d'autres invariants, comment les calculer et décrirons certaines de leurs propriétés, notamment le lien entre le dénominateur d'un coefficient du polynôme modulaire et les surfaces de Humbert.
  • Le 21 octobre 2014 à 10:00
    • Séminaire de Théorie Algorithmique des Nombres
    Salle 385
    Sorina Ionica imb
    Isogeny graphs with maximal real multiplication
    An isogeny graph is a graph whose vertices are principally polarized abelian varieties and whose edges are isogenies between these varieties. In his thesis, Kohel described the structure of isogeny graphs for elliptic curves and showed that one may compute the endomorphism ring of an elliptic curve defined over a finite field by using a depth first search algorithm in the graph. In dimension 2, the structure of isogeny graphs is less understood and existing algorithms for computing endomorphism rings are very expensive. We fully describe isogeny graphs of genus 2 jacobians, with maximal real multiplication. Over finite fields, we derive a depth first search algorithm for computing endomorphism rings locally at prime numbers, if the real multiplication is maximal. To the best of our knowledge, this is the first DFS-based algorithm in genus 2. This is joint work with Emmanuel Thomé.
  • Le 25 novembre 2014 à 10:00
    • Séminaire de Théorie Algorithmique des Nombres
    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 computing with L-functions of any reasonable degree. Most of the talk will be computer demonstrations of examples. The audience can bring their own favourite L-functions, as long as they are easy to implement and most importantly that their conductor be not too large. This will enable me to add to the examples that I will present, and/or find bugs.
  • Le 2 décembre 2014 à 10:00
    • Séminaire de Théorie Algorithmique des Nombres
    Salle 385
    Bill Allombert imb
    Symbolic integration in finite characteristic
    A well-known result by Liouville shows that some elementary functions of a real or complex variable does not admit elementary antiderivatives, the usual example being $\exp(-x^2)$. In 1968, Risch gave an algorithm to decide if an elementary function admit an elementary antiderivative. Elementary functions can be defined in term of differentials fields which allow a natural definition over fields of finite characteristic. We discuss the problem of elementary antiderivative in this context, and we extent it to elementary solutions to linear differential equations.
  • Le 9 décembre 2014 à 10:00
    • Séminaire de Théorie Algorithmique des Nombres
    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 les codes correcteurs d'erreurs dont la sécurité repose sur la difficulté à décoder un code aléatoire. Parmi les différentes familles de codes algébriques proposées pour ce schéma, les codes de Goppa classiques sont les seuls à résister à toutes les attaques algébriques, et ce, depuis près de 35 ans. Dans cet exposé, je présenterai une attaque d'un genre nouveau, dite "par filtration" qui permet de retrouver la structure d'un code de Goppa "sauvage" (Wild Goppa code) construit à partir d'une extension de corps quadratique. Cette attaque consiste à utiliser des propriétés multiplicatives du code pour en calculer une filtration (i.e. une famille de sous-codes emboités) dont chaque élément est un code de Goppa classique.
  • Le 9 décembre 2014 à 10:00
    • Séminaire de Théorie Algorithmique des Nombres
    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 les codes correcteurs d'erreurs dont la sécurité repose sur la difficulté à décoder un code aléatoire. Parmi les différentes familles de codes algébriques proposées pour ce schéma, les codes de Goppa classiques sont les seuls à résister à toutes les attaques algébriques, et ce, depuis près de 35 ans. Dans cet exposé, je présenterai une attaque d'un genre nouveau, dite "par filtration" qui permet de retrouver la structure d'un code de Goppa "sauvage" (Wild Goppa code) construit à partir d'une extension de corps quadratique. Cette attaque consiste à utiliser des propriétés multiplicatives du code pour en calculer une filtration (i.e. une famille de sous-codes emboités) dont chaque élément est un code de Goppa classique.
  • Le 27 janvier 2015 à 10:00
    • Séminaire de Théorie Algorithmique des Nombres
    Salle 385
    Andreas Enge imb
    Class polynomials for abelian surfaces
    The complex multiplication method is well-known for elliptic curves, where it may be used to construct curves used in primality proofs or to implement crytosystems, in particular pairing-based ones. A similar approach is possible for abelian surfaces, that are Jacobians of genus 2 curves, with considerable number theoretic complications. I describe an algorithm using complex floating point approximations with an asymptotically optimal running time, that is, quasi-linear in the size of the class polynomials produced as output. Our implementation has been used to carry out parallelised record computations and I present experimental data.
  • Le 27 janvier 2015 à 10:00
    • Séminaire de Théorie Algorithmique des Nombres
    Salle 385
    Andreas Enge imb
    Class polynomials for abelian surfaces
    The complex multiplication method is well-known for elliptic curves, where it may be used to construct curves used in primality proofs or to implement crytosystems, in particular pairing-based ones. A similar approach is possible for abelian surfaces, that are Jacobians of genus 2 curves, with considerable number theoretic complications. I describe an algorithm using complex floating point approximations with an asymptotically optimal running time, that is, quasi-linear in the size of the class polynomials produced as output. Our implementation has been used to carry out parallelised record computations and I present experimental data.
  • Le 3 février 2015 à 10:30
    • Séminaire de Théorie Algorithmique des Nombres
    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-key cryptography. If \(\G\) is an abelian group (written additively), then the Diffie--Hellman protocol in \(\G\) is composed of four computations in the form \[ P \longmapsto [m]P = \underbrace{P + \cdots + P}_{m \text{ times}} \] for various points \(P\) and integers \(m\); optimising this *scalar multiplication* operation is therefore crucial.
  • Le 10 février 2015 à 10:00
    • Séminaire de Théorie Algorithmique des Nombres
    Salle 385
    Eduardo Friedman Universidad de Chile
    Co-volume of high-rank subgroups of the units of a number field

  • Le 3 mars 2015 à 10:00
    • Séminaire de Théorie Algorithmique des Nombres
    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 over finite fields. Since the length of such a code is determined by the number of rational points on the curve, it is desirable to use curves with as many rational points as possible. We investigate a certain class of Artin-Schreier curves with an unusually large number of automorphisms. Their automorphism group contains a large extraspecial subgroup. Precise knowledge of this subgroup makes it possible to compute the zeta functions of these curves. As a consequence, we obtain new examples of curves that attain the provably maximal (or minimal) number of points over an appropriate field of definition.
  • Le 10 mars 2015 à 10:00
    • Séminaire de Théorie Algorithmique des Nombres
    Salle 385
    Guilhem Castagnos imb
    Linearly Homomorphic Encryption from DDH
    In this talk, we will design a linearly homomorphic encryption scheme whose security relies on the hardness of the decisional Diffie-Hellman (DDH) problem. Our approach requires some special features of the underlying group. In particular, its order is unknown and it contains a subgroup in which the discrete logarithm problem is tractable. Therefore, our instantiation holds in the class group of a non maximal order of an imaginary quadratic field. Its algebraic structure makes it possible to obtain such a linearly homomorphic scheme whose message space is the whole set of integers modulo a prime p and which supports an unbounded number of additions modulo p from the ciphertexts. A notable difference with previous works is that, for the first time, the security does not depend on the hardness of the factorization of integers. As a consequence, under some conditions, the prime p can be scaled to fit the application needs.
  • Le 31 mars 2015 à 10:00
    • Séminaire de Théorie Algorithmique des Nombres
    Salle 385
    Karim Belabas imb
    Modular symbols and p-adic L functions I

  • Le 7 avril 2015 à 10:00
    • Séminaire de Théorie Algorithmique des Nombres
    Salle 385
    Karim Belabas imb
    Modular symbols and p-adic L functions II

  • Le 14 avril 2015 à 10:00
    • Séminaire de Théorie Algorithmique des Nombres
    Salle 385
    Karim Belabas imb
    Modular symbols and p-adic L functions III

  • Le 5 mai 2015 à 10:00
    • Séminaire de Théorie Algorithmique des Nombres
    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
    • Séminaire de Théorie Algorithmique des Nombres
    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
    • Séminaire de Théorie Algorithmique des Nombres
    Salle 385
    Iuliana Ciocanea-Teodorescu Leiden+IMB
    Algorithms for finite rings
    We will discuss deterministic polynomial time algorithms designed to answer a series of fundamental questions about finite rings and finite modules. These include the module isomorphism problem, computing the minimum number of generators of a module and finding a "good" approximation for the Jacobson radical of a finite ring.
  • Le 2 juin 2015 à 10:00
    • Séminaire de Théorie Algorithmique des Nombres
    Salle 385
    Andreas Enge imb
    Optimised addition sequences for eta and theta functions
    The main ingredient of complex multiplication algorithms for elliptic curves that compute class and modular polynomials via floating point approximations is the evaluation of Dedekind's η- and of more general ϑ-functions. While algorithms are known that are asymptotically quasi-linear in the desired precision, in practice it is usually faster to evaluate lacunary power series. It has been observed experimentally that particularly short addition sequences exist for the specially structured exponents of η and ϑ. A leisurely stroll through classic number theory will provide us with proofs of this fact.
  • Le 23 juin 2015 à 10:00
    • Séminaire de Théorie Algorithmique des Nombres
    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 deux invariants qu'on appelle invariants de Gundlach qui engendrent le corps des fonctions modulaires symétriques de Hilbert. Si $\beta$ est un élément totalement positif de $O_K$ de norme $p$, les $\beta$-polynômes modulaires paramétrisent les classes d'isomorphisme de variétés abéliennes principalement polarisées ayant multiplication réelle par $O_K$ et munis d'une $\beta$-isogénie ou d'une $\beta^c$-isogénie. Nous décrivons un algorithme efficace pour calculer ces polynômes en transposant certains calculs sur l'espace de Siegel. Nous étendrons ces méthodes à des invariants dérivés des fonctions thêta.
  • Le 8 septembre 2015 à 10:00
    • Séminaire de Théorie Algorithmique des Nombres
    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 on integer factorization and discrete logarithm computation in finite fields. First, I will present the ECM algorithm for integer factorization and a new method to analyze the elliptic curves used in this algorithm by studying the Galois properties of division polynomials. Then, I will talk about the NFS algorithm for integer factorization and in particular the polynomial selection step for which I will propose improvements of existing algorithms. Finally, I will talk about a common step of the NFS algorithm for integer factorization and the NFS-DL and FFS algorithms for discrete logarithm computations: the filtering step. I will explain this step thoroughly and present an improvement for which I will study the impact using data from several computations of discrete logarithms and factorizations.
  • Le 22 septembre 2015 à 11:00
    • Séminaire de Théorie Algorithmique des Nombres
    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 based protocols and describe some countermeasures. I will particularly show that the point blinding countermeasure does not provide a complete protection to Miller's algorithm which is the main tool for pairings.
  • Le 6 octobre 2015 à 11:00
    • Séminaire de Théorie Algorithmique des Nombres
    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 integre sur $K$ et $\ell$ un nombre premier impair different de la carcteristique de $K$. Notons $W$ l'ensemble des classes d'equivalence lineaire de diviseurs effectifs de degre 1 sur $C$. Nous nous interessons aux sections globales d'un faisceau de $O_C$-modules sur la jacobienne $J_C$ de C. Plus precisement nous allons construitre une base 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
    • Séminaire de Théorie Algorithmique des Nombres
    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 last year on computing various transcendental functions in interval arithmetic. The first notable result is a large (order of magnitude) speed improvement for elementary functions. The second project concerns generalized hypergeometric functions (including the incomplete gamma function, Bessel functions, and others). This is still a work in progress, and some significant problems remain, particularly the task of computing useful enclosures when the inputs are large, inexact complex numbers. Finally, I have a fairly complete implementation of the classical Jacobi theta functions, elliptic functions and modular forms. I will describe an optimization for theta series, following up the results presented earlier by Andreas Enge (2015-06-02), and discuss the application of computing class polynomials.
  • Le 24 novembre 2015 à 11:00
    • Séminaire de Théorie Algorithmique des Nombres
    Salle 385
    Julien Keuffer Morpho
    The SEA algorithm in PARI/GP
    The Schoof-Elkies-Atkin (SEA) algorithm is currently the most efficient algorithm for counting the number of points of an elliptic curve defined over a finite field of large characteristic. The main idea of this algorithm is to use the relation between the order of the curve and the trace of the Frobenius endomorphism and then to compute this trace modulo small primes. Using the CRT and the Hasse-Weil bound leads to find the exact value of the trace. The implementation of SEA in PARI/GP is based on Reynald Lercier's thesis, published in 1997. Many improvements have been proposed since. In this talk, I will present two algorithms (respectively published by Gaudry and Morain and by Mihailescu, Morain and Schost) to compute the trace in the so-called Elkies case, their implementations in PARI and comparisons I made during my master's internship in the French Network and Information Security Agency.
  • Le 3 décembre 2015 à 10:00
    • Séminaire de Théorie Algorithmique des Nombres
    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 abelian variety and introduce an approach to characterize it through the character theory of compact Lie groups. We illustrate the method with examples of generic curves of low genus, with Sato-Tate group $\mathrm{USp}(2g)$; special curves which yield proper subgroups, and a family of Katz giving rise to Galois representations in $\mathrm{SO}(2g+1)$.
  • Le 15 décembre 2015 à 11:00
    • Séminaire de Théorie Algorithmique des Nombres
    Salle 385
    Bill Allombert imb
    Les aspect combinatoires des fonctions L d'Artin.

  • Le 26 janvier 2016 à 11:00
    • Séminaire de Théorie Algorithmique des Nombres
    Salle 1
    Bernadette Perrin-Riou Université Paris-Sud
    Présentation de WIMS (WWW Interactive Multipurpose Server)

  • Le 9 février 2016 à 11:00
    • Séminaire de Théorie Algorithmique des Nombres
    Salle 385
    Павел Соломатин imb
    L-functions of Genus Two Abelian Coverings of Elliptic Curves over Finite Fields
    Initially motivated by the relations between Anabelian Geometry and Artin's L-functions of the associated Galois-representations, here we study the list of zeta-functions of genus two abelian coverings of elliptic curves over finite fields. Our goal is to provide a complete description of such a list.
  • Le 1er mars 2016 à 11:00
    • Séminaire de Théorie Algorithmique des Nombres
    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 for factoring large integers that are free of small prime factors. The goal of the polynomial selection, the first stage of this algorithm, is to compute a pair of integer polynomials. Montgomery proposed a method for generating two nonlinear polynomials which relies on the construction of small modular geometric progressions. In this talk, I will present theoretical and practical improvements to Montgomery's method that allow us to generate pairs of a quadratic and a cubic polynomials and pairs of two cubic polynomials for larger integer that was previously possible. Joint work with Nicholas Coxon.
  • Le 8 mars 2016 à 11:00
    • Séminaire de Théorie Algorithmique des Nombres
    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 peut définir un régulateur associé au groupe de Mordell-Weil des points rationnels $A(K)$, lequel joue un rôle important dans la forme forte de la conjecture de Birch et Swinnerton-Dyer. Si l'on suppose vraie la conjecture de Lang et Silverman, on montre alors que ce régulateur vérifie la propriété de finitude suivante : il n'y a qu'un nombre fini de variétés abéliennes simples de dimension fixée $g$, définie sur $K$, de rang non nul et de régulateur borné. On montre de plus (dans le courant de la preuve) une inégalité inconditionnelle entre la hauteur de Faltings de $A$, les premiers de mauvaise réduction de $A$ et le rang de Mordell-Weil de $A$. L'exposé commencera par une introduction présentant un résultat similaire et inconditionnel pour les régulateurs de familles de corps de nombres.
  • Le 15 mars 2016 à 11:00
    • Séminaire de Théorie Algorithmique des Nombres
    Salle 385
    Bill Allombert imb
    Survey on computing isogeny between elliptic curves.
    We present methods to compute isogenies between elliptic curves, and we apply them to the computation of the isogenies matrix of an elliptic curve defined over the rational and to the Schoof Elkies Atkin algorithm for counting point on elliptic curves defined over a finite field.
  • Le 22 mars 2016 à 11:00
    • Séminaire de Théorie Algorithmique des Nombres
    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 des rapports de puissances de theta constantes avec les coordonnées affines des points de ramification d'une courbe hyperelliptique. A partir des années 80, plusieurs auteurs, ayant des préoccupations centrés sur la physique, ont montré des généralisations de ces formules au cas des courbes superelliptiques. Plus récemment, Shau Zemel et Hershel Farkas ont écrit un livre en utilisant des arguments essentiellement algé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 extensions résolubles de $k(x)$ et quelles obstructions peuvent survenir.
  • Le 5 avril 2016 à 11:00
    • Séminaire de Théorie Algorithmique des Nombres
    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.
  • Le 10 mai 2016 à 11:00
    • Séminaire de Théorie Algorithmique des Nombres
    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, en l'isolant dans la torsion de la jacobienne d'une courbe modulaire. Ceci permet notamment de calculer les coefficients a(p) de la forme en temps polynomial en log p, ce qui en fait la méthode la plus efficace connue à ce jour.
  • Le 17 mai 2016 à 11:00
    • Séminaire de Théorie Algorithmique des Nombres
    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 galoisiennes présentés dans l'exposé précédent peuvent être certifiés, en s'appuyant sur la conjecture de modularité de Serre et des calculs explicites de cohomologie des groupes.
  • Le 7 juin 2016 à 10:00
    • Séminaire de Théorie Algorithmique des Nombres
    Salle 385
    Jared Asuncion IMB
    Tower decomposition of Hilbert class fields
    The genus g function Theta : $\mathbb{C}^g x \mathfrak{H}_g -> \mathbb{C}$ has numerous applications in mathematics, from number theory to non-linear differential equations; in particular, its connection with the Abel-Jacobi map on complex elliptic and hyperelliptic curves has important applications. A connection between some values of this function (the theta-constants) and the arithmetico-geometric mean of Gauss (and its generalization in genus $g$, the Borchardt mean) yields an algorithm to compute any $P$ digits of the theta-constants in roughly $\mathrm{log} P$ multiplication of $P$-bit numbers, which is quasi-optimal. We provide a generalization of this connection using general tau-duplication formulas; with some care, this allows us to devise an algorithm to compute $P$ digits of Theta in the same quasi-linear time in $P$. We also report on an implementation in genus 1 and 2, which beats the naive algorithm for precisions as low as a few thousand digits. This is joint work with Emmanuel Thomé.
  • Le 11 octobre 2016 à 14:00
    • Séminaire de Théorie Algorithmique des Nombres
    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 des Jacobiennes de courbes de genre $g$ et sur des quotients de telles Jacobiennes par des sous-groupes isotropes maximaux de la $\ell$-torsion, pour $\ell>2$ premier. Pour le cas spécifique du genre 2, il est bien connu qu'à partir d'une courbe hyperelliptique $C$ et d'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 de degré en $O(\ell)$. L'article donne une méthode pour calculer $C'$ et ces fractions. Pour notre exposé, nous nous proposons d'exposer le contenu de ce papier et de parler de l'implantation que nous avons faite en genre 2.
  • Le 18 octobre 2016 à 10:00
    • Séminaire de Théorie Algorithmique des Nombres
    Salle 385
    Gregor Seiler ETH Zurich
    Computing ray class fields of imaginary quadratic fields

  • Le 8 novembre 2016 à 10:00
    • Séminaire de Théorie Algorithmique des Nombres
    Salle 385
    Aurélien Focqué
    Algorithmes BMSS et Lercier Sirvent pour SEA dans PARI

  • Le 22 novembre 2016 à 10:00
    • Séminaire de Théorie Algorithmique des Nombres
    Salle 385
    Razvan Barbulescu
    A brief history of pairings
    Pairings are a relatively new cryptographic tool which have been the object of many arithmetic works. In the last few years some of the pairings have become obsolete because of the progress on the underlying problem of discrete logarithm in finite fields. We propose ourselves to make a list of pairings constructions, to explain their advantages but also their weaknesses. The sporadic curves are vulnerable to the Logjam attack and have never been a popular choice. The small characteristic curves allow a very good arithmetic but are the target of a quasi-polynomial algorithm. The pairings where the characteristic has a low Hamming weight, which eliminate the cost of modular reductions, have been the object of special attacks. When the embedding degree is composite the one can use the tower field arithmetic but there are also tower field attacks.
  • Le 17 janvier 2017 à 10:00
    • Séminaire de Théorie Algorithmique des Nombres
    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
    • Séminaire de Théorie Algorithmique des Nombres
    Salle 385
    Cécile Pierrot Centrum Wiskunde & Informatica\, Amsterdam
    Nearly sparse linear algebra
    Linear algebra is a widely used tool both in mathematics and computer science, and cryptography is no exception to this rule. Yet, it introduces some particularities, such as dealing with linear systems that are often sparse, or, in other words, linear systems inside which a lot of coefficients are equal to zero. We propose to enlarge this notion to nearly sparse matrices, characterized by the concatenation of a sparse matrix and some dense columns, and to design an algorithm to solve this kind of problems. Motivated by discrete logarithms computations on medium and high characteristic finite fields, the Nearly Sparse Linear Algebra bridges the gap between classical dense linear algebra problems and sparse linear algebra ones, for which specific methods have already been established. Our algorithm particularly applies on one of the three phases of NFS (Number Field Sieve) which precisely consists in finding a non trivial element of the kernel of a nearly sparse matrix.
  • Le 23 mai 2017 à 10:00
    • Séminaire de Théorie Algorithmique des Nombres
    Salle 385
    Christophe Petit Oxford
    Post-quantum cryptography from supersingular isogeny problems?
    We review existing cryptographic schemes based on the hardness of computing isogenies between supersingular isogenies, and present some attacks against them. In particular, we present new techniques to accelerate the resolution of isogeny problems when the action of the isogeny on a large torsion subgroup is known, and we discuss the impact of these techniques on the supersingular key exchange protocol of Jao-de Feo.
  • Le 30 mai 2017 à 10:00
    • Séminaire de Théorie Algorithmique des Nombres
    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 for higher-dimensional abelian varieties. We study the case of absolutely simple ordinary abelian varieties over a finite field. We analyse graphs of so-called $\mathfrak l$-isogenies, resolving that, in arbitrary dimension, their structure is similar, but not identical, to the ``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 class of isogenies known as $(\ell, \ell)$-isogenies. These results lead to new, provable algorithms to navigate in isogeny graphs, with consequences for the CM-method in genus 2, for computing explicit isogenies, and for the random self-reducibility of the discrete logarithm problem in genus 2 cryptography.
  • Le 6 juin 2017 à 10:00
    • Séminaire de Théorie Algorithmique des Nombres
    Salle 385
    Guilhem Castagnos imb
    Encryption Switching Protocols Revisited: Switching modulo p
    Last year, Couteau, Peters and Pointcheval introduced a new primitive called encryption switching protocols, allowing to switch ciphertexts between two encryption schemes. If such an ESP is built with two schemes that are respectively additively and multiplicatively homomorphic, it naturally gives rise to a secure 2-party computation protocol. It is thus perfectly suited for evaluating functions, such as multivariate polynomials, given as arithmetic circuits. Couteau et al. built an ESP to switch between Elgamal and Paillier encryptions which do n ot naturally fit well together. Consequently, they had to design a clever variant of Elgamal over Z/nZ with a costly shared decryption. In this talk, we first present a conceptually simple generic construction for encryption switching protocols. We then give an efficient instantiation of our generic approach that uses two well-suited protocols, namely a variant of Elgamal in Z/pZ and the Castagnos-Laguillaumie encryption defined over class groups of quadrat ic fields which is additively homomorphic over Z/pZ. Among other advantages, this allows to perform all computations modulo a prime p instead of an RSA modulus. Overall, our solution leads to significant reductions in the number of rounds as well as the number of bits exchanged by the parties during the interactive protocols. We also show how to extend its security to the malici ous setting.
  • Le 13 juin 2017 à 10:00
    • Séminaire de Théorie Algorithmique des Nombres
    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 with respect to the standard inner product. It is conjectured that there is no circulant Hadamard matrix of order larger than $4$.
  • Le 17 octobre 2017 à 10:00
    • Séminaire de Théorie Algorithmique des Nombres
    Salle 385
    Fredrik Johansson imb
    Numerics of classical elliptic functions, elliptic integrals and modular forms
    We review methods for validated arbitrary-precision numerical computation of elliptic functions and their inverses (the complete and incomplete elliptic integrals), as well as the closely related Jacobi theta functions and $\mathrm{SL}_2(\mathbb{Z})$ modular forms. A general strategy consists of two stages: first, using functional equations to reduce the function arguments to a smaller domain; second, evaluation of a suitable truncated series expansion. For elliptic functions and modular forms, one exploits periodicity and modular transformations for argument reduction, after which the rapidly convergent series expansions of Jacobi theta functions can be employed. For elliptic integrals, a comprehensive strategy pioneered by B. Carlson consists of using symmetric forms to unify and simplify both the argument reduction formulas and the series expansions (which involve multivariate hypergeometric functions). Among other aspects, we discuss error bounds as well as strategies for argument reduction and series evaluation that reduce the computational complexity. The functions have been implemented in arbitrary-precision complex interval arithmetic as part of the Arb library.
  • Le 24 octobre 2017 à 10:00
    • Séminaire de Théorie Algorithmique des Nombres
    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 scheme of n points on a two-dimensional torus and showed it satisfies several number-theoretical properties via modular forms. Classifying the singularities of this rational function into zeros and poles, we define a word which contains a lot of number-theoretical information about n (the above-mentioned number of points). This nontrivial connection between natural numbers and words can be used to define many classical subsets of natural numbers in terms of rational and context-free languages (e.g. the set of semi-perimeters of Pythagorean triangles, the set of numbers such that any partition into consecutive parts has an odd number of parts). Also, some arithmetical functions can be described in way (e.g. the Erdös-Nicolas function, the number of middle divisors). Finally, this approach provides a new technique to prove number-theoretical results just using relationships among context-free languages.
  • Le 14 novembre 2017 à 10:00
    • Séminaire de Théorie Algorithmique des Nombres
    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 la multiplication complexe: un ordre dans un corps quadratique imaginaire agit sur un ensemble de courbes elliptiques ordinaires isogènes définies sur un corps fini. Pour instancier le protocole, on est amené à calculer des isogénies de différents degrés entre ces courbes à l'aide des algorithmes développés pour le comptage de points. Ce cryptosystème peut être accéléré par un bon choix de courbe elliptique initiale, notamment par la présence de points de torsion rationnels, et l'on présente une méthode de recherche de telles courbes.
  • Le 20 novembre 2017 à 14:00
    • Séminaire de Théorie Algorithmique des Nombres
    Salle 385
    Christian Klein
    Computational approach to compact Riemann surfaces
    A purely numerical approach to compact Riemann surfaces starting from plane algebraic curves is presented. The critical points of the algebraic curve are computed via a two-dimensional Newton iteration. The starting values for this iteration are obtained from the resultants with respect to both coordinates of the algebraic curve and a suitable pairing of their zeros. A set of generators of the fundamental group for the complement of these critical points in the complex plane is constructed from circles around these points and connecting lines obtained from a minimal spanning tree. The monodromies are computed by solving the de ning equation of the algebraic curve on collocation points along these contours and by analytically continuing the roots. The collocation points are chosen to correspond to Chebychev collocation points for an ensuing Clenshaw–Curtis integration of the holomorphic differentials which gives the periods of the Riemann surface with spectral accuracy. At the singularities of the algebraic curve, Puiseux expansions computed by contour integration on the circles around the singularities are used to identify the holomorphic differentials. The Abel map is also computed with the Clenshaw–Curtis algorithm and contour integrals. As an application of the code, solutions to the Kadomtsev–Petviashvili equation are computed on non-hyperelliptic Riemann surfaces.
  • Le 28 novembre 2017 à 10:00
    • Séminaire de Théorie Algorithmique des Nombres
    Salle 385
    Frank Vallentin
    Coloring the Voronoi tessellation of lattices
    We define the chromatic number of a lattice: It is the least number of colors one needs to color the interiors of the cells of the Voronoi tesselation of a lattice so that no two cells sharing a facet are of the same color. We compute the chromatic number of the irreducible root lattices and for this we apply a generalization of the Hoffman bound.
  • Le 9 janvier 2018 à 10:00
    • Séminaire de Théorie Algorithmique des Nombres
    Salle 385
    Fredrik Johansson imb
    Numerical integration in complex interval arithmetic
    We present a new implementation of validated arbitrary-precision numerical evaluation of definite integrals $\int_a^b f(x) dx$, available in the Arb library. The code uses a version of the Petras algorithm, which combines adaptive subdivision with Gauss-Legendre (GL) quadrature, evaluating the integrand on complex intervals surrounding the path of integration to obtain rigorous error bounds. The first part of the talk discusses the general algorithm and its performance for interesting families of integrals. The second part, which is based on joint work with Marc Mezzarobba, discusses the fast computation of GL quadrature nodes with rigorous error bounds. It is well known that GL quadrature achieves a nearly optimal rate of convergence for analytic integrands with singularities well isolated from the path of integration, but due to the cost of generating GL quadrature nodes, the more slowly converging Clenshaw-Curtis and double exponential quadrature rules have often been favored when an accuracy of several hundreds or thousands of digits is required. We consider the asymptotic and practical aspects of this problem. An order-of-magnitude speedup is obtained over previous code for computing GL nodes with simultaneous high degree and precision, which makes GL quadrature viable even at very high precision.
  • Le 22 janvier 2018 à 10:00
    • Séminaire de Théorie Algorithmique des Nombres
    Salle 2
    Philippe Moustrou IMB
    On the Density of Sets Avoiding Parallelohedron Distance 1
    Let $\Vert \cdot \Vert$ be a norm on $\mathbb{R}^n$. We consider the so-called unit distance graph $G$ associated with $\Vert \cdot \Vert$: the vertices of $G$ are the points of $\mathbb{R}^n$, and the edges connect the pairs $\{x,y\}$ satisfying $\Vert x-y\Vert=1$. We define $m_1\left(\mathbb{R}^n,\Vert \cdot \Vert\right)$ as the supremum of the densities achieved by independent sets of $G$. The number $m_1$ was introduced by Larman and Rogers (1972) as a tool to study the measurable chromatic number $\chi_m(\mathbb{R}^n)$ of $\mathbb{R}^n$ for the Euclidean norm.
  • Le 30 janvier 2018 à 10:00
    • Séminaire de Théorie Algorithmique des Nombres
    Salle 385
    Jared Asuncion IMB
    ECPP in PARI/GP
    The elliptic curve primality proving (ECPP) algorithm not only proves (or disproves) the primality of an integer $N$ but also provides, if $N$ is prime, a primality certificate which one can verify quickly. In this talk, we recall the steps of ECPP and discuss its implementation in PARI/GP.
  • Le 6 mars 2018 à 10:00
    • Séminaire de Théorie Algorithmique des Nombres
    Salle 385
    Takashi Fukuda Nihon University
    Class number calculation for special number fields
    I will talk about TC (an interpreter of multiprecision C language which I developed), Weber's problem, Coates' conjecture and an algorithm of calculating p-class group of abelian number fields. I also present my project trying to implement an algorithm mentioned above to PARI/GP during my stay at IMB.
  • Le 20 mars 2018 à 10:00
    • Séminaire de Théorie Algorithmique des Nombres
    Salle 385
    Tristan Vaccon Université de Limoges
    Sur les équations différentielles $p$-adiques à variables séparables
    Les trois dernières décennies ont vu le développement de méthodes et algorithmes $p$-adiques, notamment :
  • Le 3 avril 2018 à 10:00
    • Séminaire de Théorie Algorithmique des Nombres
    Salle 385
    Alex Bartel Glasgow University
    Cohen-Martinet heuristics revisited
    In the early 1990s Henri Cohen and Jacques Martinet offered a probabilistic model that explains the behaviour of ideal class groups of number fields in natural families, generalising earlier work by Cohen and Lenstra. There is a lot of numerical evidence for the correctness of the model, but very few theorems. In joint work with Hendrik Lenstra we revisit the Cohen-Martinet heuristics and, among other things, disprove them in two different ways, but also lend additional support for the expectation that they are "basically true". In this talk I will explain one of these disproofs, and will propose possible corrections.
  • Le 24 avril 2018 à 10:00
    • Séminaire de Théorie Algorithmique des Nombres
    Salle 385
    Damien Robert imb
    Huang's proposal for trilinear maps
    In a recent [paper](https://arxiv.org/abs/1803.10325), Huang proposed a trilinear map involving abelian varieties over finite fields. In this talk we present his approach.
  • Le 22 mai 2018 à 10:00
    • Séminaire de Théorie Algorithmique des Nombres
    Salle 385
    Jean Kieffer ENS Paris
    Étude et implémentation de l'algorithme de Schoof–Elkies–Atkin

  • Le 12 juin 2018 à 10:00
    • Séminaire de Théorie Algorithmique des Nombres
    Salle 385
    Xavier Caruso Université de Rennes
    Variations autour d'un théorème de Christol
    Un célèbre théorème de Christol affirme qu'une série à coefficients dans $\mathbb{Z}/p\mathbb{Z}$ est algébrique sur $\mathbb{Z}/p\mathbb{Z}(x)$ si et seulement si la suite de ses coefficients est $p$-automatique.
  • Le 5 juillet 2018 à 10:00
    • Séminaire de Théorie Algorithmique des Nombres
    Salle 385
    Jean-François Biasse University of South Florida
    Fast multiquadratic S-unit computation and application to the calculation of class groups
    Let $L=Q(√d_1, ... ,√d_n)$ be a real multiquadratic field and S be a set of prime ideals of L that does not contain any divisors of 2. In this paper, we present a heuristic algorithm for the computation of the S-class group and the S-unit group that runs in time $Poly(log(∆),Size(S)) e^{Õ(√ln d)}$ where $d=max_{i≤n} d_i$ and ∆ is the discriminant of L. We use this method to compute the ideal class group of the maximal order $O_L$ of L in time $Poly(log(∆)) e^{Õ(√log d)}$. When $log(d)≤log(log(∆))^c$ for some constant $c < 2$, these methods run in polynomial time. We implemented our algorithm using Sage 7.5.1.
  • Le 18 septembre 2018 à 10:30
    • Séminaire de Théorie Algorithmique des Nombres
    Salle 385
    Aurel Page et Pascal Molin
    Mini groupe de travail: calcul des caractères de Hecke

  • Le 6 novembre 2018 à 10:00
    • Séminaire de Théorie Algorithmique des Nombres
    Salle 385
    Elie Eid Université de Rennes
    Calcul d'isogénies en genre 2
    Étant donné une courbe algébrique $C$ de genre $2$ définie sur un corps fini $K$ de caractéristique impaire et un sous-groupe isotrope maximal $\mathcal{V}$ (pour le couplage de commutateur) de l'ensemble des points de $l$-torsion où $l$ est un entier (premier) impair, nous savons que le quotient de la jacobienne $J_K(C)$ de $C$ par $\mathcal{V}$ est une variété abélienne de dimension 2 et donc la jacobienne d'une courbe $D$ de genre $2$.
  • Le 27 novembre 2018 à 10:00
    • Séminaire de Théorie Algorithmique des Nombres
    Salle 385
    Ida Tucker
    Practical fully secure unrestricted inner product functional encryption modulo a prime p. (Chiffrement fonctionel sans restrictions pour le calcul de produits scalaires modulo un nombre premier.)
    Functional encryption (FE) is an advanced cryptographic primitive which allows, for a single encrypted message, to finely control how much information on the encrypted data each receiver can recover. To this end many functional secret keys are derived from a master secret key. Each functional secret key allows, for a ciphertext encrypted under the associated public key, to recover a specific function of the underlying plaintext.
  • Le 4 décembre 2018 à 11:00
    • Séminaire de Théorie Algorithmique des Nombres
    Salle 385
    Aurel Page
    Torsion analytique et torsion de Reidemeister en théorie des nombres
    Je ferai un exposé de style groupe de travail sur le rôle de la torsion dans l'homologie des groupes arithmétiques en théorie des nombres ; je présenterai une méthode permettant d'obtenir de l'information dessus : la formule de Cheeger--Mueller, et ses utilisations notamment par Bergeron--Venkatesh et Calegari--Venkatesh. Je parlerai aussi d'un travail que je viens de commencer avec Michael Lipnowski et Jean Raimbault, dont les aspects algorithmiques ont des points communs avec les méthodes de calcul de valeurs de fonctions L.
  • Le 11 décembre 2018 à 10:00
    • Séminaire de Théorie Algorithmique des Nombres
    Salle 385
    Aurel Page
    Torsion analytique et torsion de Reidemeister en théorie des nombres 2

  • Le 18 décembre 2018 à 10:00
    • Séminaire de Théorie Algorithmique des Nombres
    Salle 385
    Bill Allombert imb
    Sur le calcul de automorphismes d'un extension Galoisienne niltpotente de corps de nombres.
    Je présente un nouvel algorithme en temps polynomial sous GRH pour le calcul des automorphismes d'une extension Galoisienne de corps de nombres sous la condition que le groupe de Galois soit nilpoltent. Cet algorithme est basé sur la présentation des groupes nilpoltents et le relèvement des automorphismes de Frobenius et évite la couteuse reconnaissance de nombres algébriques par réduction de réseau tout en évitant le cout exponentiel des méthodes combinatoires utilisées dans ma thèse.
  • Le 19 février 2019 à 10:00
    • Séminaire de Théorie Algorithmique des Nombres
    Salle 385
    David Lubicz
    Improving the AGM point counting algorithm

  • Le 9 avril 2019 à 11:30
    • Séminaire de Théorie Algorithmique des Nombres
    Salle 385
    Xavier Caruso imb
    Vers les codes de Gabidulin géométriques
    Dans cet exposé, je commencerai par rappeler la définition et les principales propriétés de codes de Reed-Solomon. Je présenterai ensuite deux extensions classiques de ces codes, à savoir, d'une part, les codes géométriques et, d'autre part, les codes de Gabidulin. Ces deux extensions appaissent toutefois comme orthogonales : du point de vue pratique, elles gomment des limitations différentes de codes de Reed-Solomon tandis que, du point de vue technique, elles son basées sur des constructions mathématiques également très différentes. Dans une deuxième partie de l'exposé, je présenterai quelques idées et quelques résultats en vue d'une généralisation commune des codes géométriques et des codes de Reed-Solomon.
  • Le 28 mai 2019 à 10:00
    • Séminaire de Théorie Algorithmique des Nombres
    Salle 385
    Francesco Battistoni University of Milan
    A conjectural improvement for inequalities involving the regulator of number fields
    Given the family of number fields with fixed signature, there exists only a finite number of such fields having regulator less than a prescribed bound: this is due to a classical inequality by Remak, generalized years later by Friedman, which bounds the discriminant of a number field by means of some terms which depend also on the regulator.
  • Le 4 juin 2019 à 10:00
    • Séminaire de Théorie Algorithmique des Nombres
    Salle 385
    Corentin Darreye imb
    Équirépartition de sommes de coefficients de formes modulaires en progression arithmétique.
    Après avoir rappelé des résultats classiques d'équirépartition de sommes d'exponentielles, j'expliquerai en quoi ce genre de propriétés permet de mieux comprendre les sommes de coefficients de Fourier de formes modulaires en progression arithmétique. Je donnerai un aperçu de ce qui a été démontré auparavant dans cette thématique pour mieux introduire certaines questions restant ouvertes auxquelles je m'intéresse, notamment le cas des formes modulaires de poids demi-entier.
  • Le 10 septembre 2019 à 09:30
    • Séminaire de Théorie Algorithmique des Nombres
    Salle 2
    David Roe MIT
    The inverse Galois problem for p-adic fields
    We describe a method for counting the number of extensions of $\mathbb{Q}_p$ with a given Galois group $G$, founded upon the description of the absolute Galois group of $\mathbb{Q}_p$ due to Jannsen and Wingberg. Because this description is only known for odd $p$, our results do not apply to $\mathbb{Q}_2$. We report on the results of counting such extensions for $G$ of order up to $2000$ (except those divisible by 512), for $p = 3$, 5, 7, 11, 13. In particular, we highlight a relatively short list of minimal $G$ that do not arise as Galois groups. Motivated by this list, we prove two theorems about the inverse Galois problem for $\mathbb{Q}_p$: one giving a necessary condition for G to be realizable over $\mathbb{Q}_p$ and the other giving a sufficient condition.
  • Le 17 septembre 2019 à 10:00
    • Séminaire de Théorie Algorithmique des Nombres
    Salle 2
    Fredrik Johansson imb
    Fungrim : The Mathematical Functions Grimoire
    [Fungrim](http://fungrim.org) is a new, open source database of formulas and tables for mathematical functions. All formulas are represented in symbolic, computer-readable form and include explicit conditions for the variables.
  • Le 24 septembre 2019 à 10:00
    • Séminaire de Théorie Algorithmique des Nombres
    Salle 2
    Jean Kieffer imb
    Computing isogenies from modular equations in genus 2
    Given two elliptic curves such an isogeny of degree l exists between them, there is an algorithm, due to Elkies, that uses modular equations to compute this isogeny explicitly. It is an essential tool in the SEA point counting algorithm: using isogenies is superior to Schoof's original idea of using endomorphisms. In this work, we present the analogue of Elkies' algorithm for Jacobians of genus 2 curves, thus opening the way to using isogenies in higher genus point counting.
  • Le 1er octobre 2019 à 10:00
    • Séminaire de Théorie Algorithmique des Nombres
    Salle 2
    Damien Robert imb
    An overview of isogeny algorithms
    Let $A$ be an abelian variety and $K$ a finite subgroup. We will discuss several approaches to compute the isogeny $A \mapsto A/K$, starting from Vélu's algorithm for elliptic curves, and then the isogeny theorem for theta functions, Couveignes and Ezome's work on Jacobians of curves, and recent progress with David Lubicz.
  • Le 8 octobre 2019 à 10:00
    • Séminaire de Théorie Algorithmique des Nombres
    Salle 2
    Jared Asuncion imb
    Computing Hilbert class fields of quartic CM fields using Complex Multiplication
    The Hilbert class field $H_K(1)$ is the maximal unramified abelian extension of $K$. For imaginary quadratic number fields $K$, it can be generated using special values of certain analytic, modular functions. For quartic CM-fields $K$, the corresponding construction yields only a subfield of $H_K(1)$.
  • Le 15 octobre 2019 à 10:00
    • Séminaire de Théorie Algorithmique des Nombres
    Salle 2
    Gilles Zémor
    Cryptographie post-quantique à base de codes
    Nous nous proposons de faire un état de l'art et de discuter l'état actuel de la cryptologie basée sur les codes. Nous nous intéresserons à l'approche historique, le paradigme de McEliece, ainsi qu'à la méthodologie plus moderne, initiée par Alekhnovich, et inspirée de la cryptologie basée sur les réseaux suite aux travaux d'Ajtai et de Regev en particulier. Cette deuxième approche ne prétendait pas à l'origine déboucher sur des systèmes de chiffrement compétitifs, mais présentait l'avantage théorique d'avoir des preuves de sécurité bien identifiées et reconnues par la communauté de complexité algorithmique et de cryptologie théorique. Nous détaillerons les principes de ces preuves de sécurité qui ne sont pas accessibles de manière évidente dans la littérature. Nous montrerons également en quoi il y a aujourd'hui convergence des deux approches du chiffrement basé sur les codes.
  • Le 22 octobre 2019 à 10:00
    • Séminaire de Théorie Algorithmique des Nombres
    Salle 2
    Développeurs LFANT IMB
    Hacking session

  • Le 29 octobre 2019 à 10:00
    • Séminaire de Théorie Algorithmique des Nombres
    Salle 2
    Développeurs LFANT IMB
    Hacking session

  • Le 5 novembre 2019 à 10:00
    • Séminaire de Théorie Algorithmique des Nombres
    Salle 2
    Henri Cohen imb
    Apéry-Like recursions and modular forms
    Following Zagier and Beukers, we show that the sequences used by Apery in his proofs of the irrationality of zeta(2) and zeta(3) are special cases of more general sequences having surprisingly only integer values, and that many of these sequences can be parametrized by modular forms. Following Almkwist and Zudilin, we also explain that the degree three sequences used for zeta(3) and generalizations can be automatically obtained via a Clausen type hypergeometric identity from the degree two sequences used for zeta(2) and generalizations.
  • Le 8 novembre 2019 à 14:00
    • Séminaire de Théorie Algorithmique des Nombres
    Salle de conférences
    Guilhem Castagnos imb
    HDR defense: Cryptographie basée sur les corps quadratiques: cryptanalyse, primitives et protocoles

  • Le 19 novembre 2019 à 10:00
    • Séminaire de Théorie Algorithmique des Nombres
    Salle 2
    Maria Dostert EPFL
    Exact Semidefinite Programming Bounds for Packing Problems
    Semidefinite Programming (SDP) is a powerful tool to obtain upper bounds for packing problems. For example, one can consider the kissing problem of the hemisphere in dimension 8 which asks for the maximal number of pairwise non-overlapping spheres which can simultaneously touch a central hemisphere in 8-dimensional Euclidean space. The E8 lattice gives a kissing configuration of 183 points. Moreover, using an SDP given by Bachoc and Vallentin one gets an upper bound of 182.99999999996523. Hence, the optimal value is 183. But how can we obtain the exact rational solution of the SDP based on the floating point results given by the SDP solver?
  • Le 26 novembre 2019 à 10:00
    • Séminaire de Théorie Algorithmique des Nombres
    Salle 1
    Alice Pellet-Mary ÉNS de Lyon
    An LLL Algorithm for Module Lattices
    A lattice is a discrete subgroup (i.e., $\mathbb Z$-module) of $\mathbb R^n$ (where $\mathbb Z$ and $\mathbb R$ are the sets of integers and real numbers). The LLL algorithm is a central algorithm to manipulate lattice bases. It takes as input a basis of a Euclidean lattice, and, within a polynomial number of operations, it outputs another basis of the same lattice but consisting of rather short vectors.
  • Le 10 décembre 2019 à 10:00
    • Séminaire de Théorie Algorithmique des Nombres
    Salle 2
    Développeurs LFANT IMB
    Hacking session

  • Le 10 décembre 2019 à 10:00
    • Séminaire de Théorie Algorithmique des Nombres
    Salle 2
    Développeurs LFANT IMB
    Hacking session

  • Le 14 janvier 2020 à 10:00
    • Séminaire de Théorie Algorithmique des Nombres
    Salle 385
    Abdoulaye Maiga IMB
    Canonical Lift of Genus 2 Curves
    Let $\mathcal{A}/\mathbb{F}_q$ (with $q=p^n$) be an ordinary abelian variety, a classical result due to Lubin, Serre and Tate says that there exists a unique abelian variety $\tilde{\mathcal{A}}$ over $\mathbb{Z}_q$ such that the modulo $p$ reduction of $\tilde{\mathcal{A}}$ is $\mathcal{A}$ and $End(\tilde{\mathcal{A}})\cong End(\mathcal{A})$ as a ring. In 2000 T.Satoh introduced a point-counting algorithm on elliptic curves over $\mathbb{F}_q$ based on canonical lift. In fact the action of the lifted Verschiebung on the tangent space gives Frobenius eigenvalues and hence the characteristic polynomial of the ordinary elliptic curves over $\mathbb{F}_q$. We propose to extend the canonical lift algorithm introduced by T.Satoh to genus 2 curves over finite fields, using the modular polynomials in dimension 2. We first prove the Kronecker condition in dimension 2 case and then succeed to lift the endomorphism ring of $\mathcal{A}$ in dimension 2 case using a general lift algorithm of a $p$-torsion group of an ordinary abelian variety. These results provide an algorithm to compute the characteristic polynomial of a genus 2 curves in quasi-quadratic time complexity.
  • Le 28 janvier 2020 à 10:00
    • Séminaire de Théorie Algorithmique des Nombres
    Salle 385
    Jacques Martinet IMB
    Réseaux, variétés abéliennes et courbes
    On expliquera d'abord comment la notion de *variété abélienne complexe polarisée* possède une version euclidienne dans laquelle on considère des triplets $(E,\Lambda,v)$ d'un espace euclidien $E$, d'un réseau $\Lambda$ de $E$ et d'un élément $v$ de $\mathrm{GL}(E)$ tel que $v^2=-\mathrm{Id}$ et $v(\Lambda)\subset\Lambda^*$.
  • Le 4 février 2020 à 10:00
    • Séminaire de Théorie Algorithmique des Nombres
    Salle 385
    Aude Le Gluher LORIA
    Une approche géométrique efficace pour le calcul d'espaces de Riemann-Roch : Algorithme et Complexité
    Le calcul effectif de bases d'espaces de Riemann-Roch intervient dans de nombreux domaines pratiques, notamment pour l'arithmétique dans les jacobiennes de courbes ou dans des codes correcteurs d'erreurs algébraico-géométriques. Nous proposons une variante probabiliste de l'algorithme de Brill et Noether décrit par Goppa pour le calcul d'une base de l'espace de Riemann-Roch $L(D)$ associé à un diviseur $D$ d'une courbe projective plane nodale $C$ sur un corps parfait $k$ suffisamment grand.
  • Le 11 février 2020 à 10:00
    • Séminaire de Théorie Algorithmique des Nombres
    Salle 385
    Raphael Rieu-Helft Université Paris-Sud
    How to Get an Efficient yet Verified Arbitrary-Precision Integer Library
    We present a fully verified arbitrary-precision integer arithmetic library designed using the Why3 program verifier. It is intended as a verified replacement for the mpn layer of the state-of-the-art GNU Multi-Precision library (GMP).
  • Le 18 février 2020 à 10:00
    • Séminaire de Théorie Algorithmique des Nombres
    Salle 385
    Alex Bartel University of Glasgow
    The ray class group of a "random" number field
    The Cohen–Lenstra–Martinet heuristics are a probabilistic model for the behaviour of class groups of number fields in natural families. In this talk, I will discuss a generalisation to ray class groups. About 5 years ago, Varma determined the average number of 3-torsion elements in the ray class group of K with respect to m, when m is a fixed rational modulus, and K runs through the family of imaginary quadratic or of real quadratic fields. Since then, Bhargava has been challenging the community to come up with a natural probabilistic model that would explain the numbers obtained by Varma, and to predict more general averages in more general families of number fields. As I will explain in my talk, there turns out to be a very simple-minded way of doing so, and also a much more conceptual one, and they both turn out to be equivalent. The more conceptual one involves an object that does not appear to have been treated in the literature before, but that is very natural: the Aralelov ray class group of a number field. This is joint work with Carlo Pagano.
  • Le 10 mars 2020 à 10:00
    • Séminaire de Théorie Algorithmique des Nombres
    Salle 385
    Florent Jouve IMB
    Harmonie et disparités dans le théorème de Chebotarev
    Étant donné une extension galoisienne de corps de nombres L/K, le théorème de Chebotarev affirme l'équirépartition des éléments de Frobenius, relatifs aux idéaux premiers non ramifiés, dans les classes de conjugaison de Gal(L/K). On présentera une étude portant sur les variations du terme d'erreur dans le théorème de Chebotarev, lorsque L/K parcourt certaines familles d'extensions. On donnera une formule de transfert pour les fonctions classiques de décompte des nombres (ou idéaux) premiers permettant de ramener la situation à celle d'une extension des rationnels. On exposera enfin quelques conséquences à des problèmes de "type Linnik" et à l'analogue du phénomène de biais de Chebyshev dans les corps de nombres. L'exposé porte sur un travail commun avec D. Fiorilli.
  • Le 22 septembre 2020 à 10:00
    • Séminaire de Théorie Algorithmique des Nombres
    Online
    Nicolas Mascot Trinity College Dublin
    Modular Galois representations p-adically using Makdisi's moduli-friendly forms
    We will present a p-adic method to compute Galois representations attached to modular forms. This method compares very favourably to the better-known complex-analytic approach. The main ingredient is the use of “moduli-friendly" forms introduced by Makdisi, which allow us to evaluate modular forms at p-adic points of modular curves, and thus to compute in the Jacobian of modular curves without writing down any equations nor q-expansions.
  • Le 13 octobre 2020 à 10:00
    • Séminaire de Théorie Algorithmique des Nombres
    Online
    Christopher Doris Heilbronn Institute and University of Bristol
    Computing Galois groups over p-adic fields
    We give an overview of the history of computing Galois groups over p-adic fields, with some diversions to recent progress over the rational field. We focus on the "resolvent method," a family of techniques to compute Galois groups, and present a recent algorithm to do this in general over p-adic fields, the first of its kind. This algorithm greatly increases the degree of polynomial that can be routinely handled, and for example has been used to extend existing databases of Galois groups of p-adic fields to include all degree 18, 20 and 22 extensions of the 2-adic field. The implementation and tables of results are available on the speaker's website.
  • Le 3 novembre 2020 à 10:00
    • Séminaire de Théorie Algorithmique des Nombres
    Online
    Samuele Anni Université Aix-Marseille
    Isomorphismes de représentations galoisiennes modulaires et graphes
    Dans cet exposé, je vais expliquer comment tester efficacement et effectivement si deux représentations galoisiennes modulaires du groupe absolu de Galois des rationnels sont isomorphes. En particulier, je présenterai de nouvelles bornes optimales sur le nombre de traces à tester. Je discuterai également brièvement des graphes des isomorphismes, des résultats associés sur les algèbres de Hecke et de la construction d'une base de données de représentations.
  • Le 10 novembre 2020 à 10:00
    • Séminaire de Théorie Algorithmique des Nombres
    Online
    Raphaël Pagès IMB
    Calcul efficace des polynômes caractéristiques des p-courbures d'un opérateur différentiel à coefficients entiers
    Nous présentons un nouvel algorithme permettant de calculer les polynômes caractéristiques des $p$-courbures d'un opérateur différentiel à coefficients entiers pour tout $p$ premier inférieur à un entier $N$ donné, en temps quasi-linéaire, donc quasi-optimal, en $N$. L'algorithme présenté se base sur les travaux de A. Bostan, X. Caruso et E. Schost ramenant le calcul de cet invariant au calcul d'une factorielle de matrices, ainsi que sur la technique de calcul de factorielles développée par E. Costa, R. Gerbicz et D. Harvey.
  • Le 17 novembre 2020 à 10:00
    • Séminaire de Théorie Algorithmique des Nombres
    Online
    Fredrik Johansson IMB
    Calcium: computing in exact real and complex fields
    Calcium is a C library for real and complex numbers in a form suitable for exact algebraic and symbolic computation. Numbers are represented as elements of fields $\mathbb{Q}(a_1,\ldots,a_n)$ where the extension numbers $a_k$ may be algebraic or transcendental. The system combines efficient field arithmetic with automatic construction of fields and ideals of algebraic relations, resulting in a practical computational model of $\mathbb{R}$ and $\mathbb{C}$ in which equality is rigorously decidable for a large class of numbers which includes $\overline{\mathbb{Q}}$ as a subset.
  • Le 24 novembre 2020 à 10:00
    • Séminaire de Théorie Algorithmique des Nombres
    Online
    Anne-Edgar Wilke IMB
    Recouvrements optimaux d'ensembles de Siegel tronqués par des boules euclidiennes
    Étant donné un groupe algébrique $G$ agissant sur un espace affine $V$, il arrive que l'ensemble $V(\mathbb{Z})/G(\mathbb{Z})$ des orbites entières paramètre des objets arithmétiques et soit donc intéressant à énumérer. Une façon de s'y prendre consiste à expliciter un domaine fondamental de l'action de $G(\mathbb{Z})$ sur $V(\mathbb{R})$ et à y rechercher les points entiers. Pour cela, on peut essayer de recouvrir ce domaine fondamental par une famille de boules euclidiennes de rayon constant dont le cardinal soit du même ordre de grandeur que le nombre de points entiers. Je montrerai comment mettre en œuvre cette stratégie dans le cas simple de l'action à droite de $\mathrm{GL}_n$ sur $\mathrm{M}_n$, dont les orbites entières paramètrent les sous-modules de $\mathbb{Z}^n$, et pour laquelle on dispose de domaines fondamentaux approchés faciles à décrire, à savoir les ensembles de Siegel.
  • Le 1er décembre 2020 à 10:00
    • Séminaire de Théorie Algorithmique des Nombres
    Online
    Tommy Hofmann Saarland University
    The conjugacy problem in $mathrm{GL}(n, mathbb{Z})$
    We consider the problem of deciding whether two matrices are conjugate. If the coefficient ring is a field, this problem can be easily solved by using the Jordan normal form or the rational canonical form. For more general coefficient rings, the situation becomes increasingly challenging, both from a theoretical and a practical viewpoint. In this talk, we show how the conjugacy problem for integer matrices can be efficiently decided using techniques from group and number theory. This is joint work with Bettina Eick and Eamonn O'Brien.
  • Le 8 décembre 2020 à 10:00
    • Séminaire de Théorie Algorithmique des Nombres
    Salle 385
    Alexandre Bailleul ENS Lyon
    Zéros réels de fonctions L d'Artin et biais de Chebyshev dans les corps de nombres
    Le biais de Chebyshev est un phénomène qui a été étudié tout d'abord dans le cadre des "courses de nombres premiers" (Rubinstein et Sarnak, 1994) pour expliquer la prédominance apparente des nombres premiers congrus à 3 mod 4 par rapport à ceux qui sont congrus à 1 mod 4. Ces courses de nombres premiers ont été généralisées notamment dans le contexte des corps de nombres par Ng en 2000. Dans des travaux récents, Fiorilli et Jouve ont étudié le biais de Chebyshev dans des familles d'extensions de corps de nombres, et mis en évidence des comportements limites de type "grandes déviations" et "théorème central limite". Dans le travail présenté, je mets en évidence l'influence considérable qu'ont certains zéros réels de fonctions L d'Artin sur le biais de Chebyshev dans des extensions particulières de corps de nombres.
  • Le 15 décembre 2020 à 10:00
    • Séminaire de Théorie Algorithmique des Nombres
    Online
    Elie Eid Université de Rennes
    Équations différentielles $p$-adiques pour le calcul d'isogénies en.petite caractéristique
    On présente une méthode effective de calcul sur les $p$-adiques d’isogénies entre courbes elliptiques et Jacobiennes de courbes hyperelliptiques de petit genre. Une application importante est le cas des courbes définies sur un corps fini de petite caractéristique, qui peut être résolu par relèvement dans les $p$-adiques. Notre algorithme repose sur la résolution d’équations différentielles avec un bon contrôle de perte de précision. Son analyse est basée sur la théorie de la précision différentielle développée par Caruso, Roe et Vaccon.
  • Le 12 janvier 2021 à 10:00
    • Séminaire de Théorie Algorithmique des Nombres
    Online
    Alain Couvreur LIX -- Inria Saclay
    On the hardness of code equivalence problems in rank metric
    In recent years, the notion of rank metric in the context of coding theory has known many interesting developments in terms of applications such as space time coding, network coding or public key cryptography. These applications raised the interest of the community for theoretical properties of this type of codes, such as the hardness of decoding in rank metric or better decoding algorithms. Among classical problems associated to codes for a given metric, the notion of code equivalence has always been of the greatest interest. In this talk, we discuss the hardness of the code equivalence problem in rank metric for $\mathbb F_{q^m}$--linear and general rank metric codes.
  • Le 19 janvier 2021 à 10:00
    • Séminaire de Théorie Algorithmique des Nombres
    Online
    Renaud Vilmart LSV -- Inria Saclay
    Une introduction aux circuits quantiques et au ZX-calcul
    L'informatique quantique est de plus en plus un sujet brûlant, car elle promet bien des avantages, que ça soit pour la complexité de ses algorithmes, ou pour ce qu'elle permet en cryptographie. Dans cet exposé, nous allons d'abord voir les circuits quantiques : le modèle habituellement utilisé par les chercheurs et les ingénieurs pour décrire des processus quantiques. Nous nous intéresserons à une question fondamentale liée à ces circuits, celle de la complétude d'une théorie équationnelle. Nous présenterons ensuite le ZX-Calcul, un modèle issu de la théorie des catégories, qui répond, lui, positivement à cette même question.
  • Le 26 janvier 2021 à 10:00
    • Séminaire de Théorie Algorithmique des Nombres
    Online
    Mercedes Haiech Université Rennes 1
    The Fundamental Theorem of Tropical Partial Differential Algebraic .Geometry
    Given a partial differential equation (PDE), its solutions can be difficult, if not impossible, to describe. The purpose of the Fundamental theorem of tropical (partial) differential algebraic geometry is to extract from the equations certain properties of the solutions. More precisely, this theorem proves that the support of the solutions in $k[[t_1, \cdots, t_m]]$ (with $k$ a field of characteristic zero) can be obtained by solving a so-called tropicalized differential system.
  • Le 2 février 2021 à 10:00
    • Séminaire de Théorie Algorithmique des Nombres
    Online
    Bogdan Dina Ulm University
    Isogenous hyperelliptic and non-hyperelliptic Jacobians with maximal complex multiplication
    We analyze complex multiplication for Jacobians of curves of genus 3, as well as the resulting Shimura class groups and their subgroups corresponding to Galois conjugation over the reflex field. We combine our results with numerical methods to find CM fields $K$ for which there exist both hyperelliptic and non-hyperelliptic curves whose Jacobian has complex multiplication by $\mathbb{Z}_K$.
  • Le 2 mars 2021 à 10:00
    • Séminaire de Théorie Algorithmique des Nombres
    Online
    Jade Nardi Inria Saclay\, LIX
    Explicit construction and parameters of projective toric codes
    Toric codes, introduced by Hansen in 2002, generalize (weighted) Reed-Muller codes on other toric varieties than projective spaces. They consist of evaluation codes of monomials at tuples of non-zero coordinates, which correspond to the points on the dense torus contained in the associated toric variety. Our aim is to ‘projectivise’ these codes, in the same spirit that turns a Reed-Muller codes into a projective one: we consider codes obtained by evaluating global sections on the whole set of the rational points of a toric variety. We focus on simplicial toric varieties, which come with a nice quotient description, and we give an explicit construction of projective codes on them, as well as a combinatorial way to determine their parameters. 'Projectivizing' toric codes opens new possibilities of getting codes with excellent parameters, by extending some champion classical toric codes geometrically.
  • Le 9 mars 2021 à 10:00
    • Séminaire de Théorie Algorithmique des Nombres
    Online
    Cécile Armana LMB\, Université de Franche-Comté
    Bornes de Sturm pour des formes automorphes sur les corps de fonctions
    Les bornes de Sturm indiquent combien de coefficients de Fourier successifs suffisent à déterminer une forme modulaire. Pour les formes modulaires classiques, elles fournissent aussi des bornes sur le nombre d'opérateurs de Hecke engendrant l'algèbre du même nom. Cet exposé propose d'étudier la situation pour certaines formes automorphes, dites de Drinfeld, sur les corps de fonctions. Il s'agit d'un travail en commun avec Fu-Tsun Wei (National Tsing-Hua University, Taïwan).
  • Le 16 mars 2021 à 10:00
    • Séminaire de Théorie Algorithmique des Nombres
    Online
    Vincent Neiger Université de Limoges
    Deterministic computation of the characteristic polynomial in the time of matrix multiplication
    This talk describes joint work with Clément Pernet on an algorithm which computes the characteristic polynomial of a matrix over a field within the same asymptotic complexity, up to constant factors, as the multiplication of two square matrices. Previously, this was only achieved by resorting to genericity assumptions or randomization techniques, while the best known complexity bound with a general deterministic algorithm was obtained by Keller-Gehrig in 1985 and involves logarithmic factors. The new algorithm computes more generally the determinant of a univariate polynomial matrix in reduced form.
  • Le 16 mars 2021 à 10:00
    • Séminaire de Théorie Algorithmique des Nombres
    Online
    Vincent Neiger Université de Limoges
    Deterministic computation of the characteristic polynomial in the time of matrix multiplication
    This talk describes joint work with Clément Pernet on an algorithm which computes the characteristic polynomial of a matrix over a field within the same asymptotic complexity, up to constant factors, as the multiplication of two square matrices. Previously, this was only achieved by resorting to genericity assumptions or randomization techniques, while the best known complexity bound with a general deterministic algorithm was obtained by Keller-Gehrig in 1985 and involves logarithmic factors. The new algorithm computes more generally the determinant of a univariate polynomial matrix in reduced form.
  • Le 23 mars 2021 à 10:00
    • Séminaire de Théorie Algorithmique des Nombres
    Online
    Samuel Le Fourn Institut Fourier\, Université Grenoble Alpes
    Recherche de points entiers sur une variété modulaire de dimension 3
    La détermination effective des points entiers sur des variétés algébriques est un problème difficile, surtout en dimension plus grande que 1. Dans cet exposé, je présenterai brièvement deux approches naturelles pour les points entiers qui permettent dans des cas favorables de tous les trouver. En cherchant des raffinements de ces méthodes, on arrive à des problèmes combinatoires intéressants, que je mettrai en valeur dans le cas précis d'une variété "modulaire" de dimension 3, qu'on peut définir par une équation quartique dans $\mathbb{P}^4$.
  • Le 30 mars 2021 à 10:00
    • Séminaire de Théorie Algorithmique des Nombres
    Online
    Charles Fougeron IRIF\, Université de Paris
    Dynamiques des algorithmes de fraction continue multidimensionnels
    Motivés par la richesse de l'algorithme de Gauss qui permet de calculer efficacement les meilleurs approximation d'un nombre réel par des rationnels, beaucoup de mathématiciens ont proposé des généralisations de ces algorithmes pour approximer des vecteurs de dimension supérieure à 1. Citons pour exemple celui de Poincaré introduit à la fin du 19e siècle ou ceux de Brun et Selmer à la moitié du 20e siècle.
  • Le 6 avril 2021 à 10:00
    • Séminaire de Théorie Algorithmique des Nombres
    Online
    Marc Masdeu Universitat Autònoma de Barcelona
    Numerical experiments with plectic Stark--Heegner points
    Let $E/F$ be an elliptic curve defined over a number field $F$, and let $K/F$ be a quadratic extension. If the analytic rank of $E(K)$ is one, one can often use Heegner points (or the more general Darmon points) to produce (at least conjecturally) a nontorsion generator of $E(K)$. If the analytic rank of $E(K)$ is larger than one, the problem of constructing algebraic points is still very open. In very recent work, Michele Fornea and Lennart Gehrmann have introduced certain $p$-adic quantities that may be conjecturally related to the existence of these points. In this talk I will explain their construction, and illustrate with some numerical experiments that we have been able to carry out that support their conjecture. This is joint work with Michele Fornea and Xevi Guitart.
  • Le 27 avril 2021 à 10:00
    • Séminaire de Théorie Algorithmique des Nombres
    Online
    Ann Kiefer Luxembourg Centre for Educational Testing
    Property (FA) of the unit group of $2$-by-$2$ matrices over an order in a quaternion algebra
    We study property (FA) and its hereditary version for unit groups of $2$-by-$2$ matrices over orders in totally definite quaternion algebras with rational centres. In particular we consider the three matrix rings over totally definite rational quaternion algebras that can appear as Wedderbrun-Artin components of a group ring $\mathbb{Q}G$.
  • Le 4 mai 2021 à 10:00
    • Séminaire de Théorie Algorithmique des Nombres
    Online
    Barinder Banwait Harish-Chandra Research Institute
    Explicit isogenies of prime degree over quadratic fields
    Let $K$ be a quadratic field which is not an imaginary quadratic field of class number one. We describe an algorithm to compute a superset of the set of primes $p$ for which there exists an elliptic curve over $K$ admitting a $K$-rational $p$-isogeny. Combining this algorithm with recent work on the determination of quadratic points on low-genus modular curves, we determine - conditional upon the Generalised Riemann Hypothesis - the above set of isogeny primes for several quadratic fields, providing the first such examples after Mazur's 1978 determination for $K = \mathbb{Q}$. We will give a live demo of the Sage and PARI/GP implementations of the algorithm.
  • Le 11 mai 2021 à 10:00
    • Séminaire de Théorie Algorithmique des Nombres
    Online
    Weiqiang Wen Inria Rennes\, Irisa
    On algorithms for solving Euclidean lattice problems in cryptography
    In this talk, we will try to review the state-of-the-art of the algorithms for solving the Euclidean lattice problems underlying cryptography. In more details, this talk contains two parts. In the first part, we will focus on the lattice problems such as approximate Shortest Vector Problem (approx-SVP) and the lattice reduction algorithms as the best known solving algorithms so far. In particular, I will present an improved enumeration-based lattice reduction algorithm, which is shown to be (potentially) relevant to cryptanalysis. In the second part, we will instead consider a quantum problem that is computationally equivalent to approx-SVP. By directly solving a quantum problem, we may expect to have a more powerful use of the quantum computation. However, the best known algorithms for solving approx-SVP via solving this quantum problem, is not better than lattice reduction yet.
  • Le 18 mai 2021 à 10:00
    • Séminaire de Théorie Algorithmique des Nombres
    Online
    Aurore Guillevic Inria Nancy\, Loria
    Computing Murphy-alpha in the special tower number field sieve algorithm and applications to pairing-based cryptography
    Pairings on elliptic curves are involved in signatures, NIZK, and recently in blockchains (ZK-SNARKS). These pairings take as input two points on an elliptic curve $E$ over a finite field, and output a value in an extension of that finite field. Usually for efficiency reasons, this extension degree is a power of 2 and 3 (such as 12, 18, 24), and moreover the characteristic of the finite field has a special form. The security relies on the hardness of computing discrete logarithms in the group of points of the curve and in the finite field extension.
  • Le 25 mai 2021 à 10:00
    • Séminaire de Théorie Algorithmique des Nombres
    Online
    Razvan Barbulescu CNRS\, IMB
    Quelques conséquences du programme de Mazur sur la cryptographie
    Les algorithmes de factorisation d'entiers et ceux de calcul de logarithmes discrets, adaptés aux tailles cryptographiques, ont deux étapes pertinentes pour notre exposé : la sélection polynomiale et la cofactorisation. La première consiste à sélectionner deux polynômes homogènes $F(x,y)$ et $G(x,y)$ dans $\mathbb{Z}[x,y]$ tels que les entiers de l'ensemble $\{F(a,b)G(a,b)\mid a,b\in\text{ un rectangle },\gcd(a,b)=1 \}$ contiennent le plus possible d'entiers $B$-friables (ayant tous les facteurs premiers inférieurs à $B$). La deuxième consiste à factoriser des entiers de la forme $F(a,b)$ et $G(a,b)$.
  • Le 1er juin 2021 à 10:00
    • Séminaire de Théorie Algorithmique des Nombres
    Online
    Andreas Enge\, Bill Allombert\, Fredrik Johansson Inria\, CNRS\, Inria
    Présentation de l'équipe LFANT pour les stagiaires
    Cette séance spéciale est dédiée à l'accueil des stagiaires dans l'équipe LFANT. Après une présentation générale de l'équipe, nous présenterons deux logiciels que nous développons : PARI/GP et Arb.
  • Le 8 juin 2021 à 10:00
    • Séminaire de Théorie Algorithmique des Nombres
    Online
    Stéphane Ballet I2M\, Université Aix-Marseille
    Optimization of the scalar complexity of Chudnovsky^2 multiplication algorithms in finite fields
    We propose several constructions for the original multiplication algorithm of D.V. and G.V. Chudnovsky in order to improve its scalar complexity. We highlight the set of generic strategies who underlay the optimization of the scalar complexity, according to parameterizable criteria. As an example, we apply this analysis to the construction of type elliptic Chudnovsky2 multiplication algorithms for small extensions. As a case study, we significantly improve the Baum-Shokrollahi construction for multiplication in F256/F4.
  • Le 15 juin 2021 à 10:00
    • Séminaire de Théorie Algorithmique des Nombres
    Online
    Fabien Narbonne IRMAR\, Université de Rennes
    Corps de modules des courbes de genre 2 à Jacobienne décomposée
    Nous nous intéresserons aux de courbes de genre 2 dont la Jacobienne est géométriquement le produit de deux courbes elliptiques avec multiplication complexe par le même ordre (maximal). Nous proposerons un algorithme permettant de compter combien d'entre elles ont pour corps de modules Q. Pour cela nous développerons une équivalence de catégories entre certaines variétés abéliennes polarisées et des réseaux hermitiens. Il s'agit d'une généralisation d'un article de A. Gélin, E. Howe et C. Ritzenthaler de 2018 dans lequel la Jacobienne est le carré d'une même courbe elliptique.
  • Le 22 juin 2021 à 10:00
    • Séminaire de Théorie Algorithmique des Nombres
    Online
    Vandita Patel University of Manchester
    Shifted powers in Lucas-Lehmer sequences
    The explicit determination of perfect powers in (shifted) non-degenerate, integer, binary linear recurrence sequences has only been achieved in a handful of cases. In this talk, we combine bounds for linear forms in logarithms with results from the modularity of elliptic curves defined over totally real fields to explicitly determine all shifted powers by two in the Fibonacci sequence. A major obstacle that is overcome in this work is that the Hilbert newspace which we are interested in has dimension 6144. We will focus on how this space is computationally handled with respect to the underlying Diophantine equation. This is joint work with Mike Bennett (UBC) and Samir Siksek (Warwick).
  • Le 29 juin 2021 à 10:00
    • Séminaire de Théorie Algorithmique des Nombres
    Online
    Pierre Briaud Inria Paris
    An algebraic approach to the Rank Support Learning problem
    Rank-metric code-based cryptography relies on the hardness of decoding a random linear code in the rank metric. The Rank Support Learning problem (RSL) is a variant where an attacker has access to N decoding instances whose errors have the same support and wants to solve one of them. This problem is for instance used in the Durandal signature scheme. In this talk, we will present a new algebraic attack on RSL. We build upon Bardet et al., Asiacrypt 2020, where similar techniques are used to solve MinRank and RD. However, our analysis is simpler and overall our attack relies on very elementary assumptions compared to standard Gröbner bases attacks. In particular, our results show that key recovery attacks on Durandal are more efficient than was previously thought. This is joint work with Magali Bardet.
  • Le 6 juillet 2021 à 10:00
    • Séminaire de Théorie Algorithmique des Nombres
    Online
    Anna Somoza IRMAR\, Université de Rennes 1
    The Inverse Jacobian problem
    To an algebraic curve $C$ over the complex numbers one can associate a non-negative integer $g$, the genus, as a measure of its complexity. One can also associate to $C$, via complex analysis, a $g\times g$ symmetric matrix $\Omega$ called period matrix. Because of the natural relation between $C$ and $\Omega$, one can obtain information about one by studying the other. Therefore, it makes sense to consider the inverse problem: Given a period matrix $\Omega$, can we compute a model for the associated curve $C$?
  • Le 13 juillet 2021 à 15:00
    • Séminaire de Théorie Algorithmique des Nombres
    Salle de conférences
    Jean Kieffer IMB
    Équations modulaires en dimension supérieure, applications au calcul d'isogénies et au comptage de points

  • Le 5 octobre 2021 à 10:00
    • Séminaire de Théorie Algorithmique des Nombres
    Salle 2
    Henri Cohen IMB
    Algebraic values of the hypergeometric function
    In this talk, I will study the general problem of when the value of the hypergeometric function $F(a,b;c;z)$ is algebraic, assuming $a$,$b$,$c$, and $z$ rational. The results involve modular forms and functions, complex multiplication, Shimura curves, and computer searches.
  • Le 12 octobre 2021 à 10:00
    • Séminaire de Théorie Algorithmique des Nombres
    Salle 2
    Damien Robert IMB
    Revisiter l'algorithme de Satoh de comptage de points en petite caractéristique par relèvement canonique
    L'algorithme de Satoh de comptage de points sur les courbes elliptiques permet d'obtenir (après des améliorations de Harvey) une complexité quasi-quadratique en le degré pour une (petite) caractéristique fixée $p$. Dans cet exposé je passerai en revue plusieurs variantes de cet algorithme et ses extensions aux variétés abéliennes. J'expliquerai ensuite comment on peut grandement simplifier l'implémentation de cet algorithme. L'implémentation dans Pari/GP du nouvel algorithme produit un gain d'un facteur 30 à la fois de temps de calcul et de consommation mémoire.
  • Le 9 novembre 2021 à 10:00
    • Séminaire de Théorie Algorithmique des Nombres
    Salle 2
    Koen de Boer CWI Amsterdam
    Sampling relatively near-prime ideals
    We show a method to sample an element alpha from a given ideal I, such that their quotient ideal (alpha)/I is a (possibly large) prime times a smooth number ('near-prime') with reasonable probability. This method consists of 'randomizing' the ideal I by multiplying it with small primes (yielding J) and consequently sampling the element alpha from this randomized ideal J intersected with a large box. The probability that the quotient (alpha)/J is prime (i.e., that the quotient (alpha)/I is a near-prime) is tightly related to density results on prime ideals (prime ideal theorem). As an application we show an efficient way to compute power residue symbols for varying degree number fields.
  • Le 16 novembre 2021 à 10:00
    • Séminaire de Théorie Algorithmique des Nombres
    Salle 2
    Benjamin Wesolowski CNRS\, IMB
    SQISign: Compact Post-Quantum Signature from Quaternions and Isogenies
    We will present the signature scheme SQISign, (for Short Quaternion and Isogeny Signature) exploiting isogeny graphs of supersingular elliptic curves. The signature and public key sizes combined are an order of magnitude smaller than all other post-quantum signature schemes. Its efficient implementation and security analysis open new research challenges.
  • Le 23 novembre 2021 à 10:00
    • Séminaire de Théorie Algorithmique des Nombres
    Salle 2
    Aurel Page IMB
    Norm relations and class group computations
    When $L/K$ is a Galois extension of number fields with Galois group $G$, some invariants of $L$ can be related to those of its proper subfields. I will present some old and some new such relations, and an application to the computation of class groups of some large number fields. This is joint work with Jean-François Biasse, Claus Fieker and Tommy Hofmann.
  • Le 30 novembre 2021 à 10:00
    • Séminaire de Théorie Algorithmique des Nombres
    Salle 2
    Katharina Boudgoust IRISA EMSEC\, Rennes
    The partial Vandermonde knapsack problem
    In my seminar I will do an introduction to the concept of essential dimension: roughly speaking, the essential dimension is a measure of how many independent parameters we need to describe some algebraic object. The concept of essential dimension was introduced by Buhler and Reichstein in 1995 and it is linked to an algebraic version of Hilbert's 13th problem. For a finite group $G$; the essential dimension measures how much one can compress a faithful representation of $G$. When $G$ is the symmetric group $S_n$ the essential dimension tells us how many independent parameters we need to write a generic polynomial of degree $n$ on a field $k$ of characteristic zero; equivalently, the essential dimension of $S_n$ computes the number of parameters needed to write a generating polynomial for separable field extensions of degree $n$. This is still an open problem for $n geq 8. Suprisingly, the analogue problem for inseparable field extensions has been solved explicitely.
  • Le 30 novembre 2021 à 10:00
    • Séminaire de Théorie Algorithmique des Nombres
    Salle 2
    Katharina Boudgoust IRISA EMSEC\, Rennes
    The partial Vandermonde knapsack problem
    This work contributes in the field of lattice-based cryptography, a research domain of public key cryptography that was initiated at the end of the 1990s by two different branches. On the one had, there have been proposals benefiting from strong theoretical connections to presumed hard worst-case lattice problems, leading to the development of public key cryptography based on the SIS (Short Integer Solution) and LWE (Learning With Errors) problems. On the other hand, very efficient schemes basing their security on average-case structured lattice problems have been introduced, the most popular among them is the NTRU encryption scheme.
  • Le 7 décembre 2021 à 10:00
    • Séminaire de Théorie Algorithmique des Nombres
    Salle 386
    Olivier Bernard IRISA EMSEC\, Rennes
    Log-S-unit lattices using Explicit Stickelberger Generators to solve Approx Ideal-SVP
    The Twisted-PHS algorithm to solve Approx-SVP for ideal lattices on any number field, based on the PHS algorithm by Pellet-Mary, Hanrot and Stehlé in 2019, was introduced in 2020. The authors performed experiments for prime conductors cyclotomic fields of degrees at most 70, reporting exact approximation factors reached in practice. The main obstacle for these experiments is the computation of a log-S-unit lattice, which requires classical subexponential time.
  • Le 14 décembre 2021 à 10:00
    • Séminaire de Théorie Algorithmique des Nombres
    Online
    Xavier Goaoc Université de Lorraine\, LORIA
    Un phénomène de concentration en géométrie combinatoire
    Le type d'ordre d'une séquence de points du plan est une généralisation de la permutation associée à une séquence de nombres réels. Cette structure combinatoire encode de nombreuses propriétés géométriques de la séquence de points, par exemple le treillis des faces de son enveloppe convexe, ou encore les triangulations qu'elle supporte.
  • Le 4 janvier 2022 à 10:00
    • Séminaire de Théorie Algorithmique des Nombres
    Online
    Guillaume Moroz Inria\, LORIA
    New data structure for univariate polynomial approximation and applications to root isolation, numerical multipoint evaluation, and other problems
    We present a new data structure to approximate accurately and efficiently a polynomial $f$ of degree $d$ given as a list of coefficients. Its properties allow us to improve the state-of-the-art bounds on the bit complexity for the problems of root isolation and approximate multipoint evaluation. This data structure also leads to a new geometric criterion to detect ill-conditioned polynomials, implying notably that the standard condition number of the zeros of a polynomial is at least exponential in the number of roots of modulus less than $\frac{1}{2}$ or greater than $2$.
  • Le 25 janvier 2022 à 10:00
    • Séminaire de Théorie Algorithmique des Nombres
    Online
    Céline Maistret University of Bristol
    Parity of ranks of abelian surfaces
    Let $K$ be a number field and $A/K$ an abelian surface. By the Mordell-Weil theorem, the group of $K$-rational points on $A$ is finitely generated and as for elliptic curves, its rank is predicted by the Birch and Swinnerton-Dyer conjecture. A basic consequence of this conjecture is the parity conjecture: the sign of the functional equation of the $L$-series determines the parity of the rank of $A/K$.
  • Le 8 février 2022 à 10:00
    • Séminaire de Théorie Algorithmique des Nombres
    Online
    Elisa Lorenzo Garcia Université de Neuchâtel
    Reduction type of hyperelliptic curves in terms of the valuations of their invariants.
    In this talk we will first review the classical criteria to determine the (stable) reduction type of elliptic curves (Tate) and of genus 2 curves (Liu) in terms of the valuations of some particular combinations of their invariants. We will also revisit the theory of cluster pictures to determine the reduction type of hyperelliptic curves (Dokchitser's et al.). Via Mumford theta constants and Takase and Tomae's formulas we will be able to read the cluster picture information by looking at the valuations of some (à la Tsuyumine) invariants in the genus 3 case. We will also discuss the possible generalization of this strategy for any genus and some related open questions.
  • Le 8 mars 2022 à 10:00
    • Séminaire de Théorie Algorithmique des Nombres
    Online
    Elena Berardini Télécom Paris
    Calcul d'espaces de Riemann-Roch pour les codes géométriques
    Les codes de Reed-Solomon sont largement utilisés pour représenter des données sous forme de vecteurs, de sorte que les données peuvent être récupérées même si certaines coordonnées des vecteurs sont corrompues. Ces codes ont de nombreuses propriétés. Leurs paramètres sont optimaux. Ils permettent de reconstruire des coordonnées qui ont été effacées. Ils sont compatibles avec l'addition et la multiplication de données. Néanmoins, ils souffrent de certaines limitations. Notamment, la taille de stockage des coordonnées des vecteurs augmente de manière logarithmique avec le nombre de coordonnées. Les codes dits géométriques généralisent les codes de Reed-Solomon en bénéficiant des mêmes propriétés, tout en étant libres de ces limitations. Par conséquent, l'utilisation de codes géométriques apporte des gains de complexité, et s'avère utile dans plusieurs applications telles que le calcul distribué sur les secrets et les preuves zero-knowledge. Les codes géométriques sont construits en évaluant des familles de fonctions, appelées espaces de Riemann-Roch, en les points rationnels d'une courbe. Il s'ensuit que le calcul de ces espaces est crucial pour la mise en œuvre des codes géométriques. Dans cet exposé, je présenterai un travail récent en collaboration avec S. Abelard, A. Couvreur et G. Lecerf sur le calcul effectif des bases des espaces de Riemann-Roch de courbes. Après avoir révisé l'état de l'art sur le sujet, je discuterai des idées à la base de notre algorithme, en particulier la théorie de Brill-Noether et l'utilisation des expansions de Puiseux. Les courbes utilisées dans la construction des codes géométriques sont pour la plupart limitées à celles pour lesquelles les bases de Riemann-Roch sont déjà connues. Ce nouveau travail et ceux qui suivront, permettront la construction de codes géométriques à partir de courbes plus générales.
  • Le 15 mars 2022 à 10:00
    • Séminaire de Théorie Algorithmique des Nombres
    Salle 2
    Pierrick Dartois Corps des mines\, Rennes 1
    Cryptanalyse du protocole OSIDH
    Oriented Supersingular Isogeny Diffie-Hellman (OSIDH) est un échange de clé post-quantique proposé par Leonardo Colò et David Kohel en 2019. La construction repose sur l’action du groupe de classe d’un ordre quadratique imaginaire sur un espace de courbes elliptiques supersingulières et peut donc être vue comme une généralisation du célèbre échange de clé à base d’isogénies CSIDH. Cependant, OSIDH est très différent de CSIDH d’un point de vue algorithmique parce qu’OSIDH utilise des groupes de classe plus structurés que CSIDH. Comme l’ont reconnu Colò et Kohel eux-mêmes, cela rend OSIDH plus vulnérable aux attaques. Pour contourner cette faiblesse, ils ont proposé une façon ingénieuse d’effectuer l’échange de clé en échangeant de l’information sur l’action du groupe de classe au voisinage des courbes publiques, et ont conjecturé que cette information additionnelle n’impacterait pas la sécurité.
  • Le 22 mars 2022 à 10:00
    • Séminaire de Théorie Algorithmique des Nombres
    Salle 2
    Jean Kieffer Harvard University
    Schémas de Newton certifiés pour l'évaluation des fonctions thêta en petit genre
    Les fonctions thêta permettent de relier les points de vue algébrique et analytique dans l'étude des variétés abéliennes: ce sont des formes modulaires de Siegel qui fournissent des coordonnées sur ces variétés et leurs espaces de modules. Rendre ce lien effectif nécessite un algorithme efficace d'évaluation de ces fonctions thêta en un point. Dupont, dans sa thèse (2006), a décrit un algorithme heuristique basé sur la moyenne arithmético-géométrique (AGM) et un schéma de Newton pour évaluer certaines fonctions thêta en genre 1 et 2 en temps quasi-linéaire en la précision. Le but de cet exposé est de montrer que l'on peut en fait obtenir un algorithme certifié dont la complexité est uniforme. Je discuterai également des obstacles restants pour généraliser ce résultat en dimension supérieure.
  • Le 29 mars 2022 à 10:00
    • Séminaire de Théorie Algorithmique des Nombres
    Online
    Andreas Pieper Universität Ulm
    Constructing all genus 2 curves with supersingular Jacobian
    F. Oort showed that the moduli space of principally polarized supersingular abelian surfaces is a union of rational curves. This is proven by showing that every principally polarized supersingular abelian surface is the Jacobian of a fibre of one of the families of genus 2 curves $\pi: \mathcal{C}\rightarrow \mathbb{P}^1$ constructed by L. Moret-Bailly. We present an algorithm that makes this construction effective: Given a point $x\in \mathbb{P}^1$ we compute a hyperelliptic model of the fibre $\pi^{-1}(x)$. The algorithm uses Mumford's theory of theta groups to compute quotients by the group scheme $\alpha_p$.
  • Le 5 avril 2022 à 10:00
    • Séminaire de Théorie Algorithmique des Nombres
    -
    Damien Robert IMB
    Towards computing the canonical lift of an ordinary elliptic curve in medium characteristic
    Satoh's algorithm for counting the number of points of an elliptic curve $E/\mathbb F_q$ with $q=p^n$ is the fastest known algorithm when $p$ is fixed: it computes the invertible eigenvalue $»$ of the Frobenius to $p$-adic precision $m$ in time $\tilde{O}(p^2 n m)$. Since by Hasse's bound, recovering $\chi_{\pi}$ requires working at precision $m=O(n)$, the point counting complexity is of $\tilde{O}(p^2 n^2)$, quasi-quadratic in the degree $n$.Unfortunately, the term $p^2$ in the complexity makes Satoh's algorithm suitable only for smaller $p$. For medium sized $p$, one can use Kedlaya's algorithm which cost $\tilde{O}(p n^2 m)$ or a variant by Harvey's which cost $\tilde{O}(p^{1/2} n^{5/2} m + n^4 m)$, which have a better complexity on $p$ but a worse one on $n$. For large $p$, the SEA algorithm costs $\tilde{O}(log^4 q)$.In this talk, we improve the dependency on $p$ of Satoh's algorithm while retaining the dependency on $n$ to bridge the gap towards medium characteristic. We develop a new algorithm with a complexity of $\tilde{O}(p n m)$. In the particular case where we are furthermore provided with a rational point of $p$-torsion, we even improve this complexity to $\tilde{O}(p^{1/2} n m)$.This is a joint work with Abdoulaye Maiga.
  • Le 12 avril 2022 à 10:00
    • Séminaire de Théorie Algorithmique des Nombres
    -
    Josué Tonelli-Cueto Inria Paris\, IMJ-PRG
    A p-adic Descartes solver: the Strassman solve
    Solving polynomials is a fundamental computational problem in mathematics. In the real setting, we can use Descartes' rule of signs to efficiently isolate the real roots of a square-free real polynomial. In this talk, we show how to translate this method into the p-adic worlds. We show how the p-adic analog of Descartes' rule of signs, Strassman's theorem, leads to an algorithm to isolate the p-adic roots of a square-free p-adic polynomial and provide some complexity estimates adapting the condition-based complexity framework from real/complex numerical algebraic geometry to the p-adic case.
  • Le 26 avril 2022 à 10:00
    • Séminaire de Théorie Algorithmique des Nombres
    -
    Lassina Dembélé King's College London
    "Correspondance de Langlands inertielle explicite pour ${\nm GL}_2$ et quelques applications arithmétiques"
    Dans cet exposé nous allons décrire une approche explicite qui permet de calculer les types automorphes inertiels pour ${\rm GL}_2$. Nous donnerons ensuite quelques applications de cet algorithme à des problèmes diophantiens ou de nature arithmétique.
  • Le 3 mai 2022 à 10:00
    • Séminaire de Théorie Algorithmique des Nombres
    -
    Sergey Yurkevich University of Vienna\, Inria
    The generating function of the Yang-Zagier Numbers is algebraic
    In a recent paper Don Zagier mentions a mysterious integer sequence $(a_n) _{n \geq 0}$ which arises from a solution of a topological ODE discovered by Marco Bertola, Boris Dubrovin and Di Yang. In my talk I show how to conjecture, prove and even quantify that $(a_n) _{n \geq 0}$ actually admits an algebraic generating function which is therefore a very particular period. The methods are based on experimental mathematics and algorithmic ideas in differential Galois theory, which I will show in the interactive part of the talk. The presentation is based on joint work with A. Bostan and J.-A. Weil.
  • Le 17 mai 2022 à 10:00
    • Séminaire de Théorie Algorithmique des Nombres
    -
    Daniel Fiorilli Université Paris Saclay
    Résultats de type oméga pour les comptages de corps cubiques
    Il s'agit d'un travail en collaboration avec P. Cho, Y. Lee et A. Södergren. Depuis les travaux de Davenport-Heilbronn, beaucoup d'articles ont été ecrits donnant des estimations de plus en plus précises sur le comptage du nombre de corps cubiques de discriminant au plus X. Mentionnons par exemple les travaux de Belabas, Belabas-Bhargava-Pomerance, Bhargava-Shankar-Tsimerman, Taniguchi-Thorne et Bhargava-Taniguchi-Thorne. Dans cet exposé je parlerai d'un résultat négatif, qui montre que l'hypothèse de Riemann implique une limitation sur la plus petite taille possible du terme d'erreur dans ces estimations. Nous approchons la questions à partir de la théorie des petits zéros de fonctions $L$, en particulier la philosophie de Katz-Sarnak et les articles subséquents pour la famille des fonctions zeta de Dedekind de corps cubiques. Je présenterai aussi des résultats numériques obtenus avec pari/gp et le programme «cubic» de Belabas qui indiquent que notre résultat pourrait être optimal.
  • Le 18 mai 2022 à 14:30
    • Séminaire de Théorie Algorithmique des Nombres
    -
    Wessel van Woerden CWI Amsterdam
    On the Lattice Isomorphism Problem, Quadratic Forms, Remarkable Lattices, and Cryptography
    A natural and recurring idea in the knapsack/lattice cryptography literature is to start from a lattice with remarkable decoding capability as your private key, and hide it somehow to make a public key. This is also how the code-based encryption scheme of McEliece (1978) proceeds.This idea has never worked out very well for lattices: ad-hoc approaches have been proposed, but they have been subject to ad-hoc attacks, using tricks beyond lattice reduction algorithms. On the other hand the framework offered by the Short Integer Solution (SIS) and Learning With Errors (LWE) problems, while convenient and well founded, remains frustrating from a coding perspective: the underlying decoding algorithms are rather trivial, with poor decoding performance.In this work, we provide generic realisations of this natural idea (independently of the chosen remarkable lattice) by basing cryptography on the Lattice Isomorphism Problem (LIP). More specifically, we provide:- a worst-case to average-case reduction for search-LIP and distinguish-LIP within an isomorphism class, by extending techniques of Haviv and Regev (SODA 2014).- a zero-knowledge proof of knowledge (ZKPoK) of an isomorphism. This implies an identification scheme based on search-LIP.- a key encapsulation mechanism (KEM) scheme and a hash-then-sign signature scheme, both based on distinguish-LIP.The purpose of this approach is for remarkable lattices to improve the security and performance of lattice-based cryptography. For example, decoding within poly-logarithmic factor from Minkowski's bound in a remarkable lattice would lead to a KEM resisting lattice attacks down to a poly-logarithmic approximation factor, provided that the dual lattice is also close to Minkowski's bound. Recent works have indeed reached such decoders for certain lattices (Chor-Rivest, Barnes-Sloan), but these do not perfectly fit our need as their duals have poor minimal distance.
  • Le 24 mai 2022 à 10:00
    • Séminaire de Théorie Algorithmique des Nombres
    -
    Alice Pellet-Mary CNRS/IMB
    Rigorous computation of class group and unit group
    Computing the class group and the unit group of a number field is a famous problem of algorithmic number theory. Recently, it has also become an important problem in cryptography, since it is used in multiple algorithms related to algebraic lattices.Subexponential time algorithms are known to solve this problem in any number fields, but they heavily rely on heuristics. The only non-heuristic (but still under ERH) known algorithm, due to Hafner and McCurley, is restricted to imaginary quadratic number fields.In this talk, we will see a rigorous subexponential time algorithm computing units and class group (and more generally S-units) in any number field, assuming the extended Riemann hypothesis.This is a joint work with Koen de Boer and Benjamin Wesolowski.
  • Le 31 mai 2022 à 10:00
    • Séminaire de Théorie Algorithmique des Nombres
    -
    Philippe Elbaz-Vincent Institut Fourier / Inria / IMB
    Sur quelques points, plus ou moins effectifs, de cohomologie des groupes arithmétiques
    Nous donnerons un panorama de certaines techniques et résultats pour le calcul de la cohomologie des groupes arithmétiques de rang $\ge 4$ pour des anneaux d'entiers algébriques, ainsi que leurs applications arithmétiques et K-théoriques. Nous ferons ensuite un focus sur les méthodes utilisant le modèle de Voronoi (euclidien ou hermitien), ainsi que plusieurs améliorations algorithmiques. Nous préciserons certains résultats relatifs aux complexes de Voronoi et leurs cellules (pour $\mathrm{GL}_N$ avec $N \geq 12$), ainsi qu'un travail en cours avec B. Allombert et R. Coulangeon sur les formes parfaites de rang $N$ sur $\mathcal{O}_K$ et la cohomologie de $\mathrm{GL}_N(\mathcal{O}_K)$ pour certains anneaux d'entiers avec $N=4,5,6$. Nous mentionnerons aussi plusieurs problèmes ouverts relatifs à ces modèles.
  • Le 14 juin 2022 à 10:00
    • Séminaire de Théorie Algorithmique des Nombres
    -
    Antoine Leudière Université de Lorraine
    An explicit CRS-like action with Drinfeld modules
    L'une des pierres angulaires de la cryptographie des isogénies est l'action (dite CRS), simplement transitive, du groupe des classes d'un ordre d'un corps quadratique imaginaire, sur un certain ensemble de classes d'isomorphismes de courbes elliptiques ordinaires.L'échange de clé non-interactif basé sur cette action (espace homogène difficile) est relativement lent (de Feo, Kieffer, Smith, 2019) ; la structure du groupe (Beullens, Kleinjung, Vercauteren, 2019) est difficile à calculer. Pour palier à cela, nous décrivons une action, simplement transitive, de la jacobienne d'une courbe hyperelliptique imaginaire, sur un certain ensemble de classes d'isomorphismes de modules de Drinfeld. Après avoir motivé l'utilisation des modules de Drinfeld en lieu et place des courbes elliptiques, nous décrirons un algorithme efficace de calcul de l'action, ainsi que la récente attaque de Benjamin Wesolowski sur l'échange de clé donné par l'action.
  • Le 28 juin 2022 à 10:00
    • Séminaire de Théorie Algorithmique des Nombres
    -
    Andreas Enge Inria/IMB
    Implementing fastECPP in CM
    FastECPP is currently the fastest approach to prove the primality of general numbers, and has the additional benefit of creating certificates that can be checked independently and with a lower complexity. It crucially relies on the explicit construction of elliptic curves with complex multiplication.I will take you on a leisurely stroll through the different phases of the ECPP and fastECPP algorithms, with explanations of their complexity. We will then see the algorithmic choices I have made when integrating a parallelised implementation of fastECPP into my CM software, which has recently been used to prove the primality of a number of record size 50000 digits
  • Le 12 juillet 2022 à 10:00
    • Séminaire de Théorie Algorithmique des Nombres
    -
    Michael Monagan Simon Fraser University
    Computing with polynomials over algebraic number fields
    Let $K = \mathbb{Q}(\alpha_1,\dots,\alpha_k)$ be an algebraic number field. We are interested in computing polynomial GCDs in $K[x]$ and $K[x_1,\dots,x_n]$. Of course we also want to multiply, divide and factor polynomials over $K$. In $K[x]$ we have the Euclidean algorithm but it "blows up"; there is a growth in the size of the rational numbers in the remainders. It is faster to compute the GCD modulo one or more primes and use the Chinese remainder theorem and rational number reconstruction. This leads to computing a GCD in $R[x]$ where $R = K \pmod p$ is usually not be a field; it is a finite ring.How do Computer Algebra Systems represent elements of $K$? How do Computer Algebra Systems compute GCDs in $K[x]$? What is the best way to do arithmetic in $R$? How can we compute a polynomial GCD in $K[x_1,\dots,x_n]$? In the talk we will try to answer these questions and we will present some timing benchmarks comparing our own C library for computing GCDs in $R[x]$ with Maple and Magma.
  • Le 13 septembre 2022 à 10:00
    • Séminaire de Théorie Algorithmique des Nombres
    -
    Damien Robert Inria/IMB
    Breaking SIDH in polynomial time
    SIDH/SIKE was a post quantum key exchange mechanism based on isogenies between supersingular elliptic curves which was recently selected in July 5 2022 by NIST to advance to the fourth round of the PQC competition. It was soon after broken during the summer in a series of three papers by Castryck-Decru, Maino-Martindale and myself.The attacks all use the extra information on the torsion points used for the key exchange. We first review Petit's dimension 1 torsion point attack from 2017 which could only apply to unbalanced parameters. Then we explain how the dimension 2 attacks of Maino-Martindale and especially Castryck-Decru could break in heuristic (but in practice very effective) polynomial time some parameters, including the NIST submission where the starting curve $E: y^2=x^3+x$ has explicit endomorphism $i$.Finally we explain how by going to dimension 8, we could break in proven quasi-linear time all parameters for SIKE.We will explain how the SIDH protocol worked at the beginning of the talk. We will see that the attack ultimately relies on a very simple 2x2 matrix computation! There will also be (hopefully) fun memes during the talk!
  • Le 20 septembre 2022 à 10:00
    • Séminaire de Théorie Algorithmique des Nombres
    -
    Fredrik Johansson Inria/IMB
    Faster computation of elementary functions
    Over a decade ago, Arnold Schönhage proposed a method to compute elementary functions (exp, log, sin, arctan, etc.) efficiently in "medium precision" (up to about 1000 digits) by reducing the argument using linear combinations of pairs of logarithms of primes or Gaussian primes. We generalize this approach to an arbitrary number of primes (which in practice may be 10-20 or more), using an efficient algorithm to solve the associated Diophantine approximation problem. Although theoretically slower than the arithmetic-geometric mean (AGM) by a logarithmic factor, this is now the fastest algorithm in practice to compute elementary functions from about 1000 digits up to millions of digits, giving roughly a factor-two speedup over previous methods. We also discuss the use of optimized Machin-like formulas for simultaneous computation of several logarithms or arctangents of rational numbers, which is required for precomputations.
  • Le 4 octobre 2022 à 10:00
    • Séminaire de Théorie Algorithmique des Nombres
    Pierrick Dartois\, Fabrice Etienne et Nicolas Sarkis null
    Présentation des nouveaux doctorants de l'équipe LFANT

  • Le 11 octobre 2022 à 10:00
    • Séminaire de Théorie Algorithmique des Nombres
    -
    Rémy Oudompheng -
    Computation of (3,3)-isogenies from a product of elliptic curves, in the style of 19th century geometry
    The method found by W. Castryck and T. Decru to break SIDH requires computing $(2^n,2^n)$-isogenies from a product of elliptic curves to another abelian surface (which is also a product), which are realized as degree 2 correspondences between curves.Transposing the attack to the other side of the SIDH exchange involves degree $(3,3)$-isogenies that can be evaluated using either theta functions, or divisors on genus 2 curves. Methods for the curve approach exist for the Jacobian case, but the case of a product of elliptic curves (Bröker, Howe, Lauter, Stevenhagen 2014) can be difficult to implement for cryptographically relevant field sizes due to various limitations in CAS such as SageMath/Singular.I will explain how traditional algebraic geometry can be called to the rescue to give a simple construction of the curve correspondence associated to the quotient of $E_1 \times E_2$ by an isotropic $(3,3)$-kernel. This leads to a rather fast computation method relying only on elementary field operations and 2 square roots. The journey will bring back some memories of 19th century projective geometry. Theta function experts might recognize familiar objects in the geometric construction.
  • Le 18 octobre 2022 à 10:00
    • Séminaire de Théorie Algorithmique des Nombres
    -
    Èrell Gachon -
    Some Easy Instances of Ideal-SVP and Implications on the Partial Vandermonde Knapsack Problem
    In our article, we generalize the works of Pan et al. (Eurocrypt 21) and Porter et al. (ArXiv 21) and provide a simple condition under which an ideal lattice defines an easy instance of the shortest vector problem. Namely, we show that the more automorphisms stabilize the ideal, the easier it is to find a short vector in it. This observation was already made for prime ideals in Galois fields, and we generalize it to any ideal (whose prime factors are not ramified) of any number field. We then provide a cryptographic application of this result by showing that particular instances of the partial Vandermonde knapsack problem, also known as partial Fourier recovery problem, can be solved classically in polynomial time.
  • Le 25 octobre 2022
    • Séminaire de Théorie Algorithmique des Nombres
    -
    Damien Robert Inria/IMB
    Evaluating isogenies in polylogarithmic time
    We explain how the « embedding lemma » used in the recents attacks against SIDH can be used constructively. Namely we show that every $N$-isogeny between abelian varieties over a finite field admits an efficient representation allowing for its evaluation in time polylogarithmic in $N$. Furthermore, using Vélu's formula for elliptic curves, or isogenies in the theta model for dimension $g>1$, this representation can be computed in time quasi-linear in $N^g$.
  • Le 8 novembre 2022 à 10:00
    • Séminaire de Théorie Algorithmique des Nombres
    -
    Anne-Edgar Wilke IMB
    Énumération des corps de nombres quartiques
    Fixons un entier $n \geq 2$, et, pour $X \geq 0$, soit $C_n(X)$ l'ensemble des classes d'isomorphisme de corps de nombres de degré $n$ et de discriminant inférieur à $X$ en valeur absolue. La méthode de Hunter-Pohst permet d'énumérer $C_n(X)$ en temps $O(X^{\frac{n + 2}{4} + epsilon})$. Pour $n \geq 3$, on s'attend à ce que cette complexité ne soit pas optimale : en effet, une conjecture classique, démontrée pour $n leq 5$, prévoit qu'il existe une constante $c_n \geq 0$ telle que le cardinal de $C_n(X)$ soit équivalent à $c_n X$. En utilisant une paramétrisation des corps cubiques due à Davenport et Heilbronn, Belabas a mis au point un algorithme énumérant $C_3(X)$ en temps optimal $O(X^{1 + \epsilon})$. Je montrerai comment une paramétrisation des corps quartiques due à Bhargava permet de manière similaire d'énumérer $C_4(X)$ en temps $O(X^{\frac{5}{4} + \epsilon})$. Je présenterai ensuite des résultats numériques, ainsi que des perspectives d'amélioration et de généralisation en degré supérieur.
  • Le 15 novembre 2022 à 10:00
    • Séminaire de Théorie Algorithmique des Nombres
    -
    Henri Cohen IMB
    A Pari/GP package for continued fractions
    I will describe with numerous examples a new Pari/GP package for infinite continued fractions which can in particular compute numerically the limit, the exact asymptotic speed of convergence (almost never given in the literature), accelerate continued fractions, and especially apply the powerful Apéry acceleration technique to almost all continued fractions, leading to hundreds of new ones.
  • Le 22 novembre 2022 à 10:00
    • Séminaire de Théorie Algorithmique des Nombres
    -
    Sulamithe Tsakou -
    Index calculus attacks on hyperelliptic curves with efficient endomorphism
    The security of many existing cryptographic systems relies on the difficulty of solving the discrete logarithm problem (DLP) in a group. For a generic group, we can solve this problem with many algorithms such as the baby-step-giant-step, the Pollard-rho or the Pohlig-Hellman algorithm. For a group with known structure, we use the index calculus algorithm to solve the discrete logarithm problem. Then, the DLP on the Jacobian of a hyperelliptic curve defined over a finite field $\mathbb{F}_{q^n}$ with $n >1$ are subject to index calculus attacks. After having chosen a convenient factor basis, the index calculus algorithm has three steps - the decomposition step in which we decompose a random point in the factor basis, the linear algebra step where we solve a matricial equation and the descent phase in which the discrete logarithm is deduced. The complexity of the algorithm crucially depends on the size of the factor basis, since this determines the probability for a point to be decomposed over the base and also the cost of the linear algebra step. Faugère et al (EC 2014) exploit the $2$-torsion point of the curve to reduce the size of the factor basis and then improve the complexity of the index calculus algorithm. In a similar manner, we exploit the endomorphism of the Jacobian to reduce the size of the factor base for certain families of ordinary elliptic curves and genus $2$ hyperelliptic Jacobians defined over finite fields. This approach adds an extra cost when performing operation on the factor basis, but our benchmarks show that reducing the size of the factor base allows to have a gain on the total complexity of index calculus algorithm with respect to the generic attacks.
  • Le 29 novembre 2022 à 10:00
    • Séminaire de Théorie Algorithmique des Nombres
    -
    Elie Bouscatié -
    Searching substrings inside an encrypted stream of data ... without decrypting !
    Outsourcing IT services has become very common worldwide for multiple reasons ranging from costs reduction to improved services. Whatever the actual reason is, the concrete consequence for the company that delegates such services is that a third party ends up with its data in clear because of the well-known limitations of standard encryption.Ideally, this third party should only learn the minimal information necessary for performing the requested processing, which has motivated the design of countless encryption schemes compatible with specific processing. Such schemes belong to the realm of functional encryption, where the third party recovers a function f(x) from an encryption of x without learning anything else about x, with minimal interaction. Of course, the function f, and hence the encryption scheme, strongly depends on the considered application, which explains the profusion of papers related to this topic. We will focus on the possibility to allow a third party to search the presence of chosen substrings of different lengths (and more !) at any position in the encryption of a stream of data. After an introduction to this problematic and to the associated security notion, we will take a look at the proof of security of one specific construction.
  • Le 6 décembre 2022 à 10:00
    • Séminaire de Théorie Algorithmique des Nombres
    -
    Léo Poyeton -
    Admissibility of filtered $(\varphi,N)$-modules
    Filtered $(\varphi,N)$-modules over a $p$-adic field $K$ are semi-linear objects which are easy to define and can be implemented on a computer. The modules $D_{st}(V)$ defined by $p$-adic Hodge theory, where $V$ is a $p$-adic representation of the absolute Galois group of $K$, provide examples of filtered $(varphi,N)$-modules. When $V$ is nice enough (semi-stable), the data of $D_{st}(V)$ is sufficient to recover $V$. A necessary and sufficient condition for a filtered $(\varphi,N)$-module $D$ to be written as $D_{st}(V)$ for some semi-stable representation $V$ is the condition of "admissibility" which imposes conditions on the way the different structures of the $(varphi,N)$-module interact with each other.In a joint work with Xavier Caruso, we try to provide an algorithm which takes a filtered $(\varphi,N)$-module as an input and outputs whether it is admissible or not. I will explain how we can implement filtered $(\varphi,N)$-modules on a computer and why this question is well posed. I will then present an algorithm which answers the question if the $(\varphi,N)$-module is nice enough and explain the difficulties we are facing both in this nice case and in the general case.
  • Le 13 décembre 2022 à 10:00
    • Séminaire de Théorie Algorithmique des Nombres
    -
    Samuel Le Fourn -
    Points de torsion d'une variété abélienne dans des extensions d'un corps fixé
    Pour une variété abélienne A sur un corps de nombres K, on sait que pour toute extension finie L/K, le nombre c(L) de points de torsion de A(L) est fini par le théorème de Mordell-Weil.
    En fait, un résultat de Masser prédit que c(L) est polynomial en [L:K] (si on fixe A et K) avec un exposant g=dim A, et une conjecture de Hindry et Ratazzi de 2012 donne l'exposant optimal (plus petit que g en général) en fonction d'une certaine structure de la variété abélienne (liée à son groupe dit de Mumford-Tate)Dans cet exposé, je parlerai d'un travail commun avec Lombardo et Zywina dans lequel nous démontrons une forme inconditionnelle de cette conjecture (et cette conjecture en admettant la conjecture de Mumford-Tate), en insistant sur les résultats intermédiaires qui peuvent être d'intérêt indépendant pour la compréhension des représentations galoisiennes associées à des variétés abéliennes.
  • Le 17 janvier 2023 à 10:00
    • Séminaire de Théorie Algorithmique des Nombres
    -
    Wouter Castryck -
    Radical isogeny formulas
    In several applications one is interested in a fast computation of the codomain curve of a long chain of cyclic $N$-isogenies emanating from an elliptic curve E over a finite field $\mathbb F_q$, where $N = 2, 3, \ldots$ is some small fixed integer coprime to $q$. The standard approach proceeds by finding a generator of the kernel of the first $N$-isogeny, computing its codomain via Vélu's formulas, then finding a generator of the kernel of the second $N$-isogeny, and so on. Finding these kernel generators is often the main bottleneck.In this talk I will explain a new approach to this problem, which was studied in joint work with Thomas Decru, Marc Houben and Frederik Vercauteren. We argue that Vélu's formulas can be augmented with explicit formulas for the coordinates of a generator of the kernel of an $N$-isogeny cyclically extending the previous isogeny. These formulas involve the extraction of an $N$-th root, therefore we call them "radical isogeny formulas". By varying which $N$-th root was chosen (i.e., by scaling the radical with different $N$-th roots of unity) one obtains the kernels of all possible such extensions. Asymptotically, in our main cases of interest this gives a speed-up by a factor 6 or 7 over previous methods.I will explain the existence of radical isogeny formulas, discuss methods to find them (the formulas become increasingly complicated for larger N), and pose some open questions.
  • Le 24 janvier 2023 à 10:00
    • Séminaire de Théorie Algorithmique des Nombres
    -
    Razvan Barbulescu CNRS/IMB
    The particular case of cyclotomic fields whencomputing unit groups by quantum algorithms
    The computation of unit and class groups in arbitrary degree number field is done in polynomial time in a similar fashion to the Shor's factoring algorithm. Contrary to the fixed degree case which was solved in 2001 by Hallgren and a follow-up paper of Schmidt and Vollmer (2005), the arbitrary degree case requires errors estimations and is solved by the conjunction of two papers, Eisenträger et al. (2014) and de Boer et al. (2020).In the particular case of cyclotomic fields we propose a version of the algorithm which makes use of cyclotomic units. Indeed, the Shor-like procedure of Eisenträger et al.'s algorithm produces random approximations of vectors in the dual of the lattice of units. In order to guarantee the correction of the algorithm, they have to do the computations in high precision and hence require a large amount of qubits. Thanks to the lattice of cyclotomic units, one can do the computations in smaller precision and reduce the number of qubits.
  • Le 31 janvier 2023 à 10:00
    • Séminaire de Théorie Algorithmique des Nombres
    -
    Wessel van Woerden IMB
    An Algorithmic Reduction Theory for Binary Codes, LLL and more
    We will discuss an adaptation of the algorithmic reduction theory of lattices to binary codes. This includes the celebrated LLL algorithm (Lenstra, Lenstra, Lovasz, 1982), as well as adaptations of associated algorithms such as the Nearest Plane Algorithm of Babai (1986). Interestingly, the adaptation of LLL to binary codes can be interpreted as an algorithmic version of the bound of Griesmer (1960) on the minimal distance of a code.
  • Le 7 février 2023 à 10:00
    • Séminaire de Théorie Algorithmique des Nombres
    -
    Andrea Lesavourey Irisa
    Calcul de racines de polynômes dans un corps de nombres
    Computing roots of elements is an important step when solving various tasks in computational number theory. It arises for example during the final step of the General Number Field Sieve~(Lenstra et al. 1993). This problem also intervenes during saturation processes while computing the class group or $S$-units of a number field (Biasse and Fieker). It is known from the seminal paper introducing the LLL algorithm that one can recover elements of a given number field $K$ given approximations of one of their complex embeddings. This can be used to compute roots of polynomials. In the first part of this presentation, I will describe an extension of this approach that take advantage of a potential subfield $k$, which replace the decoding of one element of $K$ by the decoding $[K:k]$ elements of $k$, to the cost of search in a set of cardinality $d^{[K:k]}$ where $d$ is the degree of the targetted polynomial equation. We will also describe heuristic observations that are useful to speed-up computations.In the second part of the presentation, we will describe methods to compute $e$-th roots specifically. When $K$ and $e$ are such that there are infinitely many prime integers $p$ such that $\forall mathfrak{p} \mid p, p^{f(\mathfrak{p}\mid p)} ot equiv1 \pmod e$, we reconstruct $x$ from $x \pmod {p_1}, dots, x \pmod {p_r} $ using a generalisation of Thomé's work on square-roots in the context of the NFS~(Thomé). When this good condition on $K$ and $n$ is not satisfied, one can adapt Couveignes' approach for square roots (Couveignes) to relative extensions of number fields $K/k$ provided $[K:k]$ is coprime to $e$ and infinitely many prime integers $p$ are such that each prime ideal $\mathfrak{p}$ of $\mathcal{O}_k$ above $p$ is inert in $K$.
  • Le 14 février 2023 à 10:00
    • Séminaire de Théorie Algorithmique des Nombres
    -
    Maxime Plançon IBM Zürich
    Exploiting algebraic structure in probing security
    The so-called $\omega$-encoding, introduced by Goudarzi, Joux and Rivain (Asiacrypt 2018), generalizes the commonly used arithmetic encoding. By using the additionnal structure of this encoding, they proposed a masked multiplication gadget (GJR) with quasilinear (randomness and operations) complexity. A second contribution by Goudarzi, Prest, Rivain and Vergnaud in this line of research appeared in TCHES 2021. The authors revisited the aforementioned multiplication gadget (GPRV), and brought the IOS security notion for refresh gadgets to allow secure composition between probing secure gadgets.In this paper, we propose a follow up on GPRV. Our contribution stems from a single Lemma, linking algebra and probing security for a wide class of circuits, further exploiting the algebraic structure of $\omega$-encoding. On the theoretical side, we weaken the IOS notion into the KIOS notion, and we weaken the usual $t$-probing security into the RTIK security. The composition Theorem that we obtain by plugging together KIOS, RTIK still achieves region-probing security for composition of circuits.To substantiate our weaker definitions, we also provide examples of competitively efficient gadgets verifying our weaker security notions. Explicitly, we give 1) a refresh gadget that uses $d-1$ random field elements to refresh a length $d$ encoding that is KIOS but not IOS, and 2) multiplication gadgets asymptotically subquadratic in both randomness and complexity. While our algorithms outperform the ISW masked compiler asymptotically, their security proofs require a bounded number of shares for a fixed base field.
  • Le 21 février 2023 à 10:00
    • Séminaire de Théorie Algorithmique des Nombres
    -
    Floris Vermeulen KU Leuven
    Arithmetic equivalence and successive minima
    Two number fields are said to be arithmetically equivalent if they have the same Dedekind zeta function. The central question about arithmetic equivalence is to determine how "similar" arithmetically equivalent number fields are. That is, we would like to determine which arithmetic invariants, such as the degree, discriminant, signature, units, class number, etc., are the same, and which ones can differ. A key result about arithmetic equivalence is Gassmann's theorem, which allows one to answer such questions using Galois theory and representation theory.I will give a general introduction to arithmetic equivalence, discussing some of the main results such as Gassmann's theorem and giving examples. I will then introduce the successive minima of a number field, and show that arithmetically equivalent number fields have approximately the same successive minima. "
  • Le 8 mars 2023 à 10:00
    • Séminaire de Théorie Algorithmique des Nombres
    -
    Ross Paterson University of Bristol
    Elliptic Curves over Galois Number Fields
    As E varies among elliptic curves defined over the rational numbers, a theorem of Bhargava and Shankar shows that the average rank of the Mordell-Weil group $E(\mathbb Q)$ is bounded. If we now fix a Galois number field K, how does the Mordell-Weil group E(K) behave on average as a Galois module? We will report on progress on this question, which is obtained by instead studying the associated p-Selmer groups of E/K as Galois modules.We construct some novel Selmer groups which describe certain invariants of these modules, and go on to study the behaviour of these new Selmer groups. This in turn allows us to give bounds for certain behaviour for the Mordell-Weil groups.
  • Le 14 mars 2023 à 10:00
    • Séminaire de Théorie Algorithmique des Nombres
    -
    Leonardo Colô Université Aix-Marseille
    Oriented Supersingular Elliptic Curves and Class Group Actions
    We recently defined an OSIDH protocol with Kohel (OSIDH) for oriented supersingular isogeny Diffie-Hellman by imposing the data of an orientation by an imaginary quadratic ring $\mathcal{O}$ on the category of supersingular elliptic curves. Starting with an elliptic curve $E_0$ oriented by a CM order $\mathcal{O}_K$ of class number one, we push forward the class group action along an $\ell$-isogeny chains, on which the class group of an order $\mathcal{O}$ of large index $\ell^n$ in $\mathcal{O}_K$ acts. The map from $\ell$-isogeny chains to its terminus forgets the structure of the orientation, and the original base curve $E_0$. For a sufficiently long random $ell$-isogeny chain, the terminal curve represents a generic supersingular elliptic curve.One of the advantages of working in this general framework is that the group action by $\mathrm{Cl}(\mathcal{O})$ can be carried out effectively solely on the sequence of moduli points (such as $j$-invariants) on a modular curve, thereby avoiding expensive generic isogeny computations or the requirement of rational torsion points.The proposed attacks of Onuki (2021) and Dartois-De Feo (2021) and their analyses motivate the idea of enlarging the class group without touching the key space using clouds. In this talk we propose two approaches to augment $\mathrm{Cl}(\mathcal{O}_n(M))$ in a way that no effective data is transmitted for a third party to compute cycle relations. In both cases, it comes down to an extension of the initial chain by the two parties separately. In particular, while the original OSIDH protocol made exclusive use of the class group action at split primes in $\mathcal{O}$, we extend the protocol to include descent in the eddies at non-split primes (inert or ramified) or at large primes which are not cost-effective for use for longer isogeny walks. "
  • Le 21 mars 2023 à 10:00
    • Séminaire de Théorie Algorithmique des Nombres
    -
    Mathieu Dutour Institute Rudjer Boskovic\, Croatia
    High dimensional computation of fundamental domains
    We have developed open-source software in C++ for computing with polyhedra, lattices, and related algebraic structures. We will shortly explain its design. Then we will explain how it was used for computing the dual structure of the $W(H_4)$ polytope.Then we will consider another application to finding the fundamental domain of cocompact subgroups $G$ of $\mathrm{SL}_n(\mathbb{R})$. The approach defines a cone associated with the group and a point $x\in \mathbb{R}^n$. It is a generalization of Venkov reduction theory for $\mathrm{GL}_n(\mathbb{Z})$. We recall the Poincaré Polyhedron Theorem which underlies these constructions.We give an iterative algorithm that allows computing a fundamental domain. The algorithm is based on linear programming, the Shortest Group Element (SGE) problem and combinatorics. We apply it to the Witte cocompact subgroup of $\mathrm{SL}_3(\mathbb{R})$ defined by Witte for the cubic ring of discriminant $49$.
  • Le 28 mars 2023 à 10:00
    • Séminaire de Théorie Algorithmique des Nombres
    -
    Shane Gibbons CWI\, Netherlands
    Hull attacks on the Lattice Isomorphism Problem
    The lattice isomorphism problem (LIP) asks one to find an isometry between two lattices. It has recently been proposed as a foundation for cryptography in independent works. This problem is the lattice variant of the code equivalence problem, on which the notion of the hull of a code can lead to devastating attacks. In this talk I will present the cryptanalytic role of an adaptation of the hull to the lattice setting, which we call the s-hull. Specifically, we show that the hull can be helpful for geometric attacks, for certain lattices the minimal distance of the hull is relatively smaller than that of the original lattice, and this can be exploited. The attack cost remains exponential, but the constant in the exponent is halved.
    Our results suggests that one should be very considerate about the geometry of hulls when instantiating LIP for cryptography. They also point to unimodular lattices as attractive options, as they are equal to their own hulls. Remarkably, this is already the case in proposed instantiations, namely the trivial lattice $\mathbb{Z}^n$ and the Barnes-Wall lattices.
  • Le 4 avril 2023 à 10:00
    • Séminaire de Théorie Algorithmique des Nombres
    -
    Jean Gillibert Université de Toulouse 2
    Finite subgroups of $mathrm{PGL}_2(mathbb{Q})$ and number fields with large class groups
    For each finite subgroup $G$ of $\mathrm{PGL}_2(\mathbb{Q})$, and for each integer $n$ coprime to $6$, we construct explicitly infinitely many Galois extensions of $\mathbb{Q}$ with group $G$ and whose ideal class group has $n$-rank at least $#G-1$. This gives new $n$-rank records for class groups of number fields.
  • Le 11 avril 2023 à 10:00
    • Séminaire de Théorie Algorithmique des Nombres
    -
    Henry Bambury ENS Ulm
    An inverse problem for isogeny volcanoes
    Supersingular isogeny graphs are very complicated and intricate, and are used extensively by cryptographers. On the other side of things, the structure of ordinary isogeny graphs is well understood connected components look like volcanoes. Throughout this talk we will explore the ordinary $\ell$-isogeny graph over $\mathbb{F}_p$ for various prime numbers $\ell$ and $p$, and answer the following question, given a volcano-shaped graph, can we always find an isogeny graph in which our volcano lives as a connected component?
  • Le 25 avril 2023 à 10:00
    • Séminaire de Théorie Algorithmique des Nombres
    online
    Alessandro Languasco University of Padova\, Italy
    Computing $L'(1,chi)/L(1,chi)$ using special functions, their reflection formulae and the Fast Fourier Transform
    We will show how to combine the Fast Fourier Transform algorithm with the reflection formulae of the special functions involved in the computation of the values of $L(1,chi)$ and $L'(1,chi)$, where $chi$ runs over the Dirichlet characters modulo an odd prime number $q$. In this way, we will be able to reduce the memory requirements and to improve the computational cost of the whole procedure. Several applications to number-theoretic problems will be mentioned, like the study of the distribution of the Euler-Kronecker constants for the cyclotomic field and its subfields, the behaviour of $min_{chie chi_0} | L'(1,chi)/L(1,chi) |$, the study of the Kummer ratio for the first factor of the class number of the cyclotomic field and the ``Landau vs. Ramanujan`` problem for divisor sums and coefficients of cusp forms. Towards the end of the seminar we will tackle open problems both of theoretical and implementative nature.
  • Le 2 mai 2023 à 10:00
    • Séminaire de Théorie Algorithmique des Nombres
    salle 2
    Sorina Ionica Université de Picardie
    Computing bad reduction for genus 3 curves with complex multiplication
    Goren and Lauter studied genus 2 curves whose Jacobians are absolutely simple and have complex multiplication (CM) by the ring of integers of a quartic CM-field, and showed that if such a curve has bad reduction to characteristic p then there is a solution to a certain embedding problem. An analogous formulation of the embedding problem for genus 3 does not suffice for explicitly computing all primes of bad reduction. We introduce a new problem called the Isogenous Embedding Problem (IEP), which we relate to the existence of primes of bad reduction. We propose an algorithm which computes effective solutions for this problem and exhibits a list of primes of bad reduction for genus 3 curves with CM. We ran this algorithm through different families of curves and were able to prove the reduction type of some particular curves at certain primes that were open cases in the literature.
  • Le 9 mai 2023 à 10:00
    • Séminaire de Théorie Algorithmique des Nombres
    salle 2
    Sabrina Kunzweiler IMB
    Isogeny-based PAKE protocols
    The passwords that we use in our everyday life are often chosen to be easily memorable which evidently makes them vulnerable to attacks. This problem is addressed by password-authenticated key exchange (PAKE). The general idea of such a protocol is to enable two parties who share the same (potentially weak) password to establish a strong session key. Most PAKE protocols used today are based on Diffie-Hellman key exchange in prime order groups, hence they are not secure against quantum attackers. A promising candidate for replacing Diffie-Hellman key exchange in a post-quantum world is the Commutative-Supersingular-Isogeny-Diffie-Hellman (CSIDH) key exchange. In this talk, we introduce two novel PAKE protocols based on CSIDH.
  • Le 16 mai 2023 à 10:00
    • Séminaire de Théorie Algorithmique des Nombres
    salle 2
    Wessel van Woerden IMB
    Perfect Quadratic Forms -- an Upper Bound and Challenges in Enumeration
    In 1908 Voronoi introduced an algorithm that solves the lattice packing problem in any dimension in finite time. Voronoi showed that any lattice with optimal packing density must correspond to a so- called perfect (quadratic) form and his algorithm enumerates the finitely many perfect forms up to similarity in a fixed dimension. However, the number of non-similar perfect forms and the comlexity of the algorithm grows quickly in the dimension and as a result Voronoi’s algorithm has only been completely executed up to dimension 8. We discuss an upper bound on the number of perfect forms and the challenges that arise for completing Voronoi's algorithm in dimension 9.
  • Le 23 mai 2023 à 10:00
    • Séminaire de Théorie Algorithmique des Nombres
    bâtiment Inria, salle Sophie Germain (304)
    Boris Fuoutsa EPFL\, Switzerland
    Beyond the SIDH Countermeasures
    During summer 2022, a series of three cryptanalysis papers lead to a
    polynomial time attack on SIKE, which was in the fourth round of the NIST
    standardisation process. In a recent work, we explored countermeasures
    avenue to the SIDH attacks, M-SIDH and MD-SIDH.
    These countermeasures, despite being slow and less compact (when compared
    to SIDH and other post-quantum schemes), come with new insights that may be
    of independent interest. In this talk, we will discuss an on-going work in
    which we use M-SIDH together with the SIDH attacks to design a trapdoor one
    way function. This trapdoor one way function can be leveraged to obtain a
    public key encryption scheme, most importantly, it can be used to design an
    Identity Based Encryption scheme. The main drawback is that the design is
    purely theoretical at the moment, since inverting the one way function
    requires computing isogenies in higher dimension of prime degree up to
    5000 or even higher.


  • Le 30 mai 2023 à 10:00
    • Séminaire de Théorie Algorithmique des Nombres
    salle 2
    Sarah Arpin University of Leiden\, Netherlands
    Adding Level Structure to Supersingular Elliptic Curve Isogeny Graphs
    The classical Deuring correspondence provides a roadmap between supersingular elliptic curves and the maximal orders which are isomorphic to their endomorphism rings. Building on this idea, we add the information of a cyclic subgroup of prime order N to supersingular elliptic curves, and prove a generalisation of the Deuring correspondence for these objects. We also study the resulting ell-isogeny graphs supersingular elliptic curve with level-N structure, and the corresponding graphs in the realm of quaternion algebras. The structure of the supersingular elliptic curve ell-isogeny graph underlies the security of a new zero-knowledge proof of isogeny knowledge.



  • Le 6 juin 2023 à 10:00
    • Séminaire de Théorie Algorithmique des Nombres
    salle 2
    Daan van Gent (University of Leinden\, Netherlands
    The Closest Vector Problem for the lattice of algebraic integers
    Any number field comes with a natural inner product as in the theory of the geometry of numbers, so that any order becomes a lattice.
    We extend the definition of the inner product to $\overline{\mathbb{Q}}$, the algebraic closure of the rationals, and consider its maximal order $\overline{\mathbb{Z}}$, which has infinite rank, as an intrinsically interesting `lattice'.
    We will compute several lattice invariants and attempt to solve the Closest Vector Problem through proofs inspired by capacity theory.
    Adjacent to CVP is the problem of finding the Voronoi-relevant vectors, and we pose the challenge to compute all such vectors of degree 3.

  • Le 13 juin 2023 à 10:00
    • Séminaire de Théorie Algorithmique des Nombres
    salle 2
    Mahshid Riahinia ENS de Lyon
    Constrained Pseudorandom Functions from Homomorphic Secret Sharing
    A Constrained pseudorandom function (CPRF) is a pseudorandom function that provides fine-grained access to the evaluation of the function. In other words, for a (possibly super-polynomial) subset of inputs, a constrained pseudorandom function allows us to derive a constrained key that enables evaluating the function on that subset of inputs while learning nothing beyond. We propose and analyze a simple strategy for constructing 1-key constrained pseudorandom functions from homomorphic secret sharing (HSS) protocols. This relation, in particular, leads to instantiations of CPRFs for various constraints and from various assumptions. In this talk, I present this strategy and briefly go over one of the instantiations.
  • Le 20 juin 2023 à 10:30
    • Séminaire de Théorie Algorithmique des Nombres
    INRIA building, room George Bool 2
    Canari team INRIA
    Meeting Canari team and Inria Bordeaux head team
    The LFANT seminar is canceled. Instead, there will be a recurrent meeting between the team members and the administrative direction. The meeting is not compulsory for the PdD students.



  • Le 27 juin 2023 à 10:00
    • Séminaire de Théorie Algorithmique des Nombres
    salle 1
    Agathe Houzelot Labri
    White-Box Implementations of ECDSA
    Cryptographic algorithms are primarily designed to be secure in the black-box model, where an attacker can only observe their input/output behavior. However
    in practice, algorithms are rarely executed in a completely isolated environment
    and additional information is often leaked. In the context of mobile applications or connected objects, devices often lack secure storage to protect secret keys, and their generally open execution environment exposes a large attack surface. This hostile environment is captured by the white-box attack model.
    While many white-box implementation of block ciphers have been published since 2002, asymmetric cryptosystems have been very little studied. In my PhD thesis, we got interested in white-box implementations of ECDSA. This led us to participate in the WhibOx Contest that was organized as part of the TCHES workshops in 2021. During three months, developpers were invited to submit ECDSA white-box implementations and attackers to try to break them.
    In this talk, I will introduce the white-box model before explaining the specificities of the ECDSA algorithm in this context. I will then present the different attacks that we used to break almost all the challenges of the WhibOx Contest.

  • Le 12 septembre 2023 à 11:00
    • Séminaire de Théorie Algorithmique des Nombres
    salle 2
    Pierrick Dartois IMB
    SQISignHD : Signing with higher dimensional isogenies.
    The SQISign isogeny-based post-quantum digital signature scheme introduced by De Feo, Kohel, Leroux, Petit and Wesolowski outputs very compact signatures at the expense of a high signature time. In this presentation, we recall how SQISign works and introduce a new scheme based on SQISign and the polynomial time torsion point attacks against SIDH due to Castryck, Decru, Maino, Martindale and Robert to sign with higher dimensional isogenies. This scheme remains to be implemented but we expect a significant signature time improvement, better security properties and signatures even more compact than in the original SQISign scheme.
  • Le 19 septembre 2023 à 11:00
    • Séminaire de Théorie Algorithmique des Nombres
    salle 2
    Xavier Caruso IMB
    Drinfeld modules in SageMath
    In this talk, I will briefly introduce Drinfeld modules which, in some sense, appears as a arithmetically meaningful analogue of elliptic curves in the context of function fields. I will then discuss an implementation of Drinfeld modules which was recently included in SageMath. (Joint work with David Ayotte, Antoine Leudière and Joseph Musleh.)
  • Le 26 septembre 2023 à 11:00
    • Séminaire de Théorie Algorithmique des Nombres
    salle 2
    Joël Felderhoff ENS Lyon
    Ideal-SVP is Hard for Small-Norm Uniform Prime Ideals
    The presumed hardness of the Shortest Vector Problem for ideal lattices (Ideal-SVP) has been a fruitful assumption to understand other assumptions on algebraic lattices and as a security foundation of cryptosystems. Gentry [CRYPTO’10] proved that Ideal-SVP enjoys a worst-case to average-case reduction, where the average-case distribution is the uniform distribution over the set of inverses of prime ideals of small algebraic norm (below d^O(d) for cyclotomic fields, where d refers to the field degree). De Boer et al. [CRYPTO’20] btained another random self-reducibility result for an average-case distribution involving integral ideals of norm 2^O(d^2). In this work, we show that Ideal-SVP for the uniform distribution over inverses of small-norm prime ideals reduces to Ideal-SVP for the uniform distribution over small-norm prime ideals. Combined with Gentry’s reduction, this leads to a worst-case to average-case reduction for the uniform distribution over the set of small-norm prime ideals. Using the reduction from Pellet-Mary and Stehlé [ASIACRYPT’21], this notably leads to the first distribution over NTRU instances with a polynomial modulus whose hardness is supported by a worst-case lattice problem.
  • Le 3 octobre 2023 à 11:00
    • Séminaire de Théorie Algorithmique des Nombres
    salle 2
    Jean Gasnier IMB
    An Algebraic Point of View on the Generation of Pairing-Friendly Elliptic Curves
    In 2010, Freeman, Scott, and Teske published a well-known taxonomy compiling the
    best known families of pairing-friendly elliptic curves. Since then, the
    research effort mostly shifted from the generation of pairing-friendly curves to
    the improvement of algorithms or the assessment of security parameters to resist
    the latest attacks on the discrete logarithm problem. Consequently, very few new
    families were discovered. However, the need of pairing-friendly curves of prime
    order in some new applications such as SNARKs has reignited the interest in the
    generation of pairing-friendly curves, with hope of finding families similar to
    the one discovered by Barreto and Naehrig.
    Building on the work of Kachisa, Schaefer, and Scott, we show that some elements
    of extensions of a cyclotomic field have a higher probability of generating a
    family of pairing-friendly curves. We present a general framework which embraces
    the KSS families and many of the other families in the taxonomy paper. We finally
    introduce a new family with embedding degree k=20 which we estimate to provide
    a faster Miller loop compared to KSS16 and KSS18 at the 192-bit security level.
  • Le 10 octobre 2023 à 11:00
    • Séminaire de Théorie Algorithmique des Nombres
    salle 2
    Wouter Rozendaal IMB
    A Renormalisation Decoder for Kitaev's Toric Quantum Code
    Kitaev's toric code is expected to be at the core of the first generation of quantum computers that will incorporate error protection. To make full use of the toric code, one requires an efficient decoding scheme that will process the classical information obtained from quantum syndrome measurements, so as to be able to regularly put arrays of qubits back into their intended states. The renormalisation decoders introduced by Duclos-Cianci and Poulin exhibit one of the best trade-offs between efficiency and speed. One feature that remained a mystery however, is their behaviour over adversarial channels, i.e. their worst-case behaviour. In this talk, we introduce a relatively natural and deterministic version of a renormalisation decoder and bound its error-correcting radius.
  • Le 24 octobre 2023 à 11:00
    • Séminaire de Théorie Algorithmique des Nombres
    salle 2
    Donghyeok Lim Korea
    On the Galois structure of units of totally real $p$-rational fields
    The Galois module structure of algebraic units is fundamental in number theory. However, its investigation is difficult because we need to understand arithmetic of number fields, and the integral representations of finite groups are difficult to classify. A number field is called $p$-rational if the Galois group of the maximal pro-$p$ $p$-ramified extension is free pro-$p$. The $p$-rationality is known to be a condition that reduces the complexities in problems in number theory. In this talk, we explain our results on the implication of the existing theories on integral representations of finite groups (factor equivalence, regulator constant, Yakovlev diagram) on the algebraic units of totally real $p$-rational fields. This talk is based on the joint works with Z. Bouazzaoui, D. Burns, A. Kumon, and C. Maire.
  • Le 7 novembre 2023 à 11:00
    • Séminaire de Théorie Algorithmique des Nombres
    salle 2
    Maxime Bombar CWI
    Pseudorandom Correlation Generators from the Hardness of Decoding Codes over Group Algebras
    The main bottleneck of secure multiparty computation is the cost of the communication between all the parties. Nevertheless, it is known for a long time that if prior to the actual MPC protocol, all the parties share random field elements having a useful correlation such as random multiplication triples, or the so-called random Oblivious Linear Evaluations (OLE's), the parties can engage in a very efficient protocol. The goal is therefore to generate this large amount of correlated randomness. To achieve this goal, Boyle et al. recently introduced a new tool which they called "Pseudorandom Correlation Generators" (PCG's) and demonstrated how it can be used to generate and distribute a large amount of (pseudo)random OLE's to two parties, using minimal interactions, followed solely by local computations. This enables secure two-party computation with "silent preprocessing", which can be extended to N-party using "programmable" PCG's.

    Previous constructions of programmable PCG's for OLE's suffer from two downsides: (1) They only generate OLE's over large fields, and (2) They rely on a rather recent "splittable Ring-LPN" assumption which lacks from strong security foundations.

    In this talk, I will present a way to overcome both limitation by introducing the "Quasi-Abelian Decoding Problem" which generalises the well-known decoding problem of quasi-cyclic codes, and show how its hardness allows to build programmable PCG's for the OLE correlation over any field Fq (with q>2).

    Finally, if time permits, I will evoke some ideas towards the q=2 case, which involves some elements from the theory of Carlitz modules over F2(T).

    This is based on a joint work with Geoffroy Couteau, Alain Couvreur and Clément Ducros
  • Le 14 novembre 2023 à 11:00
    • Séminaire de Théorie Algorithmique des Nombres
    salle 2
    Stefano Marseglia Utrecht University
    Computing isomorphism classes and polarisations of abelian varieties over finite fields
    We consider abelian varieties over a finite field which are ordinary, or over a prime field, and which have commutative endomorphism algebra.
    Works of Deligne and Centeleghe-Stix allow us to describe these abelian varieties in terms of fractional ideals of an order in an étale algebra. I will explain how such descriptions can be exploited to explictly compute the abelian varieties up to isomorphism.
    Moreover, results by Howe give us a way to compute principal polarisations of the abelian varieties in the ordinary case. In a joint work with Bergström and Karemaker we extend these results to the prime field case.
  • Le 21 novembre 2023 à 11:00
    • Séminaire de Théorie Algorithmique des Nombres
    salle 2
    Lorenzo Furio University of Pisa
    Galois representations attached to elliptic curves and Serre's uniformity question
    The study of Galois representations attached to elliptic curves is a very fruitful branch of number theory, which led to the solution of very tough problems, such as Fermat's Last Theorem. Given a rational elliptic curve E, the representation \rho_{E,p} is described by the action of the absolute Galois group of \mathbb{Q} on the p-torsion points of E. In 1972 Serre proved that for every rational elliptic curve E without CM there is a constant N_E such that, for every prime p>N_E, the Galois representation \rho_{E,p} is surjective. In the same article, he asked whether the constant N_E is independent of the curve, and this became known as Serre's Uniformity Question. In this talk, I will discuss the current progress towards the answer to this question, in particular the Runge method for modular curves, developed by Bilu and Parent, and the recent improvements obtained via this method by Le Fourn--Lemos and Lombardo and the speaker.
  • Le 28 novembre 2023 à 11:00
    • Séminaire de Théorie Algorithmique des Nombres
    salle 2
    Monika Trimoska Eindhoven University of Technology
    Disorientation faults in CSIDH
    In this work, we investigate a new class of fault-injection attacks against the CSIDH family of cryptographic group actions. Our disorientation attacks effectively flip the direction of some isogeny steps, resulting in an incorrect output curve. The placement of the disorientation fault during the algorithm influences the distribution of the output curve in a key-dependent manner. We explain how an attacker can post-process a set of faulty outputs to fully recover the private key. We provide full details for attacking the original CSIDH proof-of-concept software as well as the CTIDH constant-time implementation. Finally, we present a set of lightweight countermeasures against the attack and discuss their security. This presentation will focus on analysing the graph of faulty curves formed in the post-processing stage and getting an intuition on how it can be used to infer constraints on the secret key. This is joint work with Gustavo Banegas, Juliane Krämer, Tanja Lange, Michael Meyer, Lorenz Panny, Krijn Reijnders and Jana Sotáková.
  • Le 5 décembre 2023 à 11:00
    • Séminaire de Théorie Algorithmique des Nombres
    salle 2
    Yining HU Harbin Institut of Technology\, China
    Automatic algebraic continued fractions in characteristic 2
    In this talk I will first introduce automatic sequences and their
    link with algebraicity. Then I will present two families of
    automatic algebraic continued fractions in characteristic 2.
  • Le 12 décembre 2023 à 11:00
    • Séminaire de Théorie Algorithmique des Nombres
    salle 2
    Nicolas Sarkis IMB
    Computing 2-isogenies between Kummer lines
    One of the best arithmetics on elliptic curves involves Montgomery xz-coordinates, which are used in several cryptographic protocols such as ECDSA or ECDH. These coordinates also offer fast computations of 2- and 4-isogenies, used in several protocols like it was the case with SIDH, both for doubling and images of points, so improving isogeny formulas also improves scalar products on an elliptic curve. We realized there was a more general theory of Kummer lines under which xz-coordinates fall.

    In this talk, we will describe the general framework of Kummer lines, based on two families of examples: Montgomery xz-coordinates and theta models. We will then explain how to find 2-isogeny formulas, whether they were already known or new, and how we mixed them to improve elliptic curve arithmetic.
  • Le 19 décembre 2023 à 11:00
    • Séminaire de Théorie Algorithmique des Nombres
    salle 2
    Marc Houben Leiden University Netherlands
    Pairings, class groups, and how (not) to break isogeny-based cryptography
    Maps between elliptic curves, also called isogenies, are fixed once the image on sufficiently many points is known. Last year, a method was discovered that computationally recovers isogenies just by knowing information about their image points, leading to the break of the key-exchange scheme SIDH. Isogeny-based key-exchange proposals relying on class group actions, such as CSIDH, remain unaffected, because such image information is not directly available. Using the theory of pairings on elliptic curves, we show that sometimes one may recover such information anyway, and classify when this approach results in a key-recovery attack.
  • Le 16 janvier 2024 à 11:00
    • Séminaire de Théorie Algorithmique des Nombres
    salle 2
    Jean-Marc Couveignes IMB
    Effective aspects of Riemann-Roch spaces in the Hilbert class field
    Let $K$ be a finite field, $X$ and $Y$ two
    curves over $K$, and $Y\rightarrow X$ an unramified abelian
    cover with Galois group $G$. Let $D$ be a divisor on $X$
    and $E$ its pullback on $Y$. Under mild conditions the linear space
    associated with $E$ is a free $K[G]$-module. We study the
    algorithmic aspects and applications of these modules.
  • Le 23 janvier 2024 à 11:00
    • Séminaire de Théorie Algorithmique des Nombres
    salle 2
    Vincent Neiger Sorbonne Université
    Faster modular composition of polynomials
    This talk is about algorithms for modular composition of univariate
    polynomials, and for computing minimal polynomials. For two univariate
    polynomials a and g over a commutative field, modular composition asks to
    compute h(a) mod g for some given h, while the minimal polynomial problem is
    to compute h of minimal degree such that h(a) = 0 mod g. We propose algorithms
    whose complexity bound improves upon previous algorithms and in particular upon
    Brent and Kung's approach (1978); the new complexity bound is subquadratic in
    the degree of g and a even when using cubic-time matrix multiplication. Our
    improvement comes from the fast computation of specific bases of bivariate
    ideals,
    and from efficient operations with these bases thanks to fast univariate
    polynomial
    matrix algorithms. We will also report on experimental results using the
    Polynomial Matrix Library.

    Contains joint work with Seung Gyu Hyun, Bruno Salvy, Eric Schost, Gilles
    Villard.
  • Le 30 janvier 2024 à 11:00
    • Séminaire de Théorie Algorithmique des Nombres
    salle 2
    Thomas Decru Brussels\, Belgium
    Algorithmic aspects of isogeny-based cryptography
    One of the main struggles of isogeny-based cryptographic protocols is that they are still relatively slow compared to other post-quantum candidate schemes. In this talk we will provide some info on why this is, and elaborate on some of the recent results and ongoing work in this direction.
  • Le 6 février 2024 à 11:00
    • Séminaire de Théorie Algorithmique des Nombres
    salle 2
    Christophe Levrat Télécom Paris
    l-adic point counting on surfaces: nearly almost halfway there?
    While point counting algorithms on algebraic curves over finite fields have been around for decades and seen considerable progress in the meantime, the question of counting points on algebraic surfaces without additional structure seems much more challenging. In this talk, we will present results concerning the classical l-adic method for surfaces fibered over the projective line, which was conjectured by Edixhoven and Couveignes to admit a polynomial-time complexity. This method boils down to computing the étale cohomology of a constructible sheaf: we will describe how to compute this cohomology once such a sheaf has been given, and outline a possible strategy that might allow to compute a usable description of this particular sheaf.
  • Le 13 février 2024 à 11:00
    • Séminaire de Théorie Algorithmique des Nombres
    zoom 87807228123
    Semyon Novoselov University of Kaliningrad
    Approx-SVP in multiquadratic ideal lattices
    Multiquadratic fields are exceptional objects in computational number theory. Many hard computational problems are significantly simpler there. This includes unit/class group and discrete logarithm computations, as well as computing short generators of principal ideals. However, there are still many open questions in the area. In this talk, I describe recent progress towards the next milestone -- the approximate shortest vector problem in non-principal ideal lattices. In particular, I present an algorithm for a central subroutine -- the discrete logarithm computation based on reduction of the problem to subfields
  • Le 20 février 2024 à 11:00
    • Séminaire de Théorie Algorithmique des Nombres
    salle 2
    Florette Martinez Lip6
    Discussion autour du Générateur Sac à dos
    Le Générateur Sac à dos, proposé en 1985 par Rueppel et Massey est un
    générateur pseudo aléatoire (PRNG) qui combine un premier PRNG faible, le
    LFSR, et un problème dur ,le problème de la somme de sous-ensemble, dérivé du
    problème de sac à dos.
    Ce générateur a été attaqué avec succès par Knellwolf et Meyer en 2011. Je
    discuterais ici d'une variante plus efficace de ctette attaque et des différentes
    attaques que j'ai pu proposer avec Damien Vergnaud et Charles contre des
    variantes de ce générateur.
  • Le 27 février 2024 à 11:00
    • Séminaire de Théorie Algorithmique des Nombres
    salle 2
    Pierre Briaud Inria Paris
    Variants of the Decoding Problem and algebraic cryptanalysis
    The intractability of decoding generic linear codes is at the core of an important branch of post-quantum cryptography.
    In this context, the code is random by design or it is assumed to be so in the security reduction.

    This talk will focus on versions of the Decoding Problem where the error vector is structured, in general to achieve better performance.
    While combinatorial techniques such as Information Set Decoding are often the method of choice to attack these versions, I will describe the potential of algebraic algorithms.

    I will mostly consider the Regular Syndrome Decoding Problem and a paper presented at Eurocrypt 2023.
    I will also mention ongoing work on an assumption used in the CROSS submission to new call for signature schemes launched by NIST.
  • Le 5 mars 2024 à 11:00
    • Séminaire de Théorie Algorithmique des Nombres
    salle 2
    Yuri Bilu IMB
    Skolem meets Schanuel
    A linear recurrence of order~$r$ over a number field~$K$ is a map ${U:\mathbb{Z}\to K}$ satisfying a relation of the form
    $$
    U(n+r)=a_{r-1}U(n1)+ \cdots+ a_0U(n) \qquad (n\in \mathbb{Z}),
    $$
    where ${a_0, \ldots, a_{r-1}\in K}$ and ${a_0e 0}$. A linear recurrence is called simple if the characteristic polynomial ${X^r-a_{r-1}X^{r-1}-\ldots- a_0}$ has only simple roots, and non-degenerate if ${\lambda/\lambda'}$ is not a root of unity for any two distinct roots $\lambda, \lambda'$ of the characteristic polynomial. The classical Theorem of Skolem-Mahler-Lech asserts that a non-degenerate linear recurrence may have at most finitely many zeros. However, all known proofs of this theorem are non-effective and do not produce any tool to determine the zeros.


    In this talk I will describe a simple algorithm that, when terminates, produces the rigorously certified list of zeros of a given simple linear recurrence. This algorithm always terminates subject to two celebrated conjectures: the $p$-adic Schanuel Conjecture, and the Exponential Local-Global Principle. We do not give any running time bound (even conditional to some conjectures), but the algorithm performs well in practice, and was implemented in the \textit{Skolem tool}
    $$
    \text{https://skolem.mpi-sws.org/}
    $$
    that I will demonstrate. This is a joint work with Florian Luca, Joris Nieuwveld, Joël Ouaknine, David Purser and James Worrell.
  • Le 12 mars 2024 à 11:00
    • Séminaire de Théorie Algorithmique des Nombres
    salle 2
    Olivier Ruatta Université de Limoges
    Polynômes linéarisés et cryptographie en métrique rang
    Le lien entre polynômes linéarisés et codes en métrique rang est connu depuis longtemps puisque les codes de Gabidulin peuvent être vu comme codes d’évaluation de certains de ces polynômes. Nous donnerons d’autres constructions et verrons comment la “géométrisation” des corps finis grâce aux polynômes linéarisés permet de fournir des problèmes qui pourraient être appliqués dans des contextes cryptographiques.
  • Le 19 mars 2024 à 11:00
    • Séminaire de Théorie Algorithmique des Nombres
    salle 2
    Rocco Mora CISPA
    A new approach based on quadratic forms to attack the McEliece cryptosystem
    In this talk, I will present a novel algebraic approach for attacking the McEliece cryptosystem which is currently at the 4-th round of the NIST post-quantum standardization process. The contributions are twofold.
    (1) A new distinguisher on alternant and Goppa codes working in a much broader range of parameters than previous distinguishers is introduced and its complexity analysed;
    (2) With this approach, a polynomial-time key recovery attack on alternant and Goppa codes of high-rate and under some conditions on their field size and degree is also provided.
  • Le 26 mars 2024 à 11:00
    • Séminaire de Théorie Algorithmique des Nombres
    salle 2
    Bastien Pacifico LIRMM
    From Chudnovsky-type algorithms to locally recoverable codes
    Chudnovsky's method makes it possible to construct multiplication algorithms in finite fields with good bilinear complexity, i.e. a small number of bilinear multiplications in the base field. However, their total complexity and the difficulty of efficiently constructing these algorithms are unfavorable.

    Historically, these are evaluation/interpolation algorithms using rational points of algebraic curves/rational places of function fields. Using asymptotically optimal towers, the existence of algorithms with bilinear complexity that is linear in the degree of extension has been proven. But these algorithms are not constructible in polynomial time.
    Another approach is a recursive construction using places of increasing degrees. It provides algorithms with a quasi-linear bilinear complexity, but constructible in polynomial time.

    We will introduce a hybrid construction, taking the best of both strategies to obtain algorithms with linear bilinear complexity that can be constructed in polynomial time.

    Secondly, we will see that some locally recoverable codes, where the recovery of a corrupted symbol is possible using a small amount of other symbols, appear naturally in the recursive construction of Chudnovsky-type algorithms. We will define and study these codes.
  • Le 2 avril 2024 à 11:00
    • Séminaire de Théorie Algorithmique des Nombres
    salle 2
    Dmitrii Koshelev supported by Ethereum Foundation
    Generation of "independent" points on elliptic curves by means of Mordell-Weil lattices
    This talk is devoted to a novel method of generating "independent" points on an ordinary elliptic curve over a finite field of large characteristic. Such points are actively used, e.g., in the Pedersen vector commitment scheme and its modifications. The conventional generation consists in sampling points successively via a hash function to the elliptic curve. The new generation method equally satisfies the NUMS (Nothing Up My Sleeve) principle, but it works faster on average. In other words, instead of finding each point separately, it is suggested to sample several points at once with a non-small success probability. This means that in practice the new method finishes in polynomial time, unless one is mysteriously unlucky. More precisely, some explicit formulas participate in deriving up to four "independent" points on any curve of j-invariant 0. Such curves are known to be very popular in elliptic curve cryptography.
  • Le 9 avril 2024 à 11:00
    • Séminaire de Théorie Algorithmique des Nombres
    salle 2
    Simona Etinski CWI
    Asymptotics and Improvements of Sieving for Codes
    In this talk, I am going to present a joint work with Léo Ducas, Andre Esser, and Elena Kirshanova on sieving for codes. In this work, we provide an asymptotic analysis of the sieving for codes originally introduced in the paper by Guo, Johansson, and Nguyen (Eprint’23), after which we rely on a well-established lattice-based NNS machinery, known as Locality Sensitive Hashing and Filtering (LSH/F), to obtain a more systematic analysis of the sieving for codes. We thus introduce a baseline for the sieving approach for codes with a decoding complexity of 2^0.117n for the conventional worst parameters (full distance decoding, where complexity is maximized over all code rates). Our cumulative improvements eventually enable us to lower the hardest parameter decoding complexity for SievingISD algorithms to 2^0.101n. This approach outperforms the BJMM algorithm (Eurocrypt’12) but falls behind the most advanced conventional ISD approach by Both and May (PQCrypto’18). As in the case of lattices, we found that the Random-Spherical-Code-Product (RPC) gives the best asymptotic complexity. Moreover, we consider an alternative that seems specific to the Hamming Sphere, which we believe could be of practical interest as it plausibly hides less sub-exponential overheads than RPC. For more details, refer to the full version of the paper given at https://eprint.iacr.org/2023/1577.
  • Le 16 avril 2024 à 11:00
    • Séminaire de Théorie Algorithmique des Nombres
    salle 2
    Fabrice Etienne IMB
    Computing Class Groups With an Inductive Algorithm
    In this talk, first, I will present a method by Biasse, Fieker, Hoffman and Page to compute the class group of some number fields inductively. This method uses the properties of norm relations, which are some relations in R[G] where R is a commutative ring and G a finite group. Then, I will discuss about how we can generalise the notion of norm relations and use this new kind of relations to obtain a similar method for computing class groups, that is more effective than the previous one.
  • Le 30 avril 2024 à 11:00
    • Séminaire de Théorie Algorithmique des Nombres
    salle 2
    Lars Ran Radboud University
    Analysing multi-graded polynomial systems; a step towards more precise security estimations

    Generally, polynomial systems that arise in algebraic cryptanalysis have extra structure compared to generic systems, which comes from the algebraic modelling of the cryptographic scheme. Sometimes, part of this extra structure can be caught with polynomial rings with non-standard grading. For example, in the Kipnis-Shamir modelling of MinRank one considers the system over a bi-graded polynomial ring instead. This allows for better approximations of the solving degree of such systems when using Gröbner basis algorithms.

    In this talk, I will present ongoing work in which this idea is extended to multi-graded polynomial rings. Furthermore, I will show how we can use this grading to tailor existing algorithms to use this structure and speed up computation. 


  • Le 7 mai 2024 à 11:00
    • Séminaire de Théorie Algorithmique des Nombres
    salle 2
    Félix Huber Labri
    TBA

  • Le 14 mai 2024 à 11:00
    • Séminaire de Théorie Algorithmique des Nombres
    salle 2
    Oana Padurariu Max-Planck-Institut für Mathematik Bonn
    Bielliptic Shimura curves $X_0^D(N)$ with nontrivial level
    In this talk, I explain how we work towards completely classifying all bielliptic Shimura curves X_0^D(N) with nontrivial level N, extending a result of Rotger that provided such a classification for level one. This allows us to determine the list of all pairs (D,N) for which X_0^D(N) has infinitely many degree 2 points, up to 3 explicit possible exceptions. This is joint work with Frederick Saia.
  • Le 28 mai 2024 à 11:00
    • Séminaire de Théorie Algorithmique des Nombres
    salle 2
    Jérémie Berthomieu Sorbonne Université
    TBA

  • Le 11 juin 2024 à 11:00
    • Séminaire de Théorie Algorithmique des Nombres
    salle 2
    Valentijn Karemaker Utrecht University\, The Netherlands
    TBA

  • Le 25 juin 2024 à 11:00
    • Séminaire de Théorie Algorithmique des Nombres
    salle 2
    Maria Corte-Real Santos University College London
    TBA

    Afficher 2022 - 2021 - 2020 - 2019 - 2018 - 2017 - 2016 - 2015 - antérieurs

    Institut de Mathématiques de Bordeaux UMR 5251

    Université de Bordeaux
    351, cours de la Libération - F 33 405 TALENCE

    Tél: +33 (0)5 40 00 60 70
    institut math.u-bordeaux.fr

    Universite de bordeauxcnrsinp bordeaux

    Contactez le webmaster math.u-bordeaux.fr - Mentions légales | Accessibilité