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. Se utiliza un módulo polinomial , llamado (p. ej., ), para generar una secuencia pseudoaleatoria : se elige un valor inicial, digamos 2, y la secuencia continúa como , , , etc. La secuencia se relaciona 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 reside la idea central del algoritmo.${\ estilo de visualización n = pq}$${\ estilo de visualización p}$${\ estilo de visualización n}$${\ estilo de visualización g (x)}$${\displaystyle g(x)=(x^{2}+1){\bmod {n}}}$${\ estilo de visualización x_ {1} = g (2)}$${\ estilo de visualización x_ {2} = g (g (2))}$${\ Displaystyle x_ {3} = g (g (g (2)))}$${\displaystyle \{x_{k}{\bmod {p}}\}}$${\ estilo de visualización p}$

Diagrama de ciclo que se asemeja a la letra griega  ρ

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