¿Agregar números enteros representados por su factorización es tan difícil como factorizar? Solicitud de referencia

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 momento, y luego me emocioné cuando finalmente lo vi impreso).

El problema es "agregar dos enteros en la representación factorizada": dadas las factorizaciones primas de dos números e , se obtiene la factorización prima de . Tenga en cuenta que el algoritmo ingenuo para este problema utiliza la factorización en la representación binaria estándar como una subrutina.y x + $x$$y$$x+y$

Actualización : Gracias Kaveh y Sadeq por las pruebas. Obviamente, cuantas más pruebas, mejor, pero también me gustaría alentar más ayuda para encontrar una referencia , que como dije, estoy bastante seguro de que existe. Recuerdo haberlo leído en un documento con otras ideas interesantes y no discutidas a menudo, pero no recuerdo cuáles eran esas otras ideas o de qué trataba el documento en general.

Supongamos que podemos resolver el problema (llamémoslo FactSum) en la clase de complejidad y C está cerrado bajo la lógica de registro (también conocida como recursión limitada por el registro ) (por ejemplo, si podemos calcular x ∗ y donde ∗ es una función binaria, podemos calculado x 1 ∗ … ∗ x log n ) y contiene P (esta última condición puede debilitarse). Se demuestra que la factorización es en también en C .$C$$C$$\log$$\log$$x*y$$*$$x_1*\ldots*x_{\log{n}}$$\mathsf{P}$$C$

Tenga en cuenta que cada número puede escribirse como una suma de potencias de 2 . Cada uno de ellos es fácil de factorizar.$\log n$$2$

Ahora dado un número, escríbelo como la suma de las potencias de él, luego escribe cada sumando en la representación de factorización, y luego usa el algoritmo para sumarlos en la representación de factorización. El resultado será la factorización del número de entrada.

Esto muestra que la factorización es reducible a la creación de de su problema FactSum. Por lo tanto, la factorización está en P FactSum (y creo que P puede reemplazarse con N C 1 aquí).$\log$$\mathsf{P}^{\text{FactSum}}$$\mathsf{P}$$\mathsf{NC^1}$

No conozco una referencia, pero creo que se me ocurrió una prueba:

Suponga que tiene un oráculo que, al ingresar dos números factorizados$\mathcal{O}$

$x = \prod_{i=1}^n p_i^{\alpha_i}$

y

$y = \prod_{i=1}^m q_i^{\beta_i} \enspace$,

da como resultado la factorización de .$x+y$

Al tener acceso a , podemos factorizar cualquier número N en tiempo polinómico usando el siguiente procedimiento recursivo.$\mathcal{O}$$N$

Factor de procedimiento ( )$N$

1. Encuentre una prima tal que N / 2 ≤ x ≤ N - 1 , y sea y = N - x .$x$$N/2 \le x \le N-1$$y = N - x$
2. Si no es primo, obtenga la factorización de y por el factor de llamada recursivo ( y ) y la salida O ( x , f a c t o r ( y ) ) .$y$$y$$y$$\mathcal{O}(x, factor(y))$
3. Otra salida .$\mathcal{O}(x,y)$

Análisis:

Según el teorema de los números primos para suficientemente grande , hay muchos números primos entre N / 2 y N - 1 . Si N es tan pequeño que ningún primo cae en este intervalo, puede factorizar N fácilmente. Por lo tanto, el paso 1 pasa.$N$$N/2$$N-1$$N$$N$

En el paso 2, puede usar AKS o cualquier otra prueba de primalidad de tiempo polinómico.

El número de recursión es simplemente , ya que en cada paso N se reduce a la mitad (al menos)$O(\lg(N)) = O(|N|)$$N$

PS-1: Asumir la conjetura de Goldbach podría ayudar a acelerar el procedimiento para enteros pares (y posiblemente impares).

PS-2: La reducción utilizada es una reducción de Cook. Uno podría estar interesado en llevar a cabo la prueba utilizando las reducciones de Karp.

Esta respuesta es independiente de mi respuesta anterior . Su objetivo es abordar la preocupación de @ Kaveh en los comentarios:

$\log n$$\log \log n$

Tenía una preocupación similar:

La reducción utilizada es una reducción de Cook. Uno podría estar interesado en llevar a cabo la prueba utilizando reducciones de Karp.

(Las reducciones de Karp son para problemas de decisión. Aquí, por reducción de Karp, me refiero a una reducción de Cook de una sola consulta. ¡Perdón por la terminología no estándar!)

La respuesta a continuación se basa en las discusiones aquí: /math/54580/factoring-some-integer-in-the-given-interval .

En esta respuesta, proporcionaré una reducción de Karp en tiempo polinimial determinista de factorizar a factorizar la suma de dos enteros representados por sus factorizaciones . Sin embargo, hay una trampa: en el curso de la prueba, usaré la siguiente suposición de teoría de números:

$p_n$$p_{n+1}$$p_{n+1} - p_n = O(\log^2p_n)$

$N$$n=|N|=O(\log N)$$N$$[N - \log^3N, N]$$\log^3N = O(n^3)$

$x$$[N - \log^3N, N]$$y=N-x$

$0 \le y \le \log^3N$$|y| = O(\log \log N) = O(\log n)$$y$

$(x,y)$$N = x+y$