Enseignement
Algorithmes pour l'arithmétique II 2021-22
Cours d'
Algorithmes pour l'arithmétique II, année 2021-22,
Master 2 Mathématiques et applications (parcours ACC), Université Paris 8.
Lieu : salle B 103
Horaire : le mercredi de 15h15 à 18h00
Emploi du temps prévisionnel :
- 22-09-2021. Rappels d'algorithmes pour l'algèbre linéaire. Suites récurrentes, LFSR, algorithme de Berlekamp--Massey.
- 29-09-2021. Suites vectorielles. Calcul de polynôme annulateur. Application à résolution de systèmes linéaires creux.
- 06-10-2021. Extraction de racines carrées : dans les entiers naturels, dans les corps finis, dans les entiers modulaires.
- 13-10-2021. Factorisation de polynômes sur les corps finis : algorithme de Berlekamp.
- 20-10-2021. Factorisation de polynômes sur les entiers et les rationnels.
- 27-10-2021. Factorisation d'entiers : méthodes spéciales. Fermat, Pollard ρ, p-1, ECM (aperçu).
- 03-11-2021. Pas de cours.
- 10-11-2021. Factorisation d'entiers : méthodes génériques. Crible quadratique, crible algébrique (aperçu).
- 17-11-2021. Calcul de logarithme discret dans un groupe générique : baby-step-giant-step, Pohlig--Hellman, , théorème de Shoup.
- 24-11-2021. Calcul de logarithme discret dans le groupe multiplicatif d'un corps fini.
- 01-12-2021. Pas de cours.
- 08-12-2021. Réseaux euclidiens, algorithme LLL.
- 15-12-2021. Séance de présentations courtes d'algorithmes par les étudiants (évaluation n°2).
Documents utiles :
Références :
- 1. Algorithmes Efficaces en Calcul Formel, Bostan, Chyzak, Giusti, Lebreton, Lecerf, Salvy, Schost, auto-édition, 2017, disponible en ligne ici.
- 2. Introduction to Finite Fields and their Applications, 2nd ed., Lidl, Niederreiter, Cambridge University Press, 1994.
- 3. Modern Computer Algebra, 2nd ed., Gathen, Gerhard, Cambridge University Press, 2003.