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

谷山志村対応をいくつかの楕円曲線で確認しました。その際に与えられた楕円曲線の法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) $ が３次式です）の法pでの解の個数を求める場合、平方剰余が活用できます。pをp>2の素数とします。$ f\left(x\right) $に特定のxを代入して計算した値をaとします。$ y^2=a\, mod\, p $ の解の個数は次のようにわかります。

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

そうでない場合、解があるなら２つあり、なければ、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での解の個数とする。それらの総和を求める」です。