Algoritmo rho de Pollard


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.

Contenido

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 |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 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. 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ó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( | xy | ,n) en cada paso, basta definir z como el producto de cien términos consecutivos de | xy | 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 F8 tardó dos horas en un UNIVAC 1100/42.

Ejemplo

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

i xi yi 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.

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

Referencias

Enlaces externos


Wikimedia foundation. 2010.

Mira otros diccionarios:

  • Complejidad y criptografía — La criptografía es la ciencia encargada del estudio y diseño de sistemas que permiten ocultar información. Desde sus inicios, esta capacidad de encubrimiento se ha basado en la dificultad que supondría a una entidad no autorizada el obtener la… …   Wikipedia Español

  • Factorización de enteros — Saltar a navegación, búsqueda En teoría de números, el problema de la factorización de enteros consiste en encontrar un divisor no trivial de un número compuesto; Por ejemplo dado el número 91, el reto es encontrar un número tal como el 7 que lo… …   Wikipedia Español

  • Check Wikipedia — Wikiproyecto:Check Wikipedia Saltar a navegación, búsqueda Esta página contiene de forma consciente fallos ortográficos. Los bots no deben intentar corregirlos. Atajo PR:CWPR:CW …   Wikipedia Español

  • Número semiprimo — En matemáticas , un número semiprimo, también llamado biprimo, es un número natural que es producto de dos números primos no necesariamente distintos. Contenido 1 Los 20 primeros semiprimos 2 Mayor semiprimo conocido 3 Utilidades …   Wikipedia Español

  • Número primo — Un número primo es un número natural mayor que 1, que tiene únicamente dos divisores distintos: él mismo y el 1. Se contraponen así a los números compuestos, que son aquellos que tienen algún divisor natural aparte de sí mismos y del 1. El número …   Wikipedia Español