##  [Algoritmo Rho de Pollard](/es/node/61994) 

 Definición

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

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

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

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

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

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

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

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

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.