¿Escribir un número como dos cuadrados y escribir los factores de un número es igualmente difícil?

Dejar $L_1$ y $L_2$ ser el siguiente:

$L_1=\{r:\exists x,y \in \mathbb{Z} \text{ such that } x^2+y^2=r\}$

$L_2=\{(N,M): M<N, \exists 1<d\leq M \text{ such that d|N} \}$

Reclamación $L_1 \leq_P L_2$

Prueba de croquis

Si quiero saber si $r\in L_1$.

El número de soluciones enteras para $x^2+y^2=r$ es dado por

$g(r)=\sum_{d|r}{\chi{(d)}}$ dónde $\chi (x)=sin(\frac{\pi x}{2})=\cases{ 1\text{ when }x\cong 1 \text{ mod }4 \\ -1 \text{ when }x\cong 3 \text{ mod }4 \\ 0 \text{ when } 2|x }$

Entonces $L_1=\{r: g(r)\neq 0\}$. Entonces, responder es "$r\in L_1$"es como mucho tan difícil de responder como" ¿cuáles son los divisores de $r$? "

$\square$

Lo que me gustaría saber es si esto es cierto al revés. ¿Es cierto que si tuviera una máquina que me dijera en tiempo constante si$r\in L_1$ ¿podría crear una máquina que podría responder "es $(M,N)\in L_2$? "en tiempo polinomial?

Motivaciones

Esta pregunta surgió de una discusión sobre esta pregunta .

Disculpas Soy realmente un miembro de math.se que se ha perdido y vagado a cs.se. Avíseme si mi pregunta es clara y cumple con los estándares de este sitio. Estoy feliz de hacer correcciones.

Aquí está la situación hasta donde puedo decir:

La forma más eficiente conocida para probar la membresía en $L_1$ es factorizar $r$. Parece que no se conoce un algoritmo más eficiente.

Sin embargo, no hay una reducción obvia para demostrar $L_2 \le_P L_1$. En otras palabras, si tuviéramos una máquina para decidir$L_1$, no hay una manera fácil de usar eso para factorizar. Si queremos factorizar un número$N$, podemos verificar si $N \in L_1$, pero esto solo nos da un poco de información sobre los factores de $N$. Prueba de múltiplos de$N$ (es decir, si $cN \in L_1$ para algún entero $c$) no nos proporciona ninguna información adicional, como saber si $N \in L_1$ es suficiente para predecir si $cN \in L_1$ para todos $c>0$. Probar otros números tampoco parece ayudar de ninguna manera obvia. (Prueba si$N' \in L_1$ para algún otro número $N'$ no parece dar ninguna información útil, si $\gcd(N,N') =1$; y si tuviéramos una manera de encontrar otro número tal que , ya sabríamos cómo factorizar, pero por supuesto no sabemos cómo hacerlo, así que es poco probable que cualquier número que sepamos generar nos brinde información útil sobre los factores de ) Esto no es una prueba; es solo intuición manual.$N'$$\gcd(N,N')\ne 1$$N$

Por lo tanto, parece plausible que sea ​​más fácil que , y también parece plausible que puedan tener la misma dificultad. No tengo conocimiento de ningún otro resultado sobre este tema.$L_1$$L_2$