Princípio do Algoritmo:
Pollard Rho é um algoritmo probabilístico para fatoração de inteiros, especialmente eficaz para encontrar fatores de tamanho médio de números compostos. O nome do algoritmo vem de sua trajetória que se assemelha à letra grega ρ (rho).
Estratégias de Otimização:
- Otimização por Divisão por Tentativa:Primeiro, use primos pequenos (2, 3, 5, 7, 11...) para divisão por tentativa e encontrar rapidamente fatores pequenos.
- Pollard Rho:Para números compostos maiores, use a sequência pseudoaleatória x = (x² + c) mod n para encontrar fatores.
- Algoritmo de Detecção de Ciclo de Floyd:Use ponteiros rápido e lento para detectar ciclos na sequência, otimizando a complexidade de espaço.
- Teste de Primalidade Miller-Rabin:Após encontrar um fator, verifique se ele é primo para evitar fatoração desnecessária adicional.
- Fatoração Recursiva:Fatorem recursivamente os fatores encontrados até que todos sejam primos.
Complexidade de Tempo:
- Divisão por Tentativa:O(√n), adequado para números pequenos ou encontrar rapidamente fatores pequenos.
- Pollard Rho:Tempo esperado O(n^(1/4)), altamente eficiente para números com fatores de tamanho médio.
- Miller-Rabin:O(k log³n), onde k é o número de rodadas de teste, usado para teste de primalidade.