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

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

 


 

Prochaines séances

 

 

Vendredi 23 Janvier 2015
Pierre Loidreau (IRMAR)
Titre: Codes cellulaires et applications cryptographiques  

Résumé : 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.

 

 

Vendredi 13 Mars 2015
Jacques-Arthur Weil (Xlim)
Titre:  

Résumé :

 

 

Vendredi 22 mai 2015
Claire Tête (Poitiers)
Titre: ;

Résumé:

 

 

Vendredi 5 juin 2015
Antonin Guilloux (IMJ)
Titre: ;

Résumé:

 

Séances passées

 

Vendredi 19 septembre 2014
Xavier Caruso (IRMAR)
Titre: Résultants et sous-résultants de polynômes p-adiques 

Résumé: 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.

 

Vendredi 24 octobre 2014
David Lubicz (IRMAR)
Titre: Calculer des isogénies entre variétés abéliennes en temps quasi-optimal

Résumé: 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)
Title: On the Complexity of Solving Bivariate Systems  

Abstract : 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.

Vendredi 21 novembre 2014
Audrey Tixier (INRIA Rocquencourt)
Titre: Reconstruction du couple (entrelaceur, code convolutif) à partir de données bruitées  

Résumé: 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.

Chairman : Pierre Loidreau

Vendredi 28 novembre 2014
Pierre-Jean Spaenlehauer (INRIA Nancy)
Titre: A Newton-like iteration and algebraic methods for Structured Low-Rank Approximation  

Résumé: 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.

Chairman : Tristan Vaccon

 

 

Vendredi 12 Décembre 2014, salle de la bibliothèque
Tony Ezome (USTM, Franceville, Gabon)
Titre: Fonctions sur les variétés jacobiennes et leurs quotients  

Résumé : 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.