Archives du séminaire de calcul formel et complexité
2014-2015
Vendredi 19 septembre 2014
Xavier Caruso (IRMAR)
Résultants et sous-résultants de polynômes p-adiques
Expérimentalement, on constate que l'utilisation de
l'algorithme d'Euclide étendu pour le calcul du PGCD et des
coefficients de Bézout de deux polynômes p-adiques conduit à une
importante instabilité numérique. En effet, pour des polynômes
aléatoires unitaire de degré d, on déplore en moyenne une perte
d'environ d/p chiffres significatifs sur chaque coefficient alors que
la perte théorique n'est (en moyenne) que de 1/(p-1) chiffres
significatifs ! Le but de cet exposé sera double. Je commencerai par
énoncer un panel de résultats et conjectures sur les résultants et
sous-résultants de polynômes p-adiques aléatoires et en déduirai les
estimations sur les pertes de précision énoncées précédemment. Dans un
deuxième temps, je présenterai une version « stabilisée » de
l'algorithme de calcul des sous-résultants par les suites de
pseudo-restes d'où je déduirai un algorithme de calcul de PGCD de
polynômes p-adiques qui a une complexité équivalente à celle de
l'algorithme d'Euclide mais réalise, à un chouia près, la perte de
précision théorique optimale.
Chair : D. Boucher
Vendredi 24 octobre 2014
David Lubicz (IRMAR)
Calculer des isogénies entre variétés abéliennes en temps quasi-optimal
Dans cet exposé, on explique comment généraliser à la dimension
supérieure le classique algorithme de Vélu qui permet de calculer une
isogénie entre courbes elliptiques. Plus précisément, on explique
comment à partir de la donnée d'une variété abélienne munie d'une
polarisation principale ainsi qu'un noyau rationnel isotrope maximal
pour le couplage de Weil, on peut calculer la variété abélienne
quotient de manière efficace.
Du Lundi 3 novembre au Vendredi 7 novembre 2014 : JNCF 2014 au CIRM
Mardi 18 novembre 2014, 10h30, salle 16
Eric Schost (Computer Science Department, University of Western Ontario)
On the Complexity of Solving Bivariate Systems
We present an algorithm for solving bivariate polynomial
systems with coefficients in $\mathbb{Q}$ with essentially optimal bit
complexity. The core of the algorithm is a classical Newton iteration
procedure. New ingredients are needed, though, such as Kedlaya-Umans'
modular composition algorithm and deflation techniques due to Lecerf.
Joint work with Esmaeil Mehrabi.
Chair : M.-F. Roy
Vendredi 21 novembre 2014
Audrey Tixier (INRIA Rocquencourt)
Reconstruction du couple (entrelaceur, code convolutif) à partir de données bruitées
Dans un contexte non-coopératif, des données sont observées sur
un canal de communication bruité. Celles-ci correspondent à un ensemble
de mots de code entrelacés et bruités. L'objectif est de retrouver
l'information contenue dans ces données. Pour cela, il est nécessaire
de reconstruire l'entrelaceur et le code correcteur utilisés. Les mots
de codes sont entrelacés avant émission afin de contrer les erreurs
survenant par paquet. L'entrelacement permet de répartir les erreurs
sur plusieurs mots de code qui peuvent alors être corrigés et décodés.
Par hypothèse, la longueur de l'entrelaceur est connue. Dans la
littérature, il n'existe pas de méthode permettant de retrouver le
couple (entrelaceur, code) sans hypothèse supplémentaire sur la
structure de l'entrelaceur. De plus, dans les cas étudiés, les données
sont sans erreur. Nous supposons que le code utilisé est un code
convolutif et proposons une méthode qui retrouve efficacement
l'entrelaceur et le code convolutif à partir de données bruités,
connaissant uniquement la longueur de l'entrelaceur. Afin de
reconnaître ce couple, trois étapes sont effectuées, la première
consiste à retrouver un ensemble d'équations de parité vérifiées par
les mots de code. Lors de la seconde étape, nous construisons un graphe
associé à ces équations. Dans ce graphe, les sommets représentent une
équation de parité et chaque arête symbolise un indice commun entre les
deux équations qu'elle relie. Une notion d'équivalence de graphe est
définie et permet la reconnaissance du code convolutif. Enfin, à partir
de ce même graphe, nous réordonnons les équations de parité, cela
permet alors de reconstruire l'entrelaceur.
Chair : P. Loidreau
Vendredi 28 novembre 2014
Pierre-Jean Spaenlehauer (INRIA Nancy)
A Newton-like iteration and algebraic methods for Structured Low-Rank Approximation
Given an linear/affine space of matrices E with real entries, a
data matrix U in E and a target rank r, the Structured Low-Rank
Approximation Problem consists in computing a matrix M in E which is
close to U (with respect to the Frobenius norm) and has rank at most r.
This problem appears with different flavors in a wide range of
applications in Engineering Sciences and symbolic/numeric computations
(for instance approximate GCD and low-rank matrix completion).
We propose an SVD-based numerical iterative method which converges
locally towards such a matrix M. This iteration combines features of
the alternating projections algorithm and of Newton's method, leading
to a proven local quadratic rate of convergence under mild
tranversality assumptions. We also present experimental results which
indicate that, for some range of parameters, this general algorithm is
competitive with numerical methods for approximate univariate GCDs and
low-rank matrix completion.
In a second part of the talk, we focus on the algebraic structure and
on exact methods to compute symbolically the nearest structured
low-rank matrix M to a given matrix U in E with rational entries. We
propose several ways to recast this problem as a system of polynomial
equations and investigate the algebraic degree of the problem.
The first part of the talk is a joint work with Eric Schost, the second
part is a joint work with Giorgio Ottaviani and Bernd Sturmfels.
Chair : T. Vaccon
Vendredi 12 Décembre 2014, salle de la bibliothèque
Tony Ezome (USTM, Franceville, Gabon)
Fonctions sur les variétés jacobiennes et leurs quotients
Dans cet exposé nous allons montrer comment évaluer des
fonctions sur les variétés jacobiennes et leurs quotients. Nous
commencerons par rappeler ce qui a été fait pour les courbes
elliptiques, notamment avec les isogénies de Velu. Le cas des
jacobiennes des courbes de genre 2 a été étudié par Dolgachev et
Lehavi. Leur approche a été reprise et améliorée par Smith. Lubicz et
Robert ont développé des méthodes générales pour quotienter les
variétés abéliennes par des sous-groupes maximaux d'isotropie dans la
$l$-torsion.
Chair : S. Duquesne
Vendredi 23 Janvier 2015
Pierre Loidreau (IRMAR)
Codes cellulaires et applications cryptographiques
Dans le domaine de la cryptographie à clé publique reposant
sur les codes correcteurs d'erreurs, un problème essentiel pour les
concepteurs de systèmes est de parvenir à gérer la très grande taille
de clé publique nécessaire pour assurer une sécurité convenable. Un
moyen consiste à utiliser des codes structurés tels les codes
quasi-cycliques qui permettent des représentations compactes de la clé
publique. Cependant, même si en théorie la sécurité des systèmes n'en
est pas affectée, dans la pratique la structure algébrique sous-jacente
est très peu considérée dans la mise au point d'attaques.
Dans cet exposé nous étudions une famille de codes généralisant la
notion de codes quasi-cycliques. La matrice génératrice est formée de
"cellules" qui sont des matrices carrées prises dans une algèbre de
matrices engendrée par un polynôme. Nous montrons qu'un diviseur de ce
polynôme permet d'engendrer des codes "projetés" de paramètres plus
petits. Nous étudions les effets de cette projection sur le décodage et
la recherche de mots de petit poids dans des codes quasi-cycliques tant
en métrique de Hamming qu'en métrique rang. Nous montrons comment cette
approche peut réduire la complexité des attaques déjà connues, en
fonction du poids du polynôme considéré ou bien de l'espace de ses
coefficients.
Chair : D. Boucher
Vendredi 27 Février 2015
Louis Dumont (INRIA Saclay - Specfun)
Algebraic equations for diagonals of bivariate rational functions
The diagonal of a multivariate rational function is defined
as the univariate series obtained from the diagonal coefficients of its
power series expansion. Among the fascinating properties of these
objects it has been known for a long time that diagonals of bivariate
rational functions are algebraic power series. We will give an
algorithm that, given a bivariate fraction that admits a power series
expansion at the origin, returns a polynomial that vanishes at its
diagonal. Moreover, the output polynomial has exponential degree
compared to the input rational function. We show that, generically,
this cannot be improved : the output polynomial is irreducible and is
computed in time quasi-optimal in its size.
Chair : D. Boucher
Vendredi 13 Mars 2015
Jacques-Arthur Weil (Xlim)
Un critère constructif d’irréductibilité d’équations différentielles
non-linéaires, avec applications aux équations de Painlevé II et III
(travail commun avec Guy Casale)
Chair : D. Boucher
Vendredi 22 mai 2015, exceptionnellement en salle 6
Franck Dupont (Poitiers)
Formule d'Euler Jacobi torique
Nous considérerons dans l'exposé, une famille de n polynômes de
Laurent à n indéterminées à coefficients complexes et indexés par leurs
polytopes de Newton. Il est alors possible de définir un symbole de
Kronecker dans le tore relativement à cette famille de polynômes sous
certaines conditions de régularité. Ce symbole de Kronecker coïncide
avec le résidu global dans le tore et sa construction décrite par M. F.
Roy et A. Szpirglas [Roy, M.F. et Szpirglas, A. (avril 1998). Bezoutien
et symbole de Kronecker affines, projectifs et dans le tore
(prépublication 98-15), IRMAR] fait écho aux travaux de E. Cattani et
A. Dickentein [Cattani, E. et Dickenstein, A. (1997). Théorème 4 p.
125-126 : A global view of residues in the torus, J. Pure Appl. Algebra
117/118] qui ont montré que le résidu global dans le tore s'identifie à
un résidu torique particulier.
Nous reprendrons brièvement les étapes suivies par M.F. Roy et A.
Szpirglas pour construire le symbole de Kronecker dans le tore puis
nous montrerons qu'il s'annule en tout caractère t^m où m est un
n-uplet entier, intérieur à la somme de Minkowski des polytopes de
Newton associés aux polynômes de Laurent.
La démonstration de ce résultat repose pour l'essentiel sur la formule d'Euler Jacobi affine.
Chair : M.-F. Roy
Vendredi 29 mai 2015
Claire Tête (Poitiers)
Une approche combinatoire pour le fondement du résultant multivarié
Il est bien connu que l'idéal d'élimination de n polynômes
homogènes génériques en n indéterminées est principal, engendré par le
résultant. Nous en proposons une preuve "élémentaire" qui repose sur la
théorie des résolutions libres finies (en particulier leur structure
multiplicative) et la théorie de la profondeur. Aucune hypothèse sur
l'anneau de base n'est requise. Contrairement à la plupart des auteurs,
nous examinons la composante homogène du complexe de Koszul de (P_1,
..., P_n) en degré delta et non delta+1 où delta = \sum_{i=1}^n
(deg(P_i) - 1). Cela donne naissance à une forme linéaire sur A[X_1,
..., X_n]_delta qui, évaluée en det V, fournit le résultant (où V est
une matrice vérifiant [P_1, ..., P_n] = [X_1, ..., X_n] V). On montrera
que cette forme linéaire possède de bonnes propriétés grâce à un
résultat purement combinatoire assez étonnant !
Chair : M.-F. Roy
Vendredi 5 juin 2015
Antonin Guilloux (IMJ)
Décrire les variétés de caractères : géométrie et calcul formel
Considérons une variété M et un groupe G (algébrique).
Comprendre l'ensemble des morphismes du groupe fondamental de M - la
variété (algébrique) des caractères - dans G jette une lumière sur la
géométrie de la variété M. A partir d'un exemple précis (M est le
complémentaire du noeud de huit, G est SL(3,C)), nous verrons comment
l'apport de différents domaines permet la compréhension de cette
variété algébrique. Nous discuterons chemin faisant de triangulations
topologiques, de paramétrisation de cette variété algébrique, d'un
système d'équations trop gros (32 variables, degré 6), et
d'informations théoriques a priori. Tout ceci permet la détermination
effective de cette variété. Enfin, nous discuterons quelques
applications et perspectives.
Travail en commun avec E. Falbel, P.V. Koseleff, F. Rouillier et M. Thistlethwaithe
Chair : M.-F. Roy
Vendredi 19 juin 2015, salle de la bibliothèque
Soukayna Qarboua (Université Mohamed V, Rabat & Lab-STICC Brest)
Construction de fonctions quaternaires courbes, projection et généralisation binaire.
Notre recherche porte sur l’étude et la conception de
fonctions booléennes qui jouent un rôle important en cryptographie.
Elles sont activement utilisées dans les protocoles de chiffrement
itératifs par blocs et par flux et dans la combinaison ou le filtrage
de registres à décalage à rétroaction linéaire pour la génération de
suites chiffrantes. Les critères cryptographiques que doivent
satisfaire les fonctions booléennes sont nombreux et sujets à compromis
selon leurs compatibilités. Parmi ces critères, on retiendra
l’équilibre, l’immunité aux corrélations, le critère de propagation, la
non-linéarité (d’ordre r), le degré algébrique et l’immunité
algébrique. Les fonctions booléennes varient avec le système dans
lequel elles sont employées et assurent sa résistance aux différents
types d’attaques connues comme l’attaque linéaire, l’attaque
différentielle, l’attaque par corrélation ou encore l’attaque
algébrique et l’attaque algébrique rapide.
Nous présentons ici, une nouvelle construction de fonctions
quaternaires courbes à m-variables dont la projection binaire donne des
fonctions booléennes à 2m-variables courbes et à (2m + 1)-variables de
non-linéarité maximale, ainsi qu’une généralisation de ces projections
qui donne dans le cas pair une nouvelle définition vectorielle de la
classe de fonctions PS (Partial Spread, Dillon) de degré algébrique
maximal et dans le cas impair une nouvelle classe de fonctions Plateau.
Pour ces deux classes, les expérimentations numériques menées pour des
valeurs de m < 10, témoignent que l’immunité algébrique des
fonctions booléennes projetées est optimale (AI = m) dans le cas pair
(n = 2m) et bornée (m − 1 ≤ AI ≤ m) dans le cas impair (n = 2m + 1).
L’aspect formel de la démonstration de ces propriétés est actuellement
en cours.
Chair : D. Boucher
Mercredi 24 juin 2015, 14h
Soutenance de thèse de Romain BASSON
Arithmétique des espaces de modules des courbes hyperelliptiques de genre 3 en caractéristique positive.
Vendredi 26 juin 2015
Gwezheneg Robert (IRMAR)
Codes de Gabidulin et codage espace-temps.
Après avoir présenté le codage espace-temps, j'expliquerai pourquoi il
est naturel de vouloir utiliser des codes en métrique rang à
coefficients dans le corps des complexes. Je présenterai alors les
codes de Gabidulin généralisés ainsi qu'une famille de codes
espace-temps obtenue à partir de ces derniers. Nous comparerons alors
ces codes avec d'autres constructions classiques.
Ensuite, j'éévoquerai quelques pistes concernant le décodage.
Enfin, la dernière partie sera consacrée à la réduction d'un code de
Gabidulin généralisé modulo un idéal premier, et l'impact sur la
complexité du décodage.
Chair : D. Boucher
Vendredi 3 juillet 2015, 14h30, salle 12, bâtiment 32B
Soutenance de thèse de Tristan VACCON
Précision p-adique.