Algoritmos

algoritmos de factorización por enteros

 método de factorización con fracciones continuas (CFRAC del inglés Continued Fraction Factorization Method ) es un algoritmo de factorización de enteros. Es un algoritmo de propósito general, lo que significa que es apropiado para factorizar cualquier entero n, no dependiente de una forma espacial o de propiedades. Fue descrito por D. H. Lehmer y R. E. Powers en 1931,¹ y desarrollado como un algoritmo de computadora por Michael A. Morrison y John Brillhart en 1975.²

El método de fracciones continuas está basado sobre el método de factorización de Dixon. Este usa convergentes en las expansiones de fracciones continuas regulares de

${\displaystyle {\sqrt {kn}},\qquad k\in \mathbb {Z^{+}} }$.

Puesto que es un irracional cuadrático, la fracción continua debe de ser periódica (a no ser que n sea un cuadrado, en cuyo caso la factorización es obvia).

Este tiene un tiempo de complejidad ${\displaystyle O\left(e^{\sqrt {2\log n\log \log n}}\right)=L_{n}\left[1/2,{\sqrt {2}}\right]}$, en las notaciones O y L repectivamente.

factorización de curva elíptica de Lenstra o método de factorización de curva elíptica ( del inglés elliptic curve factorization method, ECM) es un rápido algoritmo de tiempo de ejecución sub-exponencial para la factorización de enteros que emplea curvas elípticas. Para una factorización de propósito general, ECM es el tercer método más rápido conocido de factorización. El segundo más rápido es la criba cuadrática de múltiples polinomios y el más rápido es la criba general del cuerpo de números. La factorización de curva elíptica de Lenstra es llamada así en honor a Hendrik Lenstra.

En la práctica, ECM es considerado un algoritmo de factorización de propósito especial así como el más adecuado para encontrar factores pequeños. A fecha de 2012, es todavía el mejor algoritmo para divisores que no superen los 20 a 25 dígitos decimales (64 a 83 bits respectivamente), así como su tiempo de ejecución está dominado por el tamaño del factor más pequeño p en lugar de por el tamaño del número n a ser factorizado. Frecuentemente, ECM se usa para eliminar factores pequeños de un entero muy grande con muchos factores; si el entero resultante todavía es compuesto, entonces solo tiene factores grandes y es factorizado mediante el uso de técnicas de propósito general. El factor más grande encontrado usando ECM cuenta con 75 dígitos y fue descubierto el 2 de agosto de 2012 por Samuel Wagstaff.¹ Incrementando el número de curvas probadas se mejoran las posibilidades de encontrar un factor, pero no son lineales con el incremento en el número de dígitos.

 factorización de formas cuadradas de Shanks es un método para factorizar enteros inventado por Daniel Shanks como una mejora del método de factorización de Fermat.

El éxito del método depende de encontrar números enteros ${\displaystyle x}$ e ${\displaystyle y}$ tales que ${\displaystyle x^{2}-y^{2}=N}$, donde ${\displaystyle N}$ es el entero a ser factorizado. Una mejora (indicada por Kraitchik) es buscar enteros ${\displaystyle x}$ e ${\displaystyle y}$ tales que ${\displaystyle x^{2}\equiv y^{2}{\pmod {N}}}$. Encontrando un par adecuado ${\displaystyle (x,y)}$ no se garantiza una factorización de ${\displaystyle N}$, pero esto implica que ${\displaystyle N}$ es un factor de ${\displaystyle x^{2}-y^{2}=(x-y)(x+y)}$, y hay una buena posibilidad de que los divisores primos de ${\displaystyle N}$ estén distribuidos entre esos dos factores, así que el cálculo del máximo común divisor de ${\displaystyle N}$ y ${\displaystyle x-y}$ dará un factor no trivial de ${\displaystyle N}$.

Un algoritmo práctico para encontrar pares ${\displaystyle (x,y)}$ que satisfagan ${\displaystyle x^{2}\equiv y^{2}{\pmod {N}}}$ fue desarrollado por Shanks, que lo llamó Factorización de formas cuadradas (en inglés Square Forms Factorization o SQUFOF). El algoritmo puede ser expresado en términos de fracciones continuas, o en términos de formas cuadráticas. A pesar de que ahora existen métodos de factorización más eficientes disponibles, SQUFOF tiene la ventaja de que es lo suficientemente pequeño para ser implementado en una calculadora programable.

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 ${\displaystyle 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 ${\displaystyle n\in \mathbb {N} }$ es primo y ${\displaystyle a\not \equiv 0\ (mod\ n)}$, entonces la ecuación ${\displaystyle x^{2}\equiv a^{2}\ (mod\ n)}$ tiene dos soluciones distintas: ${\displaystyle a,\ -a}$.

Sin embargo, si ${\displaystyle n}$ es compuesto y no es la potencia de un primo, la ecuación ${\displaystyle x^{2}\equiv a^{2}\ (mod\ n)}$ tiene más soluciones; estas soluciones vienen de la factorización de ${\displaystyle n}$ como producto de dos enteros coprimos entre sí. Si ${\displaystyle n=p\cdot q}$ con ${\displaystyle p,q}$ coprimos entonces tomando ${\displaystyle x}$ tal que ${\displaystyle x\equiv a\ (mod\ p)}$ y ${\displaystyle x\equiv -a\ (mod\ q)}$ (esto se puede hacer gracias al Teorema chino del resto) encontramos una solución a ${\displaystyle x^{2}\equiv a^{2}\ (mod\ n)}$ que es distinta de ${\displaystyle a}$ y ${\displaystyle -a}$.

Recíprocamente, si ${\displaystyle x}$ verifica ${\displaystyle x^{2}\equiv a^{2}\ (mod\ n)}$ y ${\displaystyle x\not \equiv \pm a}$, entonces ${\displaystyle x-a}$ no es coprimo con ${\displaystyle n}$ ni múltiplo de él.

La idea básica del algoritmo es intentar encontrar dos enteros ${\displaystyle x,\ a}$ tales que ${\displaystyle x\not \equiv \pm a}$ y ${\displaystyle x^{2}\equiv a^{2}\ (mod\ n)}$, con lo que ${\displaystyle mcd(x-a,n)}$ será un divisor de ${\displaystyle 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" ${\displaystyle B=\{p_{1},\ldots ,p_{k}\}}$ formada por enteros pequeños y buscamos ${\displaystyle c_{1},\ldots c_{k+1}}$ tales que ${\displaystyle c_{1}^{2}\equiv p_{1}^{\alpha _{1,1}}\times \ldots \times p_{k}^{\alpha _{1,k}}\ (mod\ n)}$, . . . , ${\displaystyle c_{k+1}^{2}\equiv p_{1}^{\alpha _{k+1,1}}\times \ldots \times p_{k}^{\alpha _{k+1,k}}\ (mod\ n)}$. Luego escogemos ${\displaystyle c_{i_{1}},\ldots ,c_{i_{r}}}$ de forma que ${\displaystyle 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 ${\displaystyle \beta _{i}}$ par.

Dadas las k-uplas ${\displaystyle (\alpha _{1,1},\ldots ,\alpha _{1,k})}$, . . . , ${\displaystyle (\alpha _{k+1,1},\ldots ,\alpha _{k+1,k})}$, encontrar ${\displaystyle i_{1},\ldots ,i_{r}}$ tales que ${\displaystyle c_{i_{1}}\times \ldots \times c_{i_{r}}\ (mod\ n)}$ sea un producto de elementos de ${\displaystyle 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 ${\displaystyle F_{2}}$, que puede resolverse en forma rápida.

El método

Sea ${\displaystyle n\in \mathbb {N} }$ el entero compuesto que deseamos factorizar.

Tomamos ${\displaystyle H}$ una cota, llamemos ${\displaystyle B}$ al conjunto de los primos menores o iguales que ${\displaystyle H}$ unión el -1.

Inicialmente, buscamos enteros ${\displaystyle z}$ tales que ${\displaystyle z^{2}\ (mod\ n)}$ se pueda escribir como producto de elementos de ${\displaystyle B}$.

Supongamos que hemos encontrado suficientes de estos números (suficientes en general significa poco más que el cardinal de ${\displaystyle B}$): ${\displaystyle z_{1},\ldots ,z_{r}}$. Utilizamos el álgebra lineal (como se describe en la sección anterior) para encontrar un producto ${\displaystyle z_{j_{1}}^{2}\times \ldots \times z_{j_{t}}^{2}}$ que módulo n es el cuadrado de un producto de elementos de ${\displaystyle B}$.

O sea, hemos obtenido ${\displaystyle 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: ${\displaystyle (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 ${\displaystyle z_{j_{1}}\times \ldots \times z_{j_{t}}-p_{1}^{\alpha _{1}}\times \ldots \times p_{h}^{\alpha _{h}}}$ y ${\displaystyle n}$ será distinto de 1 y ${\displaystyle n}$ siempre que ${\displaystyle 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 ${\displaystyle 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 ${\displaystyle B}$.

Ejemplo

Sea ${\displaystyle n=50861}$. Tomamos ${\displaystyle H=5}$, por lo que ${\displaystyle B=\{-1,2,3,5\}}$.

Encontramos varios enteros cuyos cuadrados son factorizados (módulo ${\displaystyle n}$) sobre ${\displaystyle B}$:

${\displaystyle 1295^{2}\equiv 2^{2}\times 3\times 5;}$

${\displaystyle 1726^{2}\equiv -1\times 3;}$

${\displaystyle 2449^{2}\equiv -1\times 3\times 5;}$

${\displaystyle 2567^{2}\equiv 3;}$

${\displaystyle 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 ${\displaystyle 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á ${\displaystyle (-1)^{2}\times 2^{2}\times 3^{4}\times 5^{2}}$ (módulo n). O sea que ${\displaystyle (1295\times 1726\times 2449\times 2567)^{2}\equiv (2\times 3^{2}\times 5)^{2}\ (mod\ n)}$.

Reducimos: ${\displaystyle 1295\times 1726\times 2449\times 2567\equiv 19639\ (mod\ n)}$. Esta combinación hallada no nos da ningún factor, ya que ${\displaystyle 19639\equiv -(2\times 3^{2}\times 5)}$.

Buscamos otra suma que nos dé con entradas pares: las tres últimas. Obtenemos de allí que ${\displaystyle (2449\times 2567\times 2624)^{2}\equiv (3^{2}\times 5)^{2}\ (mod\ n)}$, o lo que es lo mismo: ${\displaystyle 4751^{2}\equiv 45^{2}\ (mod\ n)}$. De aquí sí sacamos un factor no trivial de ${\displaystyle n}$: ${\displaystyle mcd(4751-45,n)=181}$.

Tiempo de ejecución

Si en el algoritmo escogemos un ${\displaystyle H}$ pequeño entonces es fácil saber si un entero se factoriza sobre ${\displaystyle B}$, pero es difícil encontrar naturales cuyo cuadrado sea producto de elementos de ${\displaystyle B}$. A la inversa, si ${\displaystyle H}$ es grande será sencillo encontrar naturales cuyo cuadrado sea producto de elementos de ${\displaystyle B}$ pero complicado saber si un entero se factoriza sobre ${\displaystyle B}$.

La clave para optimizar este método es escoger el valor adecuado de ${\displaystyle H}$. Puede probarse que si ${\displaystyle n}$ tiene ${\displaystyle r}$ dígitos es bueno tomar ${\displaystyle H}$ con aproximadamente ${\displaystyle {\sqrt {r}}}$ dígitos. Esto hace que el tiempo de ejecución del algoritmo tenga un orden ${\displaystyle O(e^{C({\sqrt {log(n)log(log(n))}})})}$ para cierta constante ${\displaystyle C\in \mathbb {R} }$.⁷ Dixon mostró que podía tomar ${\displaystyle C=3{\sqrt {2}}}$, pero Schnorr y Knuth lograron mejorar la prueba, asegurando que ${\displaystyle C=2{\sqrt {2}}}$