Décodage en liste des codes géométriques

Travaux de doctorat de l’Université Paris VI
(désormais UPMC Sorbonne Universités)

Recherche menée, entre 1997 et 2001, au projet CODES (désormais SECRET) de l’INRIA, sous la direction de Pascale Charpin, Directrice de recherche INRIA, Directrice du projet CODES, et de Daniel Augot, Chargé de recherche INRIA.

Pour une introduction grand public à la théorie des codes, voir mon article L’algèbre qui corrige les erreurs. Une description de mes travaux destinée aux scientifiques non spécialistes de ce sujet est fournie plus bas.

Résumé : Les codes géométriques ont été introduits par Goppa en 1981 et sont construits à partir de courbes algébriques sur les corps finis. En 1982, Tsfasman, Vladuts et Zink ont montré qu’on pouvait construire de tels codes dépassant la borne de Gilbert-Varshamov. En 1996, Sudan a proposé un algorithme de décodage en liste des codes de Reed-Solomon. Cet algorithme fut adapté, en 1997, aux codes fortement géométriques à un point par Shokrollahi et Wasserman, puis amélioré par Guruswami et Sudan.

Dans cette thèse, nous étendons ces méthodes à tous les codes géométriques, à leurs sous-codes dans un sous-corps, et à une distance de Hamming généralisée qui nous permet de reformuler algébriquement le problème du décodage souple et de proposer un algorithme de décodage en liste à maximum de vraisemblance sur tout canal discret sans mémoire. Nous illustrons ces nouveaux résultats par une implantation dans le système de calcul formel Magma.

NB: il demeure quelques erreurs que je n’ai jamais eu le courage de corriger.

2000 Mathematics Subject Classification: 11T71 Algebraic coding theory; cryptography; 94B35 Decoding; 94B27 Geometric methods (including applications of algebraic geometry) [See also 11T71, 14G50]; 11Yxx Computational number theory [See also 11-04]; 14Qxx Computational aspects in algebraic geometry [See also 12Y05, 13Pxx, 68W30]; 68W30 Symbolic computation and algebraic computation [See also 11Yxx, 12Y05, 13Pxx, 14Qxx, 16Z05, 17-08, 33F10].

Mots clés : Décodage en liste; décodage souple à maximum de vraisemblance; codes géométriques; codes de Reed-Solomon; sous-codes dans un sous-corps; algorithme de Guruswami-Sudan; géométrie algébrique effective; théorie algorithmique des nombres; racines de polynômes sur un corps de fonctions de courbe sur un corps fini; calcul formel; implantation en Magma.

Soutenance: Cette thèse a obtenu la mention Très Honorable à l’issue d’une soutenance s’étant déroulée le mardi 18 décembre 2001 à 14h00, Campus de Jussieu (Batiment 41, Salle 203-205), 4, place Jussieu, 75005 Paris, France, devant un jury constitué de:

  • Daniel Lazard: Professeur (Paris VI), Président du Jury
  • Pascale Charpin: Directrice de recherche (INRIA), Directrice de thèse
  • Daniel Augot: Chargé de recherche (INRIA), Co-directeur de thèse
  • Claude Carlet: Professeur (Caen), Rapporteur
  • Tom Høholdt: Professor (DTU, Danemark), Rapporteur
  • François Morain: Professeur (Polytechnique), Examinateur

Description « non technique » à destination des scientifiques non-spécialistes du sujet

Contexte

La Théorie des codes a pour objectif principal de fiabiliser les télécommunications de manière mathématique. Elle a été fondée vers le milieu de 20e siecle par les travaux de Claude Shannon et Richard Hamming, entre autres.

De gigantesques progrès ont été faits depuis et les connexions de la Théorie des codes avec d’autres branches des mathématiques et de l’informatique comme la Combinatoire, la Cryptographie, la Théorie des nombres ou la géométrie algébrique ou encore la Théorie de la complexité sont innombrables.

L’introduction d’outils de géométrie algébrique par Goppa lui permit, en 1981, de fabriquer des codes qualifiés naturellement de « géométriques » à partir de courbes sur les corps finis. Ces codes bénéficient de la puissante Théorie de Riemann-Roch qui permet en particulier d’estimer les paramètres fondamentaux des codes que sont leur distance minimale et leur dimension.

En 1982, Michael Tsfasman, Serge Vladuts et Thomas Zink réussirent à montrer une famille explicite de codes géométriques meilleurs que tous les codes connus dont les performances dépassaient même la borne de Gilbert-Varshamov qu’on conjecturait – à tort – être optimale.

En 1996, Madhu Sudan proposa une méthode de décodage en liste des codes de Reed-Solomon, qui fut adaptée en 1997 par Amin Shokrollahi et Hal Wasserman aux codes fortement géométriques à un point, puis améliorée par Venkatesan Guruswami et Sudan.

Contributions de cette thèse

  1. La généralisation de l’algorithme de Guruswami-Sudan à tous les codes géométriques
  2. La description d’un algorithme de décodage en liste pour une distance généralisant la distance de Hamming et permettant un décodage souple algébrique maximisant la vraisemblance sur tout canal discret sans mémoire
  3. Des raffinements des conditions d’existence des polynômes auxiliaires utilisés dans les algorithme de décodage en liste
  4. Une prise en compte des structures de données et des primitives algorithmiques requises pour exploiter la structure géométrique des codes (courbe, normalisée, genre, diviseurs, espaces de Riemann-Roch) pour leur décodage en liste
  5. Une implantation en Magma d’un algorithme de désingularisation d’un modèle plan d’une courbe et d’une amélioration de l’algorithme de Brill-Noether permettant, entre-autres, le calcul de séries p-adiques de fonctions en tout point fermé p de la courbe considérée et son genre (collaboration avec Pawel Wocjan)
  6. L’implantation en Magma d’une bibliothèque de manipulation de canaux de communications permettant de tester notre algorithme de décodage souple
  7. L’adaptation de l’algorithme de Newton-Puiseux à la recherche de racines de polynômes à coefficients dans un corps de fonctions, qui nous permet de fournir l’une des primitives exploitées dans l’algorithme de décodage en liste
  8. La démonstration d’une propriété combinatoire sur les codes de faible taux de transmission permettant d’utiliser dans ce cas l’algorithme de Newton-Hensel, ce qui réduit la complexité de leur décodage en liste à un temps essentiellement quadratique (collaboration avec Daniel Augot)
  9. La preuve qu’on peut précalculer suffisamment d’information pour ne pas avoir à recourir à la Théorie de Riemann-Roch effective pendant le décodage en liste
  10. Une implantation complète, en Magma, des méthodes ci-dessus, en particulier de notre algorithme de décodage en liste généralisé et de sa version souple

Des courbes pour le codage et la cryptographie

Dans cet exposé élémentaire et introductif au Colloquium Junior de l’INRIA, nous présentons la problématique usuelle de la théorie des codes correcteurs d’erreurs et de la cryptographie. Nous montrons comment l’utilisation de la géométrie algébrique effective des courbes sur les corps finis peut être utilisée pour résoudre certaines des questions se posant dans ces disciplines.

Construction des codes géométriques avec Magma

Dans cet exposé donné au 3e Congrès Européen de Mathématiques (3ECM, Barcelone, Espagne, juillet 2000), nous illustrons un certain nombre de qualités du système de calcul formel Magma et la manière dont il peut servir à l’implantation d’algorithmes sophistiqués faisant intervenir de nombreuses primitives dans différentes branches des mathématiques effectives comme les corps finis, la géométrie algébrique ou la théorie des codes correcteurs d’erreurs en donnant pour exemple la construction des codes de Goppa géométriques au sein de ce système.

Ce travail a été réalisé en collaboration avec Pawel WOCJAN.

Un relèvement de Hensel pour le décodage en liste

Cet article propose une amélioration algorithmique de l’algorithme de Sudan pour les codes de Reed-Solomon et sa généralisation aux codes géométriques par Shokrollahi et Wasserman. Au lieu de factoriser complètement le polynôme d’interpolation sur le corps de fonctions de la courbe, nous calculons rapidement suffisamment de termes du développement p-adique des fonctions correspondant aux mots de code cherchés grâce à la méthode de Newton.

Ce travail a été réalisé en collaboration avec Daniel Augot, publié dans IEEE Transactions on Information Theory, vol. 46, n°7, pp. 2605-2614, 2000. Une version préliminaire a été proposée dans le Rapport de Recherche INRIA, n° 3532, novembre 1998.cience/codec/RR-3532.pdf »>INRIA Research Report, n° 3532, November 1998.

Théorie des jeux et stratégie

L’algorithme minimax est un algorithme qui s’applique à la théorie des jeux pour les jeux à deux joueurs à somme nulle. Il amène l’ordinateur à passer en revue toutes les possibilités pour un nombre limité de coups et à leur assigner une valeur qui prend en compte les bénéfices pour le joueur et pour son adversaire. Le meilleur choix est alors celui qui minimise les pertes du joueur tout en supposant que l’adversaire cherche au contraire à les maximiser (le jeu est à somme nulle). L’élagage alpha-beta, évitant d’explorer l’arbre intégralement, est également évoqué. Ce document est une introduction dans le cadre d’un projet.

Algorithmes de recherche de racines sur les corps de fonctions de courbes algébriques

Exposé aux Journées Nationales de Calcul Formel, CIRM (Novembre 2005)

Nous proposons un algorithme pour trouver les racines d’un polynôme univarié à coefficients dans le corps de fonction d’une courbe algébrique (ou plus généralement dans un corps discrètement valué). Cette méthode peut être appliquée au décodage en liste des codes géométriques lors que la méthode de Newton-Hensel ne peut être utilisée.

A Newton-Puiseux root finding algorithm over function fields of curves (Preprint non publié, November 2005)

Soit k un corps parfait de caracteristique quelconque, X une courbe géométriquement irréductible définie sur k et K son corps de fonctions. Soit G un polynôme sur K et D un diviseur, nous proposons un algorithme pour trouver toutes les racines de G dans l’espace de Riemann-Roch L(D). Une application de cette méthode est l’étape de recherche de racines dans le décodage en liste des codes géométriques quand la très efficace méthode de Newton-Hensel ne peut être utilisée. Notre algorithme a deux étapes :
1.) utiliser une méthode de Newton-Puiseux, calculer suffisamment de termes des racines de l’image du polynôme dans un complété;
2.) en déduire les racines comme fonctions de L(D) en utilisant de l’algèbre linéaire sur k.
Nous généralisons cette méthode aux corps discrètement valués.

Programmation fonctionnelle

Polycopié de programmation fonctionnelle en Licence

Cours de programmation fonctionnelle en Licence, Université Paris XII (2001-2003)

Découvrez Objective Caml

Publié dans GNU/Linux & Hurd Magazine France n° 43 (oct. 2002)

Objective Caml (Ocaml pour les intimes) est un langage de programmation magnifique: flexible, sûr, d’exécution rapide, doté de nombreuses bibliothèques (graphiques, réseau, …). Il est souvent, à tort, considéré comme une curiosité qui n’intéresserait que quelques informaticiens théoriciens. Dans cet article, nous parcourrons rapidement l’arbre généalogique de ce langage pour en comprendre les principes fondateurs et familiariser le lecteur avec la programmation fonctionnelle; nous présenterons ensuite les différents modes de travail d’Ocaml et quelques aspects originaux de ce langage. Nous terminerons par un petit exemple d’utilisation des bibliothèques graphique et Unix et l’évocation des autres outils de développement disponibles pour Ocaml.

Ressources autour de la validité et la sûreté/sécurité des logiciels

History’s Worst Software Bugs, by Simson Garfinkel, 2005.

Programmation orientée objet


Cours de programmation orientée objet et Java en Licence, Université de Poitiers (2002-2006):

CM1 : Introduction, environnement, types de base, notion de classe
CM2 : Classes, constructeurs, encapsulation, destruction
CM3 : héritage simple, polymorphisme, Object
CM4 : classes abstraites, héritage multiple, interfaces
CM5 : interruptions, paquetages, javadoc, collections, Java 1.5
CM6 : transtypage, égalité, comparabilité, clonage
CM7 : UML, conception OO, projet
CM8 : fichiers, sérialisation, threads, applets
CM9 : révisions autour de String, immuabilité
Polycopié

Mathematiques du secret

Mathématiques du Secret

Exposé en Terminale S au Lycée Camille Sée, Paris (6 décembre 2002)

Cet exposé est destiné à des Terminales S, option « maths ». Nous présentons les principes fondamentaux de la cryptologie et nous décrivons en détail le système de chiffrement et de signature à clé publique RSA qui n’utilise presque que des méthodes arithmétiques élémentaires (exponentiation modulaire rapide, algorithme d’Euclide étendu, Théorème de Fermat-Euler…). Nous donnons des éléments de cryptanalyse de RSA et expliquons comment les cartes « yes » sont fabriquées. Nous concluons en évoquant quelques autres cryptosystèmes.