(Non)practicabilité de l'algorithme classique-quantique de factorisation des entiers

Abstract

Les avancées dans la construction de l'ordinateur quantique ont posé la question des compromis espace-temps pour la factorisation des entiers où l'espace représente le nombre de qubits. On se pose ainsi la question de réaliser une factorisation avec NFS, le meilleur algorithme classique, d'un entier de 1024 bits sous l'hypothèse qu'on sache factoriser en temps négligeable des entiers d'au plus 150 bits.