逆元が存在しないとき

Last updated Nov 14, 2022 Edit Source

乗法群の位数が $\phi(N) = se^n$ と表されるとき $e$ の逆元が取れない.

このとき位数 $se^n$ から $e^n$ 乗することで位数 $s$ の乗法群に落とし, そこでなら逆元を取れるので, 位数 $se^n$ の元を $e^n$ 回掛けて全探索すると平文が見つかる.

$O(e^n)$

p - 1 ≡ 0 (mod e) のときの RSA 復号方法