Aller au contenuAller à la rechercheAller au menu

UE Algèbre effective et cryptographie

Diplômes intégrant cet élément pédagogique :

Descriptif

  1. Arithmétique modulaire, complexité, arithmétique des corps finis
  2. Nombres premiers, test de primalité de Miller-Rabin, certificat de primalité de Pocklington
  3. Polynômes irréductibles, tests d’irréducibilité, application à la construction des corps finis et à la factorisation des polynômes
  4. Concepts de base de cryptographie, chiffrement symétrique et asymétrique
  5. Problème du logarithme discret, échange de clefs Diffie-Hellman, réduction de Pohlig-Hellman, algorithme générique Pollard-Rho, pas-de-bébé-pas-de-géant
  6. Factorisation et cryptosystème RSA
  7. Codes correcteurs d’erreurs : concepts fondamentaux, exemple des codes de Hamming, codes polynomiaux, codes de Reed-Solomon

Les étudiants travailleront pendant le dernier quart de l’UE sur un thème à choisir et présenter oralement, dont voici quelques exemples :

  • Approfondissement d'un des points ci-dessus
  • Générateurs de nombres aléatoires, registres à décalage et suites récurrentes linéaires, algorithme de Berlekamp-Massey
  • Carrés modulaires, symbole de Legendre et réciprocité quadratique, problème de résiduosité quadratique et applications, test de primalité de Solovay-Strassen
  • Factorisation d'entiers par l’algorithme du crible quadratique
  • Factorisation dans Z[X]

Ce cours s’adresse à tous les étudiants intéressés par les applications modernes de l’algèbre et de l’arithmétique. Il est particulièrement adapté aux étudiants souhaitant passer l’agrégation option C (calcul formel) ou poursuivre dans une formation en cryptographie et/ou codes correcteurs d’erreurs. L'UE propose notamment des séances de TP sur machine avec le logiciel Xcas, offrant la possibilité de se familiariser avec la partie programmation de l’épreuve obligatoire de modélisation de l’agrégation.

Bibliographie

  • G. Zémor, Cours de cryptographie, Cassini
  • J. Vélu, Méthodes mathématiques pour l’informatique, Dunod
  • M. Hindry, Arithmétique, Calvage & Mounet
  • G. Bailly-Maitre, Arithmétique et cryptologie, Ellipses
  • V. Shoup, Computational introduction to number theory and algebra, Cambridge University Press
  • Page de SageMath et Sage Quick Reference Cards
  • Page d'installation de Xcas

Informations complémentaires

Langue(s) : Français