Enseignement
Algorithmes arithmétiques II 2022-23
Cours d'
Algorithmes arithmétiques, 2eme partie, année 2022-23,
Master 2 Mathématiques et applications (parcours ACC), Université Paris 8.
Lieu : salle A148
Horaire : le jeudi de 15h15 à 18h00
Emploi du temps prévisionnel :
- 22-09-2022. Rappels d'algorithmes pour l'algèbre linéaire. Suites récurrentes, LFSR, algorithme de Berlekamp--Massey.
- 29-09-2022. Suites vectorielles. Calcul de polynôme annulateur. Application à résolution de systèmes linéaires creux.
- 06-10-2022. Extraction de racines carrées : dans les entiers naturels, dans les corps finis, dans les entiers modulaires.
- 13-10-2022. Factorisation de polynômes sur les corps finis : algorithme de Berlekamp.
- 20-10-2022. Factorisation de polynômes sur les entiers et les rationnels.
- 27-10-2022. Factorisation d'entiers : méthodes spéciales. Fermat, Pollard ρ, p-1, ECM (aperçu).
- 03-11-2022. Pause pédagogique.
- 10-11-2022. Grève : cours reporté.
- 17-11-2022. Factorisation d'entiers : méthodes génériques. Crible quadratique, crible algébrique (aperçu).
- 24-11-2022. Calcul de logarithme discret dans un groupe générique : baby-step-giant-step, Pohlig--Hellman, théorème de Shoup.
- 01-12-2022. Calcul de logarithme discret dans le groupe multiplicatif d'un corps fini.
- 08-12-2022. Réseaux euclidiens, algorithme LLL.
- 15-12-2022. Séance de présentations (évaluation).
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.