Archives du séminaire de calcul formel et complexité
2013-2014
Vendredi 20 septembre 2013
Marius Van Der Put (Univ. of Groningen, The Netherlands)
Equivalence of first order differential equations
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.
Chair : F. Ulmer
Vendredi 27 septembre 2013
Xavier Caruso (IRMAR)
Algorithmes pour les polynômes tordus sur un corps fini
Chair : 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
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
L'exposé sera basé sur des exemples.
Chair : M.-F. Roy
Vendredi 18 octobre 2013, exceptionnellement à 9 h
Pierre Lairez (INRIA Saclay)
Le calcul des intégrales multiples de fractions rationnelles.
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.
Chair : T. Vaccon
Vendredi 13 décembre 2013
Alin Bostan (SpecFun, INRIA Saclay)
Computer Algebra for Lattice Path Combinatorics
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.
Chair : 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))
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.
Chair : P. Loidreau
Vendredi 14 février 2014, exceptionnellement en salle de la bibliothèque
Philippe Gaborit (Xlim, Limoges)
Nouveaux résultats pour la cryptographie en métrique rang
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).
Chair : D. Boucher
Vendredi 21 février 2014
Michael Sagraloff (Max-Planck Institute für Informatik, Saarbrücken)
Near-optimal Algorithms for Computing Real Roots of a Polynomial
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.
Chair : M.-F. Roy
Vendredi 14 mars 2014
Steve Szabo (Eastern Kentucky University)
On Codes over Local Frobenius Non-chain Rings of Order 16
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.
Chair : F. Ulmer
Vendredi 21 mars 2014
Aurélien Greuet (ATER Lille)
Optimisation polynomiale et variétés polaires : théorie, algorithmes et implantations.
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.
Chair: M. Coste
Semaine du 24 mars au 28 mars : Journées Codage et Cryptographie 2014
Vendredi 6 juin 2014
Tristan Vaccon (IRMAR)
Bases de Gröbner sur des corps valués (non effectifs).
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 2014
Marion Candau (Université Brest)
Codes convolutifs non-commutatifs.
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.
Chair : D. Boucher
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
Chair : M.-F. Roy