Pollard p-1 Algorithm
Méthode p-1 de Pollard : si un facteur premier p a un p-1 B-friable, alors un pgcd impliquant a^(B!) mod n révèle le facteur.
Objectif
Factoriser des nombres de certaines formes via une hypothèse de friabilité ; un algorithme de factorisation précoce.
Mécanisme
On choisit une borne B et on calcule M=∏(q^e ≤ B pour q premier), puis a=a^M mod n. Si p|n et p-1 est B-friable, alors a≡1 (mod p), et pgcd(a-1,n) donne p. En cas d'échec, on augmente B.
Cas d’usage
- Factorisation des entiers
- Algorithmes de théorie des nombres
- Cryptanalyse
Outils associés
Calculatrice de diviseurs
Factor Calculator — outil 100% côté client. Confidentialité d'abord, sans aller-retour serveur. OUTIL
Vérificateur de nombres premiers
Prime Checker — outil 100% côté client. Confidentialité d'abord, sans aller-retour serveur. OUTIL
Factorisation Pollard p-1
Pollard p-1 Factorization — outil 100% côté client. Confidentialité d'abord, sans aller-retour serveur. OUTIL