IMB > Recherche > Séminaires

Séminaire de Théorie Algorithmique des Nombres

Responsables : Xavier Caruso et Aurel Page

Page du séminaire

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

  • Le 9 février 2016 à 11:00
  • Salle 385
    Павел Соломатин (imb)
    L-functions of Genus Two Abelian Coverings of Elliptic Curves over Finite Fields
    Initially motivated by the relations between Anabelian Geometry andArtin’s L-functions of the associated Galois-representations, here westudy the list of zeta-functions of genus two abelian coverings ofelliptic curves over finite fields. Our goal is to provide a completedescription of such a list.
  • Le 1er mars 2016 à 11:00
  • Salle 385
    Cyril Bouvier (imb)
    Nonlinear polynomial selection for the number field sieve: improving Montgomery's method
    The number field sieve is the most efficient known algorithm forfactoring large integers that are free of small prime factors. The goalof the polynomial selection, the first stage of this algorithm, is tocompute a pair of integer polynomials. Montgomery proposed a method forgenerating two nonlinear polynomials which relies on the constructionof small modular geometric progressions. In this talk, I will presenttheoretical and practical improvements to Montgomery’s method thatallow us to generate pairs of a quadratic and a cubic polynomials andpairs of two cubic polynomials for larger integer that was previouslypossible.Joint work with Nicholas Coxon.
  • Le 8 mars 2016 à 11:00
  • Salle 385
    Fabien Pazuki (IMB et Université de Copenhague)
    Régulateurs de corps de nombres et de variétés abéliennes et propriété de Northcott.
    Soit $A$ une variété abélienne définie sur un corps de nombres $K$. On peutdéfinir un régulateur associé au groupe de Mordell-Weil des pointsrationnels $A(K)$, lequel joue un rôle important dans la forme forte dela conjecture de Birch et Swinnerton-Dyer. Si l’on suppose vraie laconjecture de Lang et Silverman, on montre alors que ce régulateurvérifie la propriété de finitude suivante : il n’y a qu’un nombre fini devariétés abéliennes simples de dimension fixée $g$, définie sur $K$, derang non nul et de régulateur borné. On montre de plus (dans le courantde la preuve) une inégalité inconditionnelle entre la hauteur deFaltings de $A$, les premiers de mauvaise réduction de $A$ et le rang deMordell-Weil de $A$. L’exposé commencera par une introduction présentantun résultat similaire et inconditionnel pour les régulateurs defamilles de corps de nombres.
  • Le 15 mars 2016 à 11:00
  • Salle 385
    Bill Allombert (imb)
    Survey on computing isogeny between elliptic curves.
    We present methods to compute isogenies between elliptic curves, and weapply them to the computation of the isogenies matrix of an ellipticcurve defined over the rational and to the Schoof Elkies Atkinalgorithm for counting point on elliptic curves defined over a finitefield.
  • Le 22 mars 2016 à 11:00
  • Salle 385
    Alexandre Le Meur (Université de Rennes)
    Formules de Thomae généralisées aux cas des extensions galoisiennes résolubles de $\mathbb{P}^1$.
    D’un point de vue classique, les formules de Thomae relient desrapports de puissances de theta constantes avec les coordonnées affinesdes points de ramification d’une courbe hyperelliptique. A partir desannées 80, plusieurs auteurs, ayant des préoccupations centrés sur laphysique, ont montré des généralisations de ces formules au cas descourbes superelliptiques. Plus récemment, Shau Zemel et Hershel Farkasont écrit un livre en utilisant des arguments essentiellementalgébriques. D’un point de vue arithmétique, ces courbes correspondentà des extensions galoisiennes cycliques d’un corps de fonctions $k(x)$.Nous montrerons comment généraliser ces formules au cas des extensionsrésolubles de $k(x)$ et quelles obstructions peuvent survenir.
  • Le 5 avril 2016 à 11:00
  • Salle 385
    Benjamin Matschke (IMB)
    A database of rational elliptic curves with given bad reduction
    In this talk we present a database of rational elliptic curves with good reduction outside certain finite sets of primes, including the set {2, 3, 5, 7, 11}, and all sets whose product is at most 1000.

    In fact this is a biproduct of a larger project, in which we construct practical algorithms to solve S-unit, Mordell, cubic Thue, cubic Thue–Mahler, as well as generalized Ramanujan–Nagell equations, and to compute S-integral points on rational elliptic curves with given Mordell–Weil basis. Our algorithms rely on new height bounds, which we obtained using the method of Faltings (Arakelov, Parshin, Szpiro) combined with the Shimura–Taniyama conjecture (without relying on linear forms in logarithms), as well as several improved and new sieves. In addition we used the resulting data to motivate several conjectures and questions, such as Baker’s explicit abc-conjecture, and a new conjecture on the number of S-integral points of rational elliptic curves.

    This is joint work with Rafael von Känel.


  • Le 10 mai 2016 à 11:00
  • Salle 385
    Nicolas Mascot (University of Warwick)
    Calcul de représentations galoisiennes modulaires / Computing modular Galois representations
    Nous verrons comment la représentation galoisienne modulo l associée àune forme modulaire classique peut être calculée efficacement, enl’isolant dans la torsion de la jacobienne d’une courbe modulaire. Cecipermet notamment de calculer les coefficients a(p) de la forme en tempspolynomial en log p, ce qui en fait la méthode la plus efficace connueà ce jour.

    We will explain how the mod l Galois representation attached to aclassical newform may be efficiently computed, by isolating it amongthe l-torsion of a modular jacobian. This yields a way of computing thecoefficient a(p) of the form in time polynomial in log p, which makesit the most efficient methodknown as of today.


  • Le 17 mai 2016 à 11:00
  • Salle 385
    Nicolas Mascot (University of Warwick)
    Certification de représentations galoisiennes modulaires / Certifying modular Galois representations
    Nous verrons comment les calculs de représentations galoisiennesprésentés dans l’exposé précédent peuvent être certifiés, en s’appuyantsur la conjecture de modularité de Serre et des calculs explicites decohomologie des groupes.

    We will show how the Galois representation computations presented inlast week’s talk may be certified, thanks to Serre’s modularityconjecture and explicit group cohomology computations.


  • Le 7 juin 2016 à 10:00
  • Salle 385
    Jared Asuncion (IMB)
    Tower decomposition of Hilbert class fields

  • Le 11 octobre 2016 à 14:00
  • Salle 385
    Enea Milio (Inria Nancy Grand Est)
    Une implantation en genre 2 de 'Computing functions on Jacobians and their quotients' de Jean-Marc Couveignes et Tony Ezome
    Cet article explique comment définir et évaluer des fonctions sur desJacobiennes de courbes de genre $g$ et sur des quotients de tellesJacobiennes par des sous-groupes isotropes maximaux de la$\ell$-torsion, pour $\ell>2$ premier. Pour le cas spécifique du genre2, il est bien connu qu’à partir d’une courbe hyperelliptique $C$ etd’un sous-groupe isotrope maximal $V$, le quotient $\mathrm{Jac}(C)/V$est la Jacobienne d’une courbe hyperelliptique $C’$,$(\ell,\ell)$-isogène à $C$. L’application de $C$ vers$\mathrm{Jac}(D)$ peut être décrite avec des fractions rationnelles dedegré en $O(\ell)$. L’article donne une méthode pour calculer $C’$ etces fractions. Pour notre exposé, nous nous proposons d’exposer lecontenu de ce papier et de parler de l’implantation que nous avonsfaite en genre 2.
  • Le 18 octobre 2016 à 10:00
  • Salle 385
    Gregor Seiler (ETH Zurich)
    Computing ray class fields of imaginary quadratic fields

  • Le 8 novembre 2016 à 10:00
  • Salle 385
    Aurélien Focqué
    Algorithmes BMSS et Lercier Sirvent pour SEA dans PARI

  • Le 22 novembre 2016 à 10:00
  • Salle 385
    Razvan Barbulescu
    A brief history of pairings
    Pairings are a relatively new cryptographic tool which have been theobject of many arithmetic works. In the last few years some of thepairings have become obsolete because of the progress on the underlyingproblem of discrete logarithm in finite fields. We propose ourselves tomake a list of pairings constructions, to explain their advantages butalso their weaknesses. The sporadic curves are vulnerable to the Logjamattack and have never been a popular choice. The small characteristiccurves allow a very good arithmetic but are the target of aquasi-polynomial algorithm. The pairings where the characteristic has alow Hamming weight, which eliminate the cost of modular reductions,have been the object of special attacks. When the embedding degree iscomposite the one can use the tower field arithmetic but there are alsotower field attacks.
  • Le 17 janvier 2017 à 10:00
  • Salle 385
    Damien Stehlé (ENS Lyon)
    Tuple lattice sieving
    Lattice sieving is asymptotically the fastest approach for solving the shortest vector problem (SVP) on Euclidean lattices. All known sieving algorithms for solving SVP require space which (heuristically) grows as $2^{0.2075n+o(n)}$, where n is the lattice dimension. In high dimensions, the memory requirement becomes a limiting factor for running these algorithms, making them uncompetitive with enumeration algorithms, despite their superior asymptotic time complexity. We generalize sieving algorithms to solve SVP with less memory. We consider reductions of tuples of vectors rather than pairs of vectors as existing sieve algorithms do. For triples, we estimate that the space requirement scales as $2^{0.1887n+o(n)}$. The naive algorithm for this triple sieve runs in time $2^{0.5661n+o(n)}$. With appropriate filtering of pairs, we reduce the time complexity to $2^{0.4812n+o(n)}$ while keeping the same space complexity. We further analyze the effects of using larger tuples for reduction, and conjecture how this provides a continuous tradeoff between the memory-intensive sieving and the asymptotically slower enumeration. Joint work with Shi Bai, Thijs Laarhoven
  • Le 14 mars 2017 à 10:00
  • Salle 385
    Cécile Pierrot (Centrum Wiskunde & Informatica, Amsterdam)
    Nearly sparse linear algebra
    Linear algebra is a widely used tool both in mathematics and computerscience, and cryptography is no exception to this rule. Yet, itintroduces some particularities, such as dealing with linear systemsthat are often sparse, or, in other words, linear systems inside whicha lot of coefficients are equal to zero. We propose to enlarge thisnotion to nearly sparse matrices, characterized by the concatenationof a sparse matrix and some dense columns, and to design an algorithmto solve this kind of problems. Motivated by discrete logarithmscomputations on medium and high characteristic finite fields, theNearly Sparse Linear Algebra bridges the gap between classical denselinear algebra problems and sparse linear algebra ones, for whichspecific methods have already been established. Our algorithmparticularly applies on one of the three phases of NFS (Number FieldSieve) which precisely consists in finding a non trivial element ofthe kernel of a nearly sparse matrix.

    This is a joint work with Antoine Joux.


  • Le 23 mai 2017 à 10:00
  • Salle 385
    Christophe Petit (Oxford)
    Post-quantum cryptography from supersingular isogeny problems?
    We review existing cryptographic schemes based on the hardness ofcomputing isogenies between supersingular isogenies, and present someattacks against them. In particular, we present new techniques toaccelerate the resolution of isogeny problems when the action of theisogeny on a large torsion subgroup is known, and we discuss the impactof these techniques on the supersingular key exchange protocol ofJao-de Feo.
  • Le 30 mai 2017 à 10:00
  • Salle 385
    Benjamin Wesolowski (EPFL)
    Isogeny graphs of ordinary abelian varieties
    Fix a prime number $\ell$. Graphs of isogenies of degree a power of$\ell$ are well-understood for elliptic curves, but not forhigher-dimensional abelian varieties. We study the case of absolutelysimple ordinary abelian varieties over a finite field. We analysegraphs of so-called $\mathfrak l$-isogenies, resolving that, inarbitrary dimension, their structure is similar, but not identical, tothe ``volcanoes’’ occurring as graphs of isogenies of elliptic curves.Specializing to the case of principally polarizable abelian surfaces,we then exploit this structure to describe graphs of a particular classof isogenies known as $(\ell, \ell)$-isogenies. These results lead tonew, provable algorithms to navigate in isogeny graphs, withconsequences for the CM-method in genus 2, for computing explicitisogenies, and for the random self-reducibility of the discretelogarithm problem in genus 2 cryptography.
  • Le 6 juin 2017 à 10:00
  • Salle 385
    Guilhem Castagnos (imb)
    Encryption Switching Protocols Revisited: Switching modulo p
    Last year, Couteau, Peters and Pointcheval introduced a new primitivecalled encryption switching protocols, allowing to switch ciphertextsbetween two encryption schemes. If such an ESP is built with twoschemes that are respectively additively and multiplicativelyhomomorphic, it naturally gives rise to a secure 2-party computationprotocol. It is thus perfectly suited for evaluating functions, suchas multivariate polynomials, given as arithmetic circuits. Couteau etal. built an ESP to switch between Elgamal and Paillier encryptionswhich do n ot naturally fit well together. Consequently, they had todesign a clever variant of Elgamal over Z/nZ with a costly shareddecryption. In this talk, we first present a conceptually simplegeneric construction for encryption switching protocols. We then givean efficient instantiation of our generic approach that uses twowell-suited protocols, namely a variant of Elgamal in Z/pZ and theCastagnos-Laguillaumie encryption defined over class groups of quadratic fields which is additively homomorphic over Z/pZ. Among otheradvantages, this allows to perform all computations modulo a prime pinstead of an RSA modulus. Overall, our solution leads to significantreductions in the number of rounds as well as the number of bitsexchanged by the parties during the interactive protocols. We also showhow to extend its security to the malici ous setting.

    Joint work with Laurent Imbert and Fabien Laguillaumie.


  • Le 13 juin 2017 à 10:00
  • Salle 385
    Bernhard Schmidt (Nanyang Technological University, Singapore)
    The Anti-Field-Descent Method
    A circulant Hadamard matrix of order $v$ is a matrix of the form\[H=\begin{pmatrix}a_1 & a_2 & \cdots & a_v \a_v & a_1 & \cdots & a_{v-1} \\cdots & \cdots & \cdots &\cdots \a_2 & a_3 & \cdots & a_1 \\end{pmatrix}\]with $a_i=\pm 1$ such that any two rows of $H$ are orthogonal withrespect to the standard inner product. It is conjectured that there isno circulant Hadamard matrix of order larger than $4$.

    One way to study circulant Hadamard matrices is the so-called``field-descent method’’. The essential fact behind this method is thatcertain cyclotomic integers necessarily are contained in relativelysmall fields and thus must have relatively small complex modulus. Inthis talk, I will present a method which reveals a complementaryphenomenon: certain cyclotomic integers cannot be contained in relativelysmall fields and thus must have relatively large complex modulus. Thismethod provides new necessary conditions for the existence of circulantHadamard matrices.

    This is joint work with K. H. Leung.


  • Le 17 octobre 2017 à 10:00
  • Salle 385
    Fredrik Johansson (imb)
    Numerics of classical elliptic functions, elliptic integrals and modular forms
    We review methods for validated arbitrary-precision numericalcomputation of elliptic functions and their inverses (the complete andincomplete elliptic integrals), as well as the closely related Jacobitheta functions and $\mathrm{SL}_2(\mathbb{Z})$ modular forms. A general strategy consists of two stages:first, using functional equations to reduce the functionarguments to a smaller domain; second, evaluation of a suitable truncatedseries expansion. For elliptic functions and modular forms, one exploitsperiodicity and modular transformations for argument reduction, afterwhich the rapidly convergent series expansions of Jacobi theta functionscan be employed. For elliptic integrals, a comprehensive strategypioneered by B. Carlson consists of using symmetric forms to unify andsimplify both the argument reduction formulas and the series expansions(which involve multivariate hypergeometric functions). Among otheraspects, we discuss error bounds as well as strategies for argumentreduction and series evaluation that reduce the computational complexity.The functions have been implemented in arbitrary-precision complexinterval arithmetic as part of the Arb library.
  • Le 24 octobre 2017 à 10:00
  • Salle 385
    José Manuel Rodriguez Caballero (Labri)
    Context-free languages in Algebraic Geometry and Number Theory.
    Kassel and Reutenauer computed the zeta function of the Hilbert schemeof n points on a two-dimensional torus and showed it satisfies severalnumber-theoretical properties via modular forms. Classifying thesingularities of this rational function into zeros and poles, we definea word which contains a lot of number-theoretical information about n(the above-mentioned number of points). This nontrivial connectionbetween natural numbers and words can be used to define many classicalsubsets of natural numbers in terms of rational and context-freelanguages (e.g. the set of semi-perimeters of Pythagorean triangles,the set of numbers such that any partition into consecutive parts hasan odd number of parts). Also, some arithmetical functions can bedescribed in way (e.g. the Erdös-Nicolas function, the number of middledivisors). Finally, this approach provides a new technique to provenumber-theoretical results just using relationships among context-freelanguages.
  • Le 14 novembre 2017 à 10:00
  • Salle 385
    Jean Kieffer (ENS Paris)
    Accélération du protocole d'échange de clés de Couveignes-Rostovtsev-Stolbunov
    Ce protocole d’échange de clés est fondé sur la théorie de lamultiplication complexe: un ordre dans un corps quadratique imaginaireagit sur un ensemble de courbes elliptiques ordinaires isogènes définiessur un corps fini. Pour instancier le protocole, on est amené à calculerdes isogénies de différents degrés entre ces courbes à l’aide desalgorithmes développés pour le comptage de points. Ce cryptosystème peutêtre accéléré par un bon choix de courbe elliptique initiale, notammentpar la présence de points de torsion rationnels, et l’on présente uneméthode de recherche de telles courbes.
  • Le 20 novembre 2017 à 14:00
  • Salle 385
    Christian Klein
    Computational approach to compact Riemann surfaces
    A purely numerical approach to compact Riemann surfaces starting fromplane algebraic curves is presented. The critical points of the algebraiccurve are computed via a two-dimensional Newton iteration. The startingvalues for this iteration are obtained from the resultants with respect toboth coordinates of the algebraic curve and a suitable pairing of theirzeros. A set of generators of the fundamental group for the complement ofthese critical points in the complex plane is constructed from circlesaround these points and connecting lines obtained from a minimal spanningtree. The monodromies are computed by solving the de ning equation of thealgebraic curve on collocation points along these contours and byanalytically continuing the roots. The collocation points are chosen tocorrespond to Chebychev collocation points for an ensuing Clenshaw–Curtisintegration of the holomorphic differentials which gives the periods ofthe Riemann surface with spectral accuracy. At the singularities of thealgebraic curve, Puiseux expansions computed by contour integration on thecircles around the singularities are used to identify the holomorphicdifferentials. The Abel map is also computed with the Clenshaw–Curtisalgorithm and contour integrals. As an application of the code, solutionsto the Kadomtsev–Petviashvili equation are computed on non-hyperellipticRiemann surfaces.
  • Le 28 novembre 2017 à 10:00
  • Salle 385
    Frank Vallentin
    Coloring the Voronoi tessellation of lattices
    We define the chromatic number of a lattice: It is the least number ofcolors one needs to color the interiors of the cells of the Voronoitesselation of a lattice so that no two cells sharing a facet are ofthe same color. We compute the chromatic number of the irreducible rootlattices and for this we apply a generalization of the Hoffman bound.
  • Le 9 janvier 2018 à 10:00
  • Salle 385
    Fredrik Johansson (imb)
    Numerical integration in complex interval arithmetic
    We present a new implementation of validated arbitrary-precisionnumerical evaluation of definite integrals $\int_a^b f(x) dx$,available in the Arb library. The code uses a version of the Petrasalgorithm, which combines adaptive subdivision with Gauss-Legendre (GL)quadrature, evaluating the integrand on complex intervals surroundingthe path of integration to obtain rigorous error bounds. The first partof the talk discusses the general algorithm and its performance forinteresting families of integrals. The second part, which is based onjoint work with Marc Mezzarobba, discusses the fast computation of GLquadrature nodes with rigorous error bounds. It is well known that GLquadrature achieves a nearly optimal rate of convergence for analyticintegrands with singularities well isolated from the path ofintegration, but due to the cost of generating GL quadrature nodes, themore slowly converging Clenshaw-Curtis and double exponentialquadrature rules have often been favored when an accuracy of severalhundreds or thousands of digits is required. We consider the asymptoticand practical aspects of this problem. An order-of-magnitude speedup isobtained over previous code for computing GL nodes with simultaneoushigh degree and precision, which makes GL quadrature viable even atvery high precision.
  • Le 22 janvier 2018 à 10:00
  • 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 theso-called unit distance graph $G$ associated with $\Vert \cdot \Vert$:the vertices of $G$ are the points of $\mathbb{R}^n$, and the edgesconnect 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 thedensities achieved by independent sets of $G$. The number $m_1$ wasintroduced by Larman and Rogers (1972) as a tool to study themeasurable chromatic number $\chi_m(\mathbb{R}^n)$ of $\mathbb{R}^n$for the Euclidean norm.

    The best known estimates for $\chi_m(\mathbb{R}^n)$ and$m_1\left(\mathbb{R}^n,\Vert \cdot \Vert\right)$ present relations withEuclidean lattices, in particular with the sphere packing problem.

    The determination of $m_1\left(\mathbb{R}^n,\Vert \cdot \Vert\right)$for the Euclidean norm is still a difficult question. We study thisproblem for norms whose unit ball is a convex polytope. More precisely,if the unit ball corresponding with $\Vert \cdot \Vert$ tiles$\mathbb{R}^n$ by translation, for instance if it is the Voronoiregion of a lattice, then it is easy to see that$m_1\left(\mathbb{R}^n,\Vert \cdot \Vert\right)\geq \frac{1}{2^n}$.

    C. Bachoc and S. Robins conjectured that equality always holds. We showthat this conjecture is true for $n=2$ and for some families of Voronoiregions of lattices in higher dimensions.


  • Le 30 janvier 2018 à 10:00
  • 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. Inthis talk, we recall the steps of ECPP and discuss its implementationin PARI/GP.
  • Le 6 mars 2018 à 10:00
  • Salle 385
    Takashi Fukuda (Nihon University)
    Class number calculation for special number fields
    I will talk about TC (an interpreter of multiprecision C language whichI developed), Weber’s problem, Coates’ conjecture and an algorithm ofcalculating p-class group of abelian number fields. I also present myproject trying to implement an algorithm mentioned above to PARI/GPduring my stay at IMB.
  • Le 20 mars 2018 à 10:00
  • 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 etalgorithmes $p$-adiques, notamment :
    • la factorisation de polynômes rationnels par lemme de Hensel ;
    • les algorithmes de comptage de points de Kedlaya et Lauder, reposant surdes résultats avancés de géométrie arithmétique ;
    • le calcul d’isogénies entre courbes elliptiques.

    Dans toutes ces méthodes et algorithmes, on passe par des calculs surles nombres $p$-adiques, et le problème de la gestion de la précision yest crucial. Avec Xavier Caruso et David Roe, nous avons développé uneméthode, dite de précision différentielle, pour étudier et gérer laprécision $p$-adique.

    Dans cet exposé, nous nous intéresserons à l’application de cetteméthode pour l’étude du calcul d’isogénies entre courbes elliptiquesvia la résolution de certaines équations différentielles $p$-adiques àvariables séparables. Il s’agit d’un travail en commun avec PierreLairez de 2016 qui ne traite que du cas $p>2$. Nous présenterons aussidans cet exposé quelques avancées récentes lorsque $p=2$.


  • Le 3 avril 2018 à 10:00
  • Salle 385
    Alex Bartel (Glasgow University)
    Cohen-Martinet heuristics revisited
    In the early 1990s Henri Cohen and Jacques Martinet offered aprobabilistic model that explains the behaviour of ideal class groupsof number fields in natural families, generalising earlier work byCohen and Lenstra. There is a lot of numerical evidence for thecorrectness of the model, but very few theorems. In joint work withHendrik Lenstra we revisit the Cohen-Martinet heuristics and, amongother things, disprove them in two different ways, but also lendadditional support for the expectation that they are “basically true”.In this talk I will explain one of these disproofs, and will proposepossible corrections.
  • Le 24 avril 2018 à 10:00
  • Salle 385
    Damien Robert (imb)
    Huang's proposal for trilinear maps
    In a recent paper, Huang proposed atrilinear map involving abelian varieties over finite fields. In this talkwe present his approach.

    We will first begin the talk with a review of the standard pairingsconstructions on an abelian variety.


  • Le 22 mai 2018 à 10:00
  • Salle 385
    Jean Kieffer (ENS Paris)
    Étude et implémentation de l’algorithme de Schoof–Elkies–Atkin

  • Le 12 juin 2018 à 10:00
  • 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 à coefficientsdans $\mathbb{Z}/p\mathbb{Z}$ est algébrique sur$\mathbb{Z}/p\mathbb{Z}(x)$ si et seulement si la suite de sescoefficients est $p$-automatique.

    L’objectif de cet exposé sera de raconter de jolies mathématiques enlien de ce théorème. Je commencerai par esquisser deux démonstrations“classiques” de ce résultat, puis montrerai comment les combiner pourobtenir une variante effective du théorème de Christol. Je présenteraiensuite une application de ce résultat à une question de naturealgorithmique.

    Si le temps le permet, je discuterai également les liens entre théorèmede Christol et équations différentielles p-adiques et montrerai commentutiliser ce nouvel ingrédient pour accélérer l’algorithme précédent.

    (Travail en commun avec A. Bostan, G. Christol et Ph. Dumas.)


  • Le 5 juillet 2018 à 10:00
  • 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 setof prime ideals of L that does not contain any divisors of 2. In thispaper, we present a heuristic algorithm for the computation of theS-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 thediscriminant of L. We use this method to compute the ideal class groupof 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 inpolynomial time. We implemented our algorithm using Sage 7.5.1.
  • Le 18 septembre 2018 à 10:30
  • Salle 385
    Aurel Page et Pascal Molin
    Mini groupe de travail: calcul des caractères de Hecke

  • Le 6 novembre 2018 à 10:00
  • 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 corpsfini $K$ de caractéristique impaire et un sous-groupe isotrope maximal$\mathcal{V}$ (pour le couplage de commutateur) de l’ensemble despoints de $l$-torsion où $l$ est un entier (premier) impair, noussavons 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 lajacobienne d’une courbe $D$ de genre $2$.

    La surjection canonique \[ \pi_l \: : J_K(C) \longrightarrow J_K(D) =J_K(C) / \mathcal{V}\] est une $(l,l)$-isogénie de noyau $\mathcal{V}$.

    Dans cet exposé, on s’intéresse à l’algorithme de Couveignes et Ezomepour trouver l’équation de la courbe $D$ à partir de sa kummerconstruite à l’aide de fonctions définies sur la jacobienne de lacourbe de départ et son quotient, ainsi que les équations quidéfinissent l’isogénie $\pi_l$.


  • Le 27 novembre 2018 à 10:00
  • 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 whichallows, for a single encrypted message, to finely control how muchinformation on the encrypted data each receiver can recover. To thisend many functional secret keys are derived from a master secret key.Each functional secret key allows, for a ciphertext encrypted under theassociated public key, to recover a specific function of the underlyingplaintext.

    However constructions for general FE are far from practical, or rely onnon-standard and ill-understood cryptographic assumptions.

    In this talk I will focus on the construction of efficient FE schemesfor linear functions (i.e. the inner product functionality), and theframework in which our constructions hold. Such schemes yield manypractical applications, and our constructions are the first FE schemesfor inner products modulo a prime that are both efficient and recoverthe result whatever its size. Our framework consist of a cyclic group$G$ where the decision Diffie-Hellman assumption holds together with asubgroup $F$ of $G$ where the discrete logarithm problem is easy. Thissetting can be instantiated with class groups of imaginary quadraticfields, and allows us to encode information in the exponent of thesubgroup $F$, which can be efficiently recovered whatever its size.


  • Le 4 décembre 2018 à 11:00
  • 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 torsiondans l’homologie des groupes arithmétiques en théorie des nombres ; jeprésenterai une méthode permettant d’obtenir de l’information dessus : laformule de Cheeger–Mueller, et ses utilisations notamment parBergeron–Venkatesh et Calegari–Venkatesh. Je parlerai aussi d’untravail que je viens de commencer avec Michael Lipnowski et JeanRaimbault, dont les aspects algorithmiques ont des points communs avecles méthodes de calcul de valeurs de fonctions L.
  • Le 11 décembre 2018 à 10:00
  • Salle 385
    Aurel Page
    Torsion analytique et torsion de Reidemeister en théorie des nombres 2

  • Le 18 décembre 2018 à 10:00
  • 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 lecalcul des automorphismes d’une extension Galoisienne de corps denombres sous la condition que le groupe de Galois soit nilpoltent. Cetalgorithme est basé sur la présentation des groupes nilpoltents et lerelèvement des automorphismes de Frobenius et évite la couteusereconnaissance de nombres algébriques par réduction de réseau tout enévitant le cout exponentiel des méthodes combinatoires utilisées dansma thèse.
  • Le 19 février 2019 à 10:00
  • Salle 385
    David Lubicz
    Improving the AGM point counting algorithm

  • Le 9 avril 2019 à 11:30
  • Salle 385
    Xavier Caruso (imb)
    Vers les codes de Gabidulin géométriques
    Dans cet exposé, je commencerai par rappeler la définition et lesprincipales propriétés de codes de Reed-Solomon. Je présenterai ensuitedeux extensions classiques de ces codes, à savoir, d’une part, lescodes géométriques et, d’autre part, les codes de Gabidulin. Ces deuxextensions appaissent toutefois comme orthogonales : du point de vuepratique, elles gomment des limitations différentes de codes deReed-Solomon tandis que, du point de vue technique, elles son basées surdes constructions mathématiques également très différentes. Dans unedeuxième partie de l’exposé, je présenterai quelques idées et quelquesrésultats en vue d’une généralisation commune des codes géométriques etdes codes de Reed-Solomon.
  • Le 28 mai 2019 à 10:00
  • 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 existsonly a finite number of such fields having regulator less than aprescribed bound: this is due to a classical inequality by Remak,generalized years later by Friedman, which bounds the discriminant of anumber field by means of some terms which depend also on the regulator.

    Between 2016 and 2018, Astudillo, Diaz y Diaz, Friedman and Ramirez-Raposogave a complete classification of number fields with low regulator for anydegree $\leq 7$ and for totally real and totally complex octic fields,relying both on Remak-Friedman’s inequalities and on a procedurederived by an explicit formula for the Dedekind Zeta function.

    In joint work with Giuseppe Molteni, we propose a conjectural improvementof the upper bounds for the discriminant which would allow, using thesame method, to give a classificaton for other signatures in degree 8 and9 : the main conjecture deals with the sharpest estimate for a factorwhich in fact depends on the signature of the fields.


  • Le 4 juin 2019 à 10:00
  • 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 desommes d’exponentielles, j’expliquerai en quoi ce genre de propriétéspermet de mieux comprendre les sommes de coefficients de Fourier deformes modulaires en progression arithmétique. Je donnerai un aperçu dece qui a été démontré auparavant dans cette thématique pour mieuxintroduire certaines questions restant ouvertes auxquelles jem’intéresse, notamment le cas des formes modulaires de poidsdemi-entier.
  • Le 10 septembre 2019 à 09:30
  • 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 thedescription of the absolute Galois group of $\mathbb{Q}_p$ due toJannsen and Wingberg. Because this description is only known for odd$p$, our results do not apply to $\mathbb{Q}_2$. We report on theresults of counting such extensions for $G$ of order up to $2000$(except those divisible by 512), for $p = 3$, 5, 7, 11, 13. Inparticular, we highlight a relatively short list of minimal $G$ that donot arise as Galois groups. Motivated by this list, we prove two theoremsabout the inverse Galois problem for $\mathbb{Q}_p$: one giving anecessary condition for G to be realizable over $\mathbb{Q}_p$ and theother givinga sufficient condition.
  • Le 17 septembre 2019 à 10:00
  • Salle 2
    Fredrik Johansson (imb)
    Fungrim : The Mathematical Functions Grimoire
    Fungrim is a new, open source database offormulas and tables for mathematical functions. All formulas are representedin symbolic, computer-readable form and include explicit conditions for thevariables.

    The immediate goal is to create a web-based special functions reference workthat addresses some of the drawbacks of resources such as the NIST DigitalLibrary of Mathematical Functions, the Wolfram Functions site, and Wikipedia.A potential longer-term ambition is to provide a software library forsymbolic knowledge about special functions, usable by computer algebrasystems and theorem proving software.

    This talk will discuss the motivation behind the project, design issues,and possible applications.


  • Le 24 septembre 2019 à 10:00
  • 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 tocompute this isogeny explicitly. It is an essential tool in the SEA pointcounting algorithm: using isogenies is superior to Schoof’s original ideaof using endomorphisms. In this work, we present the analogue of Elkies’algorithm for Jacobians of genus 2 curves, thus opening the way to usingisogenies in higher genus point counting.
  • Le 1er octobre 2019 à 10:00
  • Salle 2
    Damien Robert (imb)
    An overview of isogeny algorithms
    Let $A$ be an abelian variety and $K$ a finite subgroup. We will discussseveral approaches to compute the isogeny $A \mapsto A/K$, starting fromVélu’s algorithm for elliptic curves, and then the isogeny theorem for thetafunctions, Couveignes and Ezome’s work on Jacobians of curves, and recentprogress with David Lubicz.
  • Le 8 octobre 2019 à 10:00
  • 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 abelianextension of $K$. For imaginary quadratic number fields $K$, it can begenerated using special values of certain analytic, modular functions.For quartic CM-fields $K$, the corresponding construction yields only asubfield of $H_K(1)$.

    Ray class fields are generalizations of Hilbert class fields. For apositive integer $m > 0$, the ray class field $H_K(m)$ is obtained byrelaxing the ramification conditions for ideals of $\mathcal{O}_K$dividing $m$.

    It turns out that there is a particular subfield $L(m)$ of $H_K(m)$which can be generated using special values of higher-level modularfunctions and Stark’s conjectures. For some values of $m$, this $L(m)$contains the Hilbert class field $H_K(1)$. Thus, we can compute theHilbert class field as a subfield of $L(m)$. In this talk, we find anupper bound for such an integer $m$.

    If time permits, we will discuss how to compute the Hilbert class fieldas a subfield of this $L(m)$ when $m = 2$.


  • Le 15 octobre 2019 à 10:00
  • 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 actuelde 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 dela cryptologie basée sur les réseaux suite aux travaux d’Ajtai et de Regev enparticulier. Cette deuxième approche ne prétendait pas à l’origine déboucher surdes systèmes de chiffrement compétitifs, mais présentait l’avantage théoriqued’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 deces preuves de sécurité qui ne sont pas accessibles de manière évidente dans lalittérature. Nous montrerons également en quoi il y a aujourd’hui convergencedes deux approches du chiffrement basé sur les codes.

    Nous parcourrons et ferons une synthèse des propositions actuelles à lacompétition du NIST. Nous nous intéresserons également aux primitives de signature àbase de codes, domaine sensiblement moins développé que le chiffrement.


  • Le 22 octobre 2019 à 10:00
  • Salle 2
    Développeurs LFANT (IMB)
    Hacking session

  • Le 29 octobre 2019 à 10:00
  • Salle 2
    Développeurs LFANT (IMB)
    Hacking session

  • Le 5 novembre 2019 à 10:00
  • Salle 2
    Henri Cohen (imb)
    Apéry-Like recursions and modular forms
    Following Zagier and Beukers, we show that the sequencesused by Apery in his proofs of the irrationality ofzeta(2) and zeta(3) are special cases of more general sequenceshaving surprisingly only integer values, and that manyof these sequences can be parametrized by modular forms.Following Almkwist and Zudilin, we also explain that the degreethree sequences used for zeta(3) and generalizations can beautomatically obtained via a Clausen type hypergeometric identityfrom the degree two sequences used for zeta(2) and generalizations.
  • Le 8 novembre 2019 à 14:00
  • 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
  • Salle 2
    Maria Dostert (EPFL)
    Exact Semidefinite Programming Bounds for Packing Problems
    Semidefinite Programming (SDP) is a powerful tool to obtainupper bounds for packing problems. For example, one can consider thekissing problem of the hemisphere in dimension 8 which asks for themaximal number of pairwise non-overlapping spheres which cansimultaneously touch a central hemisphere in 8-dimensional Euclideanspace. The E8 lattice gives a kissing configuration of 183 points.Moreover, using an SDP given by Bachoc and Vallentin one gets an upperbound of 182.99999999996523. Hence, the optimal value is 183. But howcan we obtain the exact rational solution of the SDP based on thefloating point results given by the SDP solver?

    In this talk, I will explain how we can determine the exact result ofthe SDP. Furthermore, we use these techniques to obtain exact resultsfor the kissing problem of the hemisphere in dimension 8 as well asfor other packing problems.

    Using the exact rational solution for the kissing problem of thehemisphere, we can prove that the optimal kissing configuration isunique up to isometry.

    This is a joint work with David de Laat and Philippe Moustrou.


  • Le 26 novembre 2019 à 10:00
  • 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 takesas input a basis of a Euclidean lattice, and, within a polynomialnumber of operations, it outputs another basis of the same lattice butconsisting of rather short vectors.

    On the cryptographic side, many algorithms based on lattices in factuse structured lattices, in order to improve the efficiency of theschemes. Most of the time, these structured lattices are $R$-modules ofsmall dimension, where $R$ is the ring a integers of some number field.It is then tempting to try and adapt the LLL algorithm, which worksover lattices (i.e., $\mathbb Z$-modules), to these $R$-modules.

    All the previous works trying to solve this question focused on ringsof integers $R$ that were Euclidean, as the LLL algorithm over $\mathbb Z$crucially rely on the Euclidean division. In this talk, I willdescribe the first LLL algorithm which works in any ring of integers$R$. This algorithm is heuristic and runs in quantum polynomial time ifgiven access to an oracle solving the closest vector problem in afixed lattice, depending only on the ring of integers R.

    This is a joint work with Changmin Lee, Damien Stehlé and Alexandre Wallet


  • Le 10 décembre 2019 à 10:00
  • Salle 2
    Développeurs LFANT (IMB)
    Hacking session

  • Le 10 décembre 2019 à 10:00
  • Salle 2
    Développeurs LFANT (IMB)
    Hacking session

  • Le 14 janvier 2020 à 10:00
  • 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 aunique abelian variety $\tilde{\mathcal{A}}$ over $\mathbb{Z}_q$ such that themodulo $p$ reduction of $\tilde{\mathcal{A}}$ is $\mathcal{A}$ and $End(\tilde{\mathcal{A}})\cong End(\mathcal{A})$ as a ring. In 2000 T.Satohintroduced a point-counting algorithm on elliptic curves over $\mathbb{F}_q$based on canonical lift. In fact the action of the lifted Verschiebung on thetangent space gives Frobenius eigenvalues and hence the characteristicpolynomial of the ordinary elliptic curves over $\mathbb{F}_q$.We propose to extend the canonical lift algorithm introduced by T.Satoh togenus 2 curves over finite fields, using the modular polynomials in dimension 2. We first prove the Kronecker condition in dimension 2 case andthen succeed to lift the endomorphism ring of $\mathcal{A}$ in dimension 2case using a general lift algorithm of a $p$-torsion group of an ordinaryabelian variety. These results provide an algorithm to compute thecharacteristic polynomial of a genus 2 curves in quasi-quadratic timecomplexity.
  • Le 28 janvier 2020 à 10:00
  • 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éepossède une version euclidienne dans laquelle on considère des triplets $(E,\Lambda,v)$ d’un espace euclidien $E$, d’un réseau $\Lambda$ de $E$ et d’un élément $v$ de $\mathrm{GL}(E)$ tel que $v^2=-\mathrm{Id}$ et $v(\Lambda)\subset\Lambda^*$.

    On s’intéressera à de telles données compatibles avec l’action d’un groupe $G\subset\mathrm{SO}(E)$, et l’on décrira plus précisément deux situations :

    $\bullet$ Action d’un groupe d’ordre 7 en dimension réelle $6$, une sorte d’appendice à l’article de Elkies paru dansThe Eightfold Way (The beauty of Klein’s quartic curve), Cambridge University Press (1999); S. Levy ed.

    $\bullet$ Actions de groupes « pas trop petits » en dimension $4$ en relation avec les courbes de genre $2$.

    Dans tous les cas l’ingrédient important est le théorème de Torelli.


  • Le 4 février 2020 à 10:00
  • 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.
    On prouve que sa complexité (estimée par le nombre d’opérations arithmétiques dans le corps $k$ est en $O\big(\max\big(\deg(C)^{2\omega}, \deg(D^+)^{\omega}\big)\big)$ où $\omega > 2,38$ est la constante de l’algèbre linéaire et $D^+$ le plus petit diviseur effectif vérifiant $D^+ \geq D$. Cet algorithme probabiliste peut échouer mais sous quelques conditions, on prouve que sa probabilité d’échec est bornée par $O\big(\max\big(\deg(C)^4, \deg(D^+)^2\big)/|E|\big)$ où $E$ est un sous ensemble fini de $k$ dans lequel on peut choisir des éléments de $k$ uniformément aléatoirement.
    À notre connaissance cette borne sur la complexité est la meilleure obtenue jusqu’alors pour le calcul d’espaces de Riemann-Roch dans un cadre général. Dans le contexte du calcul de la loi de groupe dans la jacobienne d’une courbe lisse, notre borne améliore aussi la meilleure borne connue à ce jour, due à Khuri-Makdisi. Notre algorithme jouit également du fait que son efficacité repose sur deux blocs pour lesquels des algorithmes efficaces existent : algèbre linéaire et arithmétique des polynômes univariés. Nous avons implémenté cet algorithme en C++/NTL. Les résultats expérimentaux obtenus via cette implémentation semblent indiquer une amélioration des temps de calcul par rapport à l’implémentation dans le logiciel de calcul formel Magma (jusqu’à 200 fois plus rapide sur certaines instances sur de grands corps finis).


  • Le 11 février 2020 à 10:00
  • 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).
    The formal verification is done using a mix of automated provers and user-provided proof annotations. We have verified the GMP algorithms for addition, subtraction, multiplication (schoolbook and Toom-2/2.5), schoolbook division, divide-and-conquer square root and modular exponentiation. The rest of the mpn API is work in progress. The main challenge is to preserve and verify all the GMP algorithmic tricks in order to get good performance.
    Our algorithms are implemented as WhyML functions. We use a dedicated memory model to write them in an imperative style very close to the C language. Such functions can then be extracted straightforwardly to efficient C code. For medium-sized integers (less than 1000 bits, or 100,000 for multiplication), the resulting library is performance-competitive with the generic, pure-C configuration of GMP.


  • Le 18 février 2020 à 10:00
  • 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
  • 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
  • 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
  • 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
  • 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
  • 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
  • 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
  • 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
  • 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
  • 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
  • Online
    Elie Eid (Université de Rennes)
    Équations différentielles $p$-adiques pour le calcul d’isogénies en\npetite 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
  • 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
  • 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
  • Online
    Mercedes Haiech (Université Rennes 1)
    The Fundamental Theorem of Tropical Partial Differential Algebraic \nGeometry

    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
  • 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
  • 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
  • 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
  • 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
  • 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
  • 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
  • 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.
    Depuis le début des années 90 à aujourd’hui il y a eu un certain nombre de travaux étudiant la convergence de ces algorithmes. Schweiger et Broise ont notamment démontré que les algorithmes de Selmer et Brun sont convergents et ergodiques. Plus surprenant peut-être, Nogueira a démontré que l’algorithme proposé par Poincaré ne convergeait presque jamais.
    En partant du cas classique de l’algorithme de Farey, qui est une version “additive” de l’algorithme de Gauss, je présenterai un point de vu combinatoire sur ces algorithmes qui permet le passage d’une vision déterministe à une approche probabiliste. En effet, dans ce modèle, prendre un vecteur aléatoire pour la mesure de Lebesgue correspondra à suivre une marche aléatoire avec mémoire dans un graphe étiqueté nommé système simplicial. Les lois pour cette marche aléatoire sont élémentaires et nous pouvons développer des techniques probabilistes pour étudier leur comportement dynamique générique. Cela nous mènera à décrire un critère purement de théorie des graphes pour démontrer la convergence ou non d’un algorithme de fraction continue.

    slides animés
  • Le 6 avril 2021 à 10:00
  • 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
  • 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$.
    A key step is the construction of amalgamated decompositions of the elementary group $E_2(mathcal O)$, where $mathcal O$ is an order in rational division algebra, and of certain arithmetic groups $Gamma$. The methods for the latter turn out to work in much greater generality and most notably are carried out to obtain amalgam decompositions for the higher modular groups $SL_+(Gamma_n(mathbb Z))$, with $nle 4$, which can be seen as higher dimensional versions of modular and Bianchi groups.


  • Le 4 mai 2021 à 10:00
  • 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
  • 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
  • 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.
    In 2013-2016, new variants of the function field sieve and the number field sieve algorithms turned out to be faster in certain finite fields related to pairing-based cryptography, in particular those which had a very efficient arithmetic. Now small characteristic settings are discarded. The situation for $GF(p^k)$ where $p$ is prime and $k$ is small is still quite unclear. We refine the work of Menezes-Sarkar-Singh and Barblescu-Duquesne to estimate the cost of a hypothetical implementation of the Special-Tower-NFS in $GF(p^k)$ for small $k$, and deduce parameter sizes for cryptographic pairings.
    Joint work with Shashank Singh, IISER Bhopal, India.
    References
    On the alpha value of polynomials in the tower number field sieve algorithm, Aurore Guillevic and Shashank Singh, Mathematical Cryptology, Vol 1 No 1 (Feb 2021), journal version, preprint.
    A short list of pairing-friendly curves at the 128-bit security level, Aurore Guillevic, presented at PKC’2020 recorded talk, ePrint 2019/1371.
    Implementation available with MIT licence on gitlab. Alpha in Magma, alpha and TNFS simulation in SageMath.


  • Le 25 mai 2021 à 10:00
  • 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,bin ext{ 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)$.
    P. Montgomery (1986) a accéléré la cofactorisation en utilisant des courbes elliptiques correspondant à des points rationnels sur certaines courbes modulaires. Le programme de Mazur peut s’énoncer comme suit : étant donné un corps de nombres $K$, borner le niveau des courbes modulaires qui ont des points $K$-rationnels et calculer effectivement ces points. Des travaux de Rouse, Sutherland, Zureick-Brown et Zywina (2016,2017) ont résolu partiellement le cas où $K=mathbb{Q}$.
    Le progrès récent sur le programme B de Mazur (2019-2021) répond partiellement à plusieurs questions a) les points rationnels des courbes modulaires ayant un nombre fini de points; b) les courbes ayant un niveau composé c) les points $K$-rationnels pour les corps $K$ quadratiques d) les points de torsion sur des corps de nombres.
    Nous proposons une modification mineure de l’étape de sélection polynomiale. L’état de l’art consiste à construire un grand nombre de polynôme par les méthodes de Kleinjung (2006) et de garder ceux qui optimisent la fonction $alpha$ de Murphy (2000). Ceci correspond de manière empirique à augmenter la probabilité que $F(a,b)$ et $G(a,b)$ soient $B$-friables. Nous proposons de prendre en compte l’existence de familles de courbes elliptiques qui permettent de factoriser rapidement des entiers de la forme $F(a,b)$. Cela revient à décrire les corps de nombres $K$ de degré donné, par exemple $2$, admettant des courbes modulaires qui ont des points $K$-rationnels.


  • Le 1er juin 2021 à 10:00
  • 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
  • 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
  • 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
  • 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
  • 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
  • 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 imes 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$?
    In this talk, we will revise how to construct the period matrix of a curve, we will see some known results around this problem, and discuss an application of its solution.


  • Le 13 juillet 2021 à 15:00
  • 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 14 septembre 2021 à 10:00
  • Online
    Benjamin Wesolowski (CNRS, IMB)
    TBA

    TBA


    Afficher 2016 - 2015 - antérieurs