Método de factorización de Dixon
# Método de factorización de Dixon

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 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

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 (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, utilizando fracciones continuas.

John Brillhart y Michael Morrison en 1975 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.

El algoritmo de criba cuadrática, debido a Carl Pomerance, utiliza ideas similares a las de este método.

## Ideas matemáticas sobre las que se basa

Si $n\in \mathbb {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 \mathbb {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 de 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\times 3\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 \mathbb {R}$. Dixon mostró que podía tomar $C=3{\sqrt {2}}$, pero Schnorr y Knuth lograron mejorar la prueba, asegurando que $C=2{\sqrt {2}}$.

