Pollard p-1 Algorithm
Pollard's p-1 method: if a prime factor p has a B-smooth p-1, then a gcd involving a^(B!) mod n reveals the factor.
Purpose
To factor numbers of certain forms using a smoothness assumption; an early factoring algorithm.
Mechanism
Choose a bound B and compute M=∏(q^e ≤ B for q prime), then a=a^M mod n. If p|n and p-1 is B-smooth, then a≡1 (mod p), and gcd(a-1,n) yields p. On failure, increase B.
Use cases
- Integer factorization
- Number-theoretic algorithms
- Cryptanalysis
Related tools
Factor Calculator
Factor Calculator — pure client-side tool. Privacy-first, no server round-trip. TOOL
Prime Checker
Prime Checker — pure client-side tool. Privacy-first, no server round-trip. TOOL
Pollard p-1 Factorization
Pollard p-1 Factorization — pure client-side tool. Privacy-first, no server round-trip. TOOL