El mes pasado, pregunté si existe un algoritmo eficiente para encontrar la raíz cuadrada módulo de una potencia prima aquí: ¿Existe un algoritmo eficiente para encontrar una raíz cuadrada módulo de una potencia prima?
Ahora, digamos que me dan un número entero positivo n y conozco sus factores. Un artículo de Manders y Adleman dice que encontrar la raíz cuadrada de un número $\alpha$ módulo n es NP-completo, incluso si se conocen los factores de n.
Pero supongamos que $n=p_1^{e_1} p_2^{e_2} ... p_m^{e_m}$ . Si puedo calcular eficientemente la raíz cuadrada de $\alpha$ mod $p_i^{e_i}$ para cada $i$ ¿por qué no puedo utilizar el Teorema del Resto Chino para obtener la raíz cuadrada de $\alpha$ ¿módulo n eficiente?
De hecho, lo probé para $\alpha=862$ y $n=931=7^2 19$ . En este caso, 29=862 mod 49 y 7 = 862 mod 19. Las raíces cuadradas son 15,34 y 8,11 respectivamente. Para cada una de estas combinaciones, obtuve 407, 505, 426, 524 como raíces cuadradas de 862 mod 931.
Desde luego, no creo que P=NP. Entonces, ¿qué hay de malo en esta estrategia general?
