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

Responsable : Jean-Charles Faugère

Intervenants 2009-2010

• Jean-Charles Faugère: systèmes d'équations algébriques, bases de Groebner.
• Ludovic Perret: Applications en Cryptographie.
• Fabrice Rouillier: systèmes d'équations algébriques (racines réelles).
• Mohab Safey El Din: algorithmes en geometrie réelle

Objectifs

Nouveau Modalite examen disponible ici!!

 

La partie Calcul Formel de l'ancien cours 2-13 était centrée sur la résolution des systèmes polynomiaux par le calcul de bases de Gröbner et leurs applications en cryptologie (ce qui induit une restriction au cas discret). Cependant, la plupart des applications de ces techniques algorithmiques sont néanmoins issues de problèmes d’ingénierie où ce sont les solutions réelles qui doivent être étudiées (on est ici dans le cas continu). Le nouveau cours est étendu au cas continu (solutions réelles ) ce qui permet de traiter d'autres applications comme la robotique (problèmes de classification).

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 quelques applications phares de ces méthodes en cryptologie et robotique. Le cours s’articule autour de quatre axes. Le premier traite du calcul de base de Gröbner et constitue le moteur de la résolution algébrique utilisé dans la suite. 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 en Cryptologie, la modélisation et la structure des systèmes polynomiaux jouent ici un rôle crucial. Le troisième axe traite de l’étude des solutions réelles de systèmes polynomiaux admettant un nombre fini de solutions complexes (dimension 0). Le calcul de bases de Gröbner est ici un pré-requis, qui ne suffit plus à résoudre. On traitera aussi le cas des systèmes polynomiaux dont les coefficients dépendent de paramètres. Une application en robotique (classification des robots cuspidaux) illustrera cette partie de cours. Les systèmes les plus généraux sont également abordé dans le cours:  les méthodes de points critiques ramènent le problème de décider  l'existence de solutions réelles à un système d'équations et/ou d'inégalités polynomiales général à l'étude des solutions réelles de systèmes dans le cas fini.

Plan du cours

Systèmes polynomiaux, calcul formel et applications

 

Le cours s’articule autour des quatre 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.
• Résolution réelle des systèmes admettant un nombre fini de solutions complexes et applications : les calculs de bases de Gröbner sont ici un pré-requis aux algorithmes étudiés mais sont insuffisants pour étudier les solutions réelles ; on étudiera aussi le cas où on autorise le système donné en entrée a des coefficients dépendant de paramètres (l’opération d’élimination de variables dans des idéaux sera ici intensivement utilisée) ; des applications en géométrie algorithmique seront décrites.
• Résolution réelle des systèmes admettant une infinité de solutions complexes : on considère ici le problème de déterminer l’existence de solutions réelles des systèmes d’équations dépendants de paramètres. Les algorithmes de résolution des systèmes d’équations admettant un nombre fini de solutions complexes sont utilisés ici en boîte noire. Les opérations de base sur les idéaux (élimination et saturation) sont utilisées pour obtenir des algorithmes efficaces en pratique. Les aspects “modélisation” et “systèmes structurés” sont partagés avec le deuxième axe. Une application en robotique sera étudiée.

 

 

Planning 2009/2010

Jour: Lundi 10h15 - 11h45 - 30, rue du Château des Rentiers - Salle 131 au 1er étage

 

Cours	Date	Titre du Cours	Enseignant	Support de cours
1	21/9/2009	Introduction générale du cours. Principe de la cryptanalyse algébrique.	JC Faugère	Download slides.
2	28/9/2009	Idéaux et variétés, définition des bases de Gröbner. Algorithme de Buchberger. Caractérisation des bases de Gröbner.	JC Faugère	Download slides.
3	5/10/2009	Propriétés des bases de Gröbner. Critères de Buchberger. Élimination. Stratégies (Homogene/Sucre). Utilisation d'un calcul modulo p.	JC Faugère	Download slides
4	12/10/2009	Le cas de la dimension zéro. Ideal quotient. Algorithme FGLM. Matrices de Macaulay.	JC Faugère	Download slides.
5	19/10/2009	Algebre lineaire et algorithme efficace de calcul (algorithme F4). Critère F5 pour eviter les calculs inutiles .	JC Faugère	Download slides
6	26/10/2009	Algorithme F5 matriciel. Suites (semi) régulières, complexité du calcul des bases de Gröbner.	JC Faugère	Download slides Transparents
7	2/11/2009	Cryptographie multivariée à clef publique : problème d’appartenance à un idéal et résolution de systèmes polynomiaux.	L. Perret
8	9/11/2009	Principes de la cryptanalyse algébrique.	L. Perret
P	16/11/2009	Partiel (Notes de cours autorisées).		Notes sur le serveur pedagogique.
9	23/11/2009	Cryptanalyse algébrique avancée : décomposition fonctionnelle et chiffrement par blocs.	L. Perret
10	30/11/2009	Introduction à la géométrie réelle – Ensembles semi-algébriques	F. Rouillier
11	7/12/2009	Le cas de la dimension zéro : réduction systématique au cas univarié – Algorithme RUR	F. Rouillier
12	14/12/2009	Le cas univarié : Isolation des solutions réelles – Théorème de Vincent et Algorithme d’Uspensky.	F. Rouillier
13	4/1/2010	Résolution des systèmes à paramètres : définition et calcul de variétés discriminantes.	F. Rouillier
14	11/1/2010	Assemblage des algorithmes et notions par l’exemple - Application en robotique : détermination des positions cuspidales d’un robot-série en fonction des paramètres de conception.	F. Rouillier
15	18/1/2010	Systemes polynomiaux generaux : Existence de solutions reelles	M. Safey El Din
16	25/2/2010	Systemes polynomiaux generaux : Calcul d'un point par composante connexe.	M. Safey El Din
Examen	1/2/2010	Lundi 1 Fev 2010 a 9h45 30 rue Château des Rentiers, Salle 131, examen écrit (2h00). Polycopié et notes de l'étudiant autorisés. Les étudiants doivent choisir un article de recherche dans la liste suivante: J.-C. Faugère and L. Perret and F. Levy dit Vehel. Cryptanalysis of Minrank. Advances in Cryptology CRYPTO 2008, PDF ici M. Noro and K. Yokoyama : A Modular Method to Compute the Rational Univariate Representation of Zero-dimensional Ideals PDF ici M. Safey El Din andE Schost : Properness defects of projections and computation of at least one point in each connected component of a real algebraic set PDF ici

Bibliographie

• Introduction et rappels:

  Jean-Charles Faugère et Mohab Safey El Din Chapitre d’introduction à la résolution des systèmes polynomiaux (avec exercices) . Ouvrage collectif chez Pearson Education.

• Pour les aspects systèmes algébriques
• D. Cox, J. Little, and D. O'Shea. Ideals, Varieties, and Algorithms. Undergraduate Texts in Mathematics. Springer-Verlag, 1996. second edition.
• T. Becker and V. Weispfenning. Gröbner bases. Springer-Verlag, New York-Berlin-Heidelberg, 1993.
• Pour les aspects réels:
• S. Basu, M.-F. Roy, R. Pollack, Algorithms in real algebraic geometry, Spriger-Verlag, 2006.

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.12 Cryptologie. Bien que nous discuterons d'applications à la cryptologie, nous ne ferons pas les bases de la cryptologie, juste l'introduction des problèmes que nours traiterons.

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

2.14-1 Approximation géométrique : maillages et reconstruction . Pour des applications potentielles du Calcul Formel.

Stages/internships

Des stages seront proposé par l'équipe-projet SALSA de l'INRIA Rocquencourt tout au long de l'annee.

• Stage Master Recherche M2 propose dans l'equipe-projet SALSA
  Internship proposal: Optimisation algebrique sous contraintes et calcul formel (pdf here)
  Abstract: le probème de calculer l'infimum d'une application polynomiale sous contraintes (égalités et/ou inégalités polynomiales) est fondamental et a de nombreuses applications. Ce stage est consacré à l'étude de ce problème et l'implantation d'algorithmes dédiés faisant usage de techniques de Calcul Formel vues en cours.
  Contact : Mohab Safey El Din Mohab.Safey@lip6.fr
  Salary : around 500 euros /month
  Location : Paris 16, SALSA Team
  Duration : 5/6 months
  Starting Date : march or april
  
• Stage remuneréé proposé par la société Oberthur:
  Internship proposal: Lightweight Cryptography for Smart Card Applications (pdf here)
  Abstract: This internship aims at investigating alternatives to standardized or well-known cryptographic algorithms, in order to answer the new needs expressed by industrials for a lightweight cryptography.
  Contact : Emmanuel Prouff (e.prouff@oberthurcs.com)
  Salary : around 1000 euros /month
  Location : Nanterre, within the Cryptography and Security Team
  Duration : 5/6 months
  Starting Date : march or april
  

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.

Les années précédentes

• Année 2008-2009
• Année 2007-2008
• Année 2006-2007

Équipe pédagogique

J.C. Faugère	DR	INRIA	Paris-Rocquencourt
L.  Perret	MC	UPMC	Lip6
F.  Rouillier	DR	INRIA	Paris-Rocquencourt
M. Safey El Din	MC	UPMC	Lip6