M2 Algèbre appliquée

Capacité d'accueil

20
Langue(s) d'enseignement

Français
Régime(s) d'inscription

Formation initiale

Présentation

Objectifs pédagogiques de la formation

Les objectifs du parcours "Algèbre Appliquée" sont d'acquérir une formation moderne et solide au calcul formel, à la géométrie et la cryptographie et de préparer aussi bien à la recherche fondamentale qu'à la recherche et au développement dans l'industrie et les services. A l'issue de la formation, les étudiants doivent être capable de modéliser algébriquement un problème concret en estimer la complexité et utiliser des algorithmes récents pour procéder à sa résolution.

Pour plus d'informations, vous pouvez consulter le site web de cette formation M2 Algèbre appliquée.

Lieu(x) d'enseignement

VERSAILLES

Pré-requis, profil d’entrée permettant d'intégrer la formation

Les étudiants doivent avoir obtenu une première année de Master en mathématiques. Une formation solide en algèbre est particulièrement recommandée : théorie de Galois, algèbre commutative, ensembles algébriques affines. Il est préférable d'avoir quelques notions d'informatique : complexité, notions de cryptographie, algorithmes de base. Voir le programme du M1 Mathématiques et interactions, Site UVSQ qui prépare spécifiquement au M2 Algèbre Appliquée.

Compétences

Modéliser algébriquement un problème concret en estimer la complexité et utiliser des algorithmes récents pour procéder à sa résolution.
Maitriser et mettre en oeuvre des outils et méthodes mathématiques de haut niveau.
Analyser un document de recherche en vue de sa synthèse et de son exploitation.
Maitriser des outils numériques et langages de programmation de référence.
Concevoir et rédiger une preuve mathématique rigoureuse.
Expliquer clairement une théorie et des résultats mathématiques.

Profil de sortie des étudiants ayant suivi la formation

A la fin de la formation, nos étudiants se répartissent de manière à peu près égale en deux groupes : une moitié de la proposition s'engage dans une thèse, le plus souvent dans le laboratoire de recherche où le stage a été effectué. Une autre moitié se dirige vers une activité professionnelle dans une entreprise (industrie ou service). Il est fréquent que les étudiants aient trouvé un travail à la sortie du M2.

Débouchés de la formation

Nous avons deux types de débouchés :
- dans le monde académique ce qui se traduit le plus souvent pas une thèse dans un laboratoire de recherche,
- en entreprise (industrie ou service) pour un emploi en recherche et développement par exemple.

Collaboration(s)

Laboratoire(s) partenaire(s) de la formation

Laboratoire de mathématiques de Versailles.

Programme

Introduction aux bases mathématiques de l'algèbre effective et de la cryptographie.

Matières	ECTS	Cours	TD
Algèbre effective	6	21	21
Algèbre effective Langues d’enseignement : FR/AN Intitulé de l’UE en anglais : Effective Algebra ECTS : 6 Détail du volume horaire : Cours : 21 Travaux dirigés : 21 Modalités d'organisation et de suivi : Coordinateur : Perrin Nicolas Equipe pédagogique : Nicolas Perrin (cours) Christina Boura (TD). Déroulement et organisation pratique : Cette UE se déroule sur 7 semaines et comporte 21 heures de cours et 21 heures de TD devant les machines. Objectifs pédagogiques visés : Contenu : Les principaux points étudiés dans ce cours sont : - Bases de Gröbner, - Algorithme de Buchberger - Théorie de l’élimination. - Résultants. - Applications et utilisation effective. Prérequis : Il est nécessaire d'avoir une bonne formation en algèbre commutative et théorie de Galois ainsi que des bases en calcul formel. Les étudiants travaillerons sur SAGE. Bibliographie : - D. Cox, J. Little et D. O’Shea, Ideal, varieties and algorithms, Springer, 1997. - D. Cox, J. Little et D. O’Shea, Using algebraic geometry, Springer, 1998. - T. Becker et V. Weispfenning, Gröbner Bases : A Computational Approach to Commutative Algebra,. Période(s) et lieu(x) d’enseignement : Période(s) : Septembre - Octobre - Novembre. Lieu(x) : VERSAILLES
Algorithmique et Langage C	6	21	21
Algorithmique et Langage C ECTS : 6 Détail du volume horaire : Cours : 21 Travaux dirigés : 21 Modalités d'organisation et de suivi : Coordinateur : Quisquater Michael Equipe pédagogique : Michael Quisquater et Yann Rotella. Déroulement et organisation pratique : Ce crois se déroule sur 14 semaines et comprends 21 heures de cours et 21 heures de TD. Objectifs pédagogiques visés : Contenu : Le but de ce cours est l’apprentissage de techniques algorithmiques visant à programmer efficacement, ainsi que du langage C. Un aperçu des outils d’analyse et de débogage gprof et gdb, ainsi que de la librairie de grands nombres GMP vient compléter ces objectifs. Chaque cours consiste en une étude approfondie d’un exemple, choisi en relation avec les autres modules du master. L’objectif étant, pour chacun d’eux, de comprendre les facteurs limitants et d’étudier comment les contourner afin d’obtenir des performances améliorées. – Multiplication de matrices 32 × 32 dans GF (2) – Eléments de base de calcul dans GF(p) – Calcul sur les polynômes à une et plusieurs variables – Algorithmes de Tri. Algorithmes de tri à base d’arbres équilibrés – Applications en cryptographie et théorie des nombres des algorithmes de tri. – Courbes elliptiques. Comptage de points par pas de bébé – pas de géant. – Compléments sur les courbes elliptiques : diviseurs, fonctions, couplage de Weil–Tate. Algorithmes pour les couplages. Applications cryptographiques : Diffie–Hellman tripartite, chiffrement basé sur l’identité, signatures courtes. – Transformées de Fourier et applications. Multiplication de polynômes, recherche d’approximation linéaires. – Problématique des accès en mémoire et des effets de cache. Application au crible d’Eratostène. – Algèbre linéaire et calcul de base de Gröbner sur GF(2). Prérequis : Bases d'algèbre, d'algorithmique et de programmation. Bibliographie : - Introduction to Algorithms (Second Edition). Cormen, Leiserson, Rivest et Stein, MIT Press et McGraw-Hill, 2001. - A course in computational algebraic number theory. Henri Cohen. Springer GTM 138. Période(s) et lieu(x) d’enseignement : Période(s) : Septembre - Octobre - Novembre - Décembre - Janvier - Février. Lieu(x) : VERSAILLES
Complexité algébrique et cryptographie	6	21	21
Complexité algébrique et cryptographie ECTS : 6 Détail du volume horaire : Cours : 21 Travaux dirigés : 21 Modalités d'organisation et de suivi : Coordinateur : Goubin Louis Equipe pédagogique : Louis Goubin. Déroulement et organisation pratique : Ce cours se déroule sur 7 semaine et comporte 21 heures de cours et 21 heures de TD. Objectifs pédagogiques visés : Contenu : L’objectif du cours est d’aborder les notions modernes de sécurité pour les algorithmes cryptographiques. 1. Chiffrement et signature : - factorisation (RSA) - logarithme discret (ElGamal, Schnorr, DSA) - réduction de réseaux (Merkle–Hellman, Chor–Rivest, NTRU) RSA : - attaques multiplicatives - preuves de sécurité : chiffrement (PKCS#1v1.5, OAEP, REACT) - signature (ISO/IEC 9796, Full-domain-hash, Probabilistic Signature Scheme) - générateurs pseudo-aléatoires prouvés sûrs (résiduosité quadratique) - tests de primalité des entiers (Solovay–Strassen, Miller–Rabin, AKS) Logarithme discret : - problème de la chasse au pirate (Boneh–Franklin) - diffusion sécurisée de contenus audiovisuels - courbes elliptiques et algorithmes de signature (ECDSA et Nyberg–Ruppel) - jacobienne d’une courbe hyperelliptique - couplage de Weil 2. Cryptosystèmes multivariables - problème MQ : résolution des systèmes d’équations quadratiques - isomorphismes de polynômes (IP) - détermination d’une combinaison linéaires de matrices ayant un petit rang (MinRank) - algorithmes C* (Matsumoto–Imai) et HFE : signatures électroniques ultra-rapides (SFLASH) ou extrêmement courtes (QUARTZ) - cryptanalyse, y compris symétrique (AES, chiffrement par flot) 3. Attaques physiques : - cas asymétrique : attaques par injection de faute sur RSA - mesure de la consommation électrique sur les courbes elliptiques - mesure du temps de calcul sur le protocole SSL (paiement sur internet). Prérequis : Bases d'algèbre et de cryptographie. Bibliographie : - Douglas Stinson, Cryptographie – Théorie et Pratique (Vuibert, 2003) - Gilles Zemor : Cours de Cryptographie (Cassini, 2000)- Alfred J. Menezes, Paul C. van Oorschot, Scott A. Vanstone, Handbook of Applied Cryptography (CRC Press, 1997) - Oded Goldreich. Période(s) et lieu(x) d’enseignement : Période(s) : Décembre - Janvier - Février. Lieu(x) : VERSAILLES
Courbes algébriques	6	21	21
Courbes algébriques ECTS : 6 Détail du volume horaire : Cours : 21 Travaux dirigés : 21 Modalités d'organisation et de suivi : Coordinateur : Secherre Vincent Equipe pédagogique : Vincent Sécherre et Nicolas Perrin. Déroulement et organisation pratique : Ce cours se déroule sur 7 semaines et comporte 21 heures de cours et 21 heures de TD. Objectifs pédagogiques visés : Contenu : Le but du cours est de définir mathématiquement les courbes elliptiques : - Topologie de Zariski - Variétés projectives, courbes projectives planes - Corps de fonctions - Morphisme de variétés projectives - Diviseurs, diviseurs sur les courbes, degré - Groupe de Picard - Cas des courbes elliptiques. Prérequis : Algèbre commutative et Théorie de Galois. Bibliographie : - W. Fulton, Algebraic curves, Benjamin 1969 - R. Hartshorne, Algebraic Geometry Springer 1977 - R.J. Walker, Algebraic curves Princeton University Press - D. Perrin, Géométrie algébrique : une introduction, CNRS Editions, 1995. Période(s) et lieu(x) d’enseignement : Période(s) : Septembre - Octobre - Novembre. Lieu(x) : VERSAILLES
Courbes elliptiques	6	21	21
Courbes elliptiques ECTS : 6 Détail du volume horaire : Cours : 21 Travaux dirigés : 21 Modalités d'organisation et de suivi : Coordinateur : Krir Mohamed Déroulement et organisation pratique : Ce cours se déroule sur 7 semaine et comporte 21 heures de cours et 21 heures de TD. Objectifs pédagogiques visés : Contenu : Ce cours est consacré à l’étude des courbes elliptiques en vue de leurs utilisations en cryptographie. - Courbes planes affines et projectives : propriétés locales, diviseurs. - Courbes elliptiques : généralités, forme de Weierstrass, loi de groupe, couplage de Weil. - Courbes elliptiques sur les corps finis - Courbes elliptiques sur le corps des nombres rationnels – Application des courbes elliptiques. Prérequis : Algèbre commutative, théorie de Galois, courbes algébriques. Bibliographie : - D. Perrin, Géométrie Algébrique, Une introduction, Savoirs Actuels, 1995. - W. Fulton, Algebraic Curves, Benjamin, 1969. - J. H.Silverman, The Arithmetic of Elliptic Curves, Springer, Graduate texts in Math. 106, 1986. Période(s) et lieu(x) d’enseignement : Période(s) : Décembre - Janvier - Février. Lieu(x) : VERSAILLES

Perfectionnement et mise en oeuvre de l'algèbre effective et de la cryptographie.

Matières	ECTS	Cours	TD	TP	Cours-TD	Cours-TP	TD-TP	A distance	Projet	Tutorat
Algorithmes avancés de la cryptographie, Cryptanalyse	6	21	21
Algorithmes avancés de la cryptographie, Cryptanalyse ECTS : 6 Détail du volume horaire : Cours : 21 Travaux dirigés : 21 Modalités d'organisation et de suivi : Coordinateur : Patarin Jacques Déroulement et organisation pratique : Ce cours se déroule sur 7 semaines et comporte 21 heures de cours et 21 heures de TD. Objectifs pédagogiques visés : Contenu : L’objectif est ici d’une part de donner aux étudiants une réelle expertise sur les grands algorithmes cryptographiques (la façon de les générer, et de les utiliser pour des applications réelles de l’industrie), et d’autre part d’introduire les principaux axes de recherche en cryptographie actuellement. On met ainsi l’accent sur les diverses techniques modernes de cryptanalyse, sur les contre-mesures de sécurité, sur les techniques de programmation efficaces des algorithmes, et sur divers problèmes ouverts. On détaillera en particulier les points suivants : – Le RSA revisité : diverses attaques de protocoles RSA, les normes actuelles, programmation rapide du RSA. – Les techniques de cryptanalyse à clé secrète : cryptanalyse différentielle, cryptanalyse linéaire, cryp- tanalyse multivariable (algébrique), autres techniques. – Cartes à puce : présentation des cartes à puces, les attaques physiques (SPA, DPA, DFA, etc.) et contre-mesures, exemples de protocoles pour certaines applications (cartes bancaires, de téléphone, de sécurité sociale, de télévision, etc.). – Courbes elliptiques et cryptographie : ECC (Elliptic Curve Cryptography). – La recherche actuelle en cryptographie : les grandes conférences annuelles, les revues et les ouvrages de recherche, les principaux articles récents. Prérequis : Bases en algèbre et en cryptographie. Bibliographie : - Douglas Stinson, Cryptographie – Théorie et Pratique (Vuibert, 2003) – Gilles Zemor : Cours de Cryptographie (Cassini, 2000). Période(s) et lieu(x) d’enseignement : Période(s) : Septembre - Octobre - Novembre. Lieu(x) : VERSAILLES

Matières	ECTS	Cours	TD	TP	Cours-TD	Cours-TP	TD-TP	A distance	Projet	Tutorat
Séminaire étudiant	3
Séminaire étudiant ECTS : 3 Modalités d'organisation et de suivi : Coordinateur : Perrin Nicolas Equipe pédagogique : Nicolas Perrin et Louis Goubin. Objectifs pédagogiques visés : Contenu : Le but du stage étudiant est de faire le point sur l'avancement du stage a mi-parcours. Il consiste en la rédaction d'un pré-rapport et/ou d'un exposé de présentation du stage. Période(s) et lieu(x) d’enseignement : Période(s) : Juin - Juillet. Lieu(x) : VERSAILLES
Stage	21
Stage ECTS : 21 Modalités d'organisation et de suivi : Coordinateur : Goubin Louis Equipe pédagogique : Louis Goubin et Nicolas Perrin. Déroulement et organisation pratique : Le stage de déroule sur 6 mois environ dans une entreprise ou dans un laboratoire de recherche. Il débute en mars/avril et se termine par une soutenance en septembre. Le stage se déroule sous la responsabilité d'un enseignant-chercheur associé au master. Ce stage comporte obligatoirement un projet de programmation, il fait l'objet d'un rapport de stage et d'une soutenance. Objectifs pédagogiques visés : Contenu : Le but du stage est d'introduire les étudiants à la recherche en laboratoire ou en entreprise ou plus directement à un travail en entreprise qui auront alors à lire, comprendre et appliquer un ou plusieurs articles de recherche ou développement industriel. Ce stage comporte obligatoirement un projet de programmation. Période(s) et lieu(x) d’enseignement : Période(s) : Mars - Avril - Mai - Juin - Juillet. Lieu(x) : VERSAILLES

Modalités de candidatures

Période(s) de candidatures

Du 01/03/2023 au 16/07/2023

Pièces justificatives obligatoires

Lettre de motivation.
Tous les relevés de notes des années/semestres validés depuis le BAC à la date de la candidature.
Attestation de français (obligatoire pour les non francophones).
Curriculum Vitae.
Descriptif détaillé et volume horaire des enseignements suivis depuis le début du cursus universitaire.
Dossier VAPP (obligatoire pour toutes les personnes demandant une validation des acquis pour accéder à la formation) https://www.universite-paris-saclay.fr/formation/formation-continue/validation-des-acquis-de-lexperience.
Fiche de choix de M2 (obligatoire pour les candidats inscrits en M1 à l'Université Paris-Saclay) à télécharger sur https://urlz.fr/i3Lo.

Pièces justificatives complémentaires

Document justificatif des candidats exilés ayant un statut de réfugié, protection subsidiaire ou protection temporaire en France ou à l’étranger (facultatif mais recommandé, un seul document à fournir) :
- Carte de séjour mention réfugié du pays du premier asile
- OU récépissé mention réfugié du pays du premier asile
- OU document du Haut Commissariat des Nations unies pour les réfugiés reconnaissant le statut de réfugié
- OU récépissé mention réfugié délivré en France
- OU carte de séjour avec mention réfugié délivré en France
- OU document faisant état du statut de bénéficiaire de la protection subsidiaire en France ou à l’étranger.

Contact(s)

Responsable(s) de la formation

Pierre-Guy PLAMONDON - pierre-guy.plamondon@uvsq.fr