Pollard Rho Algorithm
La méthode rho de Pollard utilise une suite pseudo-aléatoire x_{i+1}=f(x_i) mod n pour trouver des facteurs de grands nombres, avec une complexité attendue en O(n^(1/4)).
Objectif
Factoriser des entiers de taille moyenne, utilisée pour attaquer des modules RSA faibles.
Mécanisme
On génère une suite avec f(x)=x^2+c mod n et on détecte des cycles avec l'algorithme de Floyd. Le long du cycle, pgcd(|x_i-x_j|, n) peut donner un facteur non trivial. Le paradoxe des anniversaires donne O(p^(1/2)) étapes attendues, p étant le plus petit facteur premier.
Cas d’usage
- Factorisation des entiers
- Attaques sur RSA
- Algorithmes de théorie des nombres
Outils associés
Vérificateur de nombres premiers
Prime Checker — outil 100% côté client. Confidentialité d'abord, sans aller-retour serveur. OUTIL
Calculatrice de diviseurs
Factor Calculator — outil 100% côté client. Confidentialité d'abord, sans aller-retour serveur. OUTIL
Factorisation Pollard Rho
Pollard Rho Factorization — outil 100% côté client. Confidentialité d'abord, sans aller-retour serveur. OUTIL