Pebble Coding

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

楕円曲線の有理点の数の求め方 schoof アルゴリズムその1

 F_p 上の楕円曲線  y^{2} = x^{3} + a x^{2} + b の有理点個数の求め方です。

ここではSchoofアルゴリズムの理解を目的とし、少しづつ理解を進めます。

まず使うのはHasseの定理です。

Hasse-Weilの定理(楕円関数限定版) - Pebble Coding

有理点の数を#Eで表すと、 -2 \sqrt {p} \leq a \leq 2 \sqrt {p}
 a = p + 1 - \#E
が成り立つのでaを求めれば、#Eが確定します。
aはある範囲内の唯一つの整数なので、  a \mod n = c を満たす非負整数n,c が見つかったと仮定します。
ここで、
 a = dn + c, c \lt nなので、 n が 4 \sqrt {p}より大きかった場合は、dは0しかありえず、aはcと求まります。

計算する必要があるのは、 a \mod n, n \lt 4 \sqrt {p}だけとなりましたが、
nが大きいと計算量が多過ぎるので、 中国の剰余定理を用いて、もう少し分解します。
中国剰余定理の証明と例題(二元の場合) | 高校数学の美しい物語

中国の剰余定理は、2元の場合だけを書くと、  l1 l2 が互いに素なとき
 a = b1 \mod l1
 a = b2 \mod l2
を満たす a が 0 以上  l1 l2 未満の範囲に唯1つ存在する。
というもので、これは任意の元の数に拡張しても成り立ちます。

 l_iをいくつかもってきて全ての積を作ったものをnとします。
 l_iは全て、互いに素な素数とします。
 n = l_1 l_2 ... l_n
 a \mod l_1 = c_1
 a \mod l_2 = c_2
...
 a \mod l_n = c_n
を計算して、あとはユークリッドの互除法を用いてaを計算します。

Schoof's algorithm - Wikipedia

暗号技術入門 第3版

暗号技術入門 第3版

プライバシーポリシー

お問い合わせ

スポンサーリンク