algorithm - primo - factorizacion primaria
¿Cuál es un buen método para factorizar enteros gaussianos? (2)
Ya tengo factorización prima (para enteros), pero ahora quiero implementarla para enteros gaussianos, pero ¿cómo debo hacerlo? ¡Gracias!
Esto resultó ser un poco detallado, pero espero que responda completamente a su pregunta ...
Un entero gaussiano es un número complejo de la forma
G = a + bi
donde i 2 = -1 , y a y b son números enteros.
Los enteros gaussianos forman un dominio de factorización único. Algunos de ellos actúan como unidades (por ejemplo, 1 , -1 , i , y -i ), otros como primos (por ejemplo, 1 + i ), y el resto compuesto, que se puede descomponer como un producto de primos y unidades que es único, Aparte del orden de los factores y la presencia de un conjunto de unidades cuyo producto es 1 .
La norma de tal número G se define como un entero: norma (G) = a 2 + b 2 .
Se puede demostrar que la norma es una propiedad multiplicativa, es decir:
norma (I * J) = norma (I) * norma (J)
Entonces, si desea factorizar un entero gaussiano G , puede aprovechar el hecho de que cualquier entero gaussiano I que divide G debe satisfacer la propiedad de que la norma (I) divide la norma (G) , y sabe cómo encontrar los factores de norma (g) .
Los números primos de los enteros gaussianos se dividen en tres categorías:
1 +/- i , con la norma 2 ,
a +/- bi , con norma prime a 2 + b 2 congruente con 1 mod 4 ,
a , donde a es primo congruente con 3 mod 4 , con norma a 2
Ahora, para convertir esto en un algoritmo ... si quieres factorizar un entero gaussiano G , puedes encontrar su norma N y luego factorizarlo en enteros primos. Luego, seguimos avanzando en esta lista, eliminando los factores primos p de N que corresponden a los factores gaussianos primos q de nuestro número G original.
Solo hay tres casos a considerar, y dos de ellos son triviales.
Si p = 2 , vamos q = (1 + i) . (Tenga en cuenta que q = (1-i) funcionaría igual de bien, ya que solo difieren por un factor unitario).
Si p = 3 mod 4 , q = p . Pero la norma de q es p 2 , por lo que podemos extraer otro factor de p de la lista de factores de norma (G) restantes.
El caso p = 1 mod 4 es el único que es un poco difícil de manejar. Es equivalente al problema de expresar p como la suma de dos cuadrados : si p = a 2 + b 2 , entonces a + bi y a-bi forman un par conjugado de primos gaussianos con la norma p , y uno de ellos será el factor que estamos buscando.
Pero con un poco de teoría de los números, resulta no ser demasiado difícil. Consideremos los enteros mod p. Supongamos que podemos encontrar un entero k tal que k 2 = -1 mod p . Entonces k 2 +1 = 0 mod p , que es equivalente a decir que p divide k 2 +1 en los enteros (y, por lo tanto, también los enteros de Gauss). En los enteros gaussianos, k 2 +1 se factoriza en (k + i) (ki) . p divide el producto, pero no divide ninguno de los dos factores. Por lo tanto, p tiene un GCD no trivial con cada uno de los factores (k + i) y (ki) , y ese GCD o su conjugado es el factor que estamos buscando.
Pero, ¿cómo encontramos tal entero k ? Sea n un cierto número entero entre 2 y p-1 inclusive. Calcule n (p-1) / 2 mod p : este valor será 1 o -1 . Si -1 , entonces k = n (p-1) / 4 , de lo contrario intente con una n diferente. Casi la mitad de los valores posibles de n nos darán una raíz cuadrada de -1 mod p , por lo que no será necesario adivinar para encontrar un valor de k que funcione.
Para encontrar los números primos gaussianos con la norma p , solo use el algoritmo de Euclides (ligeramente modificado para trabajar con enteros gaussianos) para calcular el GCD de (p, k + i) . Eso da un divisor de prueba. Si divide uniformemente el entero gaussiano que intentamos factorizar (resto = 0), habremos terminado. De lo contrario, su conjugado es el factor deseado.
El algoritmo GCD de Euclides para los enteros gaussianos es casi idéntico al de los enteros normales. Cada iteración consiste en una división de prueba con el resto. Si estamos buscando gcd (a, b) ,
q = piso (a / b) , resto = a - q * b , y si el resto es distinto de cero, devolvemos gcd (b, resto) .
En los enteros, si obtenemos una fracción como cociente, la redondeamos hacia cero.
En los enteros gaussianos, si las partes reales o imaginarias del cociente son fracciones, se redondean al entero más cercano. Además de eso, los algoritmos son idénticos.
Así que el algoritmo para factorizar un entero gaussiano G se parece a esto:
Calcule la norma (G) , luego la norma factorial (G) en los números primos p 1 , p 2 ... p n .
For each remaining factor p:
if p=2, u = (1 + i).
strike p from the list of remaining primes.
else if p mod 4 = 3, q = p, and strike 2 copies of p from the list of primes.
else find k such that k^2 = -1 mod p, then u = gcd(p, k+i)
if G/u has remainder 0, q = u
else q = conjugate(u)
strike p from the list of remaining primes.
Add q to the list of Gaussian factors.
Replace G with G/q.
endfor
Al final de este procedimiento, G es una unidad con norma 1 . Pero no es necesariamente 1 ; podría ser -1 , i , o -i , en cuyo caso agregue G a la lista de factores, para que aparezcan los signos correctos cuando multiplique todos los factores para ver si el producto coincide con el Valor original de G.
Este es un ejemplo práctico : factor G = 361 - 1767i sobre los enteros gaussianos. norma (G) = 3252610 = 2 * 5 * 17 * 19 * 19 * 53
Considerando 2 , intentamos q = (1 + i) y encontramos G / q = -703 - 1064i con el resto 0 .
G <= G / q = -703 - 1064i
Considerando 5 , vemos que es congruente con 1 mod 4 . Necesitamos encontrar un buen k . Intentando n = 2 , n (p-1) / 2 mod p = 2 2 mod p = 4 . 4 es congruente con -1 mod 5 . ¡Éxito! k = 2 1 = 2 . u = gcd (5, 2 + i) que resulta ser 2 + i . G / u = -494 - 285i , con el resto 0 , por lo que encontramos q = 2 + i .
G <= G / q = -494 - 285i
Considerando 17 , también es congruente con 1 mod 4 , por lo que necesitamos encontrar otro k mod 17 . Intentando n = 2 , 2 8 = 1 mod 17 , no está bien. Intente n = 3 en su lugar. 3 8 = 16 mod 17 = -1 mod 17 . ¡Éxito! Entonces k = 3 4 = 13 mod 17 . gcd (17, 13 + i) = u = 4-i , G / u = -99 -96i con el resto -2 . No es bueno, así que intente conjugado (u) = 4 + i . G / u = -133 - 38i con el resto 0. ¡Otro factor!
G <= G / (4 + i) = -133 - 38i
Considerando 19 , es congruente con 3 mod 4 . Así que nuestro siguiente factor es 19 , y sacamos la segunda copia de 19 de la lista.
G <= G / 19 = -7 - 2i
Teniendo en cuenta 53 , es congruente con 1 mod 4 . De nuevo con el proceso k ... Intentando n = 2, 2 26 = 52 mod 53 = -1 mod 53 . Entonces k = 2 13 mod 53 = 30 . gcd (53,30 + i) = u = -7 - 2i . Es idéntico a G , por lo que el cociente final G / (- 7-2i) = 1 , y no hay factores de -1 , i o -i de los que preocuparse.
Hemos encontrado factores (1 + i) (2 + i) (4 + i) (19 + 0i) (- 7-2i) . Y si multiplica eso (a la izquierda como un ejercicio para el lector ...), he aquí que el producto es 361-1767i , que es el número con el que comenzamos.
¿No es dulce la teoría de los números?
Utilice el punto flotante para los componentes reales e imaginarios si desea una precisión completa de enteros de una sola celda, y defina gsub, gmul y un gdivr de división especial con coeficientes redondeados, no en niveles. Esto se debe a que el método de factorización de Pollard rho necesita gcd a través del algoritmo de Euclid, con un gmodulo ligeramente modificado:
gmodulo((x,y),(x'',y''))=gsub((x,y),gmul((x'',y''),gdivr((x,y),(x'',y''))))
Pollard rho
def poly((a,b),(x,y))=gmodulo(gsub(gmul((a,b),(a,b)),(1,0)),(x,y))
input (x,y),(a,b) % (x,y) is the Gaussian number to be factorized
(c,d)<-(a,b)
do
(a,b)=poly((a,b),(x,y))
(c,d)=poly(poly((c,d),(x,y)),(x,y))
(e,f)=ggcd((x,y),gsub((a,b),(c,d)))
if (e,f)=(x,y) then return (x,y) % failure, try other (a,b)
until e^2+f^2>1
return (e,f)
Un valor de inicio normal es a = 1, b = 0.
He usado este método programado en Forth en mi blog http://forthmath.blogspot.se
Por seguridad, use valores redondeados en todos los cálculos mientras usa puntos flotantes para enteros.