…atelier ouvert de Joachim Séné, écriture…

AVERTISSEMENT :
Ce texte a été publié il y a longtemps, par conséquent, il commence à s'effacer. Les textes de plus de quatre ans sont presque illisibles. Prenez garde.
Voir la page vernis numérique pour en savoir plus sur cette patine numérique.

Shor, Peter W. Algorithme en temps polynomial pour la décomposition en produit de facteurs premiers et la recherche de logarithmes discrets sur un ordinateur quantique

mise en ligne : mercredi 14 octobre 2015

Un ordinateur numérique est généralement considéré comme une unité de calcul universellement efficace ; autrement dit, on suppose qu’il est capable de simuler n’importe quel dispositif informatique physique avec une augmentation au plus polynomiale du temps de calcul. Cela peut ne pas être le cas quand on considère la mécanique quantique. Cet article se propose d’étudier la décomposition en produit de facteurs premiers, et la recherche de logarithmes discrets ; deux problèmes généralement jugés complexes sur un ordinateur classique, et ont été justement utilisés comme base de nombreux systèmes de cryptographie. Nous donnerons pour ces deux problèmes des algorithmes probabilistes efficaces sur une machine quantique hypothétique. Ces algorithmes prennent un certains nombres d’étapes-polynomiales en entrée, i.e. le nombre de chiffres de l’entier à décomposer.

Algorithme en temps polynomial pour la décomposition en produit de facteurs premiers et pour les logarithmes discrets sur un ordinateur quantique. Peter W. Shor, IAM J.Sci.Statist.Comput. 26 (1997).
( trad. JS [1])

[1] Je précise que… n’ai pas tout compris…

Mots-clés

Peter W. Shor   paradoxe  
Vous pouvez soutenir mon écriture en achetant un livre, en commandant une Nuit écrite à la main pour vous, en devenant abonné.e à partir de 1 €/mois via Tipee, vous pouvez aussi