Pollardのp-1法
$ n = pq
の片方の
素数
$ p
の
$ p-1
が小さな素因数を持つ時に有効な
素因数分解
アルゴリズム
$ (p-1) \mid m!
を満たす
$ m
を見つけて、
$ \text{gcd}(a^{m!}-1 \mod n, n)
を計算すれば
$ p
が得られる可能性がある
gcd
は高速に計算できる
証明
https://scrapbox.io/files/667a250ecfb8a8001ca65c0a.jpeg
#整数
#数学
#セキュリティ