Parisian Master of Research in Computer Science
Master Parisien de Recherche en Informatique (MPRI)

Systèmes polynomiaux, calcul formel et applications (24h, 3 ECTS)

Responsable : Jean-Charles Faugère

Intervenants 2015-2016

English Policy

We accept to do the lectures in English if there is at least one non French speaking student in the audience, and no French speaking student is opposed to lectures in English.

Objectifs

Cette annee le cours 2-13-1 est centré sur la résolution des systèmes polynomiaux par le calcul de bases de Gröbner et leurs applications en cryptologie (c'est a dire que les solutions et les coefficients des polynomes sont dans un corps fini).

Les systèmes polynomiaux interviennent dans de nombreux de domaines des sciences de l’ingénieur ou de l’informatique, notamment en cryptologie, robotique, théorie du signal, et géométrie algorithmique. Le calcul formel est la manipulation par l’ordinateur des expressions mathématiques. Les algorithmes algébriques du Calcul Formel constituent un outil privilégié pour la résolution exacte et certifiée des systèmes polynomiaux (la non-linéarité de ces derniers rendant délicates les approches purement numériques). Le but de ce cours est de donner les algorithmes efficaces de résolution de ces systèmes ainsi que de décrire une applications phare de ces méthodes en cryptologie. Le cours s’articule autour de deux axes. Le premier traite du calcul de base de Gröbner et constitue le coeur de la résolution algébrique utilisé dans la suite. Dans cette partie du cours nous decrivons les algorithmes les plus efficaces pour le Calcul des bases Grobner (algorithmes F4 et F5) et nous donnons des resultats de complexite de Groebner qui seront utilises pour les applications en cryptologie. Le second axe étudie comment la résolution des systèmes polynomiaux (dans les corps finis) permet d’évaluer et/ou concevoir certains cryptosystèmes , la modélisation et la structure des systèmes polynomiaux jouent ici un rôle crucial.

Plusieurs applications en cryptologie utilisant les méthodes algébriques illustrent le cours: construction et cryptanalyse de nouveaux cryptosystèmes (Mc Eliece, famille HFE, ...) et cryptanalyse de cryptosystèmes existants (chiffrement par flot, chiffrement par blocs, HFE, ...). Un nouvel exemple d'application sera presente cette annee: il s'agit du probleme du logarithme discret sur les courbes algebriques (EC DLP).

Plan du cours

Systèmes polynomiaux, calcul formel et applications

 
Le cours s’articule autour des deux axes suivants :
  • Calcul de bases de Gröbner pour la résolution des systèmes polynomiaux : cet axe constitue le noyau d’algorithmique algébrique sur lequel repose l’ensemble des algorithmes donnés dans la suite ; les algorithmes les plus récemment introduits seront étudiés ; ceux-ci reposent sur une réduction à des problèmes d’algèbre linéaire ; ils permettent en outre d’effectuer efficacement des opérations de base sur les idéaux polynômiaux (élimination de variables, saturation, intersection).
  • Application en Cryptologie : cet axe étudie comment les calculs de bases de Gröbner peuvent être utilisés pour le design de nouveaux cryptosystèmes et/ou l’analyse de la sécurité de cryptosystèmes existants (Cryptanalyse algébrique) ; les systèmes polynômiaux considérés ici sont à coefficients dans un corps fini et sont parfois très structurés. L’accent est mis sur la modélisation des problèmes.
 

Planning 2015/2016

Le cours a lieu le Lundi de 8h45 a 11h45 , Salle: Bat. Sophie Germain Room 2035 (voir Emploi du Temps - MPRI)

(Les transparents sont disponibile apres chaque cours sur cette page).

Written examen: March 7 Monday (8h45)

Cours Date
Cours / Lecture
Enseignant Support de cours/Slides
1 7/12/2015

General Introduction to Polynomial System Solving.

Ideal, Varietes definition of Gröbner Bases. Buchberger's Algorithm. Gröbner bases properties.

JC Faugère  
2 14/12/2015 Characterizations of Gröbner Bases. Elimination. Buchberger's Criteria. Strategies. JC Faugère  

Bibliographie

Prérequis

De bonnes connaissances de base en algèbre élémentaire (linéaire, multi-linéaire) ainsi que les structures fondamentales que sont les groupes anneaux et corps sont fortement souhaitables. Des connaissances solides en analyse de base (niveau L1 ou L2) sont aussi recommandées (notions de continuité, dérivées, théorème des fonctions implicites).

Il est aussi recommandé d’avoir quelques notions d’algorithmique élémentaire et de complexité (notation “grand O”) ainsi qu’une connaissance des structures de données élémentaires que sont les tableaux, listes, et arbres.

Cours liés

2.22 Algorithmes efficaces en calcul formel Pour ceux qui veulent voir d'autres aspects du calcul formel.

2.12-1 Techniques en cryptographie et cryptanalyse

          Bien que nous discuterons d'applications a la cryptologie, nous ne
          ferons pas les bases de la cryptologie, juste l'introduction des
          problèmes que nours traiterons. 
          

2.12-2 Algorithmes arithmetiques pour la cryptologie.

          Bien que nous discuterons d'applications à la cryptologie, nous ne
          ferons pas les bases de la cryptologie, juste l'introduction des
          problemes que nours traiterons. 
          

2.14-1 Analyse Geometrique des Données Pour des applications potentielles du Calcul Formel.

Stages/internships

Des stages seront proposé par l'équipe-projet POLSYS de l'INRIA Rocquencourt tout au long de l'annee 2013/2014.

  • Stage de Master M2: Modélisation de mécanismes et Algorithmes incrémentaux de Calcul des Bases de Gröbner.
  • Sujet de these (Ph.D. + These en Entreprise): Algorithme incrémentaux pour le Calcul des Bases de Gröbner avec paramètres et implantation.
  • Équipe pédagogique

    J.C. FaugèreDRINRIAParis-Rocquencourt
    L. PerretMCUPMCLip6
     
    Universités partenaires Université Paris-Diderot
    Université Paris-Saclay
    ENS Cachan École polytechnique Télécom ParisTech
    ENS
    Établissements associés Université Pierre-et-Marie-Curie CNRS INRIA CEA