Algèbre et cryptologie
Ref: 2EL1740
Description
Ce cours est une introduction aux outils mathématiques modernes, et leur matérialisation en applications technologiques et scientifiques.
À la croisée des mathématiques fondamentales, de l'informatique et de la théorie de l'information, nous aborderons des questions telles que
- Comment envoyer un message depuis une sonde spatiale ?
- Comment garantir l'authenticité d'un document numérique ?
- Comment trouver de très grands nombres premiers ? Ou factoriser de grands nombres ?
- et beaucoup d'autres
L'objectif de ce cours est de doter les étudiants :
- D'un bagage culturel sur le développement des mathématiques au 20e et 21e siècle, avec un langage qui leur permettra d'approfondir ces questions
- D'une maîtrise opérationnelle du calcul dans les structures algébriques, en particulier anneaux, corps finis et courbes elliptiques
- D'une compréhension des fondements mathématiques de la cryptologie moderne
Période(s) du cours
SG8
Prérequis
Ce cours ne suppose pas de connaissances spécifiques au-delà de notions mathématiques générales normalement acquises en classes préparatoires.
Une familiarité avec la programmation informatique est fortement recommandée.
Attention, ce cours demande un travail sérieux et conséquent, pour assimiler et s'approprier les notions discutées.
Syllabus
- En 2023 le cours détaillait notamment les points suivants :
- Applications des groupes cycliques [Diffie-Hellman'76, Schnorr'89, ElGamal'85]
- Constructions élémentaires sur les corps finis [Reed-Solomon'60, Shamir'79, Toom-Cook-66]
- Outils arithmétiques élémentaires [Miller-Rabin'80, Pollard'74, Dixon'81]
- Groupe de Picard des anneaux de Dedekind et des variétés projectives lisses
- Réduction de réseaux et applications [LLL''82, Lagarias-Odlyzo'85, Wiener'02, Coppersmith'96]
- Courbes elliptiques sur les corps finis et applications [Lenstra'85, Koblitz-Miller'86, NIST'05]
- Apprentissage avec erreurs et applications [Regev'05, Dilithium'22]
Composition du cours
- Les cours sont présentés au tableau
- Des notes de cours, reprenant les éléments importants, sont fournies après les séances
- Des exemples commentés de calcul formel sont mis à disposition
- Les TDs prennent la forme d'une application détaillée des notions acquises et permet de les mettre en contexte et d'en discuter les spécificités ou les limites
- Un contrôle continu permet de s'approprier les notions importantes du cours et de les mettre en œuvre
Ressources
- Cours magistral au tableau, certains exercices nécessitent l'utilisation de l'ordinateur. Le cas échéant on précisera les logiciels à installer.
Equipe enseignante : Rémi Géraud-Stewart (remi.geraud@ens.fr)
Résultats de l'apprentissage couverts par le cours
A la
fin de ce cours, les élèves seront capables de :
- Identifier les structures algébriques manifestes dans les problèmes rencontrés
- Comprendre les enjeux et les outils de la cryptologie et de la théorie des codes, et (re)connaître leurs principales applications industrielles
- Maîtriser le langage dans lequel sont formulés et analysés les problèmes algébriques
Support de cours, bibliographie
- David Eisenbud, Commutative Algebra (with a View Toward Algebraic Geometry)
- Robin Hartshorne, Algebraic Geometry
- William Fulton, Algebraic curves: An Introduction to Algebraic Geometry
- Henning Stichtenoth, Algebraic Function Fields and Codes
- Michel Demazure, Cours d'algèbre
- Joseph H. Silverman, The Arithmetic of Elliptic Curves
- Joseph H. Silverman, Advanced Topics in the Arithmetic of Elliptic Curves
- Jean-Pierre Serre, Cours d'arithmétique
- Michael Tsfasman, Serge Vlǎduţ, Dmitry Nogin, Algebraic Geometric Codes: Basic Notions