Enumerar formas de descomponer un número entero en la suma de dos cuadrados

Question

El conocido "Suma de los Cuadrados de la Función" indica el número de maneras en que puede representar un entero como suma de dos cuadrados. El enlace para ver los detalles, pero se basa en el recuento de los factores del número N en potencias de 2, potencias de números primos = 1 mod 4 y potencias de números primos = 3 mod 4.

Dada esta factorización, es fácil encontrar el número de maneras de descomponer N en dos plazas. Pero, ¿cómo de manera eficiente enumerar las descomposiciones?

Así, por ejemplo, dado N=2*5*5*13*13=8450 , me gustaría generar los cuatro pares:

13*13+91*91=8450

23*23+89*89=8450

35*35+85*85=8450

47*47+79*79=8450

La obvia algoritmo (que he usado para el ejemplo anterior) es simplemente tomar yo=1,2,3,...,$\sqrt{N/2}$ y prueba si (N-i*i) es un cuadrado. Pero que puede ser caro para la gran N. ¿hay una manera de generar los pares de manera más eficiente? Ya tengo la factorización de N, que pueden ser útiles.

(Usted puede en lugar de iterar entre el $i=\sqrt{N/2}$ e $\sqrt{N}$ pero eso es sólo una constante de ahorros, todavía es $O(\sqrt N)$.

Answer 1

La factorización de$N$ es útil, ya que$$(a^2+b^2)(c^2+d^2)=(ac+bd)^2+(ad-bc)^2$$ There are good algorithms for expressing a prime as a sum of two squares or, what amounts to the same thing, finding a square root of minus one modulo $ p $. Ver, por ejemplo, http://www.emis.de/journals/AMEN/2005/030308-1.pdf

Editar: Tal vez debería agregar una palabra sobre la resolución de$x^2\equiv-1\pmod p$. Si$a$ es un no residuo cuadrático (mod$p$), entonces podemos tomar$x\equiv a^{(p-1)/4}\pmod p$. En la práctica, puede encontrar un no residuo cuadrático bastante rápido simplemente probando números pequeños a su vez, o probando números (pseudo-) aleatorios.

Answer 2

Este es el caso más simple de los Hardy-Muskat-Williams algoritmo. De todos modos, aquí hay un enlace a un papel de 1995 por Kenneth S. Williams, http://www.mathstat.carleton.ca/~williams/documentos/pdf/202.pdf y el original de la APM de papel http://www.ams.org/journals/mcom/1990-55-191/S0025-5718-1990-1023762-3/S0025-5718-1990-1023762-3.pdf .

Como no estoy seguro de que son conscientes de estos detalles, permítanme señalar que, si $$ 4^k \;| \; \; x^2 + y^2$$ then $ 2^k \; | \; x $ and $ 2^k \; | \; y. $ That is, you might as well divide your target by powers of 4 before doing anything difficult. Then after you are finished multiply $x,y$ by the appropriate power of $2.$

Esto es muy similar. Si hay un primer $$ q \equiv 3 \pmod 4 $$ and $ p | n,$ then keep dividing the target by powers of $q^2$ until it is no longer divisible by $q^2.$ If the remaining number is divisible by $q$ en realidad no existe, en representación de todos. Pero si $$ q^{2k} \;\parallel \; \; x^2 + y^2$$ then $ q^k \; | x / $ and $ p^k \; | y. $ La notación $ q^{2k} \;\parallel \; \; x^2 + y^2$ medio $ q^{2k} \; | \; \; x^2 + y^2$ pero no es cierto que $ q^{2k +1} \; | \; \; x^2 + y^2$

Bien, eso es suficiente precaución. Lo que usted realmente necesita saber es la expresión de los números primos $$ p \equiv 1 \pmod 4 $$ and indeed $ p^m,$ which is not much more difficult. Once you can do that, combine my notes with all possible ways of applying Gerry's multiplication formula (by changing $\pm$ signos y orden),

Answer 3

(Esto explica la respuesta de Gerry).

Este artículo describe cómo resolver la ecuación$p=x^2+y^2$ rápidamente si$p\equiv 1$ mod 4 y$p$ es primo.

John Brillhart: Nota sobre la representación de un primo como una suma de dos cuadrados

También explica cómo se puede resolver$x^2\equiv-1$ mod$p$.

Answer 4

Otro punto de vista, que podría ser más fácil a partir de un algoritmo de punto de vista (en mi opinión), es mirar a la descomposición $n = a^2+b^2$ el uso de números complejos $n = (a+bi)(a-bi)$. Supongamos que usted sabe cómo encontrar las soluciones $a,b$ cuando $n$ es primo. A continuación, tenga en cuenta que la identidad de $(a^2+b^2)(c^2+d^2)=(ac+bd)^2+(ad-bc)^2$ puede ser visto como la igualdad de producto de los módulos de dos números complejos.

Con el fin de encontrar todas las posibles descomposiciones de un número $n$ en una suma de cuadrados acaba de escribir la factorización de $n$ en $\Bbb{Z}[i]$: $n = \prod (a_j+ib_j)$ y nota que en este producto cada factor viene con su conjugado. En primer lugar, ignorar los poderes de $2$ y el de los números primos de la forma $4k+3$. Ahora, con el fin de encontrar todos los factorizations, recientemente desvinculado de todos los factores en dos columnas con el conjugado pares de estar en diferentes columnas. Haciendo esto, al tomar el producto en cada columna vamos a conseguir un par de conjugado de números cuyo producto es igual a $n$, por lo que encontramos una solución de la representación $n=a^2+b^2$. El número de maneras de dividir los factores en las dos columnas con el conjugado de a pares en los diferentes lados será igual al número de divisores de $n$ en $\Bbb{Z}[i]$ (dividido por 4, ya que puede multiplicar los factores por $1,-1,i,-i$) para todos los factores serán generados.

Si $n$ contiene los números primos de los formularios $4k+3$ o poderes de $2$ vea Jagy la respuesta. Tenga en cuenta que si usted reducir todos los poderes de $4$ y usted todavía tiene un $2$ izquierda en $n$ puede escribir $2 = (1+i)(1-i)$ y dividido en diferentes lados de las dos columnas.

Answer 5

Poner todo junto, aquí es cómo contar el número de maneras de descomponer $n$ en la suma de dos cuadrados.

Para ello se va a contar incluyendo la representación trivial $0^2+a^2$ para los números al cuadrado. (Para deshacerse de él, usted puede sustraer $1$ si el número es un cuadrado perfecto.)

1. Dividir el número por la potencia más alta de $4$ en ella. Si el número es una potencia de $4$, regresar $1$.

2. Descomponer lo que queda en factores primos.

   una. Si hay un primer factor de la forma $4n+3$ con extraño poder, regresar $0$.

   b. Descartar todos los factores primos de forma$4n+3$, incluso con el poder.

3. Ahora tienes todos los factores primos de la forma $4n+1$, y posiblemente una $2$ suspendida en medio de la descomposición. Digamos que usted ha $2^{n_0}\prod_{k=1}^m p_k^{n_k}$ con $p_k\equiv1\mod 4$, e $n_0$ ser $0$ o $1$.

4. Entonces el número de maneras en las $n$ puede ser descompuesto en la suma de cuadrados de los pares es $\left\lceil\frac{\prod_{k=1}^m (n_k+1)}{2}\right\rceil$.

Si desea enumerar en lugar de contar, se necesitan dos cosas, 1) Para seguir la pista de los poderes descarta y 2) ser capaz de extraer la raíz de $-1$ modulo $p$, y la utiliza para factorizar $4n+1$ a una gaussiana entero y su conjugado. Es sólo un poco más de trabajo, pero no es difícil - escribí el código que se basa en la discusión aquí, y algunos artículos mencionados aquí, funciona bastante bien!