C’est une "question historique" plus qu’une question de recherche, mais la réduction classique à la recherche d’ordres dans l’algorithme de factorisation de Shor a-t-elle été découverte à l’origine par Peter Shor, ou était-elle connue auparavant? Existe-t-il un document décrivant la réduction...
Le livre d’ Arora et Barak présente l’affacturage comme le problème suivant: FACTORING={⟨L,U,N⟩|(∃ a prime p∈{L,…,U})[p|N]}FACTORING={⟨L,U,N⟩|(∃ a prime p∈{L,…,U})[p|N]}\text{FACTORING} = \{\langle L, U, N \rangle \;|\; (\exists \text{ a prime } p \in \{L, \ldots, U\})[p | N]\} Ils ajoutent, plus...
Ceci est un post-cross de math.stackexchange. Soit FACT représentent le problème de factorisation d'entiers: étant donné trouver des nombres premiers p i ∈ N , et les entiers e i ∈ N , de telle sorte que n = Π k i = 0 p e i i .n∈N,n∈N,n \in \mathbb{N},pi∈N,pi∈N,p_i \in \mathbb{N},ei∈N,ei∈N,e_i \in...
Laissez PRIMES (aka test de primalité ) être le problème: Étant donné un nombre naturel , est-il un nombre premier?nnnnnnn Soit FACTORING le problème: Soit les nombres naturels , avec , a-t-il un facteur avec ?nnnmmm1≤m≤n1≤m≤n1 \leq m \leq nnnnddd1<d<m1<d<m1 < d < m Sait-on si PRIMES...
L'affacturage n'est pas connu pour être NP-complet. Cette question portait sur les conséquences de la factorisation de NP-complet. Curieusement, personne n’a demandé les conséquences de l’affacturage dans P (peut-être parce qu’une telle question est triviale). Donc mes questions sont: Quelles...
Étant donné un entier de longueur n bits, est-il difficile de produire le nombre de facteurs premiers (ou alternativement le nombre de facteurs) de N ?NNNnnnNNN Si nous connaissions la factorisation première de , ce serait facile. Cependant, si nous connaissions le nombre de facteurs premiers ou...
Le blog de Scott Aaronson a donné aujourd'hui une liste de problèmes / tâches ouverts intéressants en complexité. Un en particulier a retenu mon attention: Construisez une bibliothèque publique d'instances 3SAT, avec aussi peu de variables et de clauses que possible, qui aurait des conséquences...
Y a-t-il des références couvrant
Cette question a été migrée à partir de Computer Science Stack Exchange car il est possible d'y répondre sur Theoretical Computer Science Stack Exchange. Migré il y a 3 ans . Dans l'article scientifique de 2016 " Réalisation d'un algorithme de Shor évolutif " [ 1 ], les auteurs factorisent 15 avec...
Je recherche une référence pour le résultat suivant: Ajouter deux entiers dans la représentation factorisée est aussi difficile que factoriser deux entiers dans la représentation binaire habituelle. (Je suis presque sûr que c'est là-bas parce que c'est quelque chose que je me demandais à un moment...
Il est bien connu que l'exponentiation modulaire (la partie principale d'une opération RSA) est coûteux en calcul, et pour autant que je comprends les choses, la technique d' exponentiation modulaire de Montgomery est la méthode préférée. L'exponentiation modulaire est également mise en évidence...
Dans son article de 1995 Algorithmes à temps polynomial pour la factorisation principale et les logarithmes discrets sur un ordinateur quantique , Peter W. Shor discute d'une amélioration de la partie recherche d'ordres de son algorithme de factorisation. Les sorties algorithme standard , un...
Je viens de lire la question " La factorisation des nombres entiers est-elle un problème NP-complet? " ... alors j'ai décidé de dépenser une partie de ma réputation :-) en posant une autre question ayant :P ( Q est trivial ) ≈ 1QQQP( Q est trivial ) ≈ 1P(Q est trivial)≈1P(\text{Q is trivial})...
En lisant le blog de Dick Lipton, je suis tombé sur le fait suivant vers la fin de son billet Bourne Factor : Si, pour tout , il existe une relation de la forme où , et chacun des , et ont une longueur de bits , puis l'affacturage a un polynôme circuits de
Dans les « Conseils à un étudiant débutant » de Manuel Blum : LEONID LEVIN croit que je fais cela quelle que soit la réponse au P = NP? problème, ce ne sera pas comme vous le pensez. Et il a donné de merveilleux exemples. D'une part, il a donné un ALGORITHME DE FACTORISATION qui est de manière...
Compte tenu composite N∈NN∈NN\in\Bbb N tamis de champ numérique général est le meilleur algorithme de factorisation connu pour factorisation entier de NNN . Il s'agit d'un algorithme randomisé et nous obtenons une complexité attendue de
En 1975, Miller a montré comment réduire la factorisation de l'entier pour trouver la période d'une fonction telle que f (x + r) = f (x) avec certains choisis au hasard a <N . Il est bien connu que l'algorithme de Shor peut trouver r efficacement sur un ordinateur quantique, alors qu'il est...