- 916 名前：Kummer ◆g2BU0D6YN2 [2007/03/11(日) 22:01:44 ]
- >>914 と >>915 より p ≡ 3 (mod 4) と p ≡ 5 (mod 8) のときは
x^2 ≡ a (mod p) の解は求まった。
残るのは p ≡ 1 (mod 8) の場合である。
p - 1 = (2^e)r, r は奇数とする。
(Z/pZ)^* は位数 p - 1 の巡回群だから、その 2-Sylow 部分群(>>790)
P は位数 2^e の巡回群である。
a^(p - 1)/2 = (a^r)^(2^(e-1)) ≡ 1 (mod p)
よって b = a^r (mod p) とおくと b^(2^(e-1)) = 1 である。
P の生成元を z とする。
b = z^s とすると z^(s2^(e-1)) = 1 より s は偶数である。
-s ≡ k (mod 2^e) で 0 ≦ k ＜ 2^e となるものがある。
k も偶数である。
bz^k = 1 である。
x = (a^(r + 1)/2)z^k/2 とおく。
x^2 = (a^(r + 1))z^k = abz^k ≡ a (mod p)
よって問題は z と k を求めることに帰着する。
n を p と素な有理整数とする。
z = n^r (mod p) とおく。
z^(2^e) = (n^r)^(2^e) = n^(p - 1) ≡ 1 (mod p)
z^(2^(e-1)) = (n^r)^(2^(e-1)) = n^(p - 1)/2
よって (n/p) = -1 なら z は P の生成元である。
n をランダムに選べば 50% の確率で (n/p) = -1 となるから
z は簡単に求まる。
|
 |
