2020/2021
- 2021-07-13Jean Kieffer (IMB)Équations modulaires en dimension supérieure, applications au calcul d’isogénies et au comptage de points(doctoral defense)
- 2021-07-06Anna Somoza (IRMAR, Université de Rennes 1)The Inverse Jacobian problem
To an algebraic curve $C$ over the complex numbers one can associate a non-negative integer $g$, the genus, as a measure of its complexity. One can also associate to $C$, via complex analysis, a $g\times g$ symmetric matrix $\Omega$ called period matrix. Because of the natural relation between $C$ and $\Omega$, one can obtain information about one by studying the other. Therefore, it makes sense to consider the inverse problem: Given a period matrix $\Omega$, can we compute a model for the associated curve $C$?
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. - 2021-06-29Pierre 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.
- 2021-06-22Vandita 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).
- 2021-06-15Damien Robert (IMB)Efficient algorithms for abelian varieties and their moduli spaces(HDR defense)
- 2021-06-15Fabien 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.
- 2021-06-08Sté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.
- 2021-06-01Andreas 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.
- 2021-05-25Razvan Barbulescu (CNRS, IMB)Quelques conséquences du programme de Mazur sur la cryptographie
Les algorithmes de factorisation d’entiers et ceux de calcul de logarithmes discrets, adaptés aux tailles cryptographiques, ont deux étapes pertinentes pour notre exposé : la sélection polynomiale et la cofactorisation. La première consiste à sélectionner deux polynômes homogènes $F(x,y)$ et $G(x,y)$ dans $\mathbb{Z}[x,y]$ tels que les entiers de l’ensemble $\{F(a,b)G(a,b)\mid a,b\in\text{ un rectangle },\gcd(a,b)=1 \}$ contiennent le plus possible d’entiers $B$-friables (ayant tous les facteurs premiers inférieurs à $B$). La deuxième consiste à factoriser des entiers de la forme $F(a,b)$ et $G(a,b)$.
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. - 2021-05-18Aurore 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. - 2021-05-11Weiqiang 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.
- 2021-05-04Barinder 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.
- 2021-04-27Ann 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 $n\le 4$, which can be seen as higher dimensional versions of modular and Bianchi groups. - 2021-04-06Marc Masdeu (Universitat Autònoma de Barcelona)
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.
- 2021-03-30Charles Fougeron (IRIF, Université de Paris)
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.
slides animés
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. - 2021-03-23Samuel Le Fourn (Institut Fourier, Université Grenoble Alpes)
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$.
- 2021-03-16Vincent Neiger (Université de Limoges)
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.
- 2021-03-09Cécile Armana (LMB, Université de Franche-Comté)
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).
- 2021-03-02Jade Nardi (Inria Saclay, LIX)
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.
- 2021-02-02Bogdan Dina (Ulm University)
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$.
- 2021-01-26Mercedes Haiech (Université Rennes 1)
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.
- 2021-01-19Renaud Vilmart (LSV -- Inria Saclay)
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.
- 2021-01-12Alain Couvreur (LIX -- Inria Saclay)
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.
- 2020-12-15Elie Eid (Université de Rennes)
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.
- 2020-12-08Alexandre Bailleul (ENS Lyon)
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.
- 2020-12-01Tommy Hofmann (Saarland University)
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.
- 2020-11-24Anne-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.
- 2020-11-17Fredrik Johansson (IMB)
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.
- 2020-11-10Raphaël Pagès (IMB)
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.
- 2020-11-03Samuele Anni (Université Aix-Marseille)
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.
- 2020-10-13Christopher 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.
- 2020-09-22Nicolas Mascot (Trinity College Dublin)
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.