M1 Algèbre Appliquée et Cryptologie

Algèbre de Licence (groupes, anneaux, corps, polynômes et congruences), cours de théorie des nombres et cryptographie.

• Anneaux noethériens, théorème de la base de Hilbert.
• Topologie de Zariski de k^n.
• Correspondance entre idéaux et fermés algébriques.
• Anneaux de fractions, localisation.
• Extensions entières : going up et going down.
• Lemme de normalisation, degré de transcendance, dimension.
• Nullstellensatz

L’objectif de ce cours est de permettre aux étudiants d’aborder sereinement la géométrie algébrique et l’algèbre effective. Le cours est tourné vers l’étude des anneaux de polynômes. On cherche constamment à interpréter géométriquement les théorèmes d’algèbre abstraite : lemme de normalisation vs. projection sur un espace vectoriel, Nullstellensatz vs. recherche de l’idéal d’un fermé algébrique. Interprétation géométrique de la dimension de Krull.

Atiyah et Mac Donald, An introduction to commutative algebra, Addison-Wesley, 1969. Chambert-Loir Algèbre commutative et introduction ) la géométrie algébrique http://www.math.u-psud.fr/ chambert/enseignement/2013-14/aceiga/Dea.pdf Cox, Little et O’Shea, Ideal, varieties and algorithms, Springer, 1991. Matsumura, Hideyuki Commutative ring theory. Cambridge University Press, 1986. C. Peskine An algebraic introduction to complex projective geometry, I. Commutative algebra, Cambridge University Press, 1996. D. Perrin, Cours d’algèbre, Ellipses, 1996. Samuel et Zariski, Commutative algebra, 2 volumes, Springer.

Algèbre de Licence et cours d’algèbre générale de M1 semestre 1.

• Droite et plan projectifs
• Coniques et cubiques projectives planes
• Points d’inflexions
• Invariant modulaire
• Courbes elliptiques
• Fonctions rationnelles et diviseurs sur une courbe elliptique
• Théorème d’Abel-Jacobi

C’est un cours d’introduction à la théorie algébrique des courbes elliptiques, considérées comme des cubiques du plan projectif. On définit d’abord le plan projectif, et on effectue la classification des coniques projectives planes (sur un corps algébriquement clos). On étudie ensuite les cubiques projectives planes : on prouve qu’elles possèdent toujours un point d’inflexion, et qu’elles sont entièrement caractérisées par leur invariant modulaire. On définit ensuite les courbes elliptiques, puis la loi de groupe, les fonctions rationnelles et les diviseurs sur une courbe elliptique. On termine le cours par le théorème d’Abel-Jacobi, déterminant à quelles conditions un diviseur sur une courbe elliptique est le diviseur d’une fonction rationnelle.

J. Silverman, The arithmetic of elliptic curves, GTM 106, Springer, 1986. J. Silverman & J. Tate, Rational points on elliptic curves, Springer, 1992. Ou tout autre livre introductif sur les courbes elliptiques.

Algèbre de licence (anneaux, idéaux, groupes)

• extensions de corps : finies, algébriques, séparables, normales, galoisiennes
• morphismes d’extensions
• groupes de Galois
• théorème fondamental de la théorie de Galois

La théorie de Galois, développée par le mathématicien français Evariste Galois (1811-1832), établit le lien entre deux familles d’objets algébriques : les groupes et les corps. Dans ce cours nous allons étudier des différents types d’extensions de corps (finies, algébriques, séparables, normales, galoisiennes) et leurs groupes d’automorphismes afin d’arriver à démontrer le théorème fondamental de la théorie de Galois qui établit le lien mentionné ci-dessus.

Calais J., Extensions de corps, théorie de Galois, Ellipses, 2006. Chambert-Loir A., Algèbre corporelle, disponible à l’adresse : http://www.math.polytechnique.fr/ chambert/ Escofier J.-P., Théorie de Galois, Dunod, 2000. Gozard I., Théorie de Galois, Ellipses, 1997. Morandi P., Field and Galois theory, GTM 167, Springer, 1996. Tauvel P., Corps commutatifs et théorie de Galois, Calvage et Mounet, 2008.

Algèbre de Licence (groupes, anneaux, corps, polynômes et congruences)

• Groupes et anneaux
• Entiers et polynômes en une indéterminée
• Congruences modulo un entier
• Corps finis
• Les entiers de Gauss et le théorème des deux -carrés
• Anneaux euclidiens, principaux, factoriels
• Le théorème des unités et l’équation de Pell

L’objectif de ce cours est de mettre en évidence la façon dont des propriétés algébriques (notamment les structures de groupe et d’anneau) peuvent servir à prouver des résultats arithmétiques, avec des applications à la cryptographie. Au début du cours, on rappelle brièvement les notions de théorie des groupes et des anneaux qui seront nécessaires dans la suite. On étudie notamment l’anneau des entiers relatifs et les anneaux de polynômes en une indéterminée à coefficients dans un corps, en insistant sur leurs propriétés algébriques communes. On étudie ensuite les propriétés arithmétiques des anneaux de congruence Z/nZ et des corps finis, y compris la loi de réciprocité quadratique de Gauss, et on en déduit plusieurs tests de primalité. On introduit ensuite diverses propriétés de structure (anneaux euclidiens, principaux, factoriels, intégralement clos, etc.) et leurs conséquences en arithmétique (notamment le théorème des deux carrés). On introduit enfin la notion d’entier quadratique et on démontre le théorème des unités, qui permet de résoudre l’équation de Pell x^2+dy^2 = 1.

M. Demazure, Cours d’algèbre, Cassini, 1997. M. Hindry, Arithmétique, Calvage et Mounet, 2008. K. Ireland et M. Rosen, A classical introduction to modern number theory, Graduate texts in mathematics 84, Springer, 1990. D. Perrin, Cours d’algèbre, Ellipses, 1996.

• Analyse d’algorithmes, modèles de complexité, complexité asymptotique, classes de complexité.
• Structures de données et algorithmes : ordonnancement, piles, files, tables de hachage, arbres, graphes.
• Programmation dynamique, programmation linéaire entière.
• Algorithmes arithmétiques : multiplication, pgcd, multiplication de matrices.
• Algorithmes géométriques : programmation linéaire, diagrammes de Voronoï

Introduction aux techniques de conceptions d’algorithmes et d’analyse de performances.

TPs sur machine avec environnement Python/Sage.

Thomas H. Cormen. Charles E. Leiserson. Ronald L. Rivest. Clifford Stein. Introduction to Algorithms. Third Edition. The MIT Press. Cambridge, Massachusetts. Christos H. Papadimitriou. Computational complexity. Addison-Wesley, 1994. 523 pages.

Algèbre et algébre linéaire de licence : arithmétique modulaire, calculs dans les corps finis. Rudiments de théorie des probabilités et de statistiques. Connaissances de base en algorithmique.

Cryptographie à clé secrète, Cryptographie à clé publique

• Attaques brutales, attaques par rejeu
• Attaques à chiffré seul, attaques à clair choisi, attaques à clair et chiffré choisis
• Attaques interactives et non interactives
• Chiffrement par flot, chiffrement par blocs
• Transposition et substitution, schémas de Feistel
• DES, AES
• Fonctions à sens unique, fonctions de hachage
• Algorithmes d’échange de clés
• RSA, Algorithmes zero-knowledge
• Applications

Le but est de présenter un panorama des principaux algorithmes utilisés en chiffrement, authentification et signature électronique, ainsi que leur utilisation pour sécuriser les communications numériques. A l’issue de ce cours, les étudiants devront pouvoir :

• utiliser l’arithmétique modulaire et les opérations de base sur les corps finis liées aux techniques cryptographiques
• décrire les concepts et algorithmes cryptographiques de base, incluant le chiffrement/déchiffrement, les fonctions de hachage et la cryptographie à clé publique
• évaluer la sécurité de primitives cryptographiques
• concevoir et analyser des protocoles pour des objectifs de sécurité variés

N. Koblitz, A Course in Number Theory and Cryptography, GTM 114, Springer, 1994. A.J. Menezes, P.C. van Oorschot, S.A. Vanstone, Handbook of Applied Cryptography, CRC Press, 1997. D. Stinson, Cryptography : Theory and Practice, Third Edition (Discrete Mathematics and Its Applications), CRC Press, 2005. S. Vaudenay, A Classical Introduction to Cryptography : Applications for Communications Security, Springer, 2005.

Algèbre et analyse de licence

• Objets de base : Les grands entiers, les polynômes à 1 variable.
• Représentation. Addition et soustraction. Multiplication. Division euclidienne.
• Algorithme d’Euclide : pgcd, identité de Bézout. Applications.
• Arithmétique modulaire. Théorème chinois des restes.
• Evaluation et interpolation (polynômes de Legendre). Changement de représentation.
• Multiplication rapide : Karatsuba ; transformée de Fourier discrète.
• Division euclidienne rapide grâce à Newton.
• Evaluation et interpolation rapides. Théorème chinois des restes rapide.
• Algorithme d’Euclide rapide.
• Algèbre linéaire rapide : multiplication de matrices selon Strassen.
• Factorisation de polynômes sur un corps fini (Gauss).

Ce cours est une initiation au Calcul formel (Computer Algebra en anglais). Celui-ci s’intéresse aux méthodes qui permettent de trouver des résultats de façon :

• Exacte (par opposition au Calcul numérique).
• Effective (par opposition aux théorèmes purement existentiels).
• Efficace (par opposition aux calculs dont la faisabilité est purement théorique). L’outil de base est donc l’algorithme, dont on verra divers types. La question de l’efficacité donnera lieu à des analyses de complexité.

Une partie non négligeable du cours se passera devant des ordinateurs, et sera consacrée à implémenter des algorithmes vus en cours en s’appuyant sur des logiciels de calcul formel tels que Sage.

J. Von zur Gathen & J. Gerhard, Modern Computer Algebra, 3rd Edition, Cambridge University Press (2013). V. Shoup, A Computational Introduction to Number Theory and Algebra, 2nd Edition, Cambridge University Press (2008).

Bases de cryptographie

• Le cours couvrira des aspects pratiques de ces problèmes de sécurité (débordement de tampon, rétro-analyse de code, attaques par canaux auxiliaires, injection de fautes, ...)
• Ce sera aussi l’occasion d’approfondir des questions plus théoriques (modélisation de la notion de calcul, machines de Turing, garbled circuits, programmes auto-modifiants, obfuscation de code, ...), en montrant comment ces notions peuvent être utilisées pour prévenir les vulnérabilités du logiciel.
• Le cours et les TDs seront illustrés par de nombreux exemples, notamment issus de la sécurité des cartes à puce, de la virologie informatique, et des applications émergentes dans le «calcul en nuage» (cloud computing).

Traditionnellement, en cryptographie, on cherche à garantir la confidentialité, l’intégrité et l’authenticité de «messages», qui sont des objets «statiques» (stockés, ou transmis tels quels sur des canaux de communication non sécurisés). En revanche on ne considère pas la sécurité des algorithmes et protocoles cryptographiques eux-mêmes (qui sont en général des programmes, qui s’exécutent, et sont donc des objets «dynamiques»). Par exemple on ne s’intéresse pas :

• à la confidentialité des programmes (le principe de Kerckhoffs suppose qu’ils sont connus de tout le monde),
• ni à leur intégrité (on suppose qu’Alice et Bob exécutent ces algorithmes / protocoles / programmes correctement, sans aucune modification / erreur / bug),
• ni à leur authenticité (on suppose que les algorithmes / protocoles / programmes exécutés par Alice et Bob ont été installés par une autorité de confiance).
  Dans l’UE «Calcul sécurisé», on verra qu’en réalité il est très important de sécuriser également les calculs (au sens d’algorithmes / protocoles / programmes).

Algèbre linéaire. Quelques éléments d’algèbre. Théorie élémentaire des probabilités.

• Notions de base en théorie de l’information (entropie, information mutuelle).
• Algorithmes de compression sans perte (étape 1 de la chaîne de codage).
• Théorie des codes correcteurs d’erreurs (étape 3 de la chaîne de codage).
• Canal sans mémoire à temps discret. Notion de capacité. Théorème de codage pour un canal bruyant. Principe de décodage par maximum de vraisemblance. Borne sur la probabilité d’erreur de décodage.
• Théorie des codes correcteurs en blocs. Distance minimale et problématique des bornes sur la taille d’un code. Notion de code parfait.
• Codes linéaires. Matrice génératrice et matrice de parité. Décodage par syndrome. Codes duaux. Polynôme énumérateur des poids. Identité de Mac-Williams.
• Etude de certaines familles de codes linéaires (en bloc) et algorithmes de décodage.
• Codes convolutionnels et algorithme de Viterbi.

Le but d’un système de communication est le transport d’information d’une source à un destinataire via un canal de communication. Ce canal possède en général des imperfections ce qui peut engendrer des erreurs de transmission. Aussi, le canal peut être sujet à des écoutes ce qui peut poser des problèmes de confidentialité. Finalement, l’utilisation d’un canal a un coût, il est donc important d’optimiser son usage. Pour répondre à ces différentes exigences, on effectue un prétraitement de l’information ; il s’agit de la chaîne de codage. Celle-ci se divise en trois étapes : compression, chiffrement et ajout de redondance. Ces techniques font appel à la théorie des probabilités et à l’algèbre discrète. Ce cours présente les bases de la première et la troisième étape de la chaîne de codage, la seconde étant abondamment étudiée dans des cours de cryptographie.

The Theory of Error-Correcting Codes. F. J. MacWilliams, N. J. A. Sloane North Holland Publishing Co. 1977. Théorie des codes (Compression, cryptage, correction). J.-G. Dumas, J.-L. Roch, E. Tannier et S. Varrette, Dunod 2007.

Calcul intégral et Théorie de la mesure ; Probabilités

• Espaces de probabilités, variables aléatoires, indépendance
• Conditionnement, Espérance conditionnelle.
• Chaînes de Markov discrètes, marches aléatoires discrètes
• Convergences des variables aléatoires
• Théorèmes limites pour les chaînes de Markov discrètes

Le module est consacré principalement à l’étude des chaînes de Markov à espace d’états discret, avec des applications aux marches aléatoires et à des processus à valeurs dans un espace d’états discret. Dans le cadre de cette étude, nous approfondirons les notions d’espérance conditionnelle et de loi conditionnelle. Le cours se terminera par des théorèmes limites incluant des rappels sur les différents modes de convergence possibles dans le domaine des
probabilités.

J.F. Le Gall. Cours Fimfa. Intégration, probabilités et processus aléatoires.
https://www.math.u-psud.fr/ jflegall/IPPA2.pd P. Barbe et M. Ledoux, Probabilité, Belin, 1998.
B. Bercu et D. Chafai, Modélisation stochastique et simulation. Cours et applications, Dunod, 2007.
R. Durrett, Probability : Theory and Examples, Duxbury, 2005.
D. Foata et A. Fuchs : Calcul des Probabilités : Cours, exercices et problémes corrigés, Dunod, 2003.
Olivier Garet, Aline Kurtzmann, De l’intégration aux probabilités, Ellipses, 2011.
P. Baldi, L. Mazliak et P. Priouret Martingales et Chaînes de Markov. Hermann, collection Méthodes, 1998.

• Etre capable de comprendre à l’oral comme à l’écrit des supports d’anglais général et scientifique.
• Etre capable de faire des présentations orales et écrites sur des sujets d’actualité divers.
• Avoir d’importantes notions en grammaire anglaise.

• Job Interview
• Debating
• CV - Cover letter - Essay writing
• Listening Comprehension
• TOEIC training

Dans un contexte à caractère professionnel, les cours en anglais Master visent à aider les étudiants à faire face aux exigences du monde du travail.

Analyse et algèbre linéaire et matriciel de licence

• Eléments et bases de la programmation en Langage C (ou en Python).
• Rappels sur les méthodes directes pour la résolution de systèmes linéaires
• Méthodes itératives classiques (Jacobi, Gauss-Seidel, relaxation).
• Méthodes itératives modernes. Méthodes des sous-espaces de Krylov.
• Calcul de valeurs propres.
• Schémas de résolution d’équations différentielles.
• Méthode des différences finis.
• Introduction à la méthode des éléments finis (problèmes aux limites 1D et 2D)

Le but de cette UE est de préparer les étudiants aux bases de la programmation et du calcul
scientifique et à la modélisation. Elle comporte essentiellement trois parties.
La première partie du cours sera dédiée à la maitrise des éléments fondamentaux d’un langage de programmation de type C ou Python. L’apprentissage du langage sera accompagné
d’une mise en oeuvre de quelques algorithmes numériques.
La deuxième partie sera consacrée aux méthodes numériques modernes et leur implémentation. Il s’agira essentiellement de la résolution de systèmes linéaires, des équations différentielles et des équations aux dérivées partielles. On y abordera aussi l’étude de problèmes issus de la modélisation mathématique de phénomènes rencontrés dans d’autres disciplines (physique, biologie, sciences de l’ingénieur, science de données, etc.).
La troisième partie consistera en la réalisation d’un projet.

- J. Stoer et R. Bulirsh, Introduction to numerical analysis, Springer (2nd edition).
- : Ph. G. Ciarlet, Introduction à l’analyse numérique matricielle et Optimisation, Masson, 1988.
- Introduction au calcul scientifique. Aspects algorithmiques, P. Ciarlet, en ligne.
-  R. Herbin, Analyse numérique des équations aux dérivées partielles, HAL, en ligne.
- A. Ern et J.-L. Guermond, éléments finis : théorie, applications, mise en oeuvre, Springer.