Algoritmo rho de Pollard

El algoritmo rho de Pollard es un algoritmo para la factorización de enteros . Fue inventado por John Pollard en 1975. ^[1] Utiliza solo una pequeña cantidad de espacio, y su tiempo de ejecución esperado es proporcional a la raíz cuadrada del tamaño del factor primo más pequeño del número compuesto que se factoriza.

El algoritmo se utiliza para factorizar un número , donde es un factor no trivial. Un modulo polinomio , llamado (por ejemplo, ), se utiliza para generar una secuencia pseudoaleatoria : un valor inicial, por ejemplo 2, se elige, y la secuencia continúa como , , , etc. La secuencia está relacionada con otra secuencia . Dado que no se conoce de antemano, esta secuencia no se puede calcular explícitamente en el algoritmo. Sin embargo, en él radica la idea central del algoritmo.${\ Displaystyle n = pq}$${\ Displaystyle p}$${\ Displaystyle n}$${\ Displaystyle g (x)}$${\ Displaystyle g (x) = (x ^ {2} +1) {\ bmod {n}}}$${\ Displaystyle x_ {1} = g (2)}$${\ Displaystyle x_ {2} = g (g (2))}$${\ Displaystyle x_ {3} = g (g (g (2)))}$${\ Displaystyle \ {x_ {k} {\ bmod {p}} \}}$${\ Displaystyle p}$

Diagrama de ciclo que se asemeja a la letra griega  ρ

Ejemplo de factorización del algoritmo rho de Pollard para y , con valor inicial 2. El ejemplo utiliza el algoritmo de búsqueda de ciclos de Floyd .${\ Displaystyle n = 253}$${\ Displaystyle g (x) = x ^ {2} {\ bmod {2}} 53}$