sábado, 31 de octubre de 2015

Algoritmos

Algoritmos de factorización de enteros

 método de factorización de Dixon (conocido también como método de los cuadrados aleatorios de Dixon1 o algoritmo de Dixon) es unalgoritmo general de factorización de enteros; es el método prototípico de base de factores, y el único método de este tipo para el cual los límites de ejecución no se basan en conjeturas sobre las propiedades de suavidad de los valores de un polinomio conocido.

Historia del algoritmo

Las ideas de este algoritmo provienen de Maurice Kraitchik, quien en la década de 1920 generalizó un famoso método debido a Pierre de Fermat 2 (que funciona bien cuando los factores son cercanos). D. H. Lehmer y R. E. Powers sugirieron una idea parecida en un artículo publicado en 1931 3 , utilizando fracciones continuas.
John Brillhart y Michael Morrison en 1975 4 muestran cómo mejorar el algoritmo utilizando el álgebra lineal sobre F_2 (el cuerpo con dos elementos). John D. Dixonmuestra la eficiencia del algoritmo en un artículo publicado en 1981.5
El algoritmo de criba cuadrática, debido a Carl Pomerance 6 , utiliza ideas similares a las de este método.

Ideas matemáticas sobre las que se basa

Si n\in\N es primo y a\not\equiv 0 \ (mod\ n), entonces la ecuación x^2\equiv a^2\ (mod\ n) tiene dos soluciones distintas: a, \ -a.
Sin embargo, si n  es compuesto y no es la potencia de un primo, la ecuación x^2\equiv a^2\ (mod\ n) tiene más soluciones; estas soluciones vienen de la factorización de n  como producto de dos enteros coprimos entre sí. Si n=p\cdot q con p,q coprimos entonces tomando x  tal que x\equiv a \ (mod \ p) y  x\equiv -a\ (mod\ q) (esto se puede hacer gracias al Teorema chino del resto) encontramos una solución a x^2\equiv a^2\ (mod\ n) que es distinta de a y -a.
Recíprocamente, si x verifica x^2\equiv a^2\ (mod\ n) y x\not \equiv\pm a, entonces x-a no es coprimo con n ni múltiplo de él.
La idea básica del algoritmo es intentar encontrar dos enteros x,\ a tales que x\not \equiv\pm a y x^2\equiv a^2\ (mod\ n), con lo que mcd(x-a,n) será un divisor de  n  no trivial. Buscar al azar estos enteros lleva mucho tiempo y no hace eficaz el método. Lo que se hace para tener más probabilidad de "colisión" es tomar enteros cuyos cuadrados tengan factores primos pequeños.
Más concretamente: tomamos una "base de factores" B=\{p_1,\ldots,p_k\} formada por enteros pequeños y buscamos c_1, \ldots c_{k+1} tales que c_1^2\equiv p_1^{\alpha_{1,1}}\times \ldots\times p_k^{\alpha_{1,k}}\ (mod\ n), . . . , c_{k+1}^2\equiv p_1^{\alpha_{k+1,1}}\times\ldots\times p_k^{\alpha_{k+1,k}}\ (mod\ n). Luego escogemos c_{i_1}, \ldots, c_{i_r} de forma que c_{i_1}^2\times\ldots \times c_{i_r}^2\equiv p_1^{\beta_1} \times\ldots\times p_{k}^{\beta_k}\ (mod\ n), con cada uno de los \beta_i par.
Dadas las k-uplas (\alpha_{1,1}, \ldots,\alpha_{1,k}), . . . , (\alpha_{k+1,1},\ldots,\alpha_{k+1,k}), encontrar i_1,\ldots, i_r tales que c_{i_1}\times\ldots \times c_{i_r}\ (mod\ n) sea un producto de elementos de B al cuadrado no es otra cosa que obtener una combinación lineal de las k-uplas que sea la nula módulo 2. O sea que es un problema de álgebra lineal en F_2, que puede resolverse en forma rápida.

El método

Sea n\in\N el entero compuesto que deseamos factorizar.
Tomamos H una cota, llamemos B al conjunto de los primos menores o iguales que H unión el -1.
Inicialmente, buscamos enteros z tales que z^2 \ (mod\ n) se pueda escribir como producto de elementos de B.
Supongamos que hemos encontrado suficientes de estos números (suficientes en general significa poco más que el cardinal de B): z_1, \ldots,z_r. Utilizamos el álgebra lineal (como se describe en la sección anterior) para encontrar un producto z_{j_1}^2\times \ldots\times z_{j_t}^2 que módulo n es el cuadrado de un producto de elementos de B.
O sea, hemos obtenido z_{j_1}^2\times \ldots\times z_{j_t}^2= p_1^{2\alpha_1}\times\ldots\times p_h^{2\alpha_h} \ (mod \ n), o, escribiéndolo de otra manera: (z_{j_1}\times \ldots\times z_{j_t})^2= (p_1^{\alpha_1}\times\ldots\times p_h^{\alpha_h})^2 \ (mod \ n). Por lo tanto, el máximo común divisor entre z_{j_1}\times \ldots\times z_{j_t}- p_1^{\alpha_1}\times\ldots\times p_h^{\alpha_h} y n será distinto de 1 y n siempre que z_{j_1}\times \ldots\times z_{j_t}\neq \pm p_1^{\alpha_1}\times\ldots\times p_h^{\alpha_h} \ (mod \ n).
En caso que z_{j_1}\times \ldots\times z_{j_t}= \pm p_1^{\alpha_1}\times\ldots\times p_h^{\alpha_h} \ (mod \ n) se busca otra combinación lineal que nos dé un producto de cuadrados de elementos de B.

Ejemplo

Sea n=50861. Tomamos H=5, por lo que B=\{-1,2,3,5\}.
Encontramos varios enteros cuyos cuadrados son factorizados (módulo n) sobre B:
1295^2\equiv 2^2\times 3\times 5;
1726^2\equiv -1\times 3;
2449^2\equiv -1\times3\times 5;
2567^2\equiv 3;
2624^2\equiv -1\times 3^2\times 5 .
Tenemos las 4-uplas: (0,2,1,1), (1,0,1,0), (1,0,1,1), (0,0,1,0) y (1,0,2,1); estos son los exponentes de la factorización de los cuadrados como productos de elementos de B. Al tener 5 4-uplas, debe haber una que sea combinación de las otras (módulo 2); o lo que es lo mismo, una suma de estas 4-uplas tendrá todas sus entradas pares.
De hecho, la suma de las primeras cuatro da (2,2,4,2). Esto quiere decir que al multiplicar los primeros cuatro números, su cuadrado será (-1)^2\times 2^2\times 3^4\times 5^2(módulo n). O sea que (1295\times 1726\times 2449\times 2567)^2\equiv (2\times 3^2\times 5)^2\ (mod\ n).
Reducimos: 1295\times 1726\times 2449\times 2567\equiv 19639\ (mod\ n). Esta combinación hallada no nos da ningún factor, ya que 19639\equiv -(2\times 3^2\times 5).
Buscamos otra suma que nos dé con entradas pares: las tres últimas. Obtenemos de allí que (2449\times 2567\times 2624)^2\equiv (3^2\times 5)^2 \ (mod \ n), o lo que es lo mismo: 4751^2\equiv 45^2\ (mod\ n). De aquí sí sacamos un factor no trivial de n: mcd(4751-45,n)=181.

Tiempo de ejecución

Si en el algoritmo escogemos un H pequeño entonces es fácil saber si un entero se factoriza sobre B, pero es difícil encontrar naturales cuyo cuadrado sea producto de elementos de B. A la inversa, si H es grande será sencillo encontrar naturales cuyo cuadrado sea producto de elementos de B pero complicado saber si un entero se factoriza sobre B.
La clave para optimizar este método es escoger el valor adecuado de H. Puede probarse que si n tiene r dígitos es bueno tomar H con aproximadamente \sqrt r dígitos. Esto hace que el tiempo de ejecución del algoritmo tenga un orden O (e^{C(\sqrt{log(n)log(log(n))})}) para cierta constante C\in\R. 7 Dixon mostró que podía tomar C=3\sqrt 2, pero Schnorr y Knuth lograron mejorar la prueba, asegurando que C=2\sqrt 2.






El método de factorización de Euler es un método de factorización basado en la representación de un entero positivo N como la suma de dos cuadrados de dos maneras distintas:
N = a^2+ b^2 = c^2+ d^2
Aunque la factorización algebraica de números binomiales no sirve para factorizar sumas de dos cuadrados (en efecto un número que se puede expresar de una forma como suma de dos cuadrados es un número primo) si se pueden hallar dos representaciones distintas de un número como suma de dos cuadrados se sigue de ahí una factorización:
Partiendo de N = a^2 + b^2 = c^2 + d^2
se resta b^2+c^2 a ambos lados de la igualdad para crear una diferencia de dos cuadrados:
a^2 - c^2 = d^2 - b^2
y de ahí se sigue que:
(a - c)\cdot(a + c) = (d - b)\cdot(d + b)
Supóngase sin pérdida de generalidad que d y b son ambos pares o bien ambos impares, de forma que su diferencia es par. Ahora se define una constante k igual almáximo común divisor de (a - c) y (d - b) de forma que:
(a - c) = kl y (d - b) = km, con \operatorname{mcd}(l, m) = 1
de forma que, tras sustituir en la expresión anterior quedaría la siguiente ecuación:
l\cdot(a + c) = m\cdot(d + b)
Como l y m son primos entre sí, se supone que (a + c) es divisible por m, lo que nos daria como expresiones:
(a + c) = mn y;
(d + b) = ln
La factorización del número original N se puede mostrar que podría ser igual a:
N = \left[\left(\frac{k}{2}\right)^2 + \left(\frac{n}{2}\right)^2\right]\cdot(m^2 + l^2)


Historia y aplicaciones

La idea de que dos representaciones distintas de un entero positivo diera lugar a una factorización fue aparentemente planteada por primera vez por Marin Mersenne un loco matemático que le gustaba experimentar con los números y letras (Álgebra). Sin embargo, no fue hasta Euler, cien años después y un poco más, que su uso empezara a extenderse. Su más celebrado uso del método que hoy lleva su nombre fue el de factorizar el número N = 1000009, que, al parecer, se pensaba que era primo a pesar de que ninguno de los principales tests de primalidad lo da como pseudoprimo.
Como también:
1000009 = 1000^2 + 3^2 = 972^2 + 235 ^2
se tiene por las fórmulas anteriores:
a = 1000a - c = 28k = 4
b = 3a + c = 1972l = 7
c = 972d - b = 232m = 58
d = 235d + b = 238n = 34
Así,
\begin{align} 1000009 & = \left[\left(\frac{4}{2}\right)^2 + \left(\frac{34}{2}\right)^2\right]\cdot(58^2 + 7^2) \\ {} & = (2^2 + 17^2)\cdot(58^2 + 7^2) \\ {} & = (4 + 289)\cdot(3364 + 49) \\ {} & = 293\cdot3413 \end{align}
El método de factorización de Euler es más efectivo que el de Fermat para números naturales cuyos factores no sean próximos entre sí y es potencialmente mucho más eficiente que la división por tentativa si se pueden hallar representaciones de números como suma de cuadrados de forma razonablemente fácil. El desarrollo de Euler permitió una factorización mucho más eficiente, y, para los años 1910, el desarrollo de una tabla de factores de números hasta 10 millones. Los métodos empleados para encontrar representaciones de números como sumas de dos cuadrados son esencialmente los mismos que se usan para encontrar las diferencias de cuadrados en el método de Fermat.

Desventaja

La gran desventaja del método de factorización de Euler es que no se puede emplear para factorizar un número que tenga algún factor primo de la forma 4k+3 elevado a una potencia impar en su factorización como producto de primos, ya que tal número no podría ser la suma de dos cuadrados. Incluso algunos números compuestosimpares de la forma 4k+1 son el producto de dos primos de la forma 4k+3 (por ejemplo, 3053 = 43 × 71) y por ello no admiten factorización a través del método de Euler.
Esta restricción en su uso ha restado protagonismo al método de Euler en el campo de los algoritmos informáticos de factorización, ya que un usuario que intente factorizar un número aleatorio no tiene por qué saber (y en general no sabe) si el método de Euler se puede aplicar a ese número. Sólo recientemente se ha intentado desarrollar el método de Euler en forma de algoritmos informáticos para emplearse en números especiales en los que se sepa que se puede aplicar el método de Euler.







 método de factorización de Fermat se basa en la representación de un número natural impar como la diferencia de dos cuadrados:
n = a^2 - b^2.
Esa diferencia se puede factorizar algebraicamente como (a+b)(a-b); si ninguno de esos factores es igual a 1, se trata de una factorización propia de n.
Todo número impar se puede representar de esta manera. En efecto, si n=cd es una factorización de n, entonces
n = \left(\frac{c+d}{2}\right)^2 - \left(\frac{c-d}{2}\right)^2
Como n es impar, c y d también son impares, por lo que su semisuma y semidiferencia son ambos enteros. (Un múltiplo de cuatro también es una diferencia de cuadrados: en ese caso se pueden plantear c y d como números pares.)
En su forma más simple, el método de Fermat puede ser incluso más lento que el de división por tentativa en el peor de los casos. Sin embargo, la combinación de división por tentativa y el método de Fermat es más efectivo que el uso exclusivo de uno de ellos.

Método básico

Se van tomando varios valores de a, con la esperanza de que a^2-n = b^2 sea un cuadrado.
Algoritmo Factorización de Fermat
Entrada: Un número natural impar n.
Salida : Un factor del número n.
  1. A ← ⌈√n⌉ // ⌈.⌉ indica la función techo
  2. Bcuad ← A×A - n
  3. Mientras Bcuad no sea un cuadrado haga lo siguiente:
    1. A ← A + 1
    2. Bcuad ← A×A - n // alternativamente: Bcuad ← Bcuad + 2×A + 1
  4. Retorne A - √Bcuad // ó A + √Bcuad
Si n tiene más de dos factores primos, este procedimiento primero encuentra la factorización con el menor valor de a y b. Es decir, a+b es el menor factor mayor o igual que la raíz cuadrada de n. Por tanto, \textstyle a-b = \frac{n}{a+b} es el mayor factor menor o igual que \sqrt{n}. Si el procedimiento devuelve n = 1 \cdot n, entonces n debe ser primo.
Para n=cd, sea c el mayor factor menor que la raíz. \textstyle a = \frac{c+d}{2}, por tanto, el número de pasos requeridos es aproximadamente:
\frac{c+d}{2} - \sqrt n = \frac{\left(\sqrt d - \sqrt c\right)^2}{2} = \frac{(\sqrt n - c)^2}{2c}.
Si n es primo (es decir, c=1), ¡hacen falta O(n) pasos! Esta es desde luego una mala forma de demostrar la primalidad de un número. Pero si n tiene un factor próximo a su raíz cuadrada, el método funciona rápidamente. Concretamente, si c difiere de \sqrt n en menos de {\left(4n\right)}^{1/4}, entonces el método sólo necesita un paso, y esto es independiente del tamaño de n.

Ejemplo

Tómese el número n=5959 para realizar su factorización, se procede así:
A:787980
Bcuad:125282441
El tercer intento produce un cuadrado. A=80, B=21, y los factores son A-B = 59 y A+B = 101.

Factorización de Fermat y división por tentativa

Intentemos factorizar el número primo n=2345678917, pero también calcular b y a-b. Empezando por \sqrt{n} y subiendo desde ahí, quedan así tabulados los datos:
A:48433484344843548436
Bcuad:76572173439270308367179
B:276,7416,5519,9605,9
A-B:48156,348017,547915,147830,1
En la práctica, se puede ignorar la última fila hasta que b sea un número entero. Pero cabe observar que si n tuviera un factor menor que su raíz pero mayor que A-B=47830,1, el método de Fermat ya lo habría encontrado.
La división por tentativa normalmente tendría que seguir hasta el mayor primo menor que 48432; pero tras sólo cuatro pasos con el método de Fermat, basta intentarlo hasta 47830 para encontrar un factor o determinar la primalidad.
Esto sugiere la implementación de un método que combine los ya descritos. Basta tomar una cota c > \sqrt{n} y usar Fermat para los factores comprendidos entre \sqrt{n} y c. Esto deja una cota para la división por tentativa de c - \sqrt{c^2 - n}. En el ejemplo anterior, con c = 48436 la cota para la división por tentativa es 47830. Otra opción razonable sería c = 55000, que deja una cota de 28937.
Siguiendo con el método de Fermat, se obtiene un rendimiento cada vez menor. Así, normalmente uno pararía antes de llegar a este punto:
A:6000160002
Bcuad:12544410841254561087
B:35418,135419,8
A-B:24582,924582,2

Mejoras del algoritmo

Mejora del cribado

No es necesario computar todas las raíces cuadradas de los a^2-n, ni siquiera todos los valores de a. Por ejemplo, aquí se presenta de nuevo la tabla para n=2345678917:
A:48433484344843548436
Bcuad:76572173439270308367179
B:276,7416,5519,9605,9
Se puede ver rápidamente que ninguno de estos valores de Bcuad es un cuadrado. Los cuadrados son congruentes con 0, 1, 4, 5, 9 ó 16 módulo 20. Los valores se repiten con cada aumento de a en 10 unidades. En este ejemplo, a^2-n produce 3, 4, 7, 8, 12 y 19 módulo 20 para estos valores. De ahí se deduce que sólo el 4 de esta lista puede corresponder a un cuadrado. Por tanto, a^2 debe ser 1 mód 20, lo que implica que a es 1 ó 9 mód 10; esto dará lugar a un Bcuad congruente con 4 mód 20, y si Bcuad es cuadrado, b acabará en 2 u 8 mód 10.
Este proceso se puede realizar con cualquier módulo. Con el mismo n=2345678917,
módulo 16:Los cuadrados son0, 1, 4 ó 9
n mód 16 es5
así que a^2 sólo puede ser9
y a debe ser3 ó 5 módulo 16
módulo 9:Los cuadrados son0, 1, 4 ó 7
n mód 9 es7
así que a^2 sólo puede ser7
y a debe ser4 ó 5 módulo 9
Generalmente se toma una potencia de un primo distinto para cada módulo.
Dada una sucesión de valores de a (inicial, final y el "paso") y un módulo, se puede proceder así:
Criba_Fermat(n, Aini, Afin, Apaso, Módulo)
A ← Aini
hacer Módulo veces:
Bcuad ← A×A - n
si Bcuad es cuadrado, módulo Módulo:
Criba_Fermat(n, A, Afin, Apaso × Módulo, Siguiente_Módulo)
fin si
A ← A + Apaso
fin hacer
Pero se puede detener la recursión cuando quedan pocos valores de a, es decir, cuando (Afin-Aini)/Apaso es pequeño. Además, como el tamaño del paso de a' es constante, se pueden computar los sucesivos Bcuad mediante sumas.

Mejoras por uso de multiplicador

El método de Fermat funciona de forma óptima cuando hay un factor cercano a la raíz cuadrada de n. A lo mejor se puede favorecer que así sea.
Si se conoce la razón aproximada de dos factores (\tfrac{d}{c}), entonces se puede escoger un número racional \tfrac{v}{u} próximo a ese valor. nuv = cv \cdot du, quedando dos factores próximos que el método de Fermat, aplicado a nuv, hallará rápidamente. Entonces \mathrm{mcd}(n,cv)=c y \mathrm{mcd}(n,du)=d. (A menos que c divida a u o d divida a v.)
En general, no se conoce esa razón, pero se puede probar con diversos valores \tfrac{u}{v}, y tratar de factorizar cada nuv que surja. R. Lehman ideó una forma sistemática de hacer esto, de forma que la combinación de Fermat y la división por tentativa factorice n en O(n^{1/3}).1

Otras mejoras

La idea fundamental del método de Fermat es la base de la criba cuadrática y la criba generalizada sobre el cuerpo de los números (general number field sieve), los algoritmos mejor conocidos para la factorización de semiprimos grandes "en el peor de los casos". La principal mejora de la criba cuadrática sobre la factorización de Fermat es que, en lugar de buscar un cuadrado en la sucesión de a2−n, lo que hace es hallar un subconjunto de elementos de esta sucesión cuyo producto es un cuadrado, y lo hace de forma muy eficiente. El resultado final es el mismo: una diferencia de cuadrados mód n que, si no es trivial, puede emplearse para factorizar n.
Publicado por en

No hay comentarios:

Publicar un comentario

Suscribirse a: Enviar comentarios (Atom)