読者です 読者をやめる 読者になる 読者になる

Maxima で綴る数学の旅

紙と鉛筆の代わりに、数式処理システムMaxima / Macsyma を使って、数学を楽しみましょう

-数学- 楕円曲線の法pでの解の個数をより高速に求める

東池袋 Adomani

 

谷山志村対応をいくつかの楕円曲線で確認しました。その際に与えられた楕円曲線の法pでの解の個数を総当たりで求めていました。これを1000倍くらい高速化してみましょう。

(%i1) Nsolve(elc,p):=block([c:0,evelc],
for x:0 while x<p do
for y:0 while y<p do
(evelc:ev(elc), if 0=mod(rhs(evelc)-lhs(evelc),p) then c:c+1),
return (c))$
(%i2) NsolveF(elc,p):=sum(ev(1+jacobi(rhs(elc),p)),x,0,p-1)$
(%i3) elc:y^2=x^3+1;
$$ \tag{%o3} y^2=1+x^3 $$
(%i4) p:next_prime(1000);
$$ \tag{%o4} 1009 $$
(%i5) Nsolve(elc,p);
$$ \tag{%o5} 947 $$
(%i6) NsolveF(elc,p);
$$ \tag{%o6} 947 $$
(%i7) time(%o5,%o6);
$$ \tag{%o7} \left[ 18.406 , 0.016 \right] $$

Nsolve()よりもNsolveF()の方が1000倍強早くなっているのが分かります。どうやって高速化しているのでしょうか。

\( y^2=f\left(x\right) \)という形の曲線(楕円曲線では \( f\left(x\right) \) が3次式です)の法pでの解の個数を求める場合、平方剰余が活用できます。pをp>2の素数とします。\( f\left(x\right) \)に特定のxを代入して計算した値をaとします。\( y^2=a\, mod\, p \) の解の個数は次のようにわかります。

\( a=0\, mod\, p \)の場合、解の個数は \( y=0 \) の1つだけ

そうでない場合、解があるなら2つあり、なければ、0個、です。

一方ヤコビ記号を実装したmaximaの関数jacobi(a,p)は、pが素数であれば、aがpの倍数の場合0を、\( y^2=a\, mod\, p \)に解があるなら1を、なければ-1を返します。解の個数とちょうど1だけずれていますね。

というわけでjacobi(a,p)+1が解の個数になっていることに注意してNsolveF(elc,p)のプログラムを読むと、「xを0~p-1で変化させてelcの右辺を評価し、評価した値のpとのヤコビ記号の値に1足したものを、そのxでの解の個数とする。それらの総和を求める」です。 

楕円曲線論入門

楕円曲線論入門

 

この本の1995年版の第4章4.1 有限体上の有理点、を参考にしました。

This is a test.
天気