IMB > Recherche > Séminaires

# Séminaire de Théorie Algorithmique des Nombres

Responsables : Razvan Barbulescu et Wessel Van Woerden

Page du séminaire

• Le 12 janvier 2021 à 10:00
• Séminaire de Théorie Algorithmique des Nombres
Online
Alain Couvreur LIX -- Inria Saclay
On the hardness of code equivalence problems in rank metric
In recent years, the notion of rank metric in the context of coding theory has known many interesting developments in terms of applications such as space time coding, network coding or public key cryptography. These applications raised the interest of the community for theoretical properties of this type of codes, such as the hardness of decoding in rank metric or better decoding algorithms. Among classical problems associated to codes for a given metric, the notion of code equivalence has always been of the greatest interest. In this talk, we discuss the hardness of the code equivalence problem in rank metric for $\mathbb F_{q^m}$--linear and general rank metric codes.
• Le 19 janvier 2021 à 10:00
• Séminaire de Théorie Algorithmique des Nombres
Online
Renaud Vilmart LSV -- Inria Saclay
Une introduction aux circuits quantiques et au ZX-calcul
• Le 26 janvier 2021 à 10:00
• Séminaire de Théorie Algorithmique des Nombres
Online
Mercedes Haiech Université Rennes 1
The Fundamental Theorem of Tropical Partial Differential Algebraic .Geometry
Given a partial differential equation (PDE), its solutions can be difficult, if not impossible, to describe. The purpose of the Fundamental theorem of tropical (partial) differential algebraic geometry is to extract from the equations certain properties of the solutions. More precisely, this theorem proves that the support of the solutions in $k[[t_1, \cdots, t_m]]$ (with $k$ a field of characteristic zero) can be obtained by solving a so-called tropicalized differential system.
• Le 2 février 2021 à 10:00
• Séminaire de Théorie Algorithmique des Nombres
Online
Bogdan Dina Ulm University
Isogenous hyperelliptic and non-hyperelliptic Jacobians with maximal complex multiplication
We analyze complex multiplication for Jacobians of curves of genus 3, as well as the resulting Shimura class groups and their subgroups corresponding to Galois conjugation over the reflex field. We combine our results with numerical methods to find CM fields $K$ for which there exist both hyperelliptic and non-hyperelliptic curves whose Jacobian has complex multiplication by $\mathbb{Z}_K$.
• Le 2 mars 2021 à 10:00
• Séminaire de Théorie Algorithmique des Nombres
Online
Explicit construction and parameters of projective toric codes
Toric codes, introduced by Hansen in 2002, generalize (weighted) Reed-Muller codes on other toric varieties than projective spaces. They consist of evaluation codes of monomials at tuples of non-zero coordinates, which correspond to the points on the dense torus contained in the associated toric variety. Our aim is to â€˜projectiviseâ€™ these codes, in the same spirit that turns a Reed-Muller codes into a projective one: we consider codes obtained by evaluating global sections on the whole set of the rational points of a toric variety. We focus on simplicial toric varieties, which come with a nice quotient description, and we give an explicit construction of projective codes on them, as well as a combinatorial way to determine their parameters. 'Projectivizing' toric codes opens new possibilities of getting codes with excellent parameters, by extending some champion classical toric codes geometrically.
• Le 9 mars 2021 à 10:00
• Séminaire de Théorie Algorithmique des Nombres
Online
Cécile Armana LMB\, Université de Franche-Comté
Bornes de Sturm pour des formes automorphes sur les corps de fonctions
Les bornes de Sturm indiquent combien de coefficients de Fourier successifs suffisent Ã  dÃ©terminer une forme modulaire. Pour les formes modulaires classiques, elles fournissent aussi des bornes sur le nombre d'opÃ©rateurs de Hecke engendrant l'algÃ¨bre du mÃªme nom. Cet exposÃ© propose d'Ã©tudier la situation pour certaines formes automorphes, dites de Drinfeld, sur les corps de fonctions. Il s'agit d'un travail en commun avec Fu-Tsun Wei (National Tsing-Hua University, TaÃ¯wan).
• Le 16 mars 2021 à 10:00
• Séminaire de Théorie Algorithmique des Nombres
Online
Vincent Neiger Université de Limoges
Deterministic computation of the characteristic polynomial in the time of matrix multiplication
This talk describes joint work with ClÃ©ment Pernet on an algorithm which computes the characteristic polynomial of a matrix over a field within the same asymptotic complexity, up to constant factors, as the multiplication of two square matrices. Previously, this was only achieved by resorting to genericity assumptions or randomization techniques, while the best known complexity bound with a general deterministic algorithm was obtained by Keller-Gehrig in 1985 and involves logarithmic factors. The new algorithm computes more generally the determinant of a univariate polynomial matrix in reduced form.
• Le 16 mars 2021 à 10:00
• Séminaire de Théorie Algorithmique des Nombres
Online
Vincent Neiger Université de Limoges
Deterministic computation of the characteristic polynomial in the time of matrix multiplication
This talk describes joint work with ClÃ©ment Pernet on an algorithm which computes the characteristic polynomial of a matrix over a field within the same asymptotic complexity, up to constant factors, as the multiplication of two square matrices. Previously, this was only achieved by resorting to genericity assumptions or randomization techniques, while the best known complexity bound with a general deterministic algorithm was obtained by Keller-Gehrig in 1985 and involves logarithmic factors. The new algorithm computes more generally the determinant of a univariate polynomial matrix in reduced form.
• Le 23 mars 2021 à 10:00
• Séminaire de Théorie Algorithmique des Nombres
Online
Samuel Le Fourn Institut Fourier\, Université Grenoble Alpes
Recherche de points entiers sur une variété modulaire de dimension 3
La dÃ©termination effective des points entiers sur des variÃ©tÃ©s algÃ©briques est un problÃ¨me difficile, surtout en dimension plus grande que 1. Dans cet exposÃ©, je prÃ©senterai briÃ¨vement deux approches naturelles pour les points entiers qui permettent dans des cas favorables de tous les trouver. En cherchant des raffinements de ces mÃ©thodes, on arrive Ã  des problÃ¨mes combinatoires intÃ©ressants, que je mettrai en valeur dans le cas prÃ©cis d'une variÃ©tÃ© "modulaire" de dimension 3, qu'on peut dÃ©finir par une Ã©quation quartique dans $\mathbb{P}^4$.
• Le 30 mars 2021 à 10:00
• Séminaire de Théorie Algorithmique des Nombres
Online
Charles Fougeron IRIF\, Université de Paris
Dynamiques des algorithmes de fraction continue multidimensionnels
MotivÃ©s par la richesse de l'algorithme de Gauss qui permet de calculer efficacement les meilleurs approximation d'un nombre rÃ©el par des rationnels, beaucoup de mathÃ©maticiens ont proposÃ© des gÃ©nÃ©ralisations de ces algorithmes pour approximer des vecteurs de dimension supÃ©rieure Ã  1. Citons pour exemple celui de PoincarÃ© introduit Ã  la fin du 19e siÃ¨cle ou ceux de Brun et Selmer Ã  la moitiÃ© du 20e siÃ¨cle.
• Le 6 avril 2021 à 10:00
• Séminaire de Théorie Algorithmique des Nombres
Online
Marc Masdeu Universitat Autònoma de Barcelona
Numerical experiments with plectic Stark--Heegner points
Let $E/F$ be an elliptic curve defined over a number field $F$, and let $K/F$ be a quadratic extension. If the analytic rank of $E(K)$ is one, one can often use Heegner points (or the more general Darmon points) to produce (at least conjecturally) a nontorsion generator of $E(K)$. If the analytic rank of $E(K)$ is larger than one, the problem of constructing algebraic points is still very open. In very recent work, Michele Fornea and Lennart Gehrmann have introduced certain $p$-adic quantities that may be conjecturally related to the existence of these points. In this talk I will explain their construction, and illustrate with some numerical experiments that we have been able to carry out that support their conjecture. This is joint work with Michele Fornea and Xevi Guitart.
• Le 27 avril 2021 à 10:00
• Séminaire de Théorie Algorithmique des Nombres
Online
Ann Kiefer Luxembourg Centre for Educational Testing
Property (FA) of the unit group of $2$-by-$2$ matrices over an order in a quaternion algebra
We study property (FA) and its hereditary version for unit groups of $2$-by-$2$ matrices over orders in totally definite quaternion algebras with rational centres. In particular we consider the three matrix rings over totally definite rational quaternion algebras that can appear as Wedderbrun-Artin components of a group ring $\mathbb{Q}G$.
• Le 4 mai 2021 à 10:00
• Séminaire de Théorie Algorithmique des Nombres
Online
Barinder Banwait Harish-Chandra Research Institute
Explicit isogenies of prime degree over quadratic fields
Let $K$ be a quadratic field which is not an imaginary quadratic field of class number one. We describe an algorithm to compute a superset of the set of primes $p$ for which there exists an elliptic curve over $K$ admitting a $K$-rational $p$-isogeny. Combining this algorithm with recent work on the determination of quadratic points on low-genus modular curves, we determine - conditional upon the Generalised Riemann Hypothesis - the above set of isogeny primes for several quadratic fields, providing the first such examples after Mazur's 1978 determination for $K = \mathbb{Q}$. We will give a live demo of the Sage and PARI/GP implementations of the algorithm.
• Le 11 mai 2021 à 10:00
• Séminaire de Théorie Algorithmique des Nombres
Online
Weiqiang Wen Inria Rennes\, Irisa
On algorithms for solving Euclidean lattice problems in cryptography
In this talk, we will try to review the state-of-the-art of the algorithms for solving the Euclidean lattice problems underlying cryptography. In more details, this talk contains two parts. In the first part, we will focus on the lattice problems such as approximate Shortest Vector Problem (approx-SVP) and the lattice reduction algorithms as the best known solving algorithms so far. In particular, I will present an improved enumeration-based lattice reduction algorithm, which is shown to be (potentially) relevant to cryptanalysis. In the second part, we will instead consider a quantum problem that is computationally equivalent to approx-SVP. By directly solving a quantum problem, we may expect to have a more powerful use of the quantum computation. However, the best known algorithms for solving approx-SVP via solving this quantum problem, is not better than lattice reduction yet.
• Le 18 mai 2021 à 10:00
• Séminaire de Théorie Algorithmique des Nombres
Online
Aurore Guillevic Inria Nancy\, Loria
Computing Murphy-alpha in the special tower number field sieve algorithm and applications to pairing-based cryptography
Pairings on elliptic curves are involved in signatures, NIZK, and recently in blockchains (ZK-SNARKS). These pairings take as input two points on an elliptic curve $E$ over a finite field, and output a value in an extension of that finite field. Usually for efficiency reasons, this extension degree is a power of 2 and 3 (such as 12, 18, 24), and moreover the characteristic of the finite field has a special form. The security relies on the hardness of computing discrete logarithms in the group of points of the curve and in the finite field extension.
• Le 25 mai 2021 à 10:00
• Séminaire de Théorie Algorithmique des Nombres
Online
Razvan Barbulescu CNRS\, IMB
Quelques conséquences du programme de Mazur sur la cryptographie
Les algorithmes de factorisation d'entiers et ceux de calcul de logarithmes discrets, adaptÃ©s aux tailles cryptographiques, ont deux Ã©tapes pertinentes pour notre exposÃ© : la sÃ©lection polynomiale et la cofactorisation. La premiÃ¨re consiste Ã  sÃ©lectionner deux polynÃ´mes homogÃ¨nes $F(x,y)$ et $G(x,y)$ dans $\mathbb{Z}[x,y]$ tels que les entiers de l'ensemble $\{F(a,b)G(a,b)\mid a,b\in\text{ un rectangle },\gcd(a,b)=1 \}$ contiennent le plus possible d'entiers $B$-friables (ayant tous les facteurs premiers infÃ©rieurs Ã  $B$). La deuxiÃ¨me consiste Ã  factoriser des entiers de la forme $F(a,b)$ et $G(a,b)$.
• Le 1er juin 2021 à 10:00
• Séminaire de Théorie Algorithmique des Nombres
Online
Andreas Enge\, Bill Allombert\, Fredrik Johansson Inria\, CNRS\, Inria
Présentation de l'équipe LFANT pour les stagiaires
• Le 8 juin 2021 à 10:00
• Séminaire de Théorie Algorithmique des Nombres
Online
Stéphane Ballet I2M\, Université Aix-Marseille
Optimization of the scalar complexity of Chudnovsky^2 multiplication algorithms in finite fields
We propose several constructions for the original multiplication algorithm of D.V. and G.V. Chudnovsky in order to improve its scalar complexity. We highlight the set of generic strategies who underlay the optimization of the scalar complexity, according to parameterizable criteria. As an example, we apply this analysis to the construction of type elliptic Chudnovsky2 multiplication algorithms for small extensions. As a case study, we significantly improve the Baum-Shokrollahi construction for multiplication in F256/F4.
• Le 15 juin 2021 à 10:00
• Séminaire de Théorie Algorithmique des Nombres
Online
Fabien Narbonne IRMAR\, Université de Rennes
Corps de modules des courbes de genre 2 à Jacobienne décomposée
• Le 22 juin 2021 à 10:00
• Séminaire de Théorie Algorithmique des Nombres
Online
Vandita Patel University of Manchester
Shifted powers in Lucas-Lehmer sequences
The explicit determination of perfect powers in (shifted) non-degenerate, integer, binary linear recurrence sequences has only been achieved in a handful of cases. In this talk, we combine bounds for linear forms in logarithms with results from the modularity of elliptic curves defined over totally real fields to explicitly determine all shifted powers by two in the Fibonacci sequence. A major obstacle that is overcome in this work is that the Hilbert newspace which we are interested in has dimension 6144. We will focus on how this space is computationally handled with respect to the underlying Diophantine equation. This is joint work with Mike Bennett (UBC) and Samir Siksek (Warwick).
• Le 29 juin 2021 à 10:00
• Séminaire de Théorie Algorithmique des Nombres
Online
Pierre Briaud Inria Paris
An algebraic approach to the Rank Support Learning problem
Rank-metric code-based cryptography relies on the hardness of decoding a random linear code in the rank metric. The Rank Support Learning problem (RSL) is a variant where an attacker has access to N decoding instances whose errors have the same support and wants to solve one of them. This problem is for instance used in the Durandal signature scheme. In this talk, we will present a new algebraic attack on RSL. We build upon Bardet et al., Asiacrypt 2020, where similar techniques are used to solve MinRank and RD. However, our analysis is simpler and overall our attack relies on very elementary assumptions compared to standard GrÃ¶bner bases attacks. In particular, our results show that key recovery attacks on Durandal are more efficient than was previously thought. This is joint work with Magali Bardet.
• Le 6 juillet 2021 à 10:00
• Séminaire de Théorie Algorithmique des Nombres
Online
Anna Somoza IRMAR\, Université de Rennes 1
The Inverse Jacobian problem
To an algebraic curve $C$ over the complex numbers one can associate a non-negative integer $g$, the genus, as a measure of its complexity. One can also associate to $C$, via complex analysis, a $g\times g$ symmetric matrix $\Omega$ called period matrix. Because of the natural relation between $C$ and $\Omega$, one can obtain information about one by studying the other. Therefore, it makes sense to consider the inverse problem: Given a period matrix $\Omega$, can we compute a model for the associated curve $C$?
• Le 13 juillet 2021 à 15:00
• Séminaire de Théorie Algorithmique des Nombres
Salle de conférences
Jean Kieffer IMB
Équations modulaires en dimension supérieure, applications au calcul d'isogénies et au comptage de points

• Le 5 octobre 2021 à 10:00
• Séminaire de Théorie Algorithmique des Nombres
Salle 2
Henri Cohen IMB
Algebraic values of the hypergeometric function
In this talk, I will study the general problem of when the value of the hypergeometric function $F(a,b;c;z)$ is algebraic, assuming $a$,$b$,$c$, and $z$ rational. The results involve modular forms and functions, complex multiplication, Shimura curves, and computer searches.
• Le 12 octobre 2021 à 10:00
• Séminaire de Théorie Algorithmique des Nombres
Salle 2
Damien Robert IMB
Revisiter l'algorithme de Satoh de comptage de points en petite caractéristique par relèvement canonique
L'algorithme de Satoh de comptage de points sur les courbes elliptiques permet d'obtenir (aprÃ¨s des amÃ©liorations de Harvey) une complexitÃ© quasi-quadratique en le degrÃ© pour une (petite) caractÃ©ristique fixÃ©e $p$. Dans cet exposÃ© je passerai en revue plusieurs variantes de cet algorithme et ses extensions aux variÃ©tÃ©s abÃ©liennes. J'expliquerai ensuite comment on peut grandement simplifier l'implÃ©mentation de cet algorithme. L'implÃ©mentation dans Pari/GP du nouvel algorithme produit un gain d'un facteur 30 Ã  la fois de temps de calcul et de consommation mÃ©moire.
• Le 9 novembre 2021 à 10:00
• Séminaire de Théorie Algorithmique des Nombres
Salle 2
Koen de Boer CWI Amsterdam
Sampling relatively near-prime ideals
We show a method to sample an element alpha from a given ideal I, such that their quotient ideal (alpha)/I is a (possibly large) prime times a smooth number ('near-prime') with reasonable probability. This method consists of 'randomizing' the ideal I by multiplying it with small primes (yielding J) and consequently sampling the element alpha from this randomized ideal J intersected with a large box. The probability that the quotient (alpha)/J is prime (i.e., that the quotient (alpha)/I is a near-prime) is tightly related to density results on prime ideals (prime ideal theorem). As an application we show an efficient way to compute power residue symbols for varying degree number fields.
• Le 16 novembre 2021 à 10:00
• Séminaire de Théorie Algorithmique des Nombres
Salle 2
Benjamin Wesolowski CNRS\, IMB
SQISign: Compact Post-Quantum Signature from Quaternions and Isogenies
We will present the signature scheme SQISign, (for Short Quaternion and Isogeny Signature) exploiting isogeny graphs of supersingular elliptic curves. The signature and public key sizes combined are an order of magnitude smaller than all other post-quantum signature schemes. Its efficient implementation and security analysis open new research challenges.
• Le 23 novembre 2021 à 10:00
• Séminaire de Théorie Algorithmique des Nombres
Salle 2
Aurel Page IMB
Norm relations and class group computations
When $L/K$ is a Galois extension of number fields with Galois group $G$, some invariants of $L$ can be related to those of its proper subfields. I will present some old and some new such relations, and an application to the computation of class groups of some large number fields. This is joint work with Jean-FranÃ§ois Biasse, Claus Fieker and Tommy Hofmann.
• Le 30 novembre 2021 à 10:00
• Séminaire de Théorie Algorithmique des Nombres
Salle 2
Katharina Boudgoust IRISA EMSEC\, Rennes
The partial Vandermonde knapsack problem
In my seminar I will do an introduction to the concept of essential dimension: roughly speaking, the essential dimension is a measure of how many independent parameters we need to describe some algebraic object. The concept of essential dimension was introduced by Buhler and Reichstein in 1995 and it is linked to an algebraic version of Hilbert's 13th problem. For a finite group $G$; the essential dimension measures how much one can compress a faithful representation of $G$. When $G$ is the symmetric group $S_n$ the essential dimension tells us how many independent parameters we need to write a generic polynomial of degree $n$ on a field $k$ of characteristic zero; equivalently, the essential dimension of $S_n$ computes the number of parameters needed to write a generating polynomial for separable field extensions of degree $n$. This is still an open problem for \$n geq 8. Suprisingly, the analogue problem for inseparable field extensions has been solved explicitely.
• Le 30 novembre 2021 à 10:00
• Séminaire de Théorie Algorithmique des Nombres
Salle 2
Katharina Boudgoust IRISA EMSEC\, Rennes
The partial Vandermonde knapsack problem
This work contributes in the field of lattice-based cryptography, a research domain of public key cryptography that was initiated at the end of the 1990s by two different branches. On the one had, there have been proposals benefiting from strong theoretical connections to presumed hard worst-case lattice problems, leading to the development of public key cryptography based on the SIS (Short Integer Solution) and LWE (Learning With Errors) problems. On the other hand, very efficient schemes basing their security on average-case structured lattice problems have been introduced, the most popular among them is the NTRU encryption scheme.
• Le 7 décembre 2021 à 10:00
• Séminaire de Théorie Algorithmique des Nombres
Salle 386
Olivier Bernard IRISA EMSEC\, Rennes
Log-S-unit lattices using Explicit Stickelberger Generators to solve Approx Ideal-SVP
The Twisted-PHS algorithm to solve Approx-SVP for ideal lattices on any number field, based on the PHS algorithm by Pellet-Mary, Hanrot and StehlÃ© in 2019, was introduced in 2020. The authors performed experiments for prime conductors cyclotomic fields of degrees at most 70, reporting exact approximation factors reached in practice. The main obstacle for these experiments is the computation of a log-S-unit lattice, which requires classical subexponential time.
• Le 14 décembre 2021 à 10:00
• Séminaire de Théorie Algorithmique des Nombres
Online
Xavier Goaoc Université de Lorraine\, LORIA
Un phénomène de concentration en géométrie combinatoire