Algoritmo rho de Pollard

Para otros usos de este término, véase algoritmo rho de Pollard para logaritmos discretos.

El algoritmo rho de Pollard es un algoritmo especializado de factorización de números enteros. Fue inventado por John Pollard en 1975. Es especialmente efectivo a la hora de factorizar números compuestos que tengan factores pequeños.

Ideas principales

El algoritmo rho se basa en el algoritmo de la liebre y la tortuga y en la observación de que (como ocurre en el problema del cumpleaños) dos números x e y son congruentes módulo p con probabilidad 0,5 tras haberse elegido aleatoriamente $1,177\sqrt{p}$ números. Si p es factor de n, el número que se quiere factorizar, entonces $1 < mcd \left( |x-y|,n \right) \le n$, ya que p divide tanto a $\left|x-y\right|$ como a n.

El algoritmo rho emplea pues una función módulo n a modo de generador de una secuencia pseudoaleatoria. Hace funcionar una de las secuencias el doble de rápido que la otra, es decir, por cada iteración de una de las copias de la secuencia, la otra hace dos iteraciones. Sea x el estado actual de una secuencia e y el estado actual de la otra. En cada paso se toma el máximo común divisor (MCD) de |x − y| y n. Si este MCD llega a ser n, entonces finaliza el algoritmo con el resultado de fracaso, ya que esto significa que x = y y, por el algoritmo de la liebre y la tortuga, la secuencia ya ha completado su ciclo y seguir más allá sólo conseguiría repetir trabajo ya realizado.

El algoritmo

Entradas: n, el número que se desea factorizar; y f(x), una función pseudoaleatoria módulo n

Salidas: un factor no trivial de n, o bien un fracaso. (un factor trivial de n es n mismo o 1)

1. x ← 2, y ← 2; d ← 1
2. Mientras d = 1:
   1. x ← f(x)
   2. y ← f(f(y))
   3. d ← MCD(|x − y|, n)
3. Si d = n, devuelve fracaso.
4. De lo contrario, devuelve d.

Nótese que este algoritmo acabará en fracaso para todo n primo, pero también puede fallar para un n compuesto. En ese caso, se cambia la función f(x) y se intenta de nuevo.

Optimización

En 1980, Richard Brent publicó una versión del algoritmo más rápida. Empleó las mismas ideas fundamentales que Pollard pero un método distinto de detección de ciclos, reemplazando el algoritmo de la liebre y la tortuga por el algoritmo de Brent para la detección de ciclos.

Pollard y Brent introdujeron una mejora adicional. Observaron que si mcd(a,n) > 1, entonces también se cumple que mcd(ab,n) > 1 para cada entero positivo b. En particular, en lugar de computar mcd( | x − y | ,n) en cada paso, basta definir z como el producto de cien términos consecutivos de | x − y | módulo n, para luego computar un solo mcd(z,n). Se obtiene un importante ahorro de tiempo, ya que se ven reemplazados 100 cálculos de un máximo común divisor por 99 multiplicaciones módulo n y un solo mcd. A veces se da lugar a un error en el algoritmo al introducir un factor repetido, por ejemplo, cuando n es un cuadrado. Sin embargo, basta con volver atrás al cálculo anterior del mcd, donde mcd(z,n) = 1, y a partir de ahí volver a usar el algoritmo rho original.

En la práctica

El algoritmo es muy rápido en la factorización de números que tienen factores pequeños. Por ejemplo, en un equipo de trabajo de 3 GHz, el algoritmo original halló el factor 274177 del sexto número de Fermat (18446744073709551617) en 26 milisegundos. Por contra, la variante de Richard Brent halló el mismo factor en sólo 5 milisegundos. Sin embargo, en el caso de un semiprimo del mismo número de cifras (10023859281455311421), el mismo equipo tardó 109 milisegundos en encontrar un factor con el algoritmo original, y 31 con la variante de Richard Brent.

Para f se elige un polinomio con coeficientes enteros. Los más comunes son de la forma

$f(x)=x^2+c\hbox{ mod }n,\,c\neq0,-2.$

El éxito más relevante del algoritmo rho ha sido la factorización del octavo número de Fermat, realizada por Pollard y Brent. Emplearon la variante de Brent, que halló un factor hasta entonces desconocido. La factorización completa de F₈ tardó dos horas en un UNIVAC 1100/42.

Ejemplo

Sea n = 8051 y f(x) = x² + 1 mód 8051.

i	xi	yi	xi − yi|, 8051)
1	5	26	1
2	26	7474	1
3	677	871	97

97 es un factor no trivial de 8051. Otros valores de c pueden dar lugar al cofactor (83) en lugar de 97.

Complejidad

El algoritmo ofrece un equilibrio entre su tiempo de ejecución y la probabilidad de encontrar un factor.

Si n es producto de dos primos distintos de tamaño similar, al ejecutar el algoritmo en O(n^1/4 polylog(n)) iteraciones se obtiene un factor con probabilidad aproximadamente 0,5. (Nótese que ésta es una afirmación heurística, y que sigue abierto un análisis riguroso del algoritmo.)

Referencias

• J.M. Pollard. "A Monte Carlo method for factorization", BIT Numerical Mathematics 15(3), 1975, pp. 331-334.
• Richard P. Brent. An Improved Monte Carlo Factorization Algorithm, BIT 20, 1980, pp.176-184, http://wwwmaths.anu.edu.au/~brent/pd/rpb051i.pdf
• Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein. Introduction to Algorithms, Segunda edición. MIT Press y McGraw-Hill, 2001. ISBN 0-262-03293-7. Section 31.9: Integer factorization, pp.896–901 (esta sección sólo versa sobre el algoritmo rho de Pollard).

Enlaces externos

• Implementación Java (página en inglés)