Introduction à la résolution de systèmes polynomiaux (POSSO)

Mots-clés.

Calcul formel, Systèmes polynomiaux. Bases de Gröbner.

Langue d’enseignement.

Anglais possible

Résumé.

Résoudre algorithmiquement des systèmes polynomiaux trouve de nombreuses applications, en cryptographie notamment (évaluation de la sécurité de crypto-systèmes, cryptographie post-quantique) ou encore en géométrie algorithmique.

Ce problème est néanmoins difficile : son caractère non-linéaire rend l’usage de méthodes numériques délicat ; aussi les applications visées nécessitent d’effectuer des calculs dans des domaines discrets (corps finis). Le calcul formel permet de contourner ces difficultés et permet d’obtenir des algorithmes de résolution caractérisés par l’exactitude des résultats calculés.

Ce cours présente donc des méthodes relevant du calcul formel pour la résolution des systèmes polynomiaux, notamment par calcul de bases de Gröbner. Les algorithmes de calcul de ces bases sont étudiées et des exemples d’applications permettent la mise en œuvre des notions fondamentales.

Ce cours est mutualisé avec l’UE du MPRI consacré à la résolution des systèmes polynomiaux dont J.-C. Faugère est responsable.

Semainier.

 

  1. Structures algébriques de base.
  2. Résultant et systèmes polynomiaux bivariés.
  3. Idéaux et variétés algébriques.
  4. Ordres monomiaux, Division multivariée.
  5. Idéaux monomiaux et lemme de Dickson. Bases de Gröbner.
  6. Algorithme de Buchberger et propriétés des bases de Gröbner.
  7. Utilisation des bases de Gröbner pour la résolution.
  8. Séries de Hilbert. Dimension et degré des idéaux polynomiaux.
  9. Théorème de Bézout et complexité.

Modalités d’évaluation.

Il est probable qu’un rendu sous forme de projet soit demandé (la note serait alors incluse dans le tiers de contrôle continu).

Répartition horaire.

 

Équipe pédagogique.

L’équipe pédagogique est constituée de


Ce document a été traduit de LATEX par HEVEA