Pebble Coding

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

モジュラー多項式の定義と係数の求め方

楕円曲線

S = \begin{pmatrix} a &b \\ 0 &d \end{pmatrix} \in S_N
a, b, d \in Z
ad = N
0 \le b \lt d
とします。これは SL(2, Z) ではありませんのでご注意ください。
例えば、N=2の時の S_2の集合は、
S_{(0)} = \begin{pmatrix} 2 &0 \\ 0 &1 \end{pmatrix}
S_{(1)} = \begin{pmatrix} 1 &0 \\ 0 &2 \end{pmatrix}
S_{(2)} = \begin{pmatrix} 1 &1 \\ 0 &2 \end{pmatrix}
となります。
以下の式を考えます。
F_N (X, \tau) = \prod_{S \in S_N} (X - (j \cdot S)(\tau)) = \sum_{k} a_k(\tau) X^{k}
(j \cdot S)(\tau) = j(\frac {a \tau + b} {d} )

N=2の場合は、
F_2 (X, \tau) = (X - j(2 \tau))(X - j(\frac {\tau} {2}))(X - j(\frac {\tau + 1} {2}))
となります。

驚くべきことに、 a_k(\tau)は j(\tau)の整数係数多項式で表せることが知られています。

N=2の場合は、
F_2 (X, j) = X^{3} + X^{2} g_2(j) + X g_1(j) + g_0(j)
のように書けるということです。
ここでjをYと表現したものがモジュラー多項式の定義です。
\Phi_2 (X, Y) = X^{3} + X^{2} g_2(Y) + X g_1(Y) + g_0(Y)
具体的な計算方法は理解できていませんが、gの部分まで具体的に書くと次のようになっています。

\Phi_2 (X, Y) = -X^{2} Y^{2} + X^{3} + Y^{3} + 2^{4} \cdot 3 \cdot 31 XY ( X + Y)
+ 3^{4} \cdot 5^{3} \cdot 4027 XY - 2^{4} \cdot 3^{4} \cdot 5^{3} ( X^{2} + Y^{2})
+ 2^{8} \cdot 3^{7} \cdot 5^{6} (X + Y) - 2^{12} \cdot 3^{9} \cdot 5^{9}

なぜかX, Yの対称式になっています。
モジュラー多項式 \Phi_N (X, \tau) は j(\tau)の整数係数多項式で表せることが分かっているので、
\Phi_N(X, j(\tau))と表現できますが、
Xに j(N \tau)をいれてみましょう。すると、積のうちのa=N, b=0, c=0, d=1の式が、
S_{(0)} = \begin{pmatrix} N &0 \\ 0 &1 \end{pmatrix}となりますが、
(j \cdot S_{(0)})(\tau) = j(\frac {N \tau + 0} {1} )となり、
この項は (X-j(N \tau))で、Xに j(N \tau)を入れると、モジュラー多項式は0になることが分かります。つまり、
\Phi_N(j(N \tau), j(\tau)) = 0
であることが分かりました。
この式はモジュラー多項式の係数を求めるのに使えます。
手順は、 j(\tau) = q^{-1} + 744 + 196884 q + 21493760 q^{2} + 864299970 q^{3} + ...
q = e^{2 \pi i \tau}
j(N\tau) = q^{-N} + 744 + 196884 q^{N} + ...
をこの式に代入して、qの冪の係数を比較することによって係数が求まります。

モジュラー多項式には以下の性質があります。
(1) \Phi_N(X, Y) \in Z[X, Y]
(2) \Phi_N(X, Y) = \Phi_N(Y, X)
(3) Nが素数pの場合、 \Phi_p(X, Y) = (X^{p} - Y)(X - Y^{p}) mod pZ[X, Y]

上の性質を使うと、以下のようにかけることが分かります。
\Phi_p(X, Y) = (X^{p}-Y)(X-Y^{p}) + p \sum_{0 \le i \le p} c_{ii} X^{i} Y^{i} + p \sum_{0 \le i \lt j \le p} c_{ij} (X^{i} Y^{j} + X^{j} Y^{i})
この式のXに j(p\tau), Yに j(\tau)を代入して、qの同じ冪の係数を比較し、
未定変数 c_{ii}, c_{ij}に対する連立方程式を解けば、未定変数が求まります。

N=2の場合ですら、手計算ではしんどいので、プログラムを組んでいるところですが、完成の目処は立っていません。
完成しました。