Archives
du séminaire de calcul formel et complexité
2010-2011
Vendredi 8 octobre 2010
Daniel Perrucci (postdoc IRMAR)
Linear solving for sign determination
The sign determination problem is the following one: given P_0, P_1,
P_s in R[X], decide which are the sign conditions satisfied by P_1, ...
, P_s at the real roots of
P_0. Given the ubiquity of this problem, it is important to have an
algorithmic tool as efficient as possible to deal with it.
The current best known algorithm to solve the sign determination
problem is based in two main ingredients: the computation of
Sturm-queries and the resolution of linear systems (the Sturm-query
between polynomials P, Q in R[X] is the diference between the number of
real roots of P where Q takes a positive value and the number of real
roots of P where Q takes a negative value).
In this talk, we will explain how this algorithm works and we will also
introduce some specific method to solve the requiered linear systems
which allows us to improve the overall complexity bound.
Vendredi 5 novembre 2010
Vivien Dubois (DGA Rennes)
Cryptanalyse de cryptosystèmes basés sur des polynômes non commutatifs
Ten years ago, Ko et al. described a Diffie-Hellman like protocol based
on decomposition with respect to a non-commutative semigroup law.
Instantiation with braid groups had first been considered, however
intense research on braid groups revealed vulnerabilities of the group
structure and of the braid based DH problem itself.
Recently, Boucher et al. proposed a similar scheme based on a
particular non-commutative multiplication of polynomials over a finite
field. These so called skew polynomials have a well-studied theory and
have many applications in mathematics and coding theory, however they
are quite unknown in a cryptographic application.
In this paper, we show that the Diffie-Hellman problem based on skew
polynomials is susceptible to a very efficient attack. This attack is
in fact general in nature, it uses the availability of a one-sided
notion of gcd and exact division. Given such tools, one can reduce the
Diffie-Hellman problem to a linear algebra type problem.
Vendredi 26 novembre 2010
Bruno Grenet (ENS Lyon)
Représentations de polynômes par déterminants symétriques
Dans un célèbre papier de 1979, Valiant prouve que le déterminant est
universel pour les formules arithmétiques : tout polynôme sur un corps
K donné par une formule peut être représenté par le déterminant d'une
matrice "de petite taille" dont les coefficients sont des variables et
des éléments de K. Ce résultat a ensuite été étendu aux circuits
faiblement asymétriques indépendamment par Toda et Malod.
Dans ce travail, nous nous intéressons à la représentation de polynômes
donnés par formules ou circuits faiblement asymétriques par des
déterminants de matrices symétriques. En particulier, nous prouvons
l'universalité de ces déterminants symétriques si le corps a une
caractéristique différente de 2. Le cas de la caractéristique 2 fait
l'objet d'un travail en cours avec Thomassé et Monteil (nous avons en
particulier montré que les déterminants symétriques ne sont pas
universels).
D'autre part, nous montrons que la VNP-complétude du permanent partiel
en caractéristique 2 impliquerait un effondrement de la hiérarchie
polynomiale, répondant ainsi par la négative à une question de
Bürgisser.
Biblio : http://arxiv.org/abs/1007.3804
Vendredi 7 janvier 2011
Fabrice Rouillier (INRIA)
Calculer efficacement les points singuliers d'une courbe plane et les
multiplicités d'intersection associées.
Le calcul des points singuliers d'une courbe et des multiplicités
d'intersection associées est un verrou pour tout algorithme de calcul
de topologie.
Nous proposons un nouvel algorithme permettant le calcul
(paramétrisation rationnelle et isolation) des points singuliers et de
leurs multiplicités d'intersection dont la caractéristique principale
est d'associer des stratégies jusqu'alors opposées (sous-résultants vs
bases de Gröbner) tout en préservant une complexité minimale.
Cet algorithme permet le calcul direct d'une décomposition
équi-projetable par rapport à une coordonnée(*) des zéros de l'idéal
définissant les points singuliers d'une courbe, chaque composante étant
représentée par une paramétrisation rationnelle.
Nous montrerons que le nombre d'opérations arithmétiques nécessaires
pour cet algorithme est au plus celui nécessaire au calcul d'une suite
de sous-résultants et que la taille des coefficients intervenant dans
le résultat est du même ordre que la taille des coefficients dans le
discriminant de la courbe par rapport à l'une des variables.
Pour être complets, nous terminerons par quelques mots sur la partie
"numérique" de la résolution avec les grandes lignes d'une nouvelle
stratégie pour le calcul d'une approximation certifiée des solutions
avec une grande précision.
(*) points de mêmes multiplicités dans les fibres
Vendredi 28 janvier 2011
Guénaël Renault (LIP6)
Bases de Gröbner et symétries : le cas extrême du corps de
décomposition.
Lors de cet exposé, je commencerai par rappeler très brièvement la
méthode générale pour le calcul du groupe de Galois d'un polynôme f
unitaire à coefficients entiers. Je présenterai ensuite des algorithmes
qui à partir de la connaissance du groupe de Galois de f calculent
efficacement une base de Gröbner permettant de représenter son corps de
décomposition K. Ces calculs sont basés sur l'utilisation des symétries
(action du Groupe de Galois) pour faciliter les calculs d'interpolation
et obtenir des relations sans coût. Je terminerai par montrer comment
utiliser ces symétries pour obtenir une arithmétique
efficace dans K.
Cet exposé se base sur des travaux en collaboration avec S. Orange et
K. Yokoyama.
Vendredi 18 février 2011
Matthieu Legeay (IRMAR)
Utilisation du groupe de permutations d'un code-correcteur pour
améliorer les algorithmes génériques de décodage
Le décodage par maximum de vraisemblance d'un code-correcteur linéaire
binaire est un des grands problèmes en théorie des codes-correcteurs.
Il a été montré NP-difficile. Cependant, aucun des algorithmes de
décodage génériques des codes-correcteurs d'erreurs ne prennent en
compte le groupe de permutation des codes. On verra deux façons
distinctes d'utiliser cette information sur le code pour améliorer les
algorithmes existant.
La première idée fut lancée par MacWilliams en 1964 concernant les
codes cycliques. Elle présentait un algorithme basée sur les ensembles
d'information. Nous montrerons une évaluation théorique avec un cas
particulier de permutation (travail réalisé en commun avec Christophe
Chabot).
La seconde idée est basée sur l'utilisation d'un sous-code
(\sigma-code) du sous-code idempotent d'un code. Nous montrerons des
bornes sur la dimension du \sigma-code pour une permutation
particulière \sigma et nous expliquerons comment utiliser cette
information pour le décodage.
Vendredi 11 mars 2011
Matyas Domokos (Alfréd Rényi Institute of Mathematics, Budapest)
Multisymmetric polynomials in dimension three
The polarizations of one relation of degree five and two relations of
degree six minimally generate the ideal of relations among a minimal
generating system of the algebra of multisymmetric polynomials in an
arbitrary number of three-dimensional vector variables. In the general
case of n-dimensional vector variables, a relation of degree 2n among
the polarized power sums is presented such that it is not contained in
the ideal generated by lower degree relations. The talk is partially
based on joint work with Anna Puskas.
Vendredi 25 mars 2011
Jérémy Le Borgne (IRMAR)
Polynômes tordus et phi-modules sur les corps finis.
On présentera un certain nombre de liens entre l'anneau des polynômes
tordus sur un corps fini, et la théorie des phi-modules, qui apparaît
dans l'étude de certaines représentations galoisiennes. En explorant
ces liens, on verra notamment comment on peut obtenir en pratique un
certain nombre d'informations sur les diverses factorisations d'un
polynôme tordu, ainsi que sa "classe de similarité", ou encore comment
calculer le plus petit multiple d'un polynôme tordu qui appartienne au
centre de l'anneau.
Vendredi 1er avril 2011
Luca De Feo (Postdoc IRMAR)
Principe de transposition et applications
(travail commun avec É. Schost et M. Boespflug)
Le principe de transposition dit essentiellement que pour toute
matrice M à coefficients dans un anneau R (non nécessairement
commutatif) les fonctions v - vM et w - Mw, où v et w sont des vecteurs
ligne et colonne respectivement, ont la même complexité en termes
d’opérations algébriques dans R. Évidemment ceci n’est intéressant que
lorsque la matrice M a une structure qui permet de calculer les
produits en un nombre sous-quadratique d'opérations.
En calcul formel on connaît quatre opérations linéaires pour lesquelles
ce principe donne des applications non triviales : il s'agit de la
multiplication de polynômes, de la réduction modulaire, de l'évaluation
polynomiale (parfois appelée composition modulaire) et de l'évaluation
multipoint.
Du principe on peut obtenir une technique de transformation de code,
initiée par Shoup et raffinée par la suite, qui donne les résultats les
plus remarquables, aussi bien du point de vue de la théorie de la
complexité que de l'implantation des systèmes de calcul formel.
L'automatisation de la transformation de code et la recherche d'autres
applications non triviales ont motivé une étude du principe de
transposition et de ses généralisations. Dans cet exposé je vais
présenter les applications connues, aussi bien classiques que récentes,
de ce principe ; ensuite je vais évoquer les avancées récentes sur la
transposition de code et je vais terminer pour donner quelques pistes
sur les généralisations possibles.
Vendredi 22 avril 2011
Amadou Tall (Dakar)
Chaînes d'additions-soustractions et applications en cryptographie
Vendredi 13 mai 2011
Roland Hildebrand (Grenoble)
Relaxations semi-définies par sommes de carrés abstraits
Vendredi 10 juin : exposé annulé !
Daniel Bembe (Universität München)
A certificate for Budan's theorem in polynomial time
Vendredi 17 juin 2011
Victoria Powers (Emory University, Atlanta)
Polya's Theorem with Zeros.
Vendredi 1er juillet 2011
Saugata Basu (Purdue University)
Baby step giant step road map algorithms