Algorithmes arithmétiques II

Deuxième partie du cours d'Algorithmes arithmétiques, année 2023-24, 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, de préférence dans un langage de calcul formel (ex: sagemath).

Lieu : salle A043
Horaire : le mardi de 15h15 à 18h00

Emploi du temps prévisionnel :

• 19-09-2023. Rappels d'algorithmes pour l'algèbre linéaire. Suites récurrentes, LFSR, algorithme de Berlekamp--Massey.
• 26-09-2023. Suites vectorielles. Calcul de polynôme annulateur. Application à résolution de systèmes linéaires creux.
• 03-10-2023. Extraction de racines carrées : dans les entiers naturels, dans les corps finis, dans les entiers modulaires.
• 10-10-2023. Festival maths en ville
• 17-10-2023. Factorisation de polynômes sur les corps finis : algorithme de Berlekamp.
• 24-10-2023. Rattrapage du retard pris sur les derniers cours.
• 31-10-2023. Pause pédagogique
• 07-11-2023. Factorisation de polynômes sur les entiers et les rationnels.
• 10-11-2023. Factorisation d'entiers : méthodes spéciales. Fermat, Pollard ρ, p-1, ECM (aperçu).
• 21-11-2023. Factorisation d'entiers : méthodes génériques. Crible quadratique, crible algébrique (aperçu).
• 28-11-2023. Calcul de logarithme discret dans un groupe générique : baby-step-giant-step, Pohlig--Hellman, théorème de Shoup.
• 05-12-2023. Calcul de logarithme discret dans le groupe multiplicatif d'un corps fini.
• 12-12-2023. Évaluation orale (1/2)
• 19-12-2023. Évaluation orale (2/2)

Documents utiles :

• Notes de cours (en construction) : [cours]
• Slides : [Slides 7] [Slides 8] [Slides 9]
• TDs :
  • TD1 : [sujet] [challenges] [sol. exo]
  • TD2 : [sujet] [sol. exo]
  • TD3 : [sujet]
• Scripts : [ algebre lineaire (27/09/23)] [ sqrt (23/10/23)]
• Devoir maison (à rendre jusqu'au 31 décembre 2023 dernier délai) : [Sujet DM]
• Autres ressources : [Analyse graphique de complexité]
• Évaluation orale (présentation d'algorithmes) : [Sujets]
  
  • veuillez envoyer votre liste de choix avant le lundi 13 novembre 2023
    

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.