Description
Le cours d’algorithmique arithmétique présente les principaux problèmes algorithmiques de la théorie des nombres utilisés en cryptographie à clés publiques. La première partie du cours se place dans le cadre de l’algorithmique classique (machines de Turing). La deuxième partie du cours est une introduction au calcul quantique et à ses répercussions pour la sécurité des cryptosystèmes.
Après un rappel de théorie de la complexité, le cours présente les rudiments de l’arithmétique rapide (multiprécision, exponentiation rapide). La factorisation des entiers et le calcul des logarithmes discrets sont étudiés en détail : après un tour d’horizon des algorithmes élémentaires, les différents cribles sont présentés et analysés. Une introduction aux courbes elliptiques clôture cette première partie.
Le but de la partie quantique du cours est de présenter l’algorithme de Shor qui permet de résoudre les problèmes de factorisation et de calcul du logarithme discret en temps polynomial.
Le cours est illustré par des exercices de programmation dans le langage de programmation SAGE. En particulier les étudiants implémenteront leurs algorithmes quantiques sur un simulateur.