Algoritmo heurístico y probabilístico de factorización de enteros que utiliza una sucesión pseudoaleatoria en Z/nZ junto con detección de ciclos y cálculos de gcd para hallar un factor no trivial.

Principio

Generar la sucesión x_{i+1} = f(x_i) mod n para un polinomio f (habitualmente x^2 + c), detectar una colisión o ciclo corto y calcular gcd(|x_i - x_j|, n) para extraer un factor; la aleatoriedad y el efecto del cumpleaños hacen probable la aparición de colisiones en tiempo sublineal para factores pequeños.

Demostración

Elegir f(x)=x^2+1 mod 8051, iniciar con x_0=2 y usar la detección de ciclos de Floyd; cuando dos iterados coinciden módulo un factor no trivial, el gcd de su diferencia con 8051 proporciona un factor.

Aplicación incorrecta

Confiar en Rho de Pollard como método siempre rápido para números cuyo menor factor es muy grande, o no reiniciar con polinomios distintos tras ejecuciones largas; malas elecciones provocan ciclos prolongados y ejecuciones improductivas.

Consecuencia

Suele encontrar factores relativamente pequeños con rapidez y poco uso de memoria; eficaz como método intermedio tras eliminar pequeños factores con división por ensayo y antes de cribados más pesados.

Inversión

Sustituir la iteración pseudoaleatoria y la detección de ciclos por la recolección estructurada de relaciones sobre muchos valores (como en la criba cuadrática o NFS) para atacar la estructura compuesta global en lugar de factores individuales pequeños.

Límite

Heurístico y probabilístico: el rendimiento empeora cuando todos los factores primos son grandes o cuando la función pseudoaleatoria tiene ciclos patológicos; no sustituye a los cribados algebraicos para semiprimos muy grandes.

Tensión semántica

Se sitúa entre métodos de fuerza bruta simples y cribados a gran escala: más rápido que la división por ensayo para factores moderados, pero distinto en concepto y práctica de algoritmos algebraicos deterministas como NFS o ECM.

Síntesis

Rho de Pollard convierte colisiones aleatorias en una sucesión modular barata en factores no triviales mediante detección de ciclos y gcd, proporcionando una herramienta probabilística ligera para hallar factores pequeños a medianos.