Notice: The Lfant has exceeded its natural life span of twelve years and has been replaced by CANARI. These pages will no longer be updated.
2017/2018
- 2018-07-05Jean-François Biasse (University of South Florida)Fast multiquadratic S-unit computation and application to the calculation of class groupsLet $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.
- 2018-06-12Xavier Caruso (Université de Rennes)Variations autour d'un théorème de ChristolUn 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.
L’objectif de cet exposé sera de raconter de jolies mathématiques en lien de ce théorème. Je commencerai par esquisser deux démonstrations “classiques” de ce résultat, puis montrerai comment les combiner pour obtenir une variante effective du théorème de Christol. Je présenterai ensuite une application de ce résultat à une question de nature algorithmique.
Si le temps le permet, je discuterai également les liens entre théorème de Christol et équations différentielles p-adiques et montrerai comment utiliser ce nouvel ingrédient pour accélérer l’algorithme précédent.
(Travail en commun avec A. Bostan, G. Christol et Ph. Dumas.)
- 2018-05-22Jean Kieffer (ENS Paris)Étude et implémentation de l’algorithme de Schoof–Elkies–Atkin
- 2018-05-15Bill Allombert (imb)
- 2018-05-03Francesco Battistoni (University of Milan)Classifications of Number fields of bounded discriminant: last results and open questionsIn this seminar we show how the classic methods in Geometry of numbers by Hunter, Pohst and Martinet allow to give an algorithmic, complete classification of number fields with degree $8$, signature $(2,3)$ and absolute discriminant less than $5726300$.
Furthermore, we will discuss the problems, either computational or theoretical, arising in the attempt to run this process for the next signatures, together with other questions in related topics.
- 2018-04-24Damien Robert (imb)Huang's proposal for trilinear mapsIn a recent paper, Huang proposed a trilinear map involving abelian varieties over finite fields. In this talk we present his approach.
We will first begin the talk with a review of the standard pairings constructions on an abelian variety.
- 2018-04-03Alex Bartel (Glasgow University)Cohen-Martinet heuristics revisitedIn 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.
- 2018-03-20Tristan Vaccon (Université de Limoges)Les trois dernières décennies ont vu le développement de méthodes et algorithmes $p$-adiques, notamment :
- la factorisation de polynômes rationnels par lemme de Hensel ;
- les algorithmes de comptage de points de Kedlaya et Lauder, reposant sur des 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 sur les nombres $p$-adiques, et le problème de la gestion de la précision y est crucial. Avec Xavier Caruso et David Roe, nous avons développé une méthode, dite de précision différentielle, pour étudier et gérer la précision $p$-adique.
Dans cet exposé, nous nous intéresserons à l’application de cette méthode pour l’étude du calcul d’isogénies entre courbes elliptiques via la résolution de certaines équations différentielles $p$-adiques à variables séparables. Il s’agit d’un travail en commun avec Pierre Lairez de 2016 qui ne traite que du cas $p>2$. Nous présenterons aussi dans cet exposé quelques avancées récentes lorsque $p=2$.
- 2018-03-13Bill Allombert (imb)
- 2018-03-06Takashi Fukuda (Nihon University)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.
- 2018-02-06Bill Allombert (imb)
- 2018-01-30Jared Asuncion (IMB)ECPP in PARI/GPThe 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.
- 2018-01-22Philippe Moustrou (IMB)On the Density of Sets Avoiding Parallelohedron Distance 1Let $\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.
The best known estimates for $\chi_m(\mathbb{R}^n)$ and $m_1\left(\mathbb{R}^n,\Vert \cdot \Vert\right)$ present relations with Euclidean 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 this problem 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 Voronoi region 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 show that this conjecture is true for $n=2$ and for some families of Voronoi regions of lattices in higher dimensions.
- 2018-01-09Fredrik Johansson (imb)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.
- 2017-12-15Christophe Ritzenthaler (Rennes)Réduction hyperelliptique d'une courbe de genre 3 non hyperelliptiqueUne courbe de genre 3 non hyperelliptique sur un corps de nombres peut se réduire modulo certains premiers en une courbe hyperelliptique de genre 3. Nous donnons une caractérisation de ces premiers en fonction de la valuation des invariants de Dixmier-Ohno des quartiques planes. Travail en cours avec Reynald Lercier et Elisa Lorenzo.
- 2017-11-28Frank VallentinColoring the Voronoi tessellation of latticesWe 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.
- 2017-11-20Christian KleinComputational approach to compact Riemann surfacesA 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.
- 2017-11-14Jean Kieffer (ENS Paris)Accélération du protocole d'échange de clés de Couveignes-Rostovtsev-StolbunovCe 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.
- 2017-11-07Bill Allombert (imb)
- 2017-10-24José Manuel Rodriguez Caballero (Labri)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.
- 2017-10-17Fredrik Johansson (imb)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.
- 2017-10-10Bill Allombert (imb)
- 2017-10-03Bill Allombert (imb)
- 2017-09-26Bill Allombert (imb)
- 2017-09-19Bill Allombert (imb)
- 2017-09-08Damien Robert (IMB)Polynômes modulairesNous présentons une méthode de calcul de polynômes modulaires par évaluation/interpolation développée pour les courbes elliptiques par Enge et généralisée au genre 2 par Dupont puis par Milio et Robert.
En particulier nous donnons des exemples de polynômes modulaires paramétrisant des isogénies totalement isotrope entre surfaces abéliennes sur l’espace de module de Siegel puis des polynômes concernant les isogénies cycliques entre surfaces abéliennes sur l’espace de module de Hilbert.
- 2017-09-08Abdoul Aziz Ciss (Université Cheikh Anta Diop, Dakar, Sénégal)
- 2017-09-08Tony Ezome (Université des Sciences et Techniques de Masuku (USTM), Franceville, Gabon)Bases normales et variétés JacobiennesNous présentons une généralisation des travaux de Couveignes et Lercier au cas des variétés jacobiennes.
- 2017-09-07Damien Robert (IMB)SIDH II
- 2017-09-07Guilhem Castagnos (IMB)A Linearly Homomorphic Encryption Scheme based on the Discrete Logarithm ProblemWe present the first linearly homomorphic encryption scheme whose security relies on the sole hardness of a discrete logarithm problem. Our approach requires some special features of the underlying group. Therefore, the discrete logarithm assumption holds in the class group of a non maximal order of an imaginary quadratic field. Its algebraic structure and unknown order make 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. Under some conditions, the prime $p$ can be scaled to fit the application needs. A notable difference with previous works is that the security does not depend on the hardness of the factorization of integers, which allows in particular to embed the message space into the whole group $\mathbb{Z}/p\mathbb{Z}$.
Joint work with Fabien Laguillaumie.
- 2017-09-07Bill Allombert (IMB)Comptage de points
- 2017-09-07Aurel Page (IMB)Algèbres de quaternions et courbes elliptiques supersingulières III
- 2017-09-06Aurel Page (IMB)Algèbres de quaternions et courbes elliptiques supersingulières II
- 2017-09-06Andreas Enge (IMB)The theory of complex multiplication can be used to obtain elliptic curves with a number of points known in advance, which has applications from primality proving to cryptography. Complex multiplication provides a link between the analytic theory of elliptic curves over the complex numbers, the arithmetic of elliptic curves and explicit class field theory of imaginary-quadratic fields. We give an elementary introduction to this beautiful theory and discuss asymptotically optimal algorithms to compute the needed data, which are used successfully in practice.
- 2017-09-06Tony Ezome (Université des Sciences et Techniques de Masuku (USTM), Franceville, Gabon)Bases normales et courbes elliptiquesNous présentons la construction des bases normales utilisant les courbes elliptiques proposée par Couveignes et Lercier.
- 2017-09-06Jean-Marc Couveignes (IMB)
- 2017-09-05Abdoulaye Maiga (Université Cheikh Anta Diop, Dakar, Sénégal)Lifts canoniques
- 2017-09-05Damien Robert (IMB)SIDH INous présentons le cryptosystème post-quantique Supersingular Isogenies Diffie-Hellman proposé par De Feo, Jao et Plut basé sur les graphes d’isogénies des courbes elliptiques supersingulières.
- 2017-09-05Emmanuel Fouotsa (The University of Bamenda, Cameroon)Pairings are bilinear maps defined over groups of points of an elliptic curves. They enables many applications in cryptography and the Miller algorithm is the main tool for their computation. In this talk, we explain an alternative way of computing these maps based on the work of K. Stange and then study some recent optimizations. (References.)
- 2017-09-04Aurel Page (IMB)
- 2017-09-04Jean-Marc Couveignes (IMB)
- 2017-09-04Emmanuel Fouotsa (The University of Bamenda, Cameroon)In this talk, we explain the construction of isogenies graphs and isogenies cycles for ordinary elliptic curves. We illustrate concepts with many examples. We end with a brief presentation and a security analysis of the Rostovtev-Stolbunov cryptosystem. (References.)
- 2017-09-04Mohamadou Sall (Université Cheikh Anta Diop, Dakar, Sénégal)A finite Galois extension $E$ of a field $F$ can always be viewed as a vector space over $F$. This gives many possibilities for representing elements of $E$. Normal bases are one of the most useful representations. These concern both mathematical theory and practical applications. In this talk we give a brief overview of normal bases, namely by describing an efficient arithmetic over finite field.