Algoritmo rho de Pollard

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 principalesEditar

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   números. Si p es factor de n, el número que se quiere factorizar, entonces  , ya que p divide tanto a   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 |xy| 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 algoritmoEditar

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. xf(x)
    2. yf(f(y))
    3. d ← MCD(|xy|, 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ónEditar

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  , entonces también se cumple que   para cada entero positivo  . En particular, en lugar de computar   en cada paso, basta definir   como el producto de cien términos consecutivos de   módulo n, para luego computar un solo  . 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   y un solo  . A veces se da lugar a un error en el algoritmo al introducir un factor repetido, por ejemplo, cuando   es un cuadrado. Sin embargo, basta con volver atrás al cálculo anterior del  , donde  , y a partir de ahí volver a usar el algoritmo rho original.

En la prácticaEditar

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. En cambio, 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

 

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 F8 tardó dos horas en un UNIVAC 1100/42.

EjemploEditar

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

i xi yi MCD(|xiyi|, 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.

ComplejidadEditar

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(n1/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.)

ReferenciasEditar

Enlaces externosEditar