改善策と問題点

前々回の記事( http://ehito.hatenablog.com/entry/2019/04/11/193241 )で述べた方法では,M_i(X,1) 以降をただ 1 つの r_i を見付けるために生成していますが,実は M_i(X,0) を得た段階で,それが F_{i-1}[X] に属する場合には,先述の通り拡大を行わず,属さない場合,つまり,M_i(X,0)C\in F_{i}\setminus F_{i-1} となる係数 C をもつ場合には,その Lagrange Resolvent


\begin{align}
R_i(k)&=\sum_{j=0}^{p_i-1}  \zeta^{j k P/p_i}  \tau^j(C)\ \ (k=1,\ldots,p_i-1)
\end{align}

の中に 0 でないものがあるので,それを r_i とすることができます.

この方法では,全ての係数を生成するのは g_i に直結した M_i(X,0) のみで,後は 1 つの係数 C に対する処理となり,相応の高速化が期待できるように思えます.

ところが,この \tau^j(C)\ (j=1,\ldots,p_i-1) を定義通りに計算すると,C\sigma(A)\, (\sigma\in G_i) の基本対称式の 1 つゆえ,C=S(A) となる F_{i-1} 上の多項式 S があり,\tau の準同型性から,\tau^j(S(A))=S(\tau^j(A)) なので,\tau^j に対応する f_{\mathbb{Q}} の根を S(A)A に代入したもの,つまり,最も悪い場合には,f_{\mathbb{Q}} の次数のおよそ 2 乗の次数の多項式(しかも係数は分子分母の桁数が大変なことになっている既約分数)の簡約整理が必要となります.

これまでのところ
【1】前々回の記事のままの実装
【2】上記の改善策による実装
そして
【3】上記の C に対する次数よりも大きな次数の項を消去しながら R_i(X,k) を簡約整理する実装
の処理時間は,サイズの小さな問題では【2】が短く,大きな問題では【1】が短く,【3】はその中間といった実験結果を得ています.