- 917 名前：Kummer ◆g2BU0D6YN2 [2007/03/11(日) 23:11:38 ]
- 今度は k を求める方法を考える。
b = a^r (mod p) とおいた。b^(2^(e-1)) = 1 である。
b^2^m = 1 となる最小の m ≧ 1 を求める。
b_1 = bz^2^(e-m) とおく。
(b_1)^2^(m-1) = (b^2^(m-1))(z^2^(e-1)) = (-1)^2 = 1
よって b_1 の位数は 2^(m-1) 以下である。
以上の処理を繰り返せば bz^k = 1 となる k が求まる。
