2017 - 2018
- Vendredi 15 septembre 2017
Victor Cauchois (IRMAR) - Vendredi 6 octobre 2017
Journée de rentrée de l'équipe
10h45 – 11h30, Codes correcteurs d'erreur (par P. Loidreau)
13h15 – 14h00, Géométrie algébrique réelle (par M.-F. Roy)
14h15 – 15h00, Courbes algébriques (par C. Ritzenthaler)
15h15 – 16h00, Précision p-adique (par X. Caruso) - Vendredi 13 octobre 2017
Johannes Hoffmann (RWTH Aachen University)
A Constructive Approach to Arithmetics in Ore Localizations
Classical results of Ore from the 1930's tell, that for a domain R, a localization with respect to a multiplicatively closed set S exists if S satisfies left Ore property. We investigate the arithmetics of the localized ring S^{-1}R from both theoretical and practical points of view. We show that effective computations in S^{-1}R require a specialization of the type of S and distill three most frequently occuring types of Ore sets. We provide an implementation of arithmetics over ubiquitous G-algebras in Singular:Plural and discuss algorithmic and theoretic questions in this context. - Vendredi 20 octobre 2017
Peter Stevenhagen (Université de Leiden)
Ellpitic primitive Roots - Vendredi 27 octobre 2017
Vincent Neiger (Université de Limoges)
Efficient algorithms for computing univariate relations
In this talk, we will present recent results about the fast computation of univariate relations, including in particular rational interpolants and Hermite-Padé approximants. Such relations are a central tool in computer algebra, arising in situations such as the guessing of linear differential equations, the list-decoding of Reed-Solomon codes, or the computation of normal forms of polynomial matrices. After giving an overview of the problem and of existing fast algorithms, the emphasis will be placed on the main ideas behind the recent algorithmic improvements.
This talk involves joint work with Claude-Pierre Jeannerod, Johan Rosenkilde, Eric Schost, Grigory Solomatov, Gilles Villard, and Vu Thi Xuan. - Vendredi 10 novembre 2017
Everett Howe (Center for Communications Research)
Constructions of curves of medium genus over F_q with many points - Vendredi 17 novembre 2017
André Leroy (Université d'Artois)
Sur les factorisations dans les extensions de Ore
On commencera par définir une notion d'évaluation pour les polynômes de Ore à coefficients dans un anneau. On introduira ensuite les transformations pseudo linéaires et on définira les notions de polynômes de Wedderburn et de polynômes complètement réductibles. Après avoir donné plusieurs caractérisations de ces polynômes on s'intéressera à leurs factorisations en particulier dans le cas ou l'anneau de base est un anneau à division. On présentera aussi le comptage des racines généralisant et précisant le résultat de Gordon-Motzkin. On abordera la question de factorisation dans des anneaux généraux et on introduira la notion d'anneaux de polynômes de Ore libre qui semble être le bon moyen d'aborder l'évaluation à plusieurs variables gauches. - Vendredi 24 novembre 2017
Beth Malmskog (Colorado College)
Locally Recoverable Codes with Many Recovery Sets from Fiber Products of Curves
An error-correcting code is said to be locally recoverable if any symbol in a code word can be recovered by accessing a subset of the other symbols. This subset is known as the helper or recovery set for the given symbol. Locally recoverable codes (LRCs) have benefits for distributed storage applications. It may be desirable to have many disjoint recovery sets for each symbol, in case of multiple server failures or to provide many options for recovery. Barg, Tamo, and Vladut recently constructed LRCs with one and two disjoint recovery sets from algebraic curves. This talk presents a generalization of this construction to three or more recovery sets using iterated fiber products of curves. The construction is applied to give including the Suzuki and generalized Giulietti-Korchmaros curves. Codes with arbitrarily many recovery sets are constructed, employing maximal curves from fiber products devised by Van der Geer and Van der Vlugt. This is joint work with Kathryn Haymaker and Gretchen Matthews. - Vendredi 1er décembre 2017
Ignacio García Marco (I2M, Université d'Aix-Marseille)
Noether Resolutions
Let \(R := K[x_1,\ldots,x_n]\) be a polynomial ring over an infinite field \(K\), and let \(I \subset R\) be a graded ideal. We say that \(A := K[x_1,\ldots,x_d]\) is a Noether normalization of \(R/I\) if \(A \hookrightarrow R/I\) is an integral extension. Whenever \(A\) is a Noether normalization of \(R/I\), then \(R/I\) is a finitely generated \(A\)-module and, thus, it has a finite minimal graded free resolution as \(A\)-module. In this talk we will study this resolution, which we call the Noether resolution of \(R/I\). When the Krull dimension of \(R/I\) is 1 or 2 we provide an algorithm for obtaining this resolution that involves the computation of a particular Gröbner basis of \(I\). When \(R/I\) is a semigroup ring we will also explain how one can replace the Gröbner basis computation by computations in the underlying semigroup. - Vendredi 15 décembre 2017
Adrien Poteaux (Université de Lille)
A dichotomic Newton-Puiseux algorithm using dynamic evaluation.
Puiseux series (generalisation of Taylor series above critical points) are a fundamental object in the theory of plane algebraic curves. This talk will focus on the arithmetic complexity of the well-known Newton Puiseux algorithm and its variants. Denoted \(D\) the total degree of the input bivariate polynomial, Duval proved a \(O(D^8)\) complexity result. This has been improved to \(\tilde O(D^5)\) by truncating powers of \(X\) during the computation and introducing fast multiplication.
After providing the tools of the Newton-Puiseux algorithm, we will first present some results that enable to reduce the total number of recursive calls of the algorithm from \(O(D^2)\) to \(\tilde O(D)\), leading to a complexity in \(\tilde O(D^4)\). Finally, we will present a new divide and conquer algorithm that reduces the complexity to \(\tilde O(D^3)\).
This work begun during my PhD, under the supervision of Marc Rybowicz; the recent ameliorations started from a collaboration with Marc in 2011. The new divide and conquer algorithm is a collaboration with Martin Weimann. This paper is dedicated to Marc Rybowicz, who sadly passed away in November 2016. - Vendredi 19 janvier 2018
Enrique González Jiménez (Universidad Autónoma de Madrid)
Growth of torsion of elliptic curves.
One of the main goals in the theory of elliptic curves is to characterize the possible torsion structures over a given number field, or over all number fields of a given degree. One of the milestone in this subject was the characterization of the rational case given by Mazur in 1978. Later, the quadratic case was obtained by Kamienny, Kenku and Momose in 1992. For greater degree a complete answer for this problem is still open, although there have been some advances in the last years.
The purpose of this talk is to shed light on how the torsion group of an elliptic curve defi ned over the rationals grows upon base change.
This is an ongoing project partially joint with A. Lozano-Robledo, F. Najman and J. M. Tornero. - Vendredi 26 janvier 2018
Chloe Martindale (Technical University of Eindhoven)
Isogeny graphs of abelian varieties and applications to the discrete logarithm problem.
An isogeny graph is a graph whose vertices correspond to abelian varieties (with some structure) and whose edges correspond to isogenies of a certain degree. The structure of isogeny graphs for elliptic curves was first studied by David Kohel in his PhD thesis and has since been an essential tool in algorithmic number theory (for example to compute the endomorphism ring of an ordinary elliptic curve over a finite field) and cryptography (for example in the post-quantum cryptographic protocol SIDH). We present a structure theorem for isogeny graphs of ordinary abelian varieties, and explain how, under some heuristic assumptions, this can be applied to attacking the discrete logarithm problem for genus 3 curves and possibly some families of elliptic curves. - Vendredi 2 février 2018
Marius Vuille (École Polytechnique Fédérale de Lausanne)
Computing cyclic isogenies between principally polarized abelian varieties over finite fields.
The explicit computation of isogenies between abelian varieties over finite fields is an interesting problem that finds its applications not only in transporting instances of the Discrete Logarithm Problem, but can also be used to compute endomorphism rings or even in point counting. So far, only isogenies with kernel a maximal isotropic subgroup of the \ell - torsion have been described and implemented. We describe an algorithm to compute isogenies with cyclic kernels, provided they exist. - Vendredi 9 février 2018
Frédéric Bihan (Université de Savoie)
Croissance du volume mixte pour les polytopes convexes et une règle de Cramer pour les systèmes polynomiaux.
Si P_1,...,P_n, Q_1,...,Q_n sont des polytopes convexes à sommets dans le réseau des points entiers de R^n et que P_i est inclus dans Q_i pour tout i, alors le volume mixte de (P_1,...,P_n) est majoré par celui de (Q_1,...,Q_n). Dans un travail récent avec Ivan Soprunov (Cleveland University), nous caractérisons les paires de n-uplets de polytopes pour lesquelles cette inégalité est stricte. Le lien entre volume mixte et systèmes polynomiaux est le théorème de Bernstein-Kouchnirenko qui prédit que le nombre de solutions dans le tore complexe d'un système polynomial de polytopes de Newton P_1,...,P_n est génériquement égal au volume mixte de ces polytopes. On utilise un de nos critères pour obtenir une règle de Cramer pour les systèmes polynomiaux qui généralise celle connue dans le cas linéaire. - Vendredi 16 février 2018
Fabien Pazuky (Université de Copenhagen)
Courbes elliptiques et isogénies.
Deux courbes elliptiques E et E' définies sur un corps de nombres K sont isomorphes sur la clôture algébrique de K si et seulement si elles ont le même j-invariant. On se pose la question suivante : comment est-ce que ce j-invariant varie dans les classes d'isogénies ? On montre une majoration de la différence des hauteurs des j-invariants de courbes elliptiques isogènes et on en déduit plusieurs conséquences, notamment une borne explicite sur la hauteur des polynômes modulaires et un contrôle des formules de Vélu. Si le temps le permet, on fera de plus une remarque sur les rangs de Mordell-Weil des courbes elliptiques. - Du lundi 19 au vendredi 23 février 2018
Conférence : Méthodes numériques pour les courbes algébriques - Vendredi 16 mars 2018
Joelle Saade (Université de Limoges)
A new approach for Formal Reduction of Singular Linear Differential Systems Using Eigenrings
In this talk, we will present a new algorithm for the formal reduction of linear differential systems with Laurent series coefficients. We show how to obtain a decomposition of Balser, Jurkat and Lutz using eigenring techniques. We establish structural information on the obtained indecomposable subsystems and retrieve information on their invariants such as ramification. We show why Barkatou's algorithm then perform well on these subsystems. We also give precise estimates of the precision on the power series which is required in each step of the algorithm. We give some examples computed in Maple. - Vendredi 23 mars 2018
Elif Saçıkara (Sabanci University)
Concatenated Structure of Quasi-Abelian Codes and a Resulting Minimum Distance Bound
For a positive integer l and a group algebra Fq[H], a quasi-abelian(QA)code of index l is a Fq[H]-submodule of Fq[H]^l, where H is an abelian group of order m. The special case H := Z_m, where Z_m is a cyclic group of order m, gives a quasi-cyclic (QC) code of index l and length ml. So, QA codes are natural generalization of QC codes. Ling and Sole showed that QC codes can be decomposed as a direct sum of certain linear codes of length l by applying the Chinese Remainder Theorem, such a method is called the CRT decomposition. Jensen represented a concatenated structure of QC codes and later Guneri-Ozbudak showed that these decompositions are equivalent. In this talk, we present a concatenated structure of QA codes by using the CRT decomposition of QA codes introduced by Jitman and Ling, and we show that both decompositions are equivalent. Concatenated structure also leads to asymtotical goodness and provides a general minimum distance bound, extending the analogue bound for QC codes due to Jensen. - Vendredi 30 mars 2018
Ivan Pogildiakov (Université de la Polynésie Française et IRMAR)
On the existence of hyperelliptic curves over finite fields and linear binary codes
Given integers q, N, and g, does there exist a (non-singular irreducible) genus g curve over F_q having presicely N rational points? Statistics on the distribution of the number of rational points were studied during the last decade for various families of curves. However, we know how to answer this question in several special cases only. In this talk we will discuss the question in the case of hyperelliptic curves. Given q and N, new bounds on the genera will be presented. Several problems in the theory of (linear binary) error correcting codes will naturally arise. We will consider, if time permits, the practical side of this question and the superelliptic case of the question as well. - Vendredi 6 avril 2018
John Cremona (University of Warwick)
Black Box Galois Representations.
The Serre-Faltings-Livne method concerns the comparison of two 2-dimensional p-adic Galois representations of the absolute Galois group G_K of a number field K in the case p=2. Assuming that both are known to be unramified outside the same set S of primes of K and that they have the same determinant, the method provides a finite set T of primes of K, disjoint from S and depending only on K and S, such that if the two representations have the same trace at the Frobenius elements of all the primes in T then they are isomorphic. When we describe a Galois representation with data (K, S, p) as a a "Black Box", we mean that the only information we know about it is the trace and determinant of Frobenius at any given prime not in S; in these terms, the SFL method allows us to determine whether two 2-adic black box representations are isomorphic. In this talk we consider black box representations from a slightly wider perspective, and consider how much information we can obtain about such a representation by asking only a finite number of questions, such as residual reducibility, the determinant character, and the size and structure of the isogeny class of the representation. This is joint work with Alejandro Argaez (p=2) and Mattia Sanna (p=3). - Vendredi 6 avril 2018
David Lubicz (DGA et IRMAR)
Quelques améliorations à l'algorithme AGM et ses généralisations en genre plus grand.
Nous décrivons des améliorations à l'algorithme de comptage de points AGM et ses généralisation en genre plus grand. Nous décrivons plus précisément un algorithme qui permet de retrouver efficacement la classe de similitude de l'action du morphisme de Frobenius (ou son dual) sur l'espace cotangent du relevé canonique de la variété abélienne de départ (définie sur un corps fini). Cet algorithme a un intérêt indépendamment de l'AGM. - Vendredi 13 avril 2018
Jade Nardi (Institut de Mathématiques de Toulouse)
Paramètres des codes correcteurs sur les surfaces de Hirzebruch.
Les surfaces de Hirzeburch forment une famille de surfaces réglées au-dessus de \(\mathbb P^1\) paramétrée par les entiers naturels. Leur structure de variétés toriques les munit chacunes d'un anneau gradué de polynômes très facile à manier, l'anneau de Cox. En se fixant un degré \(s\) (i.e. une composante homogène de l'anneau), on peut définir l'évaluation des polynômes de degré \(s\) en les points \(\mathbb F_q\)-rationnels de la surface et ainsi définir le codes d'évaluation associé à la manière des codes de Reed-Muller sur \(\mathbb P^n\). Le but de cet exposé est de déterminer explicitement les paramètres [n,k,d] de tels codes. La distance minimale, obtenue grâce à des outils de bases de Gröbner, nous permet de déduire une majoration du nombre de points \(\mathbb F_q\)-rationnels d'une courbe sur une surface de Hirzebruch en fonction de sa classe de Picard et même une forme des courbes qui atteignent ce majorant. - Vendredi 20 avril 2018
Pierre Loidreau (IRMAR)
Quoi de neuf en cryptographie post-quantique ?
Retour sur les propositions de systèmes de chiffrements post-quantiques candidats à la standarditsation par le NIST. - Vendredi 18 mai 2018
Aurel Page (INRIA, Bordeaux)
Algorithmes pour la topologie des variétés arithmétiques compactes et les opérateurs de Hecke
Un groupe arithmétique est un groupe commensurable aux points entiers d'un groupe algébrique linéaire défini sur les rationnels. D'après un théorème classique de Borel et Harish-Chandra, de tels groupes admettent une présentation finie; leur preuve a été rendue algorithmique par Grunwald et Segal, mais sans analyse de complexité de l'algorithme obtenu. Depuis quelques années, on s'intéresse beaucoup à des invariants plus profonds des groupes arithmétiques : leurs groupes de cohomologie, munis de l'action des opérateurs de Hecke. Je présenterai un travail en cours avec Michael Lipnowki : nous décrivons un algorithme qui, étant donné un groupe arithmétique \(\Gamma\) dont la variété arithmétique associée est compacte, calcule la cohomologie de \(\Gamma\) munie de l'action des opérateurs de Hecke, et nous analysons sa complexité. - Vendredi 25 mai 2018 — exceptionnellement à 14h
Alain Couvreur (INRIA, École Polytechnique)
Sur les récentes soumissions au NIST basées sur des codes algébriques
On présentera différents schémas de chiffrement basés sur des codes algébriques et ayant donné lieu à une soumission au NIST. On présentera également une attaque d'un type nouveau impactant la sécurité du schéma de chiffrement appelé DAGS. L'attaque est issue d'un travail en collaboration avec Élise Barelli. - Vendredi 8 juin 2018
Gilles Villard (CNRS, ÉNS de Lyon)
Computation of the resultant of two generic bivariate polynomials over a field
An algorithm is presented for computing the resultant of two generic bivariate polynomials over a field \(K\). For such \(p\) and \(q\) in \(K[x,y]\) of degree \(d\) in \(x\) and \(n\) in \(y\), the algorithm computes the resultant with respect to \(y\) using \((n^{2–\frac 1 \omega} d)^{1+o(1)}\) arithmetic operations in \( K\), where two \(n\times n\) matrices are multiplied using \(O(n^\omega)\) operations. Previous algorithms from the early 1970’s required time \((n^2 d)^{1+o(1)}\). We also discuss some extensions of the approach to the computation of characteristic polynomials of generic structured matrices and in univariate quotient algebras. - Vendredi 29 juin 2018
Vivien Beraud, Elie Eid, Fabien Narbonne (Univeriste de Rennes 1)
Soutenance de stage de M2
2016 - 2017
- Vendredi 23 septembre 2016
Céline Maistret (Warwick)
Invariants relatifs à la conjecture de parité. - Vendredi 30 septembre 2016
Thomas Cluzeau (XLIM, Limoges)
Un algorithme pour calculer l'algèbre de Lie du groupe de Galois différentiel d'un système différentiel linéaire. - Vendredi 7 octobre 2016
Davide Lombardo (Universität Hannover)
Endomorphismes des Jacobiennes des courbes de genre 2. - Vendredi 14 octobre 2016
Jeremy Le Borgne (IRMAR)
Multiplication rapide des polynômes tordus - Vendredi 18 novembre 2016
Fabien Cléry (Max Planck Institute)
Covariants de sextiques binaires et formes modulaires de Siegel de degré 2. - Vendredi 2 décembre 2016
Jean-Pierre Tillich (INRIA Paris)
Atteindre la capacité avec des codes de Reed-Solomon à travers la construction (U|U+V) et l'algorithme de décodage de Koetter et Vardy - Vendredi 9 décembre 2016
Alp Bassa (Bogazici University, Istanbul)
Rational points on high genus curves over finite fields - Vendredi 16 décembre 2016, 9h15
Soutenance de thèse de Loubna Ghammam (IRMAR)
Utilisation des couplages en cryptographie asymétrique pour la micro-électronique - Vendredi 16 décembre 2016, 10h30
Francesc Fite (Universitat Politècnica de Catalunya, Barcelone)
On the velocity of convergence towards the Sato--Tate measure. - Vendredi 6 janvier 2017
Guillaume Moroz (INRIA Nancy)
Un algorithme rapide pour le calcul du résultant tronqué - Vendredi 13 janvier 2017
Vanessa Vitse (Institut Fourier, Grenoble)
Résolution de systèmes polynomiaux sur F2 - Vendredi 27 janvier 2017
Sven Puchinger (Ulm University)
Fast Operations on Linearized Polynomials and their Applications in Coding Theory - Vendredi 3 février 2017, à 10h30
Piermarco Milione (Helsinki)
Algèbres de quaternions : arithmétique et applications - Vendredi 3 février 2017, à 14h, en commun avec le séminaire de cryptographie
Hervé Talé Kalachi (Université de Rouen et Université de Yaoundé, Cameroun )
Improved Cryptanalysis of Rank Metric Schemes Based on Gabidulin Codes. - Vendredi 10 février 2017
Formes modulaires, aspects théoriques et calculatoires - Vendredi 10 mars 2017, exceptionnellement à 14h
Samuele Anni (Heidelberg,Germany)
Le problème inverse de Galois, courbes hyperelliptiques et la conjecture de Goldbach. - Vendredi 17 mars 2017
Steve Szabo (Eastern Kentucky University)
Size Condition on Codes over Rings and Some Duality Preserving Grey Maps - Vendredi 7 avril 2017, 15h
Ene Milio (Postdoc, INRIA Nancy)
Calcul de fonctions sur les Jacobiennes et leurs quotients. - Vendredi 5 mai 2017
Michele Bolognesi (IMAG, Montpellier)
Aspects effectifs de l'arithmétique et de la géométrie des variétés abéliennes, des courbes et de leurs espaces de modules. - Mercredi 24 mai 2017, 10h30
Tristan Vaccon (XLIM, Limoges)
Un algorithme F5 tropical. - Vendredi 2 juin 2017
Thibaut Verron (Toulouse)
Régularité du calcul de bases de Gröbner pour les systèmes homogènes avec poids
2015 - 2016
- Vendredi 18 septembre 2015
Journée de rentrée de l'équipe - Vendredi 25 septembre 2015
Alessio Fiorentino (postdoc IRMAR)
A new proof of the characterization of plane quartics by their bitangents using Weber's formula - Vendredi 9 octobre 2015
Daniel Perrucci (Universidad de Buenos Aires)
Elementary recursive degree bounds for Positivstellensatz, Hilbert 17th problem and Real Nullstellensatz - Vendredi 16 octobre 2015
Sylvain Guilley (Telecom Paris)
Complementary Dual Codes for Counter-measures to Side-Channel Attacks - Vendredi 23 octobre 2015
Soutenance de thèse de Charles Savel - Vendredi 20 novembre 2015
David Lubicz (IRMAR)
Espaces de modules de variétés abéliennes munies de structures de niveau : une approche effective - Vendredi 4 décembre 2015
Soutenance de thèse de Gwezheneg Robert (à 14h) - Vendredi 11 décembre 2015
Aurel Page (Université de Warwick)
Torsion dans l'homologie des groupes kleinéens arithmétiques - Vendredi 18 décembre 2015
Adrien Poteaux (Lille)
Autour du calcul des séries de Puiseux - Vendredi 8 janvier 2016
Grey Violet (University of Konstanz)
Geometry of univariate stability: continuity argument, symmetric powers and stability theories - Vendredi 15 janvier 2016
Janko Boehm (Kaiserslautern)
Modular Techniques in Computational Algebraic Geometry - Vendredi 22 janvier 2016
Thomas Dreyfus (Université Lyon1)
Equations de Mahler et transcendance - Vendredi 22 janvier 2016
Adamou Otto (Université Abdou Moumouni, Niamey)
Analyse d'un modèle de transmission d'une maladie à deux souches avec traitement antibiotique par le calcul formel avec ou sans vaccination - Vendredi 29 janvier 2016
Jean-Michel Muller (LIP, ENS Lyon)
Rendre la virgule flottante plus rigoureuse - Vendredi 12 février 2016
Fabio Tanturri (Institut de Mathématiques de Marseille)
Factorisations matricielles et courbes dans P^4 - Vendredi 26 février 2016
Victor Cauchois (IRMAR)
Construction de matrices de diffusions optimales à partir de codes de Gabidulin 2-cycliques - Vendredi 4 mars 2016
Loubna Ghammam (IRMAR)
Le calcul du couplage Optimal Ate sur les courbes elliptiques - Vendredi 11 mars 2016
Clément Pernet (UJF Grenoble et LIP Lyon)
Computing the Rank Profile Matrix - Vendredi 18 mars 2016
Alexandre Le Meur (IRMAR)
Formules de Thomae généralisées aux cas des extensions galoisiennes résolubles de P^1 - Vendredi 25 mars 2016
Pierre Lairez (Berlin)
Une solution déterministe au 17e problème de Smale - Vendredi 1er avril 2016
Hugo Labrande (Nancy)
Computing Theta functions in quasi-optimal time - Vendredi 29 avril 2016
Christophe Ritzenthaler (IRMAR)
Reconstruction de courbes à partir de leurs invariants - Vendredi 13 mai 2016
Khalil Ghorbal (INRIA Rennes)
Caractérisation des variétés affines invariantes pour les équations différentielles algébriques - Vendredi 20 mai 2016
Tristan Vaccon (Rikkyo University)
Précision p-adique : exemples et applications - Vendredi 27 mai 2016
Turku-Ozlum Celik (IRMAR)
An Approach towards Weber's Formula - Vendredi 10 juin 2016
Frédéric Chyzak (INRIA Saclay)
Computing solutions of linear Mahler equations - Vendredi 1er juillet 2016
Egbert Rijke (Carnegie Mellon University)
Introduction to Homotopy Type Theory
