IQIS Lecture 6.9 — Shor's algorithm

Cette leçon, dispensée par Artur Ekert, présente l’algorithme de Shor pour la factorisation des entiers. L’auteur commence par rappeler le problème de Simon, qui a inspiré la recherche de problèmes de périodicité dans d’autres structures algébriques. Il explique ensuite comment Shor a adapté cette idée au groupe multiplicatif des entiers modulo n, reliant ainsi la factorisation à l’estimation de période. La fonction considérée est a^x mod n, dont la période s permet de factoriser n via le calcul de PGCD. L’auteur illustre la méthode avec l’exemple de la factorisation de 15. Il souligne que la difficulté classique de ce problème est à la base de la sécurité du cryptosystème RSA, mais que l’algorithme quantique de Shor le résout en temps polynomial. La mise en œuvre quantique repose sur une superposition d’états, une évaluation de fonction quantique et une transformée de Fourier quantique adaptée au groupe Z_n^*. L’algorithme nécessite un post-traitement classique et peut échouer avec une probabilité fixe, mais en répétant les essais, la probabilité de succès tend vers 1. L’auteur conclut en soulignant l’impact majeur de cet algorithme sur la cryptographie.