IMB > Recherche > Séminaires
Le 12 janvier 2021
à 10:00
Séminaire de Théorie Algorithmique des Nombres
Online
Alain Couvreur LIX -- Inria Saclay
On the hardness of code equivalence problems in rank metric
In recent years, the notion of rank metric in the context of coding theory has known many interesting developments in terms of applications such as space time coding, network coding or public key cryptography. These applications raised the interest of the community for theoretical properties of this type of codes, such as the hardness of decoding in rank metric or better decoding algorithms. Among classical problems associated to codes for a given metric, the notion of code equivalence has always been of the greatest interest. In this talk, we discuss the hardness of the code equivalence problem in rank metric for $\mathbb F_{q^m}$--linear and general rank metric codes.
Le 19 janvier 2021
à 10:00
Séminaire de Théorie Algorithmique des Nombres
Online
Renaud Vilmart LSV -- Inria Saclay
Une introduction aux circuits quantiques et au ZX-calcul
L'informatique quantique est de plus en plus un sujet brûlant, car elle promet bien des avantages, que ça soit pour la complexité de ses algorithmes, ou pour ce qu'elle permet en cryptographie. Dans cet exposé, nous allons d'abord voir les circuits quantiques : le modèle habituellement utilisé par les chercheurs et les ingénieurs pour décrire des processus quantiques. Nous nous intéresserons à une question fondamentale liée à ces circuits, celle de la complétude d'une théorie équationnelle. Nous présenterons ensuite le ZX-Calcul, un modèle issu de la théorie des catégories, qui répond, lui, positivement à cette même question.
Le 26 janvier 2021
à 10:00
Séminaire de Théorie Algorithmique des Nombres
Online
Mercedes Haiech Université Rennes 1
The Fundamental Theorem of Tropical Partial Differential Algebraic .Geometry
Given a partial differential equation (PDE), its solutions can be difficult, if not impossible, to describe. The purpose of the Fundamental theorem of tropical (partial) differential algebraic geometry is to extract from the equations certain properties of the solutions. More precisely, this theorem proves that the support of the solutions in $k[[t_1, \cdots, t_m]]$ (with $k$ a field of characteristic zero) can be obtained by solving a so-called tropicalized differential system.
Le 2 février 2021
à 10:00
Séminaire de Théorie Algorithmique des Nombres
Online
Bogdan Dina Ulm University
Isogenous hyperelliptic and non-hyperelliptic Jacobians with maximal complex multiplication
We analyze complex multiplication for Jacobians of curves of genus 3, as well as the resulting Shimura class groups and their subgroups corresponding to Galois conjugation over the reflex field. We combine our results with numerical methods to find CM fields $K$ for which there exist both hyperelliptic and non-hyperelliptic curves whose Jacobian has complex multiplication by $\mathbb{Z}_K$.
Le 2 mars 2021
à 10:00
Séminaire de Théorie Algorithmique des Nombres
Online
Jade Nardi Inria Saclay\, LIX
Explicit construction and parameters of projective toric codes
Toric codes, introduced by Hansen in 2002, generalize (weighted) Reed-Muller codes on other toric varieties than projective spaces. They consist of evaluation codes of monomials at tuples of non-zero coordinates, which correspond to the points on the dense torus contained in the associated toric variety. Our aim is to ‘projectivise’ these codes, in the same spirit that turns a Reed-Muller codes into a projective one: we consider codes obtained by evaluating global sections on the whole set of the rational points of a toric variety. We focus on simplicial toric varieties, which come with a nice quotient description, and we give an explicit construction of projective codes on them, as well as a combinatorial way to determine their parameters. 'Projectivizing' toric codes opens new possibilities of getting codes with excellent parameters, by extending some champion classical toric codes geometrically.
Le 9 mars 2021
à 10:00
Séminaire de Théorie Algorithmique des Nombres
Online
Cécile Armana LMB\, Université de Franche-Comté
Bornes de Sturm pour des formes automorphes sur les corps de fonctions
Les bornes de Sturm indiquent combien de coefficients de Fourier successifs suffisent à déterminer une forme modulaire. Pour les formes modulaires classiques, elles fournissent aussi des bornes sur le nombre d'opérateurs de Hecke engendrant l'algèbre du même nom. Cet exposé propose d'étudier la situation pour certaines formes automorphes, dites de Drinfeld, sur les corps de fonctions. Il s'agit d'un travail en commun avec Fu-Tsun Wei (National Tsing-Hua University, Taïwan).
Le 16 mars 2021
à 10:00
Séminaire de Théorie Algorithmique des Nombres
Online
Vincent Neiger Université de Limoges
Deterministic computation of the characteristic polynomial in the time of matrix multiplication
This talk describes joint work with Clément Pernet on an algorithm which computes the characteristic polynomial of a matrix over a field within the same asymptotic complexity, up to constant factors, as the multiplication of two square matrices. Previously, this was only achieved by resorting to genericity assumptions or randomization techniques, while the best known complexity bound with a general deterministic algorithm was obtained by Keller-Gehrig in 1985 and involves logarithmic factors. The new algorithm computes more generally the determinant of a univariate polynomial matrix in reduced form.
Le 16 mars 2021
à 10:00
Séminaire de Théorie Algorithmique des Nombres
Online
Vincent Neiger Université de Limoges
Deterministic computation of the characteristic polynomial in the time of matrix multiplication
This talk describes joint work with Clément Pernet on an algorithm which computes the characteristic polynomial of a matrix over a field within the same asymptotic complexity, up to constant factors, as the multiplication of two square matrices. Previously, this was only achieved by resorting to genericity assumptions or randomization techniques, while the best known complexity bound with a general deterministic algorithm was obtained by Keller-Gehrig in 1985 and involves logarithmic factors. The new algorithm computes more generally the determinant of a univariate polynomial matrix in reduced form.
Le 23 mars 2021
à 10:00
Séminaire de Théorie Algorithmique des Nombres
Online
Samuel Le Fourn Institut Fourier\, Université Grenoble Alpes
Recherche de points entiers sur une variété modulaire de dimension 3
La détermination effective des points entiers sur des variétés algébriques est un problème difficile, surtout en dimension plus grande que 1. Dans cet exposé, je présenterai brièvement deux approches naturelles pour les points entiers qui permettent dans des cas favorables de tous les trouver. En cherchant des raffinements de ces méthodes, on arrive à des problèmes combinatoires intéressants, que je mettrai en valeur dans le cas précis d'une variété "modulaire" de dimension 3, qu'on peut définir par une équation quartique dans $\mathbb{P}^4$.
Le 30 mars 2021
à 10:00
Séminaire de Théorie Algorithmique des Nombres
Online
Charles Fougeron IRIF\, Université de Paris
Dynamiques des algorithmes de fraction continue multidimensionnels
Motivés par la richesse de l'algorithme de Gauss qui permet de calculer efficacement les meilleurs approximation d'un nombre réel par des rationnels, beaucoup de mathématiciens ont proposé des généralisations de ces algorithmes pour approximer des vecteurs de dimension supérieure à 1. Citons pour exemple celui de Poincaré introduit à la fin du 19e siècle ou ceux de Brun et Selmer à la moitié du 20e siècle.
Le 6 avril 2021
à 10:00
Séminaire de Théorie Algorithmique des Nombres
Online
Marc Masdeu Universitat Autònoma de Barcelona
Numerical experiments with plectic Stark--Heegner points
Let $E/F$ be an elliptic curve defined over a number field $F$, and let $K/F$ be a quadratic extension. If the analytic rank of $E(K)$ is one, one can often use Heegner points (or the more general Darmon points) to produce (at least conjecturally) a nontorsion generator of $E(K)$. If the analytic rank of $E(K)$ is larger than one, the problem of constructing algebraic points is still very open. In very recent work, Michele Fornea and Lennart Gehrmann have introduced certain $p$-adic quantities that may be conjecturally related to the existence of these points. In this talk I will explain their construction, and illustrate with some numerical experiments that we have been able to carry out that support their conjecture. This is joint work with Michele Fornea and Xevi Guitart.
Le 27 avril 2021
à 10:00
Séminaire de Théorie Algorithmique des Nombres
Online
Ann Kiefer Luxembourg Centre for Educational Testing
Property (FA) of the unit group of $2$-by-$2$ matrices over an order in a quaternion algebra
We study property (FA) and its hereditary version for unit groups of $2$-by-$2$ matrices over orders in totally definite quaternion algebras with rational centres. In particular we consider the three matrix rings over totally definite rational quaternion algebras that can appear as Wedderbrun-Artin components of a group ring $\mathbb{Q}G$.
Le 4 mai 2021
à 10:00
Séminaire de Théorie Algorithmique des Nombres
Online
Barinder Banwait Harish-Chandra Research Institute
Explicit isogenies of prime degree over quadratic fields
Let $K$ be a quadratic field which is not an imaginary quadratic field of class number one. We describe an algorithm to compute a superset of the set of primes $p$ for which there exists an elliptic curve over $K$ admitting a $K$-rational $p$-isogeny. Combining this algorithm with recent work on the determination of quadratic points on low-genus modular curves, we determine - conditional upon the Generalised Riemann Hypothesis - the above set of isogeny primes for several quadratic fields, providing the first such examples after Mazur's 1978 determination for $K = \mathbb{Q}$. We will give a live demo of the Sage and PARI/GP implementations of the algorithm.
Le 11 mai 2021
à 10:00
Séminaire de Théorie Algorithmique des Nombres
Online
Weiqiang Wen Inria Rennes\, Irisa
On algorithms for solving Euclidean lattice problems in cryptography
In this talk, we will try to review the state-of-the-art of the algorithms for solving the Euclidean lattice problems underlying cryptography. In more details, this talk contains two parts. In the first part, we will focus on the lattice problems such as approximate Shortest Vector Problem (approx-SVP) and the lattice reduction algorithms as the best known solving algorithms so far. In particular, I will present an improved enumeration-based lattice reduction algorithm, which is shown to be (potentially) relevant to cryptanalysis. In the second part, we will instead consider a quantum problem that is computationally equivalent to approx-SVP. By directly solving a quantum problem, we may expect to have a more powerful use of the quantum computation. However, the best known algorithms for solving approx-SVP via solving this quantum problem, is not better than lattice reduction yet.
Le 18 mai 2021
à 10:00
Séminaire de Théorie Algorithmique des Nombres
Online
Aurore Guillevic Inria Nancy\, Loria
Computing Murphy-alpha in the special tower number field sieve algorithm and applications to pairing-based cryptography
Pairings on elliptic curves are involved in signatures, NIZK, and recently in blockchains (ZK-SNARKS). These pairings take as input two points on an elliptic curve $E$ over a finite field, and output a value in an extension of that finite field. Usually for efficiency reasons, this extension degree is a power of 2 and 3 (such as 12, 18, 24), and moreover the characteristic of the finite field has a special form. The security relies on the hardness of computing discrete logarithms in the group of points of the curve and in the finite field extension.
Le 25 mai 2021
à 10:00
Séminaire de Théorie Algorithmique des Nombres
Online
Razvan Barbulescu CNRS\, IMB
Quelques conséquences du programme de Mazur sur la cryptographie
Les algorithmes de factorisation d'entiers et ceux de calcul de logarithmes discrets, adaptés aux tailles cryptographiques, ont deux étapes pertinentes pour notre exposé : la sélection polynomiale et la cofactorisation. La première consiste à sélectionner deux polynômes homogènes $F(x,y)$ et $G(x,y)$ dans $\mathbb{Z}[x,y]$ tels que les entiers de l'ensemble $\{F(a,b)G(a,b)\mid a,b\in\text{ un rectangle },\gcd(a,b)=1 \}$ contiennent le plus possible d'entiers $B$-friables (ayant tous les facteurs premiers inférieurs à $B$). La deuxième consiste à factoriser des entiers de la forme $F(a,b)$ et $G(a,b)$.
Le 1er juin 2021
à 10:00
Séminaire de Théorie Algorithmique des Nombres
Online
Andreas Enge\, Bill Allombert\, Fredrik Johansson Inria\, CNRS\, Inria
Présentation de l'équipe LFANT pour les stagiaires
Cette séance spéciale est dédiée à l'accueil des stagiaires dans l'équipe LFANT. Après une présentation générale de l'équipe, nous présenterons deux logiciels que nous développons : PARI/GP et Arb.
Le 8 juin 2021
à 10:00
Séminaire de Théorie Algorithmique des Nombres
Online
Stéphane Ballet I2M\, Université Aix-Marseille
Optimization of the scalar complexity of Chudnovsky^2 multiplication algorithms in finite fields
We propose several constructions for the original multiplication algorithm of D.V. and G.V. Chudnovsky in order to improve its scalar complexity. We highlight the set of generic strategies who underlay the optimization of the scalar complexity, according to parameterizable criteria. As an example, we apply this analysis to the construction of type elliptic Chudnovsky2 multiplication algorithms for small extensions. As a case study, we significantly improve the Baum-Shokrollahi construction for multiplication in F256/F4.
Le 15 juin 2021
à 10:00
Séminaire de Théorie Algorithmique des Nombres
Online
Fabien Narbonne IRMAR\, Université de Rennes
Corps de modules des courbes de genre 2 à Jacobienne décomposée
Nous nous intéresserons aux de courbes de genre 2 dont la Jacobienne est géométriquement le produit de deux courbes elliptiques avec multiplication complexe par le même ordre (maximal). Nous proposerons un algorithme permettant de compter combien d'entre elles ont pour corps de modules Q. Pour cela nous développerons une équivalence de catégories entre certaines variétés abéliennes polarisées et des réseaux hermitiens. Il s'agit d'une généralisation d'un article de A. Gélin, E. Howe et C. Ritzenthaler de 2018 dans lequel la Jacobienne est le carré d'une même courbe elliptique.
Le 22 juin 2021
à 10:00
Séminaire de Théorie Algorithmique des Nombres
Online
Vandita Patel University of Manchester
Shifted powers in Lucas-Lehmer sequences
The explicit determination of perfect powers in (shifted) non-degenerate, integer, binary linear recurrence sequences has only been achieved in a handful of cases. In this talk, we combine bounds for linear forms in logarithms with results from the modularity of elliptic curves defined over totally real fields to explicitly determine all shifted powers by two in the Fibonacci sequence. A major obstacle that is overcome in this work is that the Hilbert newspace which we are interested in has dimension 6144. We will focus on how this space is computationally handled with respect to the underlying Diophantine equation. This is joint work with Mike Bennett (UBC) and Samir Siksek (Warwick).
Le 29 juin 2021
à 10:00
Séminaire de Théorie Algorithmique des Nombres
Online
Pierre Briaud Inria Paris
An algebraic approach to the Rank Support Learning problem
Rank-metric code-based cryptography relies on the hardness of decoding a random linear code in the rank metric. The Rank Support Learning problem (RSL) is a variant where an attacker has access to N decoding instances whose errors have the same support and wants to solve one of them. This problem is for instance used in the Durandal signature scheme. In this talk, we will present a new algebraic attack on RSL. We build upon Bardet et al., Asiacrypt 2020, where similar techniques are used to solve MinRank and RD. However, our analysis is simpler and overall our attack relies on very elementary assumptions compared to standard Gröbner bases attacks. In particular, our results show that key recovery attacks on Durandal are more efficient than was previously thought. This is joint work with Magali Bardet.
Le 6 juillet 2021
à 10:00
Séminaire de Théorie Algorithmique des Nombres
Online
Anna Somoza IRMAR\, Université de Rennes 1
The Inverse Jacobian problem
To an algebraic curve $C$ over the complex numbers one can associate a non-negative integer $g$, the genus, as a measure of its complexity. One can also associate to $C$, via complex analysis, a $g\times g$ symmetric matrix $\Omega$ called period matrix. Because of the natural relation between $C$ and $\Omega$, one can obtain information about one by studying the other. Therefore, it makes sense to consider the inverse problem: Given a period matrix $\Omega$, can we compute a model for the associated curve $C$?
Le 13 juillet 2021
à 15:00
Séminaire de Théorie Algorithmique des Nombres
Salle de conférences
Jean Kieffer IMB
Équations modulaires en dimension supérieure, applications au calcul d'isogénies et au comptage de points
Le 5 octobre 2021
à 10:00
Séminaire de Théorie Algorithmique des Nombres
Salle 2
Henri Cohen IMB
Algebraic values of the hypergeometric function
In this talk, I will study the general problem of when the value of the hypergeometric function $F(a,b;c;z)$ is algebraic, assuming $a$,$b$,$c$, and $z$ rational. The results involve modular forms and functions, complex multiplication, Shimura curves, and computer searches.
Le 12 octobre 2021
à 10:00
Séminaire de Théorie Algorithmique des Nombres
Salle 2
Damien Robert IMB
Revisiter l'algorithme de Satoh de comptage de points en petite caractéristique par relèvement canonique
L'algorithme de Satoh de comptage de points sur les courbes elliptiques permet d'obtenir (après des améliorations de Harvey) une complexité quasi-quadratique en le degré pour une (petite) caractéristique fixée $p$. Dans cet exposé je passerai en revue plusieurs variantes de cet algorithme et ses extensions aux variétés abéliennes. J'expliquerai ensuite comment on peut grandement simplifier l'implémentation de cet algorithme. L'implémentation dans Pari/GP du nouvel algorithme produit un gain d'un facteur 30 à la fois de temps de calcul et de consommation mémoire.
Le 9 novembre 2021
à 10:00
Séminaire de Théorie Algorithmique des Nombres
Salle 2
Koen de Boer CWI Amsterdam
Sampling relatively near-prime ideals
We show a method to sample an element alpha from a given ideal I, such that their quotient ideal (alpha)/I is a (possibly large) prime times a smooth number ('near-prime') with reasonable probability. This method consists of 'randomizing' the ideal I by multiplying it with small primes (yielding J) and consequently sampling the element alpha from this randomized ideal J intersected with a large box. The probability that the quotient (alpha)/J is prime (i.e., that the quotient (alpha)/I is a near-prime) is tightly related to density results on prime ideals (prime ideal theorem). As an application we show an efficient way to compute power residue symbols for varying degree number fields.
Le 16 novembre 2021
à 10:00
Séminaire de Théorie Algorithmique des Nombres
Salle 2
Benjamin Wesolowski CNRS\, IMB
SQISign: Compact Post-Quantum Signature from Quaternions and Isogenies
We will present the signature scheme SQISign, (for Short Quaternion and Isogeny Signature) exploiting isogeny graphs of supersingular elliptic curves. The signature and public key sizes combined are an order of magnitude smaller than all other post-quantum signature schemes. Its efficient implementation and security analysis open new research challenges.
Le 23 novembre 2021
à 10:00
Séminaire de Théorie Algorithmique des Nombres
Salle 2
Aurel Page IMB
Norm relations and class group computations
When $L/K$ is a Galois extension of number fields with Galois group $G$, some invariants of $L$ can be related to those of its proper subfields. I will present some old and some new such relations, and an application to the computation of class groups of some large number fields. This is joint work with Jean-François Biasse, Claus Fieker and Tommy Hofmann.
Le 30 novembre 2021
à 10:00
Séminaire de Théorie Algorithmique des Nombres
Salle 2
Katharina Boudgoust IRISA EMSEC\, Rennes
The partial Vandermonde knapsack problem
In my seminar I will do an introduction to the concept of essential dimension: roughly speaking, the essential dimension is a measure of how many independent parameters we need to describe some algebraic object. The concept of essential dimension was introduced by Buhler and Reichstein in 1995 and it is linked to an algebraic version of Hilbert's 13th problem. For a finite group $G$; the essential dimension measures how much one can compress a faithful representation of $G$. When $G$ is the symmetric group $S_n$ the essential dimension tells us how many independent parameters we need to write a generic polynomial of degree $n$ on a field $k$ of characteristic zero; equivalently, the essential dimension of $S_n$ computes the number of parameters needed to write a generating polynomial for separable field extensions of degree $n$. This is still an open problem for $n geq 8. Suprisingly, the analogue problem for inseparable field extensions has been solved explicitely.
Le 30 novembre 2021
à 10:00
Séminaire de Théorie Algorithmique des Nombres
Salle 2
Katharina Boudgoust IRISA EMSEC\, Rennes
The partial Vandermonde knapsack problem
This work contributes in the field of lattice-based cryptography, a research domain of public key cryptography that was initiated at the end of the 1990s by two different branches. On the one had, there have been proposals benefiting from strong theoretical connections to presumed hard worst-case lattice problems, leading to the development of public key cryptography based on the SIS (Short Integer Solution) and LWE (Learning With Errors) problems. On the other hand, very efficient schemes basing their security on average-case structured lattice problems have been introduced, the most popular among them is the NTRU encryption scheme.
Le 7 décembre 2021
à 10:00
Séminaire de Théorie Algorithmique des Nombres
Salle 386
Olivier Bernard IRISA EMSEC\, Rennes
Log-S-unit lattices using Explicit Stickelberger Generators to solve Approx Ideal-SVP
The Twisted-PHS algorithm to solve Approx-SVP for ideal lattices on any number field, based on the PHS algorithm by Pellet-Mary, Hanrot and Stehlé in 2019, was introduced in 2020. The authors performed experiments for prime conductors cyclotomic fields of degrees at most 70, reporting exact approximation factors reached in practice. The main obstacle for these experiments is the computation of a log-S-unit lattice, which requires classical subexponential time.
Le 14 décembre 2021
à 10:00
Séminaire de Théorie Algorithmique des Nombres
Online
Xavier Goaoc Université de Lorraine\, LORIA
Un phénomène de concentration en géométrie combinatoire
Le type d'ordre d'une séquence de points du plan est une généralisation de la permutation associée à une séquence de nombres réels. Cette structure combinatoire encode de nombreuses propriétés géométriques de la séquence de points, par exemple le treillis des faces de son enveloppe convexe, ou encore les triangulations qu'elle supporte.
Séminaire de Théorie Algorithmique des Nombres
Responsables : Razvan Barbulescu et Wessel Van Woerden
Afficher 2022 - 2021 - 2020 - 2019 - 2018 - 2017 - 2016 - 2015 - antérieurs
Institut de Mathématiques de Bordeaux UMR 5251
Université de Bordeaux
351, cours de la Libération - F 33 405 TALENCE
Tél: +33 (0)5 40 00 60 70
institut
math.u-bordeaux.fr
