Qu'est-ce que Algorithme de Shor ?

Réponse : A. La cryptographie à clé publique, comme RSA et la cryptographie sur courbes elliptiques

La sécurité de RSA repose sur la difficulté de factoriser de grands nombres, et celle de la cryptographie sur courbes elliptiques sur la difficulté du problème du logarithme discret. L'algorithme de Shor résout ces problèmes en temps polynomial en trouvant des périodes grâce à la transformée de Fourier quantique. Des clés trop longues pour être cassées en un temps réaliste par des ordinateurs classiques pourraient alors l'être par un ordinateur quantique tolérant aux fautes suffisamment grand. Face à la cryptographie symétrique, comme AES, il n'existe que l'accélération quadratique de l'algorithme de Grover, que l'on peut contrer par des clés plus longues.

Réponse : C. Un nombre énorme de portes doit être exécuté sans erreur, ce qui exige de nombreux qubits logiques construits par correction d'erreurs et un nombre gigantesque de qubits physiques pour les porter

Casser RSA-2048 demande d'exécuter à la suite des portes de l'ordre de plusieurs milliards sur environ un millier à plusieurs milliers de qubits logiques. Le taux d'erreur logique doit donc être extrêmement faible, et la correction d'erreurs exige plusieurs centaines de qubits physiques ou plus par qubit logique. Les estimations faites dans les années 2020 situent le besoin entre quelques centaines de milliers et quelques dizaines de millions de qubits physiques avec des taux d'erreur d'environ 0,1 % (les chiffres varient beaucoup selon les hypothèses), soit des ordres de grandeur au-delà de l'échelle des dispositifs actuels. Ces estimations diminuent toutefois à mesure que les algorithmes s'améliorent : la préparation de la migration cryptographique doit donc commencer tôt.