Algorithmes arithmétiques II


Deuxième partie du cours d'Algorithmes arithmétiques, année 2025-26, enseigné en Master 2 Mathématiques et applications (parcours ACC), à l'Université Paris 8.

Résumé. Ce cours a pour but de présenter et d'analyser divers algorithmes de nature arithmétique ou algébrique, dans des contextes d'application en cryptographie et en codage. Une attention particulière sera donnée à l'implantation effective de ces algorithmes.

Lieu : salle A188.
Horaire : le lundi de 9h à 11h45.

Programme prévisionnel :
  • 22-09-2025. Introduction. Évaluation de complexité. Rappels d'algorithmes pour l'algèbre linéaire dense. TP1 : opérations matricielles.
  • 29-09-2025. Suites récurrentes, algorithme de Berlekamp--Massey. Suite du TP1.
  • 06-10-2025. Algèbre linéaire creuse, méthode de Horner, algorithme de Wiedemann. Fin du TP1.
  • 13-10-2025. Racines carrées sur les corps finis. TP2 (Berlekamp).
  • 20-10-2025. Factorisation de polynômes sur les corps finis. TP3 (Wiedemann).
  • 27-10-2025. Pause pédagogique.
  • 03-11-2025. Factorisation des entiers : méthodes génériques. TP4.
  • 10-11-2025. Factorisation des entiers : méthodes spéciales. TP5.
  • 17-11-2025. Factorisation des entiers : crible quadratique. TP6.
  • 24-11-2025. Logarithme discret.
  • 01-12-2025. Fin des TPs. Conseils pour les présentations orales.
  • 08-12-2025. Évaluations orales 1.
  • 15-12-2025. Évaluations orales 2.
Documents pour les TP :
  1. TP1 (algèbre linéaire dense) [sujet] [fichiers python initiaux] [fichiers après la séance 2]
  2. TP2 (LFSR et Berlekamp-Massey) [sujet] [fichiers python initiaux]
  3. TP3 (Algèbre linéaire creuse) [sujet] [fichiers python initiaux]
  4. TP4 (Factorisation de polynômes) [sujet] [fichiers python initiaux]
  5. TP5 (Factorisation d'entiers 1 -- méthodes exponentielles) [sujet] [fichiers python initiaux]
  6. TP6 (Factorisation d'entiers 2 -- méthodes spéciales) [sujet] [fichiers python initiaux]
Documents de cours : Évaluation :
  1. Devoir maison. [Sujet DM] À rendre par email jusqu'au dimanche 23 novembre 2025 dernier délai.
  2. Présentation d'algorithmes. [Sujets et consignes] Veuillez envoyer votre liste de choix avant le vendredi 21 novembre 2025. L'assignation des sujets vous sera ensuite envoyée par email.
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.