Séminaire de géométrie et algèbre effectives (2016-2017)


Le séminaire se tient en salle 16 du RDC de la tour de maths les vendredis à 10h30 (campus de Beaulieu).

Vendredi 5 mai
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.

Dans cet exposé, je vais décrire la construction, à l'aide des fonctions thêta constantes, de certains espaces de modules de surfaces abéliennes, dotées d'une structure thêta symétrique et d'une thêta caractéristique. Je passerai ensuite à l’étude de leur géométrie birationnelle et notamment de leur dimension de Kodaira, en me concentrant sur un cas particulier, qui révèle un lien plutôt surprenant avec un nouveau type de variété de sommes de puissances. C'est un travail en collaboration avec A. Massarenti (UFF- Rio de Janeiro).
Mercredi 24 mai, 10h30
Tristan Vaccon (XLIM, Limoges)
Un algorithme F5 tropical

Le calcul de base de Gröbner est un outil fondamental en géométrie et algèbre effectives. Les algorithmes F4 et F5 de Faugère sont reconnus comme parmi les plus efficaces pour de tels calculs. Dans cet exposé, nous présenterons ces algorithmes et expliquerons comment l'algorithme F5 peut être modifié pour le calcul de bases de Gröbner tropicales. Celles-ci ont été définies pour des besoins en géométrie tropicale, mais sont aussi très prometteuses en ce qui concerne les calculs effectifs sur des corps valués (e.g. le corps des nombres p-adiques) grâce à leur bon comportement vis-à-vis de la précision. Nous détaillerons ce phénomène. Il s'agit d'un travail en commun avec Kazuhiro Yokoyama (Rikkyo University, Japon).
Vendredi 2 juin
Thibaut Verron (Toulouse)
Régularité du calcul de bases de Gröbner pour les systèmes homogènes avec poids

Les étapes d'un calcul de bases de Gröbner pour un système homogène générique peuvent être décrites avec précision, et la complexité du calcul est bien maîtrisée dans ce cas. Pour les systèmes inhomogènes, sous des
hypothèses de généricité portant sur les composantes de plus haut degré des polynômes du système, les algorithmes ont un comportement "régulier" et les mêmes bornes de complexité s'appliquent.
En revanche, en l'absence de telles conditions de généricité, on ne peut pas a priori prédire la complexité du calcul. Dans ce travail, on s'intéresse à la structure homogène avec poids : étant donné n entiers positifs (les poids) $w_1, ..., w_n$, on considère le degré pondéré des monômes, défini, pour un monôme $X_1^a_1 ... X_n^a_n$ comme $\sum w_i a_i$.
De nombreuses applications font apparaître des systèmes inhomogènes dont les composantes de plus haut degré pondéré, pour un bon système de poids, satisfont des hypothèses de régularité. Pour ces systèmes, on montre
comment une stratégie de calcul usuelle pour la structure homogène avec poids permet de retrouver un comportement "régulier" pour les algorithmes, et comment on peut en déduire des bornes de complexité.
 
 
 

 Séances passées (2016-17)

 

 

Vendredi 23 septembre 2016
Céline Maistret (Warwick)
Invariants relatifs à la conjecture de parité.

Soit K un corps des nombres et A/K une variété abélienne. Les points de A à coordonnées dans K forment un groupe abélien finiment engendré par r(A/K) générateurs. Déterminer le rang r(A/K) d'une variété abélienne donnée est une question ouverte majeure qu'il est possible de rendre plus abordable en se contentant de trouver s'il existe un nombre pair ou impair de générateurs. Il s'agit de la conjecture de parité, connue sous certaines conditions pour les courbes elliptiques ainsi que les Jacobiennes de courbes hyperelliptiques de genre 2. Dans ces deux cas, la preuve repose de manière cruciale sur l'utilisation d'invariants associés aux courbes concernées. Nous nous proposons de présenter ces invariants pour une courbe elliptique ainsi que leur généralisation aux courbes hyperelliptiques de genre 2. Afin de tenter d'en comprendre la nature et leur généralisation à toutes variétés abéliennes, nous détaillerons leurs propriétés et leur rôle dans la determination de la parité du rang.
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.

On considère un système différentiel linéaire [A] : y' = Ay où A est une matrice carrée à coefficients dans C(x). Le groupe de Galois différentiel G de [A] est un groupe linéaire algébrique qui mesure les relations algébriques entre les solutions. Bien qu'il existe dans la littérature des algorithmes généraux pour calculer G, aucun d'entres eux n'est praticable ou implémenté. Dans cet exposé, je proposerai un algorithme pour calculer non pas le groupe G mais son algèbre de Lie g dans le cas d'un système absolument irréductible. Les outils utilisés seront des techniques de décomposition de systèmes différentiels via l'eigenring, des calculs modulaires basés sur la p-courbure, des calculs de conjugaisons entre algèbres de Lie semi-simples et la notion de forme réduite d'un système différentiel. L'algorithme présenté est implémenté dans le logiciel de calcul formel Maple. C'est un travail en collaboration avec Moulay Barkatou (Univ. de Limoges, XLIM), Lucia Di Vizio (Univ. de Versailles - St Quentin) et Jacques-Arthur Weil (Univ. de Limoges, XLIM).
Vendredi 7 octobre 2016
Davide Lombardo (Universität Hannover) 
Endomorphismes des Jacobiennes des courbes de genre 2.

Résumé.
Vendredi 14 octobre 2016
Jeremy Le Borgne (IRMAR)
Multiplication rapide des polynômes tordus

Dans cet exposé, nous présenterons un algorithme de multiplication rapide pour les polynômes tordus. Après avoir rappelé ce que sont ces polynômes et dans quels contextes ils peuvent apparaître, nous décrirons un algorithme de multiplication rapide, d’abord dans un cadre modulaire, puis général, qui améliore les meilleures complexités connues. Nous donnerons quelques conséquences pour la complexité d’autres problèmes faisant intervenir les polynômes tordus, notamment le décodage des codes de Gabidulin.
Vendredi 18 novembre 2016
Fabien Cléry (Max Planck Institute)
Covariants de sextiques binaires et formes modulaires de Siegel de degré 2.

Dans cet exposé, nous expliquerons comment construire des formes modulaires de Siegel de degré 2 à valeurs vectorielles via la théorie des covariants de sextiques binaires. Tout au long de l'exposé, nous insisterons sur des exemples concrets pour montrer l'efficacité de cette méthode. Il s'agit d'un travail commun avec Carel Faber et Gerard van der Geer.
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
(travail en commun avec Irene Màrquez-Corbella).

Dans cet exposé, nous montrons comment on peut atteindre la capacité de tout canal de communication pour peu qu'il soit sans mémoire et symétrique au moyen de codes de Reed-Solomon décodés avec l'algorithme de Koetter-Vardy. Pour cela on considère une construction de type $(U|U+V)$ itérative avec des codes composants qui sont des codes de Reed-Solomon justement. Notre construction peut être vue comme une variation sur les codes polaires. L'intérêt de cette variante est que l'on peut montrer que la probabilité d'erreur décroit beaucoup plus vite vers $0$ que pour les codes polaires. On peut encore améliorer le comportement de la probabilité d'erreur après décodage en utilisant des codes géométriques à la place de codes de Reed-Solomon. Par ailleurs, cette construction peut aussi être utilisée dans un schéma de chiffrement à clé publique de type McEliece et permet ici d'éviter a priori les attaques algébriques qui ont entaché le schéma de McEliece à base de codes de Reed-Solomon.
Vendredi 9 décembre 2016
Alp Bassa (Bogazici University, Istanbul)
Rational points on high genus curves over finite fields

In this talk we will be concerned with rational points on algebraic curves over finite fields. The central result in this area is without doubt the Hasse—Weil Theorem, which implies strong bounds on the number of rational points. As noticed by Ihara, for curves of large genus this bound can be improved significantly. In this talk we be interested in the question of how many rational points a high genus curve over a finite field can have. We will introduce several approaches to this problem and present a recent result (joint work with Beelen, Garcia, Stichtenoth) which provides strong lower bounds for the maximal possible number of rational points on curves over non-prime 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

10h30
Francesc Fite (Universitat Politècnica de Catalunya, Barcelone)
On the velocity of convergence towards the Sato--Tate measure.

Attached to an abelian variety $A$ of dimension $g$ and defined over a number field there is a compact real Lie subgroup $G$ of $\mathrm{USp}(2g)$, whose Haar measure $\mu$ conjecturally governs the asymptotic distribution of the Frobenius elements attached to $A$.
In this talk we relate the velocity of the (conjectural) convergence of the Frobenius elements distributions towards the measure $\mu$ with the asymptotic $L^2$-norm of a certain counting function attached to any virtual character of $G$. The main result of the talk is the computation, under GRH and an automorphy assumption, of a formula for this asymptotic $L^2$-norm. This is achieved by following the methods introduced by Sarnak to study Chebyshev's bias in the sign of the Frobenius traces of an elliptic curve in terms of its Mordell--Weil group rank. From the formula, and assuming the Birch and Swinnerton--Dyer conjecture, one also observes a direct influence of the rank of the Mordell--Weil group of $A$ on the velocity of convergence of the Frobenius elements distributions towards $\mu$. Additionally, the formula provides theoretical support to Shieh's experimental observation that the irreducible characters of $G$ exhibit a better convergence than that of the moments of $G$.
This is a joint work with Xevi Guitart.
Vendredi 6 janvier 2017
Guillaume Moroz (INRIA Nancy)
Un algorithme rapide pour le calcul du résultant tronqué

Soient P et Q deux polynômes de K[x][y], de degrés au plus d, et à coefficients dans l'anneau K[x], où K est un corps. Le résultant de P et Q est un polynôme R de K[x] de degré au plus 2d². Le meilleur algorithme connu pour calculer R requiert Õ(d^3) opérations arithmétiques dans K, où la notation Õ signifie que nous omettons les facteurs poly-logarithmiques. Nous montrerons que si l'on s'intéresse uniquement à calculer les k premiers coefficients de R, il existe un algorithme permettant de calculer R mod x^k en Õ(kd) opérations dans K.
Vendredi 13 janvier 2017
Vanessa Vitse (Institut Fourier, Grenoble)
Résolution de systèmes polynomiaux sur F2

De nombreux algorithmes existent pour tenter de résoudre des systèmes polynomiaux multivariés, mais leur complexité est en général difficile à établir. Dans cet exposé, on présentera plusieurs de ces méthodes ainsi que les outils permettant de donner des bornes sur leurs complexités, en particulier dans le cas où le corps de base est F2.
Vendredi 20 janvier 2017
-- JNCF 2017 au CIRM du lundi 16 au vendredi 20 janvier midi
-- Séminaire CCA la journée du vendredi
Vendredi 27 janvier 2017
Sven Puchinger (Ulm University)
Fast Operations on Linearized Polynomials and their Applications in Coding Theory

In this talk, we consider algorithms for operations on linearized polynomials. We present fast algorithms for division, multi-point evaluation, finding minimal subspace polynomials, and interpolation. The complexity of all these operations is sub-quadratic in the $q$-degree of the linearized polynomials, also if the degree of the polynomials is in the order of the degree of the underlying field extension. We briefly explain how this leads to the first error and erasure decoding algorithm for Gabidulin codes with sub-quadratic complexity. This is a joint work with Antonia Wachter-Zeh.
Vendredi 3 février 2017, à 10h30
Piermarco Milione (Helsinki)
Algèbres de quaternions : arithmétique et applications
Résumé

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.

In this presentation, we prove that any variant of the GPT cryptosystem which uses a right column scrambler over the extension field as advocated by the works of Gabidulin et al. with the goal to resist to Overbeck’s structural attack are actually still vulnerable to that attack. We show that by applying the Frobenius operator appropriately on the public key, it is possible to build a Gabidulin code having the same dimension as the original secret Gabidulin code but with a lower length. In particular, the code obtained by this way correct less errors than the secret one but its error correction capabilities are beyond the number of errors added by a sender, and consequently an attacker is able to decrypt any ciphertext with this degraded Gabidulin code.

A joint work with Ayoub OTMANI and Selestin NDJEYA.
Vendredi 10 février
Formes modulaires, aspects théoriques et calculatoires 
Vendredi 10 mars, exceptionnellement à 14h
Samuele Anni (Heidelberg,Germany)
Le problème inverse de Galois, courbes hyperelliptiques et la conjecture de Goldbach.

Le problème inverse de Galois est l'un des plus grands problèmes ouverts dans la théorie des groupes et aussi un des plus faciles à énoncer: chaque groupe fini est-il un groupe de Galois ? Mon intérêt pour ce problème est lié à la réalisation de groupes linéaires et symplectiques en tant que groupes de Galois sur Q et sur les corps de nombres. Dans cet exposé, je donnerai des exemples de réalisations uniformes (par exemple GSp_2g (F_l) pour tous premiers l) en utilisant des courbes elliptiques et des courbes de genre 2. Après cette introduction, je vais expliquer comment étendre ces résultats à des genres plus grands en utilisant les jacobiennes de courbes hyperelliptiques (travail en cours avec Vladimir Dokchitser). Ici, la conjecture de Goldbach aura un rôle central.
Vendredi 17 mars
Steve Szabo (Eastern Kentucky University)
Size Condition on Codes over Rings and Some Duality Preserving Grey Maps

A generalization of Wood’s result on the size condition of codes over rings is presented. Duality preserving grey maps used to project a code over a ring R onto a code over a subring of R and techniques for finding such maps are also discussed.
Vendredi 7 avril, exceptionnellement à 15h
Ene Milio (Postdoc, INRIA Nancy)
Calcul de fonctions sur les Jacobiennes et leurs quotients.
Vendredi 28 avril
Daniel Perrucci (University of Buenos Aires)
On the Davenport-Mahler Bound

The Davenport-Mahler bound is a lower bound for the product of the lengths of the edges on a graph whose vertices are the complex roots of a univariate polynomial, under certain assumptions. Roughly speaking, this bound makes evident an interaction between the involved lengths, in the sense that not all of them can be simultaneously very small.
In this talk, we will show that by considering divided differences, the Davenport-Mahler bound can be extended to arbitrary graphs with vertices on the set of roots of a given univariate polynomial, and we show some applications.

 

 

Archives

 

Vous pouvez trouver ici les archives du séminaire de calcul formel et complexité (2001-2015) et ci-dessous les archives du sémainaire de géométrie et algèbre effectives (2015-2016).

Archives 2015-2016

 

Vendredi 18 septembre 2015, exceptionnellement en salles 04-06
Journée de l'équipe GAE.
Vendredi 25 septembre 2015, expectionnellement en salle 04
Alessio Fiorentino (postdoc IRMAR)
A new proof of the characterization of plane quartics by their bitangents using Weber's formula 

The classical problem of recovering plane curves from their bitangents dates back to the late nineteenth century with contributions from mathematicians such as Plücker, Cayley, Hesse and Aronhold. In a 2003 paper Caporaso and Sernesi resorted to GIT techniques to prove that the general plane quartic is uniquely determined by its 28 bitangents, whereas in a paper published in 2005 Lehavi showed how to recover a smooth plane quartic from its bitangents explicitly. In this talk we present a different proof of Caporaso and Sernesi's statement, which is based on classical results such as Weber's formula and the properties of Riemann theta functions. 
 
Vendredi 2 octobre 2015, exposé annulé
Maxime Lebreton (IRMAR & Orange)
Critères de sécurité et procédure de génération de courbe

Les révélations de Snowden en 2013 ont ouvert la voie à la suspicion autour de la genèse des courbes du NIST. Un sentiment de défiance que la découverte d’un biais dans le générateur pseudo-aléatoire EC-DRBG, spécifié par le NIST, n’a fait que renforcer. Cette perte de confiance a récemment conduit le NIST a organisé un workshop visant à répondre à ce problème délicat. Dans un premier temps, je résumerai les consensus et les points de divergences qui en sont ressortis. Puis je présenterai une procédure de génération de courbe digne de confiance présentée à ce workshop.
Semaine du 5 au 9 octobre : journées C2 2015 à La Londe-les-Maures.
Vendredi 9 octobre 2015
Daniel Perrucci (Universidad de Buenos Aires)

Elementary recursive degree bounds for Positivstellensatz, Hilbert 17th problem and Real Nullstellensatz

Hilbert's 17th problem is to express a non-negative polynomial as a sum of squares of rational functions. The original proof by Artin is non-constructive and gives no information on degree bounds. A more general problem is to give an identity which certifies the unrealizability of a system of polynomial equations and inequalities. The existence of such an identity is guaranteed by the Positivstellensatz, and Hilbert 17th problem as well as Real Nullstellensatz follow easily from such identity. In this talk, we explain a new constructive proof which provides elementary recursive bounds for the Positivstellensatz, Hilbert's 17th problem, and the Real Nullstellensatz, namely a tower of five levels of exponentials. This is a joint work with Henri Lombardi (Universite de Franche-Comte, France) and Marie-Francoise Roy (Universite de Rennes 1, France)
Vendredi 16 octobre 2015
Sylvain Guilley (Telecom Paris)

Complementary Dual Codes for Counter-measures to Side-Channel Attacks

We recall why linear codes with complementary duals (LCD codes) play a role in counter-measures to passive and active side-channel analyses on embedded cryptosystems. The rate and the minimum distance of such LCD codes must be as large as possible. We recall the known primary construction of such codes with cyclic codes, and investigate other constructions, with expanded Reed-Solomon codes and generalized residue codes, for which we study the idempotents. These constructions do not allow to reach all the desired parameters. We study then those secondary constructions which preserve the LCD property, and we characterize conditions under which codes obtained by direct sum, direct product, puncturing, shortening, extending codes, or obtained by the Plotkin sum, can be LCD.
Vendredi 23 octobre 2015
Soutenance de thèse de Charles Savel (après-midi)
Vendredi 30 octobre 2015
Pause
Semaine du 2 au 6 novembre 2015 : JNCF 2015 à Cluny.

 

Vendredi 20 novembre 2015
David Lubicz (IRMAR)
Espaces de modules de variétés abéliennes munies de structures de niveau : une approche effective.

Nous expliquons comment construire des systèmes de coordonnées pour des espaces de modules de variétés abéliennes munies de structures de niveau en considérant des polynômes en les thêta constantes invariants pour des sous-groupes bien choisis du groupe métaplectique. Nous nous intéressons à des solutions effectives au problème de reconstruction des thêta constantes à partir des invariants obtenus.
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.

Un groupe kleinéen arithmétique est un réseau arithmétique dans PSL_2(C). Je décrirai brièvement un algorithme efficace pour calculer une présentation finie d'un tel groupe, puis je me concentrerai sur deux applications. Tout d'abord, j'expliquerai la conjecture "Jacquet-Langlands pour la torsion" de Calegari et Venkatesh et je présenterai un travail en cours avec M. H. Sengun où nous vérifions numériquement et prouvons automatiquement des instances de cette conjecture. Puis je décrirai un travail avec A. Bartel dans lequel nous exhibons des paires de 3-variétés hyperboliques qui sont isospectrales (et ont donc les mêmes nombres de Betti), revêtent une même variété, mais dont la torsion dans l'homologie diffère.
Vendredi 18 décembre 2015
Adrien Poteaux (Lille)
Autour du calcul des séries de Puiseux

L'orateur présentera le papier ISSAC15 "Improving Complexity Bounds for the Computation of Puiseux Series over Finite Fields".
Vendredi 8 janvier 2016
Grey Violet (University of Konstanz)
Geometry of univariate stability: continuity argument, symmetric powers and stability theories.

Various definitions of stable polynomial are among the most basic mathematical tools arising in different areas of control. Geometric approach to stability problems is one of the most fruitful approaches in parametric stability theory. Despite this, geometry of parametric stability problems is still poor understood even for such most basic examples as PID-controller. In order to provide better understandin of that geometry author introduces and examines elements of general algebro-geometric framework for different definitions of stability based on interpretation of root-coefficient correspondence via symmetric products. Author examines different aspects of geometry of stratified spaces arising through that approach and provides an explanation of distinguished position of Schur stability, Hurwitz stability and hyperbolicity among all other stability theories.
Vendredi 15 janvier 2016
Janko Boehm (Kaiserslautern)
Modular Techniques in Computational Algebraic Geometry.

Computations over the rational numbers often suffer from intermediate coefficient growth. One approach to this problem is to determine the result modulo a number of primes and then lift to the rationals. This method is guaranteed to work if we use a sufficiently large set of good primes. In many applications, however, there is no efficient way of excluding bad primes. We develop a new technique for rational reconstruction which will nevertheless return the correct result, provided the number of good primes in the set is large enough. We discuss applications of this technique in computational algebraic geometry. This is joint work with Claus Fieker, Wolfram Decker, Gerhard Pfister, and Santiago Laplagne.
Vendredi 22 janvier 2016, exceptionnellement deux exposés à 10h30 et à 14h
-------------------------------------------
Thomas Dreyfus (Université Lyon1)
Equations de Mahler et transcendance.

Les équations de Mahler sont les équations faisant intervenir l’opérateur y(z)->y(z^{p}), où p est un entier. Les séries génératrices de suites automatiques sont notamment solutions de telles équations. Dans cet exposé nous montrerons comment la théorie de Galois à paramètre permet de déterminer si une série formelle solution d’une équation de Mahler est transcendante ou non.
(Travail en commun avec C. Hardouin et J. Roques.)

--------------------------------------------------------
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.
(travail en commun avec M. El Kahoui, M.-F. Roy et T. Van Effelterre)

Abstract.
Vendredi 29 janvier 2016
Jean-Michel Muller (LIP, ENS Lyon)
Rendre la virgule flottante plus rigoureuse

L'arithmétique virgule flottante est de loin le moyen le plus utilisé pour représenter des nombres réels sur ordinateur. Elle souffre cependant d'une mauvaise réputation: on ne pourrait pas faire confiance aux résultats qu'elle retourne, à moins de faire de longs calculs d'erreur, qui eux mêmes sont d'ailleurs très approximatifs. Nous montrerons par quelques exemples simples qu'on peut obtenir des informations beaucoup plus précises qu'on ne le croit, que l'on peut prouver des propriétés d'algorithmes utilisant la virgule flottante, faire quand on en a besoin des calculs "exacts ». On abordera également quelques problèmes mathématiques sous-jacents, dont la résolution permettrait de nouvelles améliorations.

 

Vendredi 12 février 2016
Fabio Tanturri (Institut de Mathématiques de Marseille)
Factorisations matricielles et courbes dans P^4

Dans cet exposé, je vais présenter une nouvelle technique pour construire des courbes projectives dans P^4 à partir de factorisations matricielles de polynômes homogènes. En utilisant cette méthode effective, on peut produire exemples concrets de courbes de genre et degré assignés ; en construisant explicitement une famille unirationnelle dominante de courbes de genre 12 et degré 14, par exemple, nous pouvons démontrer l'unirationalité de l'espace de Brill-Noether W^4_(14,12) et de l'espace de Hurwitz H_(8,12).
Travail avec F.-O. Schreyer.
Vendredi 26 février 2016
Victor Cauchois (IRMAR)
Construction de matrices de diffusions optimales à partir de codes de Gabidulin 2-cycliques.

La plupart des schémas de chiffrement par blocs et des fonctions de hachage utilisent des couches de diffusion pour se protéger contre les attaques classiques linéaires et différentielles. Dans ce contexte, les matrices MDS sont privilégiées pour la minoration la plus grande possible qu'elles fournissent sur la somme des poids de Hamming des vecteurs d'entrée et de sortie. Pour optimiser les coûts d'implémentation, problématique récurrente en cryptographie, on s'intéresse par ailleurs aux matrices récursives, puissances d'une matrice compagnon, qui peuvent s'implémenter par un LFSR simple. Pour les mêmes raisons, le caractère involutif d'une telle matrice est intéressant puisqu'il autorise l'utilisation d'un même circuit pour calculer le produit matrice-vecteur comme le produit matrice-inverse vecteur. On utilise alors des codes de Gabidulin 2-cyclique pour construire des matrices MDS qui vérifient une forme de récursivité et une forme d'involution.
Vendredi 4 mars 2016
Loubna Ghammam (IRMAR)
Le calcul du couplage Optimal Ate sur les courbes elliptiques.

Lors de cet exposé je présenterai le couplage Optimal Ate sur les courbes elliptiques pour des niveaux de sécurité différents (le 128 et le 192). Je présenterai dans un premier lieu une manière plus efficace pour le calcul de l'exponentiation finale des couplages sur les courbes de Barreto et Naehrig (pour le niveau 128 bit de sécurité). Cette méthode est moins gourmande en mémoire par rapport aux anciennes méthodes et cela est un avantage très important pour les implémentations dans un environnement restreint. Dans un deuxième lieu, je présenterai les courbes BLS12 qui sont recommandées pour le calcul du couplage Optimal Ate pour le niveau de sécurité 192. Dans ce contexte je vais proposer un autre paramètre u de la courbe elliptique qui rend le calcul plus efficace. Je terminerai mon exposé par présenter les courbes elliptiques les plus adéquates pour le calcul de produit ou du quotient de n couplages. Ce problème est très important en pratique pensant à plusieurs protocoles cryptographiques qui nécessitent ce calcul.
Vendredi 11 mars 2016
Clément Pernet (UJF Grenoble et LIP Lyon)
Computing the Rank Profile Matrix.

The row (resp. column) rank profile of a matrix describes the stair case shape of its row (resp. column) echelon form. We propose the definition of a new matrix invariant, the rank profile matrix, summarizing all information on the row and column rank profiles of a matrix of all its leading sub-matrices. We also explore the conditions for a Gaussian elimination algorithm to compute all or part of this invariant, through the corresponding PLUQ decomposition. As a consequence, we first propose a tile recursive Gaussian elimination algorithm that can compute simultaneously the row and column rank profiles of a matrix, as well as those of all of its leading sub -matrices, in the same time as state of the art Gaussian elimination algorithms. We then show how the classical iterative CUP decomposition algorithm can actually be adapted to compute the rank profile matrix. Used, in a Crout variant, as a base-case to the recursive algorithm, it delivers a significant improvement in efficiency. The row (resp. column) echelon form of a matrix are usually computed via various dedicated triangular decompositions. We show here that, from some PLUQ decompositions, it is possible to recover the row and column echelon forms of a matrix and of any of its leading sub-matrices thanks to an elementary post-processing algorithm. Lastly, we will make connections with the recent algorithmic improvements of Storjohann and Yang [ISSAC'14, ISSAC'15] for the computation of the rank profiles of matrices with small ranks, leading to an Õ(r^ω+mn) algorithm computing the rank profile matrix.

Joint work with Jean-Guillaume Dumas and Ziad Sultan.
Vendredi 18 mars 2016
Alexandre Le Meur (IRMAR)
Formules de Thomae généralisées aux cas des extensions galoisiennes résolubles de P1.

D'un point de vue classique, les formules de Thomae relient des rapports de puissances de theta constantes avec les coordonnées affines des points de ramification d'une courbe hyperelliptique. A partir des années 80, plusieurs auteurs, ayant des préoccupations centrées sur la physique, ont montré des généralisations de ces formules au cas des courbes superelliptiques. Plus récemment, Shau Zemel et Hershel Farkas ont écrit un livre en utilisant des arguments essentiellement algébriques. D'un point de vue arithmétique, ces courbes correspondent à des extensions galoisiennes cycliques d'un corps de fonctions k(x). Nous montrerons comment généraliser ces formules au cas des extensions résolubles de k(x) et quelles obstructions peuvent survenir.
Vendredi 25 mars 2016
Pierre Lairez (Berlin)
Une solution déterministe au 17e problème de Smale.

Une racine d'un système d'équations polynomiales peut être calculée numériquement par la méthode homotopique: pour résoudre un système F, on part d'un système G dont on connait une racine, et on le déforme progressivement jusqu'à arriver à F tout en faisant suivre la racine à l'aide d'itérations de Newton. La complexité de cette méthode est bien comprise en terme du conditionnement des systèmes polynomiaux que l'on rencontre le long du chemin de déformation, mais il est difficile de trouver a priori un chemin de déformation efficace. Shub et Smale ont étudié la complexité en moyenne des méthodes homotopiques, où l'on suppose que le système à résoudre est uniformément distribué dans un certain espace. Beltrán et Pardo ont décrit un algorithme probabiliste pour calculer une racine approchée d'un système polynomial dont la complexité est polynomiale par rapport à la taille de l'entrée, en moyenne, à la fois par rapport à l'entrée de l'algorithme et sa source d'aléa. L'objet de l'exposé est de montrer comment supprimer l'aléa dans l'algorithme de Beltràn et Pardo, donnant ainsi un algorithme déterministe de complexité moyenne polynomiale.
Vendredi 1er avril 2016
Hugo Labrande (Nancy)
Computing Theta functions in quasi-optimal time

The genus g function Theta : C^g x H_g -> C has numerous applications in mathematics, from number theory to non-linear differential equations; in particular, its connection with the Abel-Jacobi map on complex elliptic and hyperelliptic curves has important applications. A connection between some values of this function (the theta-constants) and the arithmetico-geometric mean of Gauss (and its generalization in genus g, the Borchardt mean) yields an algorithm to compute any P digits of the theta-constants in roughly log P multiplication of P-bit numbers, which is quasi-optimal. We provide a generalization of this connection using general tau-duplication formulas; with some care, this allows us to devise an algorithm to compute P digits of Theta in the same quasi-optimal time in P. We also report on an implementation in genus 1 and 2, which beats the naive algorithm for precisions as low as a few thousand digits. This is joint work with Emmanuel Thomé.
Vendredi 29 avril 2016
Christophe Ritzenthaler (IRMAR)
Reconstruction de courbes à partir de leurs invariants.

On sait calculer pour les courbes hyperelliptiques et les courbes non hyperelliptiques de genre 3 un ensemble générateur d’invariants pour caractériser leurs classes d’isomorphismes. Par contre, la reconstruction à partir des invariants d’un représentant de la classe n’était connue que pour le cas hyperelliptique. Nous montrerons comment résoudre (génériquement) le cas du genre 3.
Vendredi 13 mai 2016
Khalil Ghorbal (INRIA Rennes)
Caractérisation des variétés affines invariantes pour les équations différentielles algébriques.

Étant donnée une équation différentielle algébriques d'ordre n (i.e. ne faisant intervenir que des polynômes), on s'intéresse à deux problèmes duaux. Le premier consiste à générer des équations invariantes de la forme p=0 où p est un polynôme. C'est dire, si la condition initiale est une racine de p, alors toute la solution du problème de Cauchy ainsi obtenu est contenue dans l'ensemble des racines de p. Le second problème, consiste à vérifier formellement si un candidat de la même forme (c'est à dire p=0) est un invariant. D'abord, pour une condition initiale donnée, on abstrait la solution par la plus petite variété affine la contenant (opérateur de clôture dans la topologie de Zariski), on caractérise ensuite tous les polynômes qui s'annulent sur la clôture (variété) ainsi définie. Cette caractérisation fait abstraction du temps et réduit la génération des variétés affines invariantes à un problème purement algébrique, attractif pour mécaniser une telle procédure. D'un autre coté, elle permet aussi de définir une nouvelle règle d'inférence, nécessaire et suffisante, pour valider ou falsifier l'invariance d'un candidat par un prouveur automatique. La performance et la précision de cette approche sont illustrées par des exemples réputés difficiles pouvant servir, entre autres, à la vérification formelle des systèmes dynamiques et/ou à la synthèse de contrôleurs.
Vendredi 20 mai 2016
Tristan Vaccon (Rikkyo University)
Précision p-adique : exemples et applications

Lorsqu'on souhaite travailler de manière effective avec des nombres p -adiques, on est confronté avec le fait de devoir travailler en précision finie. Avec X.Caruso et D.Roe, nous avons développé une méthode (essentiellement) optimale pour gérer la perte de précision. Elle est appelée précision différentielle, et montre essentiellement qu'il suffit de travailler au premier ordre. Cet exposé aura ainsi pour but de présenter et d'illustrer cette méthode, ainsi que différents phénomènes sur le comportement de la précision p-adique. Nous présenterons en particulier une application aux calculs d'isogénies entre courbes elliptiques définies sur des corps finis en améliorant un algorithme de R.Lercier et T.Sirvent datant de 2008 (travail en commun avec P.Lairez).
Vendredi 27 mai 2016, à 9 h exceptionnellement
Turku-Ozlum Celik (IRMAR)
An Approach towards Weber’s Formula

Weber’s Formula gives the quotient of two Thetanullwerte for a plane smooth quartic in terms of the bitangents. In this talk, we illustrate (parts of) the proof of Weber’s formula in order to convey some ideas for the higher genera. In that manner, we will focus on a quotient which appears in the proof and is formed by the sections on that quartic, which one could interpret for the generalisation. We also present some algorithms about the computations that occurs on the way of this work.
Vendredi 10 juin 2016
Frédéric Chyzak (INRIA Saclay)
Computing solutions of linear Mahler equations

Mahler equations relate evaluations of the same function f at iterated bth powers of the variable. They arise in particular in the study of automatic sequences and in the complexity analysis of divide-and-conquer algorithms. Recently, the problem of solving Mahler equations in closed form has occurred in connection with number-theoretic questions. A difficulty in the manipulation of Mahler equations is the exponential blow-up of degrees when applying a Mahler operator to a polynomial. In this work, we present and analyze polynomial-time algorithms for solving linear Mahler equations for series, polynomials, and rational functions.
(Joint work with Th. Dreyfus, Ph. Dumas, and M. Mezzarobba.)
Vendredi 1er juillet 2016, 10h30, exceptionnellement en salle 6
Egbert Rijke (Carnegie Mellon University)
Introduction to Homotopy Type Theory.

Homotopy type theory combines methods and ideas from homotopy theory and type theory in a constructive foundational system for mathematics. Proofs and constructions can be programmed with the help of algorithms for computation, and the correctness of these formalized construction can be automatically verified automatically. I will give a brief introduction to the basic concepts of homotopy type theory, including identity types, the univalence axiom, and higher inductive types. The higher inductive types include many familiar spaces, such as CW-complexes. To see all of the univalence axiom and higher inductive types in action, we will prove that the loop space of the circle is the type of integers.

Responsables du séminaire : Xavier Caruso et Delphine Boucher.