Cette thèse porte sur l'algorithmique des techniques de décodage en liste, initiée par Guruswami et Sudan en 1998, dans le contexte des codes de Reed-Solomon sur les anneaux finis. Deux approches sont considérées. Dans un premier temps, nous adaptons l'algorithme de décodage en liste de Guruswami-Sudan aux codes de Reed-Solomon généralisés sur les anneaux finis. Nous étudions en détails les complexités de l'algorithme pour les anneaux de Galois et les anneaux de séries tronquées. Dans un deuxième temps nous approfondissons l'étude d'une technique de remontée pour le décodage en liste. Nous montrons que cette derni're permet de corriger davantage de motifs d'erreurs que la technique de Guruswami-Sudan originale. Nous appliquons ensuite cette même technique aux codes de Reed-Solomon généralisés sur les anneaux de Galois et les anneaux de séries tronquées et obtenons de meilleures bornes de complexités. Enfin nous présentons l'implantation des algorithmes en C et C++ des algorithmes de décodage en liste étudiés au cours de cette thèse. Tous les sous-algorithmes nécessaires au décodage en liste, comme la recherche de racines pour les polynômes univariés, l'arithmétique des corps et anneaux finis sont aussi présentés. Indépendamment, ce manuscrit contient d'autres travaux sur les codes quasi-cycliques. Nous prouvons qu'ils sont en correspondance biunivoque avec les idéaux à gauche d'un certain anneaux de matrices. Enfin nous adaptons le cadre proposé par Guruswami et Sudan pour les codes à base d'ideaux aux codes construits à l'aide des corps de nombres. Nous fournissons un algorithme de décodage en liste dans ce contexte.

Dans cette thèse, nous étudions des algorithmes pour un problème de recherche de relations à une ou plusieurs variables. Il généralise celui de calculer une solution à un système d’équations linéaires modulaires sur un anneau de polynômes, et inclut par exemple le calcul d’approximants de Hermite-Padé ou d’interpolants bivariés. Plutôt qu’une seule solution, nous nous attacherons à calculer un ensemble de générateurs possédant de bonnes propriétés. Précisément, l’entrée de notre problème consiste en un module de dimension finie spécifié par l’action des variables sur ses éléments, et en un certain nombre d’éléments de ce module ; il s’agit de calculer une base de Gröbner du modules des relations entre ces éléments. En termes d’algèbre linéaire, l’entrée décrit une matrice avec une structure de type Krylov, et il s’agit de calculer sous forme compacte une base du noyau de cette matrice. Nous proposons plusieurs algorithmes en fonction de la forme des matrices de multiplication qui représentent l’action des variables. Dans le cas d’une matrice de Jordan,nous accélérons le calcul d’interpolants multivariés sous certaines contraintes de degré ; nos résultats pour une forme de Frobenius permettent d’accélérer le calcul de formes normales de matrices polynomiales univariées. Enfin, dans le cas de plusieurs matrices denses, nous accélérons le changement d’ordre pour des bases de Gröbner d’idéaux multivariés zéro-dimensionnels. / In this thesis, we study algorithms for a problem of finding relations in one or several variables. It generalizes that of computing a solution to a system of linear modular equations over a polynomial ring, including in particular the computation of Hermite- Padéapproximants and bivariate interpolants. Rather than a single solution, we aim at computing generators of the solution set which have good properties. Precisely, the input of our problem consists of a finite-dimensional module given by the action of the variables on its elements, and of some elements of this module; the goal is to compute a Gröbner basis of the module of syzygies between these elements. In terms of linear algebra, the input describes a matrix with a type of Krylov structure, and the goal is to compute a compact representation of a basis of the nullspace of this matrix. We propose several algorithms in accordance with the structure of the multiplication matrices which specify the action of the variables. In the case of a Jordan matrix, we accelerate the computation of multivariate interpolants under degree constraints; our result for a Frobenius matrix leads to a faster algorithm for computing normal forms of univariate polynomial matrices. In the case of several dense matrices, we accelerate the change of monomial order for Gröbner bases of multivariate zero-dimensional ideals.

Je traite du décodage de deux grandes familles de codes algébriques :<br />les codes cycliques binaires et les codes de Reed-Solomon sur un<br />alphabet $q$-aire (ainsi que les codes géométriques). En ce qui<br />concerne les codes cycliques, ceux-ci n'ont pas d'algorithme générique<br />de décodage, mis à part les codes BCH ou assimilés (bornes de<br />Hartman-Tzeng, de Roos). Au premier rang des codes intéressants pour<br />lesquels on ne connaît pas d'algorithme de décodage {\em générique}<br />figurent les {\em codes à résidus quadratiques}, qui ont de bons<br />paramètres. J'étudie une mise en équation du problème du décodage par<br />syndrôme de ces codes, que l'on peut résoudre avec des outils de base<br />de Gröbner. On obtient ainsi des algorithmes de décodage de complexité<br />raisonnable pour ces codes. Ces travaux ont fait l'objet d'une partie<br />de la thèse de Magali Bardet.<br /><br /><br />En ce qui concerne les codes de Reed-Solomon, ceux-ci peuvent être vus<br />comme des {\em codes d'évaluation}, et le problème de décodage associé<br />revient à approcher une fonction par des polynômes de base degré. De<br />grands progrès ont été réalisés par Guruswami et Sudan, qui ont trouvé<br />un algorithme qui décode bien au delà des rayons classiques de<br />décodage, en relaxant l'hypothèse que la solution doit être unique. Je<br />propose d'améliorer certaines étapes de cet algorithme, en le rendant<br />plus rapide et déterministe (notamment en évitant une factorisation de<br />polynôme sur un corps fini), dans le cas des codes Reed-Solomon, et<br />dans le cas des codes géométriques. Ces travaux ont été effectués en<br />encadrant Lancelot Pecquet.<br /><br />Du point de vue théorique, j'ai étudié des généralisations<br />multivariées, qui correspondent à certains codes: les codes produits<br />de Reed-Solomon, et les codes de Reed-Muller. On obtient ainsi un bon<br />rayon de décodage, dans le cas des codes de petit taux. Dans le cas de<br />codes de Reed-Muller sur l'alphabet binaire, Cédric Tavernier, dans sa<br />thèse sous ma direction, a produit et implanté un algorithme efficace,<br />plus que ceux basés sur l'algorithme de Guruswami-Sudan.<br /><br /><br /><br />J'ai étudié les aspects négatifs du problème de décodage par syndrôme<br />des codes linéaires, et du décodage des codes de Reed-Solomon, quand<br />le nombre d'erreurs est élevé, en but d'application en cryptographie.<br />Dans le premier cas, j'ai construit une fonction de hachage<br />cryptographique à réduction de sécurité, c'est-à-dire que trouver une<br />faiblesse dans le fonction de hachage revient à résoudre un problème<br />réputé difficile de codage. J'ai aussi construit une nouvelle<br />primitive de chiffrement à clé publique, reposant sur la difficulté de<br />décoder les codes de Reed-Solomon.<br /><br />Dans un domaine plus appliqué, j'ai proposé avec Raghav Bhaskar un<br />nouvel algorithme d'échange de clé multi-utilisateurs, fondé sur le<br />problème du logarithme discret. Raghav Bhaskar a fourni une preuve de<br />sécurité de ce protocole, pendant sa thèse sous ma direction. Nous<br />avons aussi étudié comment adapter ce protocole aux pertes de<br />messages, car notre protocole est un des seuls qui est robuste à ces<br />pertes.