群論では、抽象的な群の要素を群の演算を保つように数字（複素数）に写像することがあり、この写像を指標と呼びます。指標の値は数字なので、解析的な道具（四則演算、微積、ゼータ関数の係数など）と組み合わせることで、群の性質を式に取り入れて計算したり、解析的に証明したりできるようになります。
この本では有限体\(F_p\)の乗法群\(F_p^{\times}\)の指標\(\chi : F_p^{\times}\to C^{\times}\)は\(\forall a,b \in F_p^{\times}, \chi\left(a\,b\right)=\chi\left(a\right)\,\chi\left(b\right)\)を満たす写像として定義されます（便宜上\(\chi\left(0\right)=0\)とします）。
例えば、\(F_5\)の乗法群\(F_5^{\times}=\{1,2,3,4\}\)に対して、
\(\chi\left(1\right)=1,\chi\left(2\right)=i,\chi\left(3\right)=-i,\chi\left(4\right)=-1\)
と定義すると\(\chi\)は指標になっています。是非じっと睨んで確認してください。この例のように\(\chi\)の値域がちょうど\(\{1,-1, i, -i\}\)であるとき、\(\chi\)は位数４の指標である、と言います。
ちなみに\(F_5\)の乗法群\(F_5^{\times}\)の指標は他にもあります。 任意の\(a \in F_p\)について\(\chi_0\left(a\right)=1\)と定義すれば\(\chi_0\)（単位指標と呼びます）も指標になります。また指標同士の積も指標になります。
今回、もう一つ面倒な数学対象を導入します。ヤコビ和と呼ばれる、\(F_p\)上の２つの指標に対して次の式で定義される和です。
\(J\left(\chi , \chi^{\prime}\right)=\sum_{k=1}^{p-1}{\chi^{\prime} \left(1-k\right) \, \chi\left(k \right )}\)
このヤコビ和が本来何に使われるのか、は別の記事にしたいと思います。ここでは今回の記事で重要な次の３つを指摘だけをします（橋本先生の本のp285を参照)。
- \(\chi,\chi^{\prime},\chi\,\chi^{\prime}\)のいずれも単位指標でないとき、\(\left| J\left(\chi , \chi^{\prime}\right)\right| =\sqrt{p}\)
- \(p\)を\(4\,k+1\)型の素数であるとするとき、指標\(\chi\colon F_p^{\times}\to \{\pm 1,\pm i\}\)で位数が4であるものが存在します。その指標\(\chi\)について、\(J\left(\chi,\chi\right)\)はガウス整数
- (定理13.13) 位数が4の\(F_p^{\prime}\)の指標\(\chi\)に対するヤコビ和\(J\left(\chi,\chi\right)\)を、\(J\left(\chi , \chi\right)=a+b\,i,\, a,b\in Z\)と書くとき\(p=a^2+b^2\)が成立
1は自明ではないのですが認めることにすると、2は比較的自明で、この２つのことからほぼ自明に3が成り立ちます。
これでようやく数学的な準備が終了しました。ここから次のような流れでpからa,bを求めることができます。
- \(4\,k+1\)型素数\(p\)に対して位数4の指標\(\chi\)を求める。
- \(J\left(\chi,\chi^{\prime}\right)\)を定義し、上記の\(\chi\)に対して\(J\left(\chi,\chi\right)\)を求める。
- その値の虚部と実部を取り出す。それらがa, bになる。
では早速プログラムを見てみましょう。
init_chi(p)はpに対して位数4の指標を求めて、配列として返します。ここで使っている指標の計算方法も別の記事で書ければと思います。
(%i1) init_chi(p):=
block([pr,chi_array,index],pr:zn_primroot(p),chi_array:make_array(any,p),index:1,val:1,
chi_array[0]:0,
for i:0 thru p-1 do chi_array[index:mod(index*pr,p)]:(val:val*%i),
chi_array)$
次はヤコビ和を定義します。こちらは定義通りです。
(%i2) JacobiSum(x1,x2,p):=sum(x1[k]*x2[mod(1-k,p)],k,1,p-1)$
では早速試してみましょう。使う素数は1000033です。
(%i3) p:1000033;
$$ \tag{%o3} 1000033 $$
この素数に対して位数4の指標を計算します。
(%i4) chi:init_chi(p)$
この指標に対してヤコビ和を計算します。
(%i5) js:JacobiSum(chi,chi,p);
$$ \tag{%o5} -408\,i-913 $$
元に戻ることを確認しましょう。
(%i6) realpart(js)^2+imagpart(js)^2;
$$ \tag{%o6} 1000033 $$
時間を計測してみました。
(%i7) time(%o4,%o5);
$$ \tag{%o7} \left[ 27.476 , 7.666 \right] $$
単位は秒です。
遅いです。最初に指標を求めるのに27秒、ヤコビ和の計算に7.6秒、pに比例した時間がかかるので遅いです。
