Manera eficiente encontrar dos cuadrados que suma a un primer

Question

La web está plagada de cualquier número de páginas (porejemplo), dando una existencia y unicidad se prueba que un par de cuadrados se puede encontrar suma de los números primos congruentes con 1 mod 4 (y también que no hay ningún tipo de pares de números primos congruentes a 3 mod 4).

Sin embargo, ninguna de las cosas que he leído sobre el tema ofrece ninguna ayuda con la realidad de manera eficiente la búsqueda (es decir recta de búsqueda hasta sqrt(p)) los valores concretos de dichas plazas.

¿Cuál es la mejor manera de encontrarlos en realidad ?

Answer 1

En la práctica, esto viene a que el mismo algoritmo como Imbécil, pero te voy a dar mis dos penn'orth de todos modos. Hay dos etapas: (i) encontrar $z$ con $z^2\equiv -1$ (mod p$$), y (ii) el uso a $z$ a encontrar $x$ y $y$.

La etapa (i). Si $a$ es una ecuación cuadrática nonresidue modulo $p$ entonces $a^{(p-1)/2} \equiv-1$ (mod p$$) para que podamos tomar $z\equiv a^{(p-1)/4}$ (mod p$$) (y que es fácil de calcular, por exponenciación modular). ¿Cómo hace uno para encontrar cuadrática nonresidues? Bien poco más de la mitad de todos los los números de $a$ que $1 < a < p-1$ son cuadrática nonresidues, por lo que $a$ al azar será necesario en la mayoría de los dos se va, en promedio.

La etapa (ii). Calcular el máximo común divisor de $p$ y $z+i$ utilizando el Algoritmo de euclides para los enteros de Gauss. La respuesta sea $x+yi$ donde $x^2+y^2=p$.

Si $p\equiv 1$ (mod $2^k$) donde $k\ge3$ uno puede acelerar la etapa (i) un poco en promedio. Calcular $w=a^{(p-1)/2^k}$ modulo $p$. Si $w\equiv\pm1$ perdemos pero de lo contrario, mantenga el cuadrado $w$. A continuación, hemos llegado a conseguir a $-1$ y antes de que tenemos los $z$. Esto a veces se gana, incluso si $a$ es una ecuación cuadrática el residuo.

En efecto Gaussiano mcd arriba y Morón de la Hermite-Serret algoritmo cantidad a la misma cosa.

A continuación se muestra algunos áspero y listo código en Python para calcular $a$ y $b$ que $p=a^2+b^2$. La función que hace esto es 2sq. Se comportan de forma errática si se alimenta p no primos congruentes con 1 modulo 4.

---

def mods(a, n):
    if n <= 0:
        return "negative modulus"
    a = a % n
    if (2 * a > n):
        a -= n
    return a

def powmods(a, r, n):
    out = 1
    while r > 0:
        if (r % 2) == 1:
            r -= 1
            out = mods(out * a, n)
        r /= 2
        a = mods(a * a, n)
    return out

def quos(a, n):
    if n <= 0:
        return "negative modulus"
    return (a - mods(a, n))/n

def grem(w, z):
    # remainder in Gaussian integers when dividing w by z
    (w0, w1) = w
    (z0, z1) = z
    n = z0 * z0 + z1 * z1
    if n == 0:
        return "division by zero"
    u0 = quos(w0 * z0 + w1 * z1, n)
    u1 = quos(w1 * z0 - w0 * z1, n)
    return(w0 - z0 * u0 + z1 * u1,
           w1 - z0 * u1 - z1 * u0)

def ggcd(w, z):
    while z != (0,0):
        w, z = z, grem(w, z)
    return w

def root4(p):
    # 4th root of 1 modulo p
    if p <= 1:
        return "too small"
    if (p % 4) != 1:
        return "not congruent to 1"
    k = p/4
    j = 2
    while True:
        a = powmods(j, k, p)
        b = mods(a * a, p)
        if b == -1:
            return a
        if b != 1:
            return "not prime"
        j += 1

def sq2(p):
    a = root4(p)
    return ggcd((p,0),(a,1))

Answer 2

Sólo por diversión, aquí es una fórmula exacta para encontrar $a$ así que $a ^ 2 + b ^ 2 = p$:

$a = \dfrac{1}{2}\sum_{x = 0} ^ {p-1} \bigl (\dfrac{x^3 - x} \bigr),$ {p}

donde $\bigl (\bigr)$ \dfrac{a}{p} indica el símbolo de Legendre de $a$ mod $p$.

Añadido: Por sugerencia de Bill Dubuque, estoy señalando aquí que esta fórmula exacta no es un eficiente significa calcular el valor de $a$ (por lo tanto mi introductorio "apenas para la diversión...").

Answer 3

Uno puede calcular rápidamente una representación de un primer $\rm\:p\equiv 1\ (mod\ 4)\:$ como una suma de dos cuadrados, mediante el empleo de la distancia Euclídea MCD algoritmo en $\rm\mathbb Z[\:i\:]\:$ y un algoritmo para el cálculo de raíces cuadradas $\rm\:(mod\ p)\:$.

TEOREMA de $\ $ Deje que $\rm\ \: c = \sqrt{-1}\ \:(mod\ p)\ $ y $\rm\ gcd(p,\:i-c)\: = \: a+b\:i\ $.$\ $ Entonces $\rm\ p = a^2 + b^2\:$.

Prueba $\ $ vamos a mostrar: $\:$(1)$\ $ Representa $\rm\ p\:$ como una suma de cuadrados, es equivalente a encontrar una adecuada división de $\rm\: p = \alpha\:\beta\ $ $\rm\: \mathbb Z[\:i\:]\:$. $\ $(2)$\ $ Desde $\rm\: \mathbb Z[\:i\:]\:$ tiene un algoritmo de Euclides, una adecuada separación de los $\rm\ p\:$ puede ser calculado por el MCD con una adecuada separación de algún múltiplo de $\rm\: p\ $. (3)$\ \:$ Una adecuada separación de algún múltiplo de $\rm\ p\:$ surge por la factorización de $\rm\ \: x^2+1\ \ (mod\ p\:)\:$,$\ $ es decir,$\ $ por computación $\rm\ \ \sqrt{-1}\ \ (mod\ p\:)\:$. $\:$ A continuación están las pruebas.

(1) $\:$ Si $\rm\:\alpha|p\ $ correctamente, entonces, la conjugación, $\rm\:\alpha|p\ $ correctamente. La multiplicación de ellos produce $\rm\:\alpha\:\alpha|p^2\:$ correctamente en $\:\mathbb Z\:$. Pero en $\rm\mathbb{Z}\:$ el apropiado factor$a>0$ de $\rm\:p^2\:$ es $\rm\ p\:$, por lo tanto $\rm\: p = \alpha\:\alpha' = (a+b\:i)(a-b\:i) = a^2 + b^2\:$.

(2) $\ $ Si $\rm\ p\ \gamma \:=\: \alpha\:\beta\ $ y $\rm\p\:$ no dividir $\rm\:\alpha\:$ ni $\rm\:\beta\:$,$\ $ $\rm\: mcd(\alpha,p)\:$ es $\:$ apropiada$\ $ factor de $\rm\:p\ $.
Otro de $\rm\ gcd(\alpha,p) = p\:$ o $1$. Si el mcd es de $\rm p$ entonces $\rm\ p\:|\:\alpha\:$ contra la hipótesis. De lo contrario, si $\rm\ gcd(\alpha,p)=1\ $ por Euclides del Lexema, $\rm\ \alpha\:|\:p\:\gamma \ \Rightarrow\ \alpha\:|\:\gamma\:$,$\ $ entonces $\rm\ \gamma\alpha = \beta/p\ \Rightarrow\ p\:|\:\beta\:$,$\ $ nuevo contra la hipótesis. Nota: por lo general, en los anillos, GCDs única hasta la unidad de múltiplos. Aquí las unidades son $\rm\ i^n = \pm 1,\:\pm i\:$.

(3) $\rm\ \ x^2 + 1 \ =\ (x-c)\:(x+c) + p\ f(x)\ $ $\rm\mathbb\ Z[x]\ \: \Rightarrow\: -p\ f(i)\ =\ (i-c)\:(i+c)\ $ $\rm\mathbb\ Z[\:i\:]\ \ $ evaluación $\rm\: x = i\:$. Esta división es adecuado para dividir $\rm\p\:$ por (2) desde $\rm\p\:$ no dividen $\rm\: i\pm c\ \:$ en $\rm\ \: Z[\:i\:]\:$.

COMENTARIO de $\ $ Hay muchas variaciones en el algoritmo de Euclides en $\rm\mathbb \ Z[\:i\:]\ $ que se emplean en la práctica, por ejemplo, el empleo de fracciones continuas, la formas cuadráticas binarias, etc. Además, también hay al menos un par de algoritmos para calcular sqrts $\rm\:(mod\ p)\:$, por ejemplo mediante la factorización de polinomios $\rm\:(mod\ p)\:$, por curvas elípticas (Schoof), y el algoritmo de Tonelli y los Mangos. Para mucha más información, véase Henri Cohen del libro "Un curso computacional de la teoría algebraica de números". Aquí es un extracto de la hermosa algoritmo de Cornacchia:

Answer 4

Puedes intentar usar el Hermite-Serret algoritmo, que es brevemente como sigue:

Encontrar un $z$ tales que $z^2 = -1 \mod p$. Aplicar el algoritmo de Euclides para $p$ y $z$ detenerse en el primer par de restos de $(x,y)$ ir por debajo de $\sqrt{p}$. Hermite demostrado que $x^2 + y^2 = p$.

A encontrar $z^2 = -1 \mod p$, usted probablemente puede adivinar un $z$ y comenzar con $z^{p-1} = 1 \mod p$ y empezar a tomar las raíces cuadradas o como Robin señaló (en un ya eliminado de comentario y su respuesta) supongo que un $a$ y ver si $z = a^{\frac{p-1}{4}}$ es un candidato.

Ha habido mejoras en este por BrillHart. Derek fue lo suficientemente amable como para cazar a la referencia que de aquí: http://jstor.org/pss/2005889 y un enlace (gracias a J. M) http://www.ams.org/journals/mcom/1972-26-120/S0025-5718-1972-0314745-6/S0025-5718-1972-0314745-6.pdf

Answer 5

A continuación es un algoritmo para calcular una representación $\rm\ p = a^2 + b^2\ $ para un entero $\rm\ p = 1\ \: (mod\ 4)\:.\ \ $ El algoritmo codificado en $\ $ $\rm Macsyma$ $ \ $ , pero puede ser fácilmente traducido a casi cualquier otro idioma. La única Macsyma subrutinas específicas que usted puede ser que necesite para implementar en otro idioma exponenciación $\rm (mod\ p)$ (por repetir la cuadratura) y la función del suelo en $\rm \mathbb Q[\:i\:]\:$. Mientras que este algoritmo es razonablemente eficiente, el punto no es para optimizar la eficiencia, sino que, más bien, a destacar la simplicidad de la solución empleando el algoritmo de Euclides en $\rm\ \mathbb Z[\:i\:]\:.\ $ Para la teoría subyacente ver a mi compañero de post. Para un algoritmo más rápido ver, por ejemplo, Collins, Un rápido algoritmo de Euclides para los enteros de Gauss, y ver también Agarwal y Frandsen, Binario MCD Como Algoritmos de complejidad Cuadrática de los Anillos.

/ * $ \ : $ $\Rm\ p = 1\ \: (mod\ 4)\ $ computar $\rm\ \alpha = a + b\:i\ $ $\rm \ p = \alpha\:\alpha' = a^2 + b^2\ \ $*/

$\rm\text {particionado: psplit(p) := block([}\ \:\text{j : 0,}\ \ \text{e : piso(p/4),}\ \ \text{algebraicas : true, x, y ], }$

$\rm\quad\text{block([ módulo : p ],}\quad\quad\quad\quad\ $ /* búsqueda para $\rm\ j = \sqrt{-1}\ \ (mod\ p)\ $ */

$\rm\quad\quad\ \text{para}\ \: \text{ r : 2}\ \ \text{mientras}\ \ \text{j^2 # -1}$

$\rm\quad\quad\quad\quad\quad\quad\quad\quad\quad\ \ \text{do}\ \: \text{ j : rata(a)^e)} $

$\rm\quad \text{x : p,}\ \ \: \text{y : j - %i,} \quad\quad\quad\quad\quad\quad\quad $ /* encontrar $\rm\ gcd(p,\:j - i)\ \en\ \mathbb Z[\:i\:]\ $ por el algoritmo de Euclides */

$\rm\quad \text{hacer ( si}\ \text{ y = 0}\ \ \text{entonces}\ \text{ return(x)} $

$\rm\quad\quad\quad\ \ \text{j : rata(x - y * piso(rata(x/y))), }$

$\rm\quad\quad\quad\ \ \text{x : y,}\ \text{ y : j )) }$