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

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

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

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

有理点の数を#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が大きいと計算量が多過ぎるので、中国の剰余定理を用いて、もう少し分解します。
中国剰余定理の証明と例題（二元の場合） | 高校数学の美しい物語

中国の剰余定理は、２元の場合だけを書くと、 $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を計算します。