Principe de l'algorithme :
Pollard Rho est un algorithme probabiliste de factorisation, particulièrement efficace pour trouver des facteurs de taille moyenne. Son nom vient de sa trajectoire qui ressemble à la lettre grecque ρ (rho).
Stratégies d'optimisation :
- Optimisation par division :D'abord, utilisez les petits nombres premiers (2, 3, 5, 7, 11...) pour trouver rapidement les petits facteurs.
- Pollard Rho :Pour les grands nombres composés, utilisez la séquence pseudo-aléatoire x = (x² + c) mod n.
- Détection de cycle de Floyd :Utilisez des pointeurs rapides et lents pour détecter les cycles, optimisant la complexité spatiale.
- Test de primalité Miller-Rabin :Après avoir trouvé un facteur, vérifiez s'il est premier pour éviter des factorisations inutiles.
- Factorisation récursive :Factorisez récursivement les facteurs trouvés jusqu'à ce qu'ils soient tous premiers.
Complexité temporelle :
- Division par essais :O(√n), adapté aux petits nombres ou à la recherche rapide de petits facteurs.
- Pollard Rho :Temps attendu O(n^(1/4)), très efficace pour les nombres avec des facteurs de taille moyenne.
- Miller-Rabin :O(k log³n), où k est le nombre de tests, utilisé pour les tests de primalité.