Calcul formel, codes et cryptographie

M2 Informatique et Math-Info, U. Montpellier, 2015-2022

Une partie des sujets de TD est due à Romain Lebreton.

Quelques notes de cours

Ces notes sont sans doute remplies de typos ou erreurs plus graves. À utiliser à vos risques et périls (et n’hésitez pas à me signaler les problèmes !).

• L’algorithme du demi-pgcd
• Codes correcteurs (première partie uniquement)

Sujets de TD/TP

• 2021-2022 +-
  • TD1 : arithmétique entière
  • TD2 : PGCD et inversion modulaire
  • TD3 : Multiplication de polynômes
  • TD4 : Produit médian et inversion
  • TD5 : PGCD rapide
  • TD6 : évaluations de polynômes
  • TD7 : décodage en liste
  • TD11 : codes de Reed-Solomon

• 2020-2021 +-
  • TD1 : arithmétique entière
  • TD2 : PGCD et inversion modulaire
  • TD3 : multiplication de polynômes
  • TD4 : produit médian et inversion
  • TD5 : PGCD rapide
  • TD6 : protocoles d'échanges de clef
  • TD10 : évaluations de polynômes
  • TD11 : codes de Reed-Solomon
  • DM [poly_corps_finis.py]
• 2019-2020 +-
  • TD 1 : arithmétique entière
  • TD 2 : PGCD et inversion modulaire
  • TD 3 : multiplication de polynômes
  • TD 4 : décalage de polynômes et produit médian
  • TD 7 : autour d'ElGamal (certes, la numérotation est un peu chaotique...)
  • TD 8 : autour d'ElGamal
  • TD 10 : PGCD et résultant
  • TD 11 : codes correcteurs d'erreurs
  • TD 12 : évaluations de polynômes
  • DM : implantation de l'algorithme du demi-PGCD [corps_finis.py]
• 2018-2019 +-
  • TD 1 : arithmétique entière naïve
  • TD 2 : PGCD et inversion modulaire
  • TD 3 : multiplication de polynômes
  • TD 4 : décalage et produit médian de polynômes
  • TD 5 : résultant de polynômes
  • TD 6 : protocoles d'échange de clés
  • TD 7 : ElGamal et algorithmes pour le logarithme discret
  • TD 8 : Algorithmes pour le logarithme discret
  • TD 9 : RSA et algorithmes de factorisation
  • TD 10 : Codes correcteurs d'erreurs
  • TD 11 : Codes de Reed-Solomon
  • TD 12 : Algorithme de Guruswami et Sudan
• 2017-2018 +-
  • TP 1 : arithmétique entière naïve
  • TP 2 : PGCD, Z/nZ, primalité
  • TD 3 : multiplication de polynômes
  • TP 4 : arithmétique rapide de polynômes
  • TP 5 : algorithme du demi-pgcd pour les polynômes
  • TD 6 : protocoles d'échange de clés
  • TD 7 : ElGamal et algorithmes pour le logarithme discret
  • TD 8 : RSA et algorithmes de factorisation
  • TD 9 : Codes correcteurs d'erreurs
  • TD 10 : Codes de Reed-Solomon
  • TD 11 : Algorithme de Guruswami et Sudan
• 2016-2017 +-
  • TD6 : protocole d'échange de clefs

Bibliographie

• J. von zur Gathen, J. Gerhard. Modern Computer Algebra. 3nd ed. Cambridge University Press, 2013. La bible du calcul formel.
• A. Bostan, F. Chyzak, M. Giusti, R. Lebreton, G. Lecerf, B. Salvy. Algorithmes efficaces en calcul formel, 2017. Ouvrage en français téléchargeable librement : que demander de plus ?
• J. Katz, Y. Lindell. Introduction to Modern Cryptography, 2nd ed. CRC Press, 2015. Le titre dit tout…
• V. Guruswami, A. Rudra, M. Sudan. Essential Coding Theory, 2017. Version préliminaire d’un ouvrage initialement prévu pour fin 2017.

Dernière modification : 24 janvier 2023