Modular Polynomials

[2002.02.08]modular多項式

modular多項式を求めるプログラム(pari/GP)
上記プログラムの実行例

■2次正方行列の集合D_n^*,S_n^*を以下のように定義する。ここで、nは自然数である。
     D_n^*={ ((a b)(c d)) ∈ M₂(Z): ad-bc=n, gcd(a,b,c,d)=1}
     S_n^*={ ((a b)(0 d)) ∈ D_n^*: d > 0, 0 <= b < d}

このとき、自然な写像
     S_n^* ----> SL₂\backslash D_n^*
は全単射になる。また、
     #S_n^*=nΠ_p|n(1+1/p)
特に、nが素数lの場合は、
     #S_l^*=l+1
となる。

■modular多項式
n次のModular多項式Φ_n(X)を、次のように定義する。
     Φ_n(X)=Π_{α ∈ S_n^*}(X-j \circ α)

このとき、
(a)Φ_n ∈ Z[j][X].
Φ_nを２変数の多項式とみる場合、Φ_n(j,X)と書く。
(b)Φ_nはC[j]上で既約である。
(c)Φ_n(X,Y)=Φ_n(Y,X)
(d)nが完全平方数でないならば、Φ_n(X,X)は±1から始まる係数を持つ非定数の多項式である。

■素数lに対して、modular多項式Φ_l(X,Y)を求める。
     Φ_l(j,X) = X^l+1+Σ_k=1^l+1{(-1)^ks_k(j)X^l-k+1}
となるs_k(j) = s_k(τ)を求めればよい。
s_k(τ)は、{j(lτ),j((τ+1)/l),...,j((τ+l-1)/l)}の基本対称式である。

そこで、対称式に関するNewtonの公式を利用する。
n個の変数x₁,x₂,...,x_nに関する基本対称式をt_r(1≦r≦n)とする。つまり、
     t_r = Σ_σ{x_σ₁x_σ₂...x_{σ_r}}
とする。x_iの累乗(k乗)和を
     u_k = Σ_i=1ⁿ{x_i^k} = x₁^k+x₂^k+...+x_n^k
(k≧0)とすると、以下の漸化式が成立する。

     t₁ = u₁,
     t₂ = -(1/2)(u₂-t₁u₁),
     t₃ = (1/3)(u₃-t₁u₂+t₂u₁),
     ......
     t_l-1 = (-1)^l(1/(l-1))(u_l-1-t₁u_l-2+...+(-1)^lt_l-2u₁)

つまり、x_iの累乗和u₁,...,u_lから、x_iの対称式を求めることができる。

j(lτ)を除くJ_l={j(τ/l),j((τ+1)/l),...,j((τ+l-1)/l)}についての基本対称式を
     t₁ = Σ_k{j((τ+k)/l)},
     t₂ = Σ_k,k'{j((τ+k)/l)j((τ+k')/l)},
     .....
     t_l = j(τ/l)j((τ+1)/l)...j((τ+l-1)/l)
とする。ただし、t₀=1, t_l+1=0と置く。
このとき、
     s_k = j(lτ)t_k-1+t_k
となる。
ここで、j(τ)のr乗を
     j^r(τ) = Σ_m=-r^∞{c_m^(r)q^m}
J_lの元のr乗和を
     u_r = Σ_m=0^l-1{j^r((τ+k)/l)}
とすると、
     u_r = lΣ_n=0^∞{c_ln^(r)qⁿ}    (1≦r≦l),
     u_l = l(1/q+Σ_n=0^∞{c_ln^(l)qⁿ}
となる。
jの累乗和の係数からu_rを求め、Newton公式により、{t_k}, {s_k}を求めるとよい。

最後に、{s_k}がq-展開の形で求まるので、j^(l+1),j^l,..,jで割ることにより、jの多項式が求まる。
j^l+1におけるq^lの項の係数が必要になるので、j(q)はl(l+1)次まで求める必要がある。

■Φ₂(X,Y),Φ₃(X,Y),Φ₅(X,Y)をPARI/GPで計算してみると以下のようになる。

l	Φ_l(X,Y)
2	X³ + (-Y² + 1488Y - 162000)X² + (1488Y² + 40773375Y + 8748000000)X + (Y³ - 162000Y² + 8748000000*Y - 157464000000000)
3	X⁴ + (-Y³ + 2232Y² - 1069956Y + 36864000)X³ + (2232Y³ + 2587918086Y² + 8900222976000Y + 452984832000000)X² + (-1069956Y³ + 8900222976000Y² - 770845966336000000Y + 1855425871872000000000)X + (Y⁴ + 36864000Y³ + 452984832000000Y² + 1855425871872000000000Y)
5	X⁶ + (-Y⁵ + 3720Y⁴ - 4550940Y³ + 2028551200Y² - 246683410950Y + 1963211489280)X⁵ + (3720Y⁵ + 1665999364600Y⁴ + 107878928185336800Y³ + 383083609779811215375Y² + 128541798906828816384000Y + 1284733132841424456253440)X⁴ + (-4550940Y⁵ + 107878928185336800Y⁴ - 441206965512914835246100Y³ + 26898488858380731577417728000Y² - 192457934618928299655108231168000Y + 280244777828439527804321565297868800)X³ + (2028551200Y⁵ + 383083609779811215375Y⁴ + 26898488858380731577417728000Y³ + 5110941777552418083110765199360000Y² + 36554736583949629295706472332656640000Y + 6692500042627997708487149415015068467200)X² + (-246683410950Y⁵ + 128541798906828816384000Y⁴ - 192457934618928299655108231168000Y³ + 36554736583949629295706472332656640000Y² - 264073457076620596259715790247978782949376Y + 53274330803424425450420160273356509151232000)X + (Y⁶ + 1963211489280Y⁵ + 1284733132841424456253440Y⁴ + 280244777828439527804321565297868800Y³ + 6692500042627997708487149415015068467200Y² + 53274330803424425450420160273356509151232000Y + 141359947154721358697753474691071362751004672000)

[参考文献]

[1]Ian Blake, Gadiel Seroussi, Nigel Smart, "Elliptic Curves in Cryprography", LMS 265, Cambridge University Press, 1999, p50-55, ISBN0-521-65374-6.
[2]Joseph H. Silverman, "Advanced Topics in the Arithmetic of Elliptic Curves", GTM 151, Springer-Verlag New York Inc., 1994, p181-182, ISBN0-387-94328-5.
[3]伊豆哲也, "Risa/Asirによるmodular polynomialの計算", 京都大学数理解析研究所講究録, 1996.
[4]伊豆哲也, 野呂正行, 横山和弘, "モジュラー多項式の計算", SCIS'98-1.1.A, 1998.
[5]Ian Blake, Gadiel Seroussi, Nigel Smart, "Elliptic Curves in Cryprography", LMS 265, Cambridge University Press, p50-55, 1999, ISBN0-521-65374-6.

Last Update: 2005.06.12

H.Nakao

l	Φ_l(X,Y)
2	X³ + (-Y² + 1488Y - 162000)X² + (1488Y² + 40773375Y + 8748000000)X + (Y³ - 162000Y² + 8748000000*Y - 157464000000000)
3	X⁴ + (-Y³ + 2232Y² - 1069956Y + 36864000)X³ + (2232Y³ + 2587918086Y² + 8900222976000Y + 452984832000000)X² + (-1069956Y³ + 8900222976000Y² - 770845966336000000Y + 1855425871872000000000)X + (Y⁴ + 36864000Y³ + 452984832000000Y² + 1855425871872000000000Y)
5	X⁶ + (-Y⁵ + 3720Y⁴ - 4550940Y³ + 2028551200Y² - 246683410950Y + 1963211489280)X⁵ + (3720Y⁵ + 1665999364600Y⁴ + 107878928185336800Y³ + 383083609779811215375Y² + 128541798906828816384000Y + 1284733132841424456253440)X⁴ + (-4550940Y⁵ + 107878928185336800Y⁴ - 441206965512914835246100Y³ + 26898488858380731577417728000Y² - 192457934618928299655108231168000Y + 280244777828439527804321565297868800)X³ + (2028551200Y⁵ + 383083609779811215375Y⁴ + 26898488858380731577417728000Y³ + 5110941777552418083110765199360000Y² + 36554736583949629295706472332656640000Y + 6692500042627997708487149415015068467200)X² + (-246683410950Y⁵ + 128541798906828816384000Y⁴ - 192457934618928299655108231168000Y³ + 36554736583949629295706472332656640000Y² - 264073457076620596259715790247978782949376Y + 53274330803424425450420160273356509151232000)X + (Y⁶ + 1963211489280Y⁵ + 1284733132841424456253440Y⁴ + 280244777828439527804321565297868800Y³ + 6692500042627997708487149415015068467200Y² + 53274330803424425450420160273356509151232000Y + 141359947154721358697753474691071362751004672000)