Pebble Coding

ソフトウェアエンジニアによるIT関連技術の備忘録

Hasseの定理から導き出される補題

楕円曲線に限定した Hasse の定理
 F_p 上の任意の楕円曲線の有理点の個数  \#E の範囲は以下となる。
 p + 1 - 2 \sqrt{p} \leq \#E \leq p + 1 + 2 \sqrt{p}

補題
楕円曲線 E ( F_p) に含まれる点Pで、
 m P = O
となる m が Hasse の定理により定まる曲線の位数の区間
 p + 1 - 2 \sqrt{p} \leq m \leq p + 1 + 2 \sqrt{p}
に唯一存在する時、
 \#E = mとなる。

この補題は Hasse の定理から導かれます。
 m P = Oということは点Pの位数がmということです。
曲線の位数 #E は点の位数の倍数です。
範囲の最小値、最大値を以下のように表現する。
 a_{min} = p + 1 - 2 \sqrt{p}
 a_{max} = p + 1 + 2 \sqrt{p}

最小値の2倍と最大値の差をとってみる。
 2 a_{min} - a_{max}
 = 2p + 2 - 4 \sqrt{p} - (p + 1 + 2 \sqrt{p})
 = p - 6 \sqrt{p}
これはpが十分大きいと0より大きい。
これは a_{min}, a_{max}の範囲内の値の倍数はこの範囲内にはないということである。
したがって、倍数は1しかありえないため  \#E = m だということになる。

この補題はBaby-step giant-step(BSGS)法の根拠の一部になっている。
力任せに総当り法で#Eを求めたい場合は、 4 \sqrt{p}通りの値を総当たりすれば良いということになる。
BSGS法はこれよりももっと効率が良い方法である。