Séminaire de calcul formel et complexité (2013-2014)

Le séminaire a lieu environ deux fois par mois, les vendredis, de 10:30 à 12:00, salle 016, rez-de chaussée du bâtiment 22, Campus de Beaulieu

 


 

Séances passées


 
Vendredi 20 septembre 2013
Marius Van Der Put (Univ. of Groningen, The Netherlands)
Equivalence of first order differential equations

Abstract : A first order differential equation has the form f(y', y, z)= 0 with f in C(z)[s,t]. We will discuss "algebraic solutions", "Painlevé property" and algorithms for testing equivalence of first order equations.

Chairman : F. Ulmer
Vendredi 27 septembre 2013
Xavier Caruso (IRMAR)Algorithmes pour les polynômes tordus sur un corps fini

 "Chairman"  : D. Boucher
Vendredi 4 octobre 2013, exceptionellement, deux exposés à 9h (en commun avec le séminaire de géométrie algébrique réelle) et à 10h30

9h
Christophe Raffalli (Université de Chambéry)
17 ème problème de Hilbert effectif (1)
Nullstellensatz et Positivstellensatz à partir de l'Elimination des coupures

Résumé : On donne une preuve effective du Nullstellensatz de Hilbert et du Positivstellensatz de Krivine-Stengle basée sur la théorie de la démonstration : l'élimination des coupures du calcul des séquents. Les mêmes techniques s'appliquent avec très peu de modifications au Nullstellensatz pour les corps différentiellement clos. La preuve semble très proche des techniques actuelles en algèbre constructive. Nous donnont un algorithme effectif (implanté en OCaml) pour construire l'identité algébrique cherchée. Nous souhaitons discuter quel type de nouveaux résultats ces méthodes pourraient produire et également si elles présentent un intérêt pour produire des bornes.

10h30
Henri Lombardi (Université de Besançon)

17 ème problème de Hilbert effectif (2)
Existences faibles, No Counterexample Interpretation et Élimination des coupures

Résumé : l'exposé sera basé sur des exemples.

" Chairman"  : M.F. Roy
Vendredi 18 octobre 2013, exceptionnellement à 9 h
Pierre Lairez (INRIA Saclay) 
Le calcul des intégrales multiples de fractions rationnelles.

Résumé : L'étude et le calcul des intégrales de fractions rationnelles trouvent leurs premières motivations dès le XVIIIe siècle quand des propriétés de certaines fonctions, comme le périmètre d'une ellipse en fonction de l'excentricité, sont déduites de formules intégrales, sans passer par une expression en forme close. Le point important est que chacune de ces intégrales satisfait à une équation linéaire à coefficients polynomiaux, appelée équation de Picard-Fuchs. La question à laquelle s'intéresse l'exposé est le calcul de ces équations. 

Je présenterai une famille de trois algorithmes permettant de répondre à cette question, chacun généralisant le précédent, des intégrales simples, aux intégrales multiples régulières ou singulières.

 
Chairman : T. Vaccon

Vendredi 13 décembre 2013 
Alin Bostan (SpecFun, INRIA Saclay) 
Computer Algebra for Lattice Path Combinatorics

Abstract : Classifying lattice walks in restricted lattices is an important problem in enumerative combinatorics. Recently, computer algebra methods have been used to explore and solve a number of difficult questions related to lattice walks. In this talk, we will give an overview of recent results on structural properties and explicit formulas for generating functions of walks in the quarter plane, with an emphasis on the algorithmic methodology.

Chairman : X. Caruso
Vendredi 24 janvier 2014
Alain Couvreur (INRIA Saclay, LIX)
Une attaque polynomiale du Schéma de McEliece à partir de codes de Goppa sur des extensions quadatiques. (Travail en collaboration avec Ayoub OTMANI (Univ. Rouen) et Jean-Pierre TILLICH (INRIA Rocquencourt))

RÉSUMÉ : Le schéma de McEliece est un schéma de chiffrement basé sur les codes correcteurs d'erreurs dont la sécurité repose sur la difficulté à décoder un code aléatoire. Parmi les différentes familles de codes algébriques proposées pour ce schéma, les codes de Goppa classiques sont les seuls à résister à toutes les attaques algébriques, et ce, depuis plus de 35 ans. 
Dans cet exposé, je commencerai par décrire le schéma de McEliece puis rappellerai les définitions ainsi que quelques propriétés des codes de Goppa classiques. Dans une second temps, je présenterai une attaque d'un genre nouveau, dite "par filtration" qui permet de recouvrer la structure d'un code de Goppa construit à partir d'une extension de corps quadratique. Cette attaque consiste à utiliser des propriétés multiplicatives du code pour en calculer une filtration dont chaque élément est un code de Goppa classique. 
Dans un second temps, on utilise des propriétés de cette filtration afin de recouvrer la structure de ce code. Cette attaque a été implémentée en Magma et permet de casser en moins d'une heure des clés proposées par Bernstein, Lange et Peters dont la sécurité était estimée supérieure à 128 bits (Wild McEliece, SAC 2010). Depuis l'introduction du schéma de McEliece, c'est la première attaque sur des codes de Goppa classiques.

Chairman : P. Loidreau
Vendredi 14 février, exceptionnellement en salle de la bibliothèque
Philippe Gaborit (Xlim, Limoges) 
Nouveaux résultats pour la cryptographie en métrique rang 

Résumé: La cryptographie en métrique rang s'est développée à partir de 1991 et du cryposystème GPT qui est une adaptation du cryptosystème de McEliece en métrique rang. L'intérêt principal de la métrique rang est que les meilleures attaques connues ont une complexité qui grandit très vite, permettant d'avoir des tailles de clés relativement petites de quelques milliers de bits. Cependant le système GPT étant basé sur des codes très structurés (les codes de Gabidulin qui sont en équivalent des codes de Reed-Solomon en métrique rang), il a fait l'objet d'attaques structurelles fortes et de réparations successives. Dans cet exposé nous présenterons une nouvelle approche pour la cryptographie en métrique rang à partir d'une nouvelle famille de codes peu structurés décodables: les codes LRPC (Low Rank Parity Check codes), qui permettent d'avoir des tailles de clés de chiffrement de l'ordre de 1500b, tout en étant très rapides. On présentera aussi une nouvelle approche générale pour la signature basée sur les codes, qui à partir des codes LRPC permet d'obtenir un algorithme de signature très efficace avec des tailles de clé et de signature de seulement quelques milliers de bits. Enfin on présentera un nouvel algoritme générique d'attaque en métrique rang qui adapte efficacement les idées traditionnelles de l'approche Information Set Decoding. 

Les resultats présentés sont issus de collaborations avec: O. Ruatta, J. Schrek et G. Murat (Univ. Limoges) et G. Zémor (Univ. Bordeaux).

"Chairman" : D. Boucher
Vendredi 21 février
Michael Sagraloff (Max-Planck Institute für Informatik, Saarbrücken) 
Near-optimal Algorithms for Computing Real Roots of a Polynomial 

Abstract: Computing the roots of a univariate polynomial is a fundamental and long-studied problem of computational algebra with numerous applications in mathematics, engineering, computer science, and the natural sciences. For isolating as well as for approximating all complex roots, the best algorithm known is based on an almost optimal method for approximate polynomial factorization, introduced by Pan in 2002. Pan's factorization algorithm goes back to the splitting circle method from Schoenhage in 1982. The main drawback of Pan's method is that it is quite involved and that all roots have to be computed at the same time. For the important special case, where only the real roots have to be computed, much simpler methods are used in practice; however, they considerably lag behind Pan's method with respect to complexity. It has been an open question for decades whether there exists a dedicated real root solver with a comparable runtime as the splitting circle method. In the first part of my talk, I will report on recent progress giving a positive answer to the above question. More precisely, I will present a variant of the Descartes method, denoted ANEWDSC, that computes isolating intervals for the real roots of any real square-free polynomial, given by an oracle that provides arbitrary good approximations of the polynomial's coefficients. Our algorithm can also be used to refine the isolating intervals to an arbitrary small size. The bit complexity of ANEWDSC matches the complexity of Pan's method and, in particular, it achieves near optimal complexity for computing arbitrary good approximations of all real roots. ANEWDSC derives its speed from the combination of the Descartes method with Newton iteration and approximate arithmetic. By comparison, the algorithm is considerably simpler than Pan's method, and it can be used to compute the roots in a given interval only. In the second part of my talk, I will concentrate on sparse polynomials, that is, polynomials with a small number of non-vanishing coefficients. Using a subroutine from ANEWDSC, I will show how to isolate the real roots of a sparse integer polynomial with a number of arithmetic operations over the rationals that is polynomial in the input size of the sparse representation of the input polynomial. The bit complexity of the algorithm is by one magnitude better than that of ANEWDSC and Pan's method. Considering a family of Mignotte-like polynomials, one can show that the algorithm is optimal up to logarithmic factors in the degree of the polynomial and the bitsize of the coefficients.

"Chairman" : M.-F. Roy

 

Vendredi 14 mars 
Steve Szabo (Eastern Kentucky University)
On Codes over Local Frobenius Non-chain Rings of Order 16

Abstract : It has been shown that for certain reasons, the most appropriate rings to use as code alphabets are Frobenius rings. Most rings in current studies are chain rings which happen to be Frobenius rings. As the next logical step in the development of codes over rings, some work has been done on codes over local Frobenius rings that are not chain rings. We show that the smallest local Frobenius non-chain rings are of order 16 and give a complete list of rings of this type. Along the way, all local rings of order 16 are shown. In addition to these rings, commonalities between them pertaining to codes are presented. 

Chairman : F. Ulmer

 

Vendredi 21 mars
Aurélien Greuet (ATER Lille) 
Optimisation polynomiale et variétés polaires : théorie, algorithmes et implantations. 

Résumé : Le calcul de l'infimum global $f^\star$ d'un polynôme à $n$ variables sous contraintes est une question centrale qui apparaît dans de nombreux domaines des sciences de l'ingénieur. Pour certaines applications, il est important d'obtenir des résultats fiables. De nombreuses techniques ont été développées dans le cas où les contraintes sont données par des inéquations polynomiales. Dans cet exposé, on se concentre sur le problème d'optimisation d'un polynôme à $n$ variables sous des contraintes définies par des équations polynomiales à $n$ variables. Le but est d'obtenir des outils, algorithmes et implémentations efficaces et fiables pour résoudre ces problèmes d'optimisation. La stratégie est de ramener le problème d'optimisation sous des contraintes qui définissent des ensembles algébriques de dimension quelconque à un problème équivalent, sous des nouvelles contraintes dont on maîtrise la dimension. La variété algébrique définie par ces nouvelles contraintes est l'union du lieu critique du polynôme objectif et d'un ensemble algébrique de dimension au plus $1$. Pour cela, on utilise des objets géométriques définis comme lieux critiques de projections linéaires. Grâce au bon contrôle de la dimension, on prouve l'existence de certificats pour des bornes inférieures sur $f^\star$ sur nos nouvelles variétés. Ces certificats sont donnés par des sommes de carrés et on ne suppose pas que $f^\star$ est atteint. De même, on utilise les propriétés de nos objets géométriques pour concevoir un algorithme exact pour le calcul de $f^\star$. S'il existe, l'algorithme renvoie aussi un minimiseur. Pour un problème avec $s$ contraintes et des polynômes de degrés au plus $D$, la complexité est essentiellement cubique en $(sD)^n$ et linéaire en la complexité d'évaluation des entrées. L'implantation, disponible sous forme de bibliothèque Maple, reflète cette complexité. Elle a permis de résoudre des problèmes inatteignables par les autres algorithmes exacts. 
Les travaux présentés sont issus de collaborations avec Feng Guo, Mohab Safey El! Din et Lihong Zhi.

Chairman: M. Coste
 

Semaine du 24 mars au 28 mars : Journées Codage et Cryptographie 2014
Vendredi 6 juin
Tristan Vaccon (IRMAR)
Bases de Gröbner sur des corps valués (non effectifs).

Résumé : Dans cet exposé, nous étudierons quelles bases de Gröbner peuvent être calculées sur un corps valué qui peut ne pas être effectif. Bien que le calcul de bases de Gröbner sur les "nombres flottants" a été longuement étudié durant la dernière décennie, nos motivations sont de natures p-adique, et nous verrons que sur de tels corps, la gestion de la précision est plus aisée. Plus particulièrement, nous verrons que l'on peut donner une réponse positive lorsque l'on a une hypothèse de structure sur les polynômes en entrée (régularité et "faiblement grevlex"). Nous donnerons et analyserons un algorithme, fondé sur une modification de l'algorithme de F5 matriciel. Nous verrons ensuite que les définitions de bases de Gröbner "tropicales" initiées en géométrie tropicale, et tordant par la valuation la définition de monôme de tête, permettent une meilleure gestion de la précision ainsi que des hypothèses de structures moins fortes sur l'entrée (régularité seulement).
Vendredi 27 juin
Marion Candau (Univ Brest)
Codes convolutifs non-commutatifs.

Résumé : Les codes convolutifs sont définis, mathématiquement parlant, comme la convolution sur le groupe des entiers relatifs, d'un message et d'une fonction de transfert. On va remplacer le groupe des entiers relatifs par, tout d'abord, le groupe diédral infini, puis, par un groupe fini non commutatif. Les codes obtenus par la convolution sur ces groupes vont avoir de bonnes performances et vont, de plus, rendre la reconnaissance du code plus difficile pour un attaquant ayant intercepté des mots de code.

 
 

Mardi 1er juillet à 14 h, salle de la bibliothèque
Mathieu Kohli (ENS Cachan)17 ème problème de Hilbert, élimination des quantificateurs et algorithme de détermination de signe

 



 

Archives 2011-2013

 

Archives 2010-2011

 

Archives 2001-2010 :

 

Année 2001-2002, Année 2002-2003, Année 2003-2004, Année 2004-2005, Année 2005-2006, Année 2006-2007, Année 2007-2008, Année 2008-2009, Année 2009-2010