mathématiques

Algorithmes à Temps Polynomial pour Factorisation Primaire et Logarithmes Discrets sur un Ordinateur Quantique :
On considère généralement qu'un ordinateur numérique est un dispositif informatique universel efficace; C'est-à-dire qu'on l'estime capable de simuler n'importe quel dispositif de calcul physique avec augmentation du temps de calcul d'un facteur polynomial au plus.
Cela peut ne pas être vrai lorsque la mécanique quantique est prise en considération. Cet article examine l'affacturage des entiers et la recherche de logarithmes discrets, deux problèmes qui sont généralement considérés comme difficiles sur un ordinateur classique et qui ont servi de base à plusieurs propositions de cryptosystèmes. Des algorithmes aléatoires efficaces sont donnés pour ces deux problèmes sur un ordinateur quantique hypothétique. Ces algorithmes passent un certain nombre d'étapes polynomiales dans la mémoire d'entrée, par exemple le nombre de numéros de l'entier à prendre en compte.

Auteur: Shor Peter W

Info: AT&T Research, révisé en 1996

[ computation ]