Pebble Coding

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

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

Schoofアルゴリズム

アルゴリズムの実際の計算をもう少し詳しくみていきます。

x' = x_j^{q} \mod \psi_l(x)が成り立つかどうかの計算をみていきます。
まず、この式は x' - x_j^{q}がreductionの最終結果がxのみの多項式で分母と分子があるということを意味します。
lは奇数なので \psi_l(x)にはyは入らないです。
そして、 \psi_l(x)で割り切れるかどうかを調べる場合、分母は必要なく、分子の多項式だけ調べればよいです。

x'は２つの点を加算したものです。点の加算公式で、 x_1 \ne x_2の場合、
x_3 = \frac {y_2 - y_1} {x_2 - x_1} - x_1 - x_2です。
1つめの点は (x^{q^{2}}, y^{q^{2}})
2つめの点は (\frac {\phi_{q_l}(x)} {\psi_{q_l}^{2}(x, y)}, \frac {\omega_{q_l}(x, y)} {\psi_{q_l}^{3}(x, y)})
したがって、 x' = (\frac {\frac {\omega_{q_l}(x, y)} {\psi_{q_l}^{3}(x, y)} - y^{q^{2}}} { \frac {\phi_{q_l}(x)} {\psi_{q_l}^{2}(x, y)} - x^{q^{2}} })^{2} - x^{q^{2}} - \frac {\phi_{q_l}(x)} {\psi_{q_l}^{2}(x, y)} となります。
分母を揃えると、 x' = \frac {(\omega - y^{q^{2}} \psi^{3})^{2} - (\phi + x^{q^{2}} \psi^{2})(\phi - x^{q^{2}} \psi^{2})^{2} } {\psi^{2} (\phi - x^{q^{2}} \psi^{2})^{2}} となります。
残りはフロベニウス写像部分 x_j^{q}ですが、次のようになります。
x_j^{q} = \frac {\phi_{j}(x^{q})} {\psi_{j}^{2}(x^{q}, y^{q})}
したがって、 x' - x_j^{q} = \frac {(\omega - y^{q^{2}} \psi^{3})^{2} - (\phi + x^{q^{2}} \psi^{2})(\phi - x^{q^{2}} \psi^{2})^{2} } {\psi^{2} (\phi - x^{q^{2}} \psi^{2})^{2}} - \frac {\phi_{j}(x^{q})} {\psi_{j}^{2}(x^{q}, y^{q})}
分母を揃えて分子だけを取り出すと次のようになります。
((\omega_{q_l} - y^{q^{2}} \psi_{q_l}^{3})^{2} - (\phi_{q_l} + x^{q^{2}} \psi_{q_l}^{2})(\phi_{q_l} - x^{q^{2}} \psi_{q_l}^{2})^{2} ) \psi_j^{2}(x^{q}, y^{q}) - \psi_{q_l}^{2} (\phi_{q_l} - x^{q^{2}} \psi_{q_l}^{2})^{2} \phi_j(x^{q})
このx, yの多項式を計算して、 y^{2}=x^{3} + Ax + Bでreductionしていくと、yの変数は消えるので、
それが \psi_l(x)で割り切れるかどうか、つまりgcdが1でないかどうかを計算します。