Esta es una "pregunta histórica" más de lo que es una pregunta de investigación, pero ¿fue la reducción clásica a la búsqueda de orden en el algoritmo de factorización de Shor inicialmente descubierta por Peter Shor, o se sabía previamente? ¿Existe algún documento que describa la reducción...
El libro de Arora y Barak presenta el factoring como el siguiente problema: FACTORING={⟨L,U,N⟩|(∃ a prime p∈{L,…,U})[p|N]}FACTORIZACIÓN={⟨L,U,norte⟩El |(∃ un primer pags∈{L,...,U})[pagsEl |norte]}\text{FACTORING} = \{\langle L, U, N \rangle \;|\; (\exists \text{ a prime } p \in \{L, \ldots, U\})[p...
Deje que PRIMES (también conocido como prueba de primalidad ) sea el problema: Dado un número natural nnn , ¿es nnn un número primo? Deje que FACTORING sea el problema: Dados los números naturales , m con 1 ≤ m ≤ n , ¿ n tiene un factor d con 1 < d < m ?nnnmmm1≤m≤n1≤m≤n1 \leq m \leq...
Esta es una publicación cruzada de math.stackexchange. Deje que FACT denote el problema de factorización de enteros: dado encuentre los primos y los enteros modo quep i ∈ N , e i ∈ N , n = ∏ k i = 0 p e i i .n ∈ N ,n∈N,n \in \mathbb{N},pagsyo∈ N ,pi∈N,p_i \in \mathbb{N},miyo∈ N ,ei∈N,e_i \in...
No se sabe que la factorización es NP-completa. Esta pregunta solicitó las consecuencias de que Factoring sea NP-completo. Curiosamente, nadie preguntó por las consecuencias de Factoring estar en P (tal vez porque esa pregunta es trivial). Entonces mis preguntas son: Cual seria el teorico...
Dado un entero de longitud bits, ¿qué tan difícil es generar el número de factores primos (o alternativamente el número de factores) de ?NNNnnnNNN Si supiéramos la factorización principal de , entonces esto sería fácil. Sin embargo, si supiéramos el número de factores primos, o el número de...
La publicación de blog de Scott Aaronson hoy dio una lista de interesantes problemas / tareas abiertas en complejidad. Uno en particular me llamó la atención: Cree una biblioteca pública de instancias 3SAT, con la menor cantidad de variables y cláusulas posibles, que tendrían consecuencias...
¿Hay alguna referencia que cubra
Esta pregunta se migró de Computer Science Stack Exchange porque se puede responder en Teorematic Computer Science Stack Exchange. Migrado hace 3 años . En el artículo de Ciencia de 2016 " Realización de un algoritmo Shor escalable " [ 1 ], los autores factorizan 15 con...
Estoy buscando una referencia para el siguiente resultado: Agregar dos enteros en la representación factorizada es tan difícil como factorizar dos enteros en la representación binaria habitual. (Estoy bastante seguro de que está ahí afuera porque esto es algo que me había preguntado en algún...
Es bien sabido que la exponenciación modular (la parte principal de una operación RSA) es computacionalmente costosa, y hasta donde yo entiendo, la técnica de exponenciación modular de Montgomery es el método preferido. La exponenciación modular también se destaca en el algoritmo de factorización...
En su artículo de 1995 Algoritmos de tiempo polinómico para la factorización prima y los logaritmos discretos en una computadora cuántica , Peter W. Shor analiza una mejora en la parte de búsqueda de orden de su algoritmo de factorización. Las salidas algoritmo estándar r′r′r' , un divisor de la...
Acabo de leer la pregunta " ¿Es la factorización entera un problema NP-completo? " ... así que decidí gastar algo de mi reputación :-) haciendo otra pregunta teniendo :QQQPAG( Q es trivial ) ≈ 1PAG(Q es trivial)≈1P(\text{Q is trivial}) \approx 1 Si es un oráculo que resuelve la factorización de...
Mientras leía el blog de Dick Lipton, me topé con el siguiente hecho cerca del final de su publicación de Bourne Factor : Si, por cada nnn , existe una relación de la forma (2n)!=∑k=0m−1akbckk(2n)!=∑k=0m−1akbkck (2^n)! = \sum_{k=0}^{m-1} a_k b_k^{c_k} donde m=poly(n)m=poly(n)m = poly(n) , y...
En el " Consejo para un estudiante graduado principiante " de Manuel Blum : LEONID LEVIN cree mientras hago eso, sea cual sea la respuesta a la P = NP? problema, no será como todo lo que crees que debería ser. Y ha dado algunos ejemplos maravillosos. Por un lado, ha dado un ALGORITMO DE...
Dada compuesto N∈NN∈NN\in\Bbb N tamiz campo de número general es mejor algoritmo de factorización conocida para la factorización de enteros de NNN . Es un algoritmo aleatorio y obtenemos una complejidad esperada de
En 1975, Miller mostró cómo reducir la factorización del número entero para encontrar el período r de una función f ( x ) = a xNNNrrr tal que f ( x + r ) = f ( x ) con algunos elegidos al azar a < N . Es bien sabido que el algoritmo de Shor puede encontrar r eficientemente en una computadora...
¿Cuál es el algoritmo más rápido conocido para factorizar polinomios con nnn variables y grado total ≤d≤d\leq d ? Aquí, nnn está creciendo ddd está arreglado. La mayoría del trabajo parece considerar el caso cuando ddd está creciendo nnn es fijo. Me interesan los resultados tanto en campos finitos...
Me parece que la tarea de eliminación de cuadrados se puede reducir a la tarea de factorización , pero que no hay forma de reducir la factorización a la eliminación de cuadrados. ¿Hay alguna manera de hacer que este "sentimiento" sea más preciso, es decir, alguna hipótesis comúnmente creída que se...