Pebble Coding

プログラマーの作業メモ

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

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

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

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

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

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

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

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

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

Schoof's algorithm - Wikipedia