Algoritmo rho de Pollard

Es especialmente efectivo a la hora de factorizar números compuestos que tengan factores pequeños.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 aleatoriamenteSi p es factor de n, el número que se quiere factorizar, entonces, ya que p divide tanto acomo a n. El algoritmo rho emplea pues una función módulo n a modo de generador de una secuencia pseudoaleatoria.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.En 1980, Richard Brent publicó una versión del algoritmo más rápida.Pollard y Brent introdujeron una mejora adicional.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óduloSin embargo, basta con volver atrás al cálculo anterior delEl algoritmo es muy rápido en la factorización de números que tienen factores pequeños.En cambio, la variante de Richard Brent halló el mismo factor en sólo 5 milisegundos.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.Sea n = 8051 y f(x) = x2 + 1 mód 8051.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.