Pollard p-1 Algorithm
Pollardのp-1法：素因数pのp-1がB-スムーズなら、a^(B!) mod n を含むgcdがその因数を明らかにする。
目的
スムーズ性の仮定を利用して特定の形の数を素因数分解する。初期の素因数分解アルゴリズムである。
メカニズム
境界Bを選びM=∏(q^e ≤ B、qは素数)を計算し、a=a^M mod nとする。p|nかつp-1がB-スムーズならa≡1 (mod p)となり、gcd(a-1,n)がpを与える。失敗時はBを増やす。
ユースケース
- 整数の素因数分解（ファクタリング）
- 数論的アルゴリズム
- 暗号解読（クリプトアナリシス）