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

y'についてもみていきます。 $y'= \frac {y_2 - y_1} {x_2 - x_1} (x_1 - x_3) - y_1$
を使うと、
$y' = \frac { \frac {\omega} {\psi^{3}} - y^{q^{2}} } { \frac {\phi} {\psi^{2}} - x^{q^{2}} }$ $(x^{q^{2}} - ({ (\frac { \frac {\omega} {\psi^{3}} - y^{q^{2}} } { \frac {\phi} {\psi^{2}} - x^{q^{2}} }) }^{2} - x^{q^{2}} - \frac {\phi} {\psi^{2}} )) - y^{q^{2}}$
$= \frac {1 } { \psi^{3} (\phi - x^{q^{2}} \psi^{2})^{3}} \left((\omega - y^{q^{2}} \psi^{3}) \left((- \phi + 2 x^{q^{2}} \psi^{2})(\phi-x^{q^{2}} \psi^{2})^{2} - (\omega - y^{q^{2}} \psi^{3})^{2}\right) - y^{q^{2}}(\phi - x^{q^{2}} \psi^{2})^{3} \right)$

残りのフロベニウス写像部分 $y_j^{q}$ は
$y_j^{q} = \frac {\omega_j(x^{q}, y^{q})} {\psi_j^{3}(x^{q}, y^{q})}$

したがって、 $y' - y_j^{q} = \frac { 1 } { \psi^{3} (\phi - x^{q^{2}} \psi^{2})^{3}} (( \omega - y^{q^{2}} \psi^{3}) ((- \phi + 2 x^{q^{2}} \psi^{2})(\phi-x^{q^{2}} \psi^{2})^{2} - (\omega - y^{q^{2}} \psi^{3})^{2}) - y^{q^{2}}(\phi - x^{q^{2}} \psi^{2})^{3} ) - \frac { \omega_j(x^{q}, y^{q})} {\psi_j^{3}(x^{q}, y^{q})}$
分母を揃え、分子だけ取り出したものが $\psi_l(x)$ で割り切れるかどうかを調べます。
コンピュータ計算上は分母にyが含まれるか否かの分岐が面倒なので、
分子だけの計算結果にyが含まれている場合はyで割り、含まれていなければそのまま使うという計算方法でかまいません。

pythonでschoofアルゴリズムを実装してみる

実装する必要があるのは、
- 多項式係数の群演算
- x,y の多項式環演算、yの1次の除算、xの多項式の剰余算
- $y^{2} = x^{3} + Ax + B$ の式を使ってyの2乗をxに置き換える演算
- 等分点多項式 $\psi, \phi, \omega$ の表現
になります。

l=2の場合は割と簡単に実装できましたが、 l=3以上の場合が結構大変で、正直速度がでませんでした。
以下の計算に数時間かかりますがせっかくなので結果を載せておきます。
ここでは、標数19、 $y^{2} = x^{3} + 2x + 1$ でフロベニウストレースaの値が、
a = -1 mod 3
a = -2 mod 5
であることをschoofアルゴリズムで求めています。

q:19 l:3 ql:1
j:[1, 1]
j:1
x found
psi(3):3x^4 + 12x^2 + 12x + 15
pol % psi(3):14x^3 + 12x^2 + 5x + 4
a = -1 mod 3
q:19 l:5 ql:4
j:[1, 2]
j:1
x invalid
j:2
x found
psi(5):5x^12 + 10x^10 + 17x^8 + 5x^7 + x^6 + 9x^5 + 12x^4 + 2x^3 + 5x^2 + 8x + 8
pol % psi(5):16x^11 + x^10 + 6x^9 + 7x^8 + 2x^7 + 7x^6 + 14x^5 + 8x^4 + 8x^3 + 6x^2 + 14x + 8
a = -2 mod 5

実装したコードはこちらです。 https://github.com/pebble8888/ecpython

githubでみつけた他のschoofアルゴリズムの実装を参考までにリンクしておきます。
動作の仕方は分かっていません。

https://github.com/elliptic-shiho/ecpy

https://github.com/pdinges/python-schoof

schoofの原論文はこちら。(読むにはログインが必要です。) https://www.jstor.org/stable/2007968?seq=1#metadata_info_tab_contents