- 929 名前：Kummer ◆g2BU0D6YN2 [2007/03/12(月) 21:02:02 ]
- >>616 と >>617 のアルゴリズムがどこから来たのかがやや分かりにくい。
これを私の想像で説明して見よう。
>>916 の記号を使う。
b = a^r (mod p) とおくと b^(2^(e-1)) = 1 である。
よって b ∈ P である。
この観察が最初のキーポイントだと思われる。
y = a^(r + １)/2 (mod p) とおく。
y^2 = a^(r + １) = ab である。
w^2 = b となる w が求まれば
y^2 = aw^2
よって x = yw^(-1) おくと、
x^2 = (y^2)(w^(-2)) = abb^(-1) = a
となって x^2 ≡ a (mod p) が解ける。
従って、w^2 = b となる w を求めればよい。
これには P の生成元 z と b = z^s となる s を求めればよい。
以上が Tonelli と Shanks の基本アイデアだと思われる。
