p 1 法
概要
 フェルマーの小定理
x

p 1
 1mod p を使う
p  1 が小さい素因数しかもたない
ときに有効
概要
 ある比較的小さい
Kで
K
a  1mod p となる
a
 GCD
K
1, n
p
が
になる可能性が大きい
例
n  1037 のとき a  3 , K  2  3 とおくと
K
b  a  497 mod n  , GCD496 , n   1
2
b  302
3
b  123
5
よって
mod n  , GCD301, n   1
mod n  , GCD122 , n   61
n  61 17 と素因数分解できる。
対策法

p  1 に大きな素因数を含める
ダウンロード

攻撃への対策