Método de factorización de Dixon

De Wikipedia, la enciclopedia libre
Saltar a: navegación, búsqueda

En teoría de números, el método de factorización de Dixon (conocido también como método de los cuadrados aleatorios de Dixon[1] o algoritmo de Dixon) es un algoritmo 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[editar]

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. Dixon muestra 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[editar]

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[editar]

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[editar]

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[editar]

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. [6]

Referencias[editar]

  1. Kleinjung, Thorsten; et al. (2010). «Factorization of a 768-bit RSA modulus». Advances in Cryptology – CRYPTO 2010. Lecture Notes in Computer Science 6223. pp. 333–350. doi:10.1007/978-3-642-14623-7_18. 
  2. Pomerance, Carl. (1996). «A tale of two sieves». Notices of the American Mathematical Society 43 (12): 1473–1485. 
  3. D.H. Lehmer; R.E. Powers (1931). «On factoring large numbers». Bulletin American Math. Soc. 37: 1770–776. 
  4. M.A. Morrison; J. Brillhart (1975). «A method of factoring and the factorization of F7». Mathematics of computation 29: 183–205. 
  5. Dixon, J. D. (1981). «Asymptotically fast factorization of integers». Math. Comp. 36 (153): 255–260. doi:10.1090/S0025-5718-1981-0595059-1. JSTOR 2007743. 
  6. a b Pomerance, Carl (1982). «Analysis and Comparison of Some Integer Factoring Algorithms». Math. Centre Tract 154: 89–139. 
  7. Koblitz, Neal (2006). «Fermat factorization and factor bases». A course in number theory and cryptography (en inglés) (segunda edición). Springer. pp. 148–153. ISBN 0-387-94293-9. 

Enlaces externos[editar]