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.