Enseignement

Algorithmes pour l'arithmétique II 2020-21

Cours d'Algorithmes pour l'arithmétique II, enseigné en 2020-21 aux étudiants des Masters 2 ACC et CSSD de l'Université Paris 8.

Lieu : en ligne (pour l'instant)
Horaire : le mardi de 12h00 à 15h00

Emploi du temps prévisionnel :

• 17-11-2020. Cours déplacé. (chevauchement avec Histoire des sciences)
• 24-11-2020. [Visio] Factorisation de matrices. Suites récurrentes linéaires, algorithme de Berlekamp-Massey.
• 01-12-2020. [Visio] Suites récurrentes vectorielles, polynômes minimaux de matrices et algorithme de Wiedemann. TD.
• 08-12-2020. [Visio] Extraction de racines carrées.
• 15-12-2020. [Visio] Factorisation de polynômes sur les corps finis.
• 05-01-2021. [Visio] Factorisation de polynômes dans les entiers.
• 12-01-2021. [Visio] Factorisation des entiers. Méthodes spéciales : Fermat, Pollard ρ, p-1, p+1, ECM (aperçu).
• 19-01-2021. [Visio] Factorisation des entiers. Méthodes génériques : crible quadratique, crible algébrique.
• 26-01-2021. [Visio] Logarithme discret dans un groupe générique. Baby-step-giant-step, Pohlig-Hellman, théorème de Shoup.
• 02-02-2021. [Visio] Logarithme discret dans le groupe multiplicatif d'un corps fini.

Documents utiles :

• Support des cours en visio : [Cours 1] [Cours 2] [Cours 3] [Cours 4] [Cours 5] [Cours 6] [Cours 7] [Cours 8] [Cours 9]
• Devoir à la maison, à rendre pour le 10 janvier : [Sujet]
• Devoir à la maison 2, à rendre pour le 13 février : [Sujet] [Fichier annexes (zip)]

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.