Syllabus :
Objectifs visés
Voir comment l'arithmétique, la pratique et la théorie, permet de développer quelques applications spectaculaires en informatique, en particulier dans le domaine de la sécurité.
Utiliser le formalisme algébrique de la théorie des langages réguliers à la résolution de problèmes concrets relatifs aux langages de programmation (critères de régularité ou de non-régularité, approximation d'un langage par un langage régulier, …).
- Pré-requis
Mathématiques discrètes et notion des langages
- Contenu
Arithmétique et primalité.
Arithmétique élémentaire : anneau Z/nZ, théorème chinois, théorème d'Euler, petit théorème de Fermat.
Cryptographie à clés publiques utilisant les nombres premiers : méthode RSA
Critères de primalité et non-primalité
Calculabilité et complexité
Langages réguliers
Automate minimal d'un langage régulier.
Théorème de Myhill-Nerode.
Congruence syntaxique et monoïde syntaxique d'un langage.
Applications : critères de régularité.
Langages réguliers.
- Références bibliographique
Marc Hindry, Arithmétique : Primalité et codes, Théorie analytique des nombres, Equations diophantiennes, Courbes elliptiques Broché – 28 février 2008
P.Wolper, introduction à la calculabilité;