Pollard p-1 Algorithm
Pollard p-1 分解法：若素因子 p 满足 p-1 为 B-平滑，则用 a^(B!) mod n 的 gcd 找因子。
用途
利用平滑性假设分解特定形式大数，是早期因子分解算法。
机制
选界 B，计算 M=∏(q^e ≤ B for q prime)，a=a^M mod n。若 p|n 且 p-1 为 B-平滑，则 a≡1 (mod p)，gcd(a-1,n) 给出 p。失败则增大 B。
用例
- 整数因子分解
- 数论算法
- 密码分析
Pollard p-1 分解法：若素因子 p 满足 p-1 为 B-平滑，则用 a^(B!) mod n 的 gcd 找因子。
利用平滑性假设分解特定形式大数，是早期因子分解算法。
选界 B，计算 M=∏(q^e ≤ B for q prime)，a=a^M mod n。若 p|n 且 p-1 为 B-平滑，则 a≡1 (mod p)，gcd(a-1,n) 给出 p。失败则增大 B。