Table of Contents
Systèmes polynomiaux, calcul formel et applications (24h, 3 ECTS)Responsable : Jean-Charles Faugère Intervenants 2015-2016
English PolicyWe 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. ObjectifsCette 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
Planning 2015/2016Le 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)
Bibliographie
PrérequisDe 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és2.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/internshipsDes stages seront proposé par l'équipe-projet POLSYS de l'INRIA Rocquencourt tout au long de l'annee 2013/2014. Équipe pédagogique
|