代数体上の多項式の高速乗算

一連の冪根拡大の構成では， $\{\sigma(A)\,|\,\sigma\in G_i\}$ を根全体とする多項式 $M_i(X,0)$ の係数 $C$ から冪根を生成し，その過程で得られる情報を $M_i(X,0)$ に還元して分解体の primitive element の最小多項式 $g_i$ を得ていますが， $C$ については $\sigma(A)$ 達の基本対称式を漸化式から得る方法，最小多項式についても幾度か述べたように例えば $g_i=\text{gcd}(g_{i-1},e_i-r_i)$ といった位置付けがあり，規模の小さな問題に対しては実用的でもある一方，こうした工夫はサイズの大きな問題に対しては実装上の問題により逆効果となります．つまり， $M_i(X,0)$ をそのまま展開することとなり，そのうちとくに負担となりえる $M_1(X,0)$ を如何に整理，展開するべきかという視点から今回の表題に至ります．

まず， $M_1(X,0)$ の計算に現れるデータのサイズがどの程度となりえるのかを例示しましょう．入力のサンプルは次の４つです．

例１　 $x^6+x^4-x^2+5 x-5$
Hirokazu Anai,Kazuhiro Yokoyama, Radical Representation of Polynomial Roots
http://www.jssac.org/Editor/Suushiki/V09/No1/V9N1_108.pdf より．
例２　 $x^{14}+28 x^{11}+28 x^{10}-28 x^9+140 x^8+360 x^7+147 x^6+196 x^5+336 x^4-546 x^3-532 x^2+896 x+823$
Andreas Distler, Ein Algorithmus zum Lösen einer Polynomgleichung durch Radikale
http://www.icm.tu-bs.de/ag_algebra/software/distler/Diplom.pdf より．
例３　 $2(1+x)^{13}-x^{13}$
例４　 $x^{13}-2$

例１，２は各先行研究において処理時間が最大，或いは結果が得られなかったもの（なお，これらは冪根拡大に限らない中間体の列を生成した後，それらの primitive element を冪根に置き換える方法によるもので，例１，２はそれぞれ逐次拡大を推奨，単純拡大を採用しています）．例４は標準的（？）なサンプルで，分解体は例３と同型ですが，生成されるデータサイズは全く異なります．

Galois 群の位数は，順に 72，98，156，156．
$\mathbb{Q}$ 上の最小分解体 $\operatorname{sp}(f)$ の $\mathbb{Q}$ 上の定義多項式の文字列としてのサイズは，順に 2208，1367，3638，159 バイト．
$\operatorname{sp}(f)$ の $\mathbb{Q}$ 上の primitive element $A$ の円分体上の最小多項式 $g_0$ の文字列としてのサイズは，順に 2208，2284，1413，132 バイト．
$\sigma(A)$ 全体の文字列としてのサイズは，順に 3276035，4452826，20461351，88263 バイト．

実際の $\sigma(A)$ の利用には
（Ａ） $\sigma(A)$ のまま用いる方法
（Ｂ） $\sigma(A)$ の $g_0$ による剰余を用いる方法
（ $f_{\mathbb{Q}}=g_0$ の場合，（Ａ），（Ｂ）は同じ）があり，展開には
（Ｃ）maxima プロパーの（乗算毎に $g_0$ による剰余をとる）方法
（Ｄ）外部ツール（Julia の Nemo パッケージ http://nemocas.org/ の ResidueRing）を呼び出す方法
があります．各場合の入力から出力までの時間は，次の通りです．

（Ａ），（Ｃ）の場合，順に 23.89，127.47，643.56，7.15 秒．
（Ａ），（Ｄ）の場合，順に 19.88，50.35，175.85，7.43 秒．
（Ｂ），（Ｃ）の場合，順に 24.05，86.62，128.49，3.82 秒．
（Ｂ），（Ｄ）の場合，順に 19.80，50.75，229.23，3.86 秒．

なお，上記の Nemo の ResidueRing は同パッケージの NumberField や Hecke パッケージ http://thofma.github.io/Hecke.jl/latest/ の代数体関連の関数よりも高速です．また，giac https://www-fourier.ujf-grenoble.fr/~parisse/giac.html で乗算毎に rem を用いる方法では

（Ｂ），（Ｄ）の場合，順に 21.83，51.03，397.46，3.94 秒

となります．