Comprobar si un número entero es la suma de dos cuadrados

Question

¿Existe un algoritmo rápido (probabilístico o determinista) para determinar si un número entero $n$ es la suma de dos cuadrados?

Por "rápido" me refiero a tiempo polinómico (es decir, tiempo $O((\log n)^{O(1)})$ ). Obsérvese que sólo me interesa saber si el número entero puede representarse de esa manera, no cómo se representa.

Dado que se requiere un algoritmo rápido, no se puede utilizar la factorización.

Sería impar si esto resultara más difícil que detectar la primalidad, ya que los números primos son más raros.

(Esta es una pregunta que surgió en una charla que acabo de dar).

Answer 1

Este problema es equivalente a detectar si existe algún primo $p\equiv3\pmod4$ dividiendo el número elevado a una potencia impar. En el peor de los casos, cuando el número es un semiprimo grande equivalente a 1 mod 4, esto es casi seguramente tan difícil como la FACTORIZACIÓN. Si fuera fácil, entonces se daría el segundo bit más bajo en los dos factores primos de tales números; si tuviéramos suficiente información de este tipo podríamos recuperar los factores mediante el algoritmo de Coppersmith.

Prácticamente, comprueba el número mod 4 (una vez que elimines los 0 finales) y mira si es 3, luego prueba a dividir por primos pequeños.

Answer 2

Hay situaciones en las que sabemos que un número es una suma de dos cuadrados aunque no conozcamos la factorización, y de hecho sabemos muy poco sobre los factores. Esta pregunta por ejemplo, señala que $F_{2k+1}=F_k^2+F_{k+1}^2$ (el $F_k$ son los números de Fibonacci). Por otro lado, aunque los números de Fibonacci son más fáciles de factorizar que la mayoría, no son triviales (creo que Blair Kelly mantiene una lista de factores ).

Para ser más específicos, $F_{1049}$ es una suma de dos cuadrados, pero aún no ha sido factorizada.

Answer 3

La pregunta es equivalente a probar si -1 es un cuadrado módulo n. Esto corresponde al problema de la residualidad cuadrática que es supuestamente difícil de calcular: http://en.wikipedia.org/wiki/Quadratic_residuosity_problem