Principio del Algoritmo:
Pollard Rho es un algoritmo probabilístico para la factorización de enteros, especialmente efectivo para encontrar factores de tamaño mediano de números compuestos. El nombre del algoritmo proviene de que su trayectoria se asemeja a la letra griega ρ (rho).
Estrategias de Optimización:
- Optimización por División por Tentativa:Primero, usa números primos pequeños (2, 3, 5, 7, 11...) para división por tentativa y encontrar rápidamente factores pequeños.
- Pollard Rho:Para números compuestos más grandes, usa la secuencia pseudoaleatoria x = (x² + c) mod n para encontrar factores.
- Algoritmo de Detección de Ciclos de Floyd:Usa punteros rápido y lento para detectar ciclos en la secuencia, optimizando la complejidad espacial.
- Prueba de Primalidad Miller-Rabin:Después de encontrar un factor, verifica si es primo para evitar factorizaciones innecesarias adicionales.
- Factorización Recursiva:Factoriza recursivamente los factores encontrados hasta que todos sean primos.
Complejidad Temporal:
- División por Tentativa:O(√n), adecuado para números pequeños o para encontrar rápidamente factores pequeños.
- Pollard Rho:Tiempo esperado O(n^(1/4)), muy eficiente para números con factores de tamaño mediano.
- Miller-Rabin:O(k log³n), donde k es el número de rondas de prueba, usado para pruebas de primalidad.