 | | |
| MATH0064-1 | Mathématiques discrètes II
|
|
| Durée : | 30h Th, 30h Pr |
|
| Nombre de crédits : |
|
|
| Nom du professeur : | Michel Rigo |
|
Langue(s) du cours :
|
| Langue française |
|
Contenus du cours :
|
| Dans ce cours de mathématiques discrètes, on aborde principalement les thèmes suivants : étude des suites linéaires récurrentes (sur un anneau quelconque), introduction à la cryptographie et aux codes correcteurs. Ces sujets trouvent de nombreuses applications : problèmes de dénombrement en combinatoire, sécurisation du commerce électronique, problème d'authentification, partage de secrets, ....
En se basant sur des connaissances classiques en algèbre acquises lors des deux premières années du cursus, on étudie les suites linéaires récurrentes (sur un anneau, sur un champ ou sur un champ fini). On donne quelques techniques de résolution des suites linéaires (par des méthodes exactes mais aussi par des méthodes approchées au moyen d'une analyse asymptotique élémentaire). Comme application, on passe en revue plusieurs problèmes de dénombrement comme le comptage du nombre de mots bien parenthésés. Ensuite, on présente certains aspects classiques de la cryptographie moderne : systèmes à clé privée, à clé publique, cryptosystème RSA, problème du logarithme discret, cryptanalyse, génération aléatoire de grands nombres premiers, algorithmes de factorisation, fonctions de hachage,... (Suivant le temps disponibles, on pourra aussi s'intéresser aux cryptosystèmes construits sur une courbe elliptique.) On s'intéresse en particulier aux algorithmes mis en oeuvre et à leur complexité. En guise d'illustration, des implémentations sont réalisées sous Mathematica. Enfin, on présente une introduction élémentaire aux codes correcteurs d'erreurs. Le cours s'intéresse principalement aux aspects théoriques, les nombreuses applications n'étant qu'esquissées. |
|
Acquis d'apprentissage (objectifs d'apprentissage) du cours :
|
| Au terme de ce cours, l'étudiant maîtrisera des notions fondamentales issues de l'étude des champs finis (structure, générateurs, construction de tels champs), de la cryptographie (RSA et sa mise en oeuvre, logarithme discret,...) et des suites linéaires récurrentes (séries formelles et génératrices, matrice compagnon, corps fini, nombres de Catalan,...) ainsi que les preuves et raisonnements sous-jacents. L'étudiant aura appréhendé la structure des corps finis et intégré les concepts de cryptosystème à clé privée/publique et de chiffrement. Il/elle sera capable d'expliquer et d'appliquer les différents mécanismes pouvant apparaître lors de la recherche d'une formule clause pour une suite linéaire récurrente. |
|
Prérequis et corequis / Modules de cours optionnels recommandés :
|
| De bonnes bases en algèbre générale (groupes, anneaux, espaces vectoriels) sont nécessaires pour aborder le cours (cours de 2e bachelier en mathématique ou équivalent). |
|
Mode d'enseignement (présentiel ; enseignement à distance) :
|
| Le cours est consacré principalement aux aspects théoriques. Les séances de répétition permettent de présenter la résolution d'exercices et l'illustration ou la concrétisation des concepts vus au cours. On pourra envisager d'implémenter certains algorithmes lors de ces séances d'exercices (par exemple, on pourra illustrer les concepts cryptographiques dans un logiciel du type Mathematica). L'horaire des cours et des séances d'exercices sera communiqué en début d'année. |
|
Lectures recommandées ou obligatoires et notes de cours :
|
| Des notes reprenant l'ensemble de la matière enseignée au cours théorique seront distribuées aux étudiants en début d'année. Ces notes sont téléchargeables sur http://www.discmath.ulg.ac.be/ (http:///) |
|
Modalités d'évaluation et critères :
|
| L'examen en session comporte uniquement une partie orale. Cet examen porte sur la théorie et ses applications directes (on pourra par exemple demander de résoudre au tableau ou sur feuille un petit exercice). |
|
Remarques organisationnelles :
|
| Des compléments d'information sont disponibles sur
http://www.discmath.ulg.ac.be/ |
|
Contacts :
|
| M. Rigo
Institut de Mathématique (B37) - Grande Traverse 12 - Sart Tilman, 4000 Liège
Tél. : (04) 366.94.87 - E-mail : M.Rigo@ulg.ac.be |
|
|
|
| Notes en ligne : |
|
|
| |
