数理解析研究所講究録920 巻 1995 年 9-24

92.

Radical Representation of
Polynomial Roots
穴井宏和 (富士通情報研)
横山和弘 (’)

2.1 数学的基礎

2.1.1 Galois 理論
まず, Galois 理論について簡単に復習する. mmonic で既約な$\mathrm{Z}$

上の

$n$

次の多項式を $f(x)$ とする.

このとき,f(x) の Galois 群 $G$ は以下のような群の列が存在するときにかぎり可解である.
$G=G_{0}\supset G_{1}\supset\cdots\supset G_{r-1}\supset G_{r}=1$,

ここで,G8 は $G_{i-1}$ の正規部分群で各々の $G_{i-1}/G_{i}$ は素数次数 : の巡回群である. この列を組成列$p$(composition series) という. 組成下が存在する, すなわち $G$ が可解であるとすると Galois 対応より
体の列$\mathrm{Q}=I\zeta_{0}\subset K_{1}\subset\cdots\subset K_{r-1}\subset K_{r}=I\iota_{f}’$が存在する. ここで,

$K_{f}$

は $f$ の分解体で,成される体である. このとき,は$\beta$$p_{i}$$K_{i}$. は$\mathrm{A}’:-1$$K_{i}$

は $G$ :,の作用の下で不変であるような全ての元から構の巡回 (Galois) 拡大であり, その拡大次数$|\mathrm{A}’.$:$I\acute{\mathrm{t}}_{i1}-|$である. さらに, 各拡大 $I\zeta./K_{1-1}$ は有限次拡大であるから, $K:=I\mathrm{f}:-1(\beta:)$ なる $K$: の原始元

: が存在する.
全ての原始元$\beta$: がベキ根で表されれば,$f$の全ての根もまたべ*根で表される. よって,Galois 群

10

$G$

の可解性とは, 体の列における全ての原始元$\beta$うと次のようになる. ここで,1 の原始 p:乗根を1.

$\zeta_{P:}\in K$: ならば,.

がベキ根で表されることを意味する. より詳しくいなる $K$ : の原始元$\beta_{i}^{\mathrm{p}}\in I\mathrm{f}:-1$の p:乗根である.

2.

$\mathrm{C}_{P:}\not\in K$

の原始元

素数
ば

$\beta_{1}$: ならば, $L:-1=K_{-1}.(\zeta \mathrm{p}:),$$P$.

: が存在する. すなわち,\beta , はある元$=K_{:}(\zeta_{\mathrm{p}:})$

とする.

$i$

$\text{そのとき},\beta^{p}.\cdot$

乗根はべ*根表現可能なので, ひとたびもベキ根表現できる. 最終的に$\beta i+1$

$L$$\beta$$\in L:-1$$\beta^{p}.\cdot$

なる$L_{i}$が存在する.

にたいして, 全ての 1 の原始

$P$

とする.

$\zeta_{\mathrm{P}}.\cdot$$I\acute{\mathrm{t}}_{r}$の原始元がベキ根表現され$K_{r}$$\beta_{:}$

がベキ根で表されれ

上の $f$ の全ての根のべキ

根表現ができる.
したがって, 多項式の根のべ $*$ 根表現の問題は, 巡回拡大の原始元のべ $*$ 根表現の問題へと帰着される.

2.1.2 巡回拡大
巡回拡大の場合のベキ根表現の方法について, 代数の教科書 [18] [14] 等で見られる Lagrange の分解式 (resolvent) に基づいた標準的な方法を見よう.
巡回拡大’ を考える. { は体で, 拡大次数$I$

$I\iota’(\beta)/I\backslash$

生成元とする. すなわち,G$I\zeta$上の$\beta$$=\{1, \sigma, \cdots, \sigma^{\mathfrak{n}}-1\}$$|I\mathrm{f}(\beta)$: $K|$ を$\gamma$が見つかれば,$\sigma$

をその Galois 群 $G$ の.

のべキ根表現に向けて, 必要なのは $K(\beta)$ の元元である. もしこのような元

とし,

$n$

$\beta$は $K$ 上$\gamma$$\gamma$で,は原始元でもあり$\gamma$$\gamma^{n}\in I\{’$なるの多項式として表されるからである. 実は,Lagrange の分解式はこの性質をもち, さらに効率的に計算可能なのである.
以下, 基礎体

は 1 の原始$I\backslash ’$$n$乗根を含んでいるとし,$n$は $K$ の標数 (Charact 可 stic) によって割れないとする. この仮定の下で次の良く知られた命題が成立する.

命題 1K の元で $x^{n}-a$ が既約多項式で $x^{n}-a$ のどの根もする. さらに, 元 $\gamma\in K(\beta)$ は, ある 1 の原始$K(\beta)$の原始元かつ$K(\beta)$の原始元$\beta$$\gamma^{\mathfrak{n}}$は$I\mathrm{t}^{r}$$\beta\nu+1$$\zeta$に対して$\sigma(\gamma)=\gamma\zeta$

$a$

が存在

が成立するときに限り,に対して, Lagrange の分解式はここで,\mbox{\boldmath $\zeta$} は 1 の$(\beta_{\mathfrak{n}}=\beta 0)$乗根の原始元になるような元に属する.

$u(\beta, \zeta)$

で与えられる.

$n$$I\backslash ’(\beta)$. ($\beta$$=$$\beta+\zeta\sigma(\beta)+\cdots+\zeta^{\mathfrak{n}}-1\sigma(n-1\beta\rangle$$=$$\beta_{0+}\zeta\beta_{1}+\cdots+\zeta^{\mathfrak{n}-1}\beta n-1$$n$,乗根 (かならずしも原始ではない) で\beta v

は原始元なので$\beta_{1},$$\cdots,$$\beta_{n-1}$

は次数は

$n$

(1)

より小さい

$=\sigma^{\nu}(\beta),$$\beta$$\sigma(\beta_{\nu})=$の多項式として表される.) このとき,$\sigma(u(\beta, \zeta))$$=$$\beta_{1}+\zeta\beta_{2}+\cdots+\zeta n-2\beta_{n-1}+\zeta^{n-1}\beta_{0}$

(2)

11

よって,
$0$

$n$

乗 $u(\beta, ()^{n}$ はなる 1 の原始

た 1 の原始$n$$n$$\sigma$&+\mbox{\boldmath $\zeta$}\beta 1+$=$$\zeta^{-1}.$$=$$\zeta^{-1}u(\beta, \zeta)$$($$\cdots$.

の作用の下で不変であり,$u(\beta, \zeta)^{n}$

乗根 (が存在すれば (そういう 1 の原始乗根なので,$u(\beta, \zeta)$

は$K(\beta)/I\mathrm{f}$$+\zeta^{\mathfrak{n}-1}\beta_{n-1})$

は基礎体
$n$

乗根

$\zeta$$I\zeta$に属する. さらに,u \beta ,$($は存在する (補題 9)),$\zeta^{-1}$$\zeta)\neq$

もまの原始元である.

それゆえ, この場合 $P(u(\beta, \zeta))=\beta$ なる $K$ 上の多項式 $P(x)$ が存在する. これより,K 上の$\beta$のベキ根表現が得られる.
他に教科書等で見られるものとして, 全てのた以下のような記述がある.

$\zeta^{-r}$

$n$

乗根

$\zeta$に対する Lagrange の分解式

を (1) 式に掛けて全ての 1 の$n$$u(\beta, \zeta)$

乗根 (について和をとると,(3)$\sum_{\zeta}(^{-\Gamma}u(\beta, \zeta)=n\beta r$

したがって,$\beta$は$u(\beta, \zeta)$$u(\beta, \zeta)$

がわかれば

$n$

$\overline{\backslash }$は If の標数によって割れないので (3) から(これらは全て $K$ の元の

$n$

を用い

$\beta_{r}$が求まる. そして,乗根) の K-線形和として表される.

2.2 概要多項式の根のべ*根表現は以下のような$(\mathrm{a})(\mathrm{b})(\mathrm{c})3$

部構成になっている. ただし, 冒頭でも述べたとおりここでは (c) について着目している. (c) においては前節の議論から, (i) Galois 群の組成列の構或 (ii) 組成列に対応した部分体の列の構或 (iii) 各拡大の原始元のべキ根表現の構成という手順が必要である. 根をベキ根で表すことが目的であるので Galois 群は根の上の置換群として具体的に求める必要がある. よって (a) については [$3|$の direct method

与えられた既約多項式 $f(x)$ に対し, その分解体$\alpha_{1},$$\cdots,$$\alpha_{\mathfrak{n}}$$K_{f}$を用いる.

は剰余環として, また Galois 群$G$

は $f(x)$ の根の上の置換群として求まっている. (根といっても, 全ての根はある変数に割り当てられている.)$[\mathrm{a}]$

したがって,(C) に進む前には,$[\mathrm{b}]$

[C]

12

具体的には以下のような状況が設定される (詳細は [3] 参照);
分解体
$1,$ $\cdots,$ $n$$K_{f}\simeq \mathrm{Q}(\alpha_{1}, \cdots, \alpha_{n})$は変数のイデアル $J$ を

$y$

.

は剰余環

に割り当てられ, $J$ は,$K_{f}$

で$f_{i}(\alpha_{1}, \cdots, \alpha.)=0$

method を用いると, その中で長さ (length) という. このとき,作用はる.

$\text{し}_{}^{\backslash \mathrm{B}_{\grave{\grave{\mathrm{a}}}}}$$y_{1},$ $\cdots$,$y_{n}$$\alpha_{i},$$i=$$defin\dot{l}7\iota g$こpolynomials)

により生庫される. ここで, 各 $f_{i}(y_{1}, \cdots, y_{i})$ は,$y_{i}$

について(以降, 多項式の集合

は $f$ の根

$y_{1},$の原始元$K_{f}$とする.[3] より,$\cdots,$$\beta$$y_{n}$に対して ($P$$P\rangle$

は $P$ によって上の置換群として表されている. direct

は根の Z-線形和として求まっている. それを$K_{f}=\mathrm{Q}(\alpha_{1}, \cdots, \alpha_{l})$なる整数 $\ell(\leq n)$ が存在し,において $op+1=\cdots=a_{n}=0$ としてよく, また,i $=P+1,$$\beta$$\cdots,$ $n$: を多項式として $f_{i}=x:-A:(x_{1}, \cdots, x_{l})$ となる. またこのとき, Galois 群の各元の$\cdots,$$\alpha_{1},$

$G$

上の

$\mathrm{Q}$$\beta=a_{1}\alpha_{1}+\cdots+a_{n}\alpha_{n}(a|\in \mathrm{Z})$$A$

ここで, 各根となる. また, $f.(y_{1}, \cdots, y:)$ は拡大体 $\mathrm{Q}[y_{1}, \cdots, y_{-}.\cdot 1]/(fi, \cdots, fi-1)$ 上生成されるイデアルを表すとする)

に対しては, $y_{n}|/J$ により表される.

の間の全ての代数関係からなるイデアルで極大である.

$\alpha_{1}$について monic で既約な多項式である.

$y_{i}$$\cdots$の定義イデアル (defining ideal) という. $J$ は定義多項式 ($\{fi(y\iota), f_{2}(y_{1}, y_{2}), \cdot ‘ \cdot, f_{n}(y_{1}, \cdots, y_{\mathfrak{n}})\}$

monic で$\mathrm{Q}[y_{1},$$\alpha p$って,の上の作用できまることから, 余分な変数 $y\ell+1,$$K_{f}\equiv \mathrm{Q}[y_{1},$あるいは$y_{1},$$\cdots,$$y_{P}$$\cdots,$$yp1/(f_{i}(y_{1}), \cdots, f_{t}(y_{1}, \cdots, yp))$$\cdots,$

を省いても良いことがわか$yn$. よって, 以下$y_{1},$$\cdots,$$y_{t}$によってを表すことにする.

(b) の Galois 群の可解性の判定については, 群論に関する既存のアルゴリズムを用いる. ここでは解説は省略する (詳しくは [1] [4] を参照) さらに, 群の組成列の計算についても dominant な部分ではないこともあり, 既存の方法 ([5], [8], [11]) を用いる. 以後, 組成列もすでにわかっているとする.

2.3 部分体の構成
既存の置換群のアルゴリズムを使って組成列 $;Go=$. $G,$
なわち, 組成列の各剰余群 $G_{-1}./G.,$ $i=1,$$\cdots,$ $r$$G_{1},$$\cdots,$

は, 位数が素数$G_{r}=1$ ,$p$が構成されたとする. す: の巡回群であるとする.

き, 組成列に対応する部分体の列を構成する. 部分体はそれぞれ各原始元$\beta_{i}$

このとと最小多項式として与えられる.
まず, ある原始元は原始元だから$B_{0}$$\beta$はり,|B| $|=|G||=|K_{f}$ :を含む $G$ , の軌道 (orbit) を$Ii_{f}’$

中のの全ての共役元の集合であり,G は$\beta$$K\dot{.}|=|I\acute{\iota}_{f}$とする. すなわち, $B.,$ $=\{\sigma(\beta)|\sigma\in G_{i}\}$ .

$B_{i}$:$\mathrm{Q}|/|K|$

定義 $1K_{f}$ の有限集合 $B$ に対して, 多項式:$\mathrm{Q}|$$f_{B}$

.各

$B$

.

$B_{0}$$\beta$に正則に作用する. これよに対して以下を考える.

は以下のように定義される.

$f_{B}= \prod(x-b)$$b\in B$

$f_{B}$

を $B$ に対応した多項式 (polynomial corresponding to $B$ ) という. さらに,係数を$\mathrm{Q}$に添加して得られる体とする. そのとき,る体 (field corresponding to $B$ ) という.

$I\mathrm{t}_{B}’$は$K_{f}$の部分体である.

$I\acute{\mathrm{t}}_{B}$$I\acute{\mathrm{t}}_{B}$を$f_{B}$の全てのを $B$ に対応す

13

軌道

$B_{1},$

補題 2 各$\cdots,$にそれぞれ対応した部分体$B_{r}$

に対して,

$i$

:

$p:=|K_{i-1}$$K_{B}$$K_{B_{1}},$$\cdots,$ $K_{B_{r}}$を考えと, 直ちに次を得る.

: は $K$ : と –致する.

が素数なので瓦 と $K_{i-1}$ の間には真の部分体は存在しない. これと,[19] とより次

$K_{i}|$

が成立する.

系3$f_{B}.\cdot$の係数の集合の中に$I\zeta_{-1}.\cdot$.

上の If: の原始元が存在する. さらに,

$I\zeta_{-1}$に属さない$f_{B}\dot{.}$の係数はすべて瓦-1 上の瓦の原始元となる.
$K_{i-1}$

定義上の原始元と$2K_{-1}.\cdot$

上の$\mathrm{Q}$上の原始元とことなることがあるので, 以下を定義しておく.

の原始元を逐次 (successive) 原始元,

$K_{i}$

上の$I\zeta:-1$$I\acute{\mathrm{t}}_{i}$の原始元でまた,Q 上のの原始元でもあるとき絶対的 (absolutely) 原始元という.

$K.\cdot$

注意 1 明らかに, $f_{B_{\Gamma}}=x-\beta$ なので\beta は $K_{r-1}$ 上の $K_{f}=K_{r}$ の最後の原始元であり, 絶対的原始元である. また, $K_{r-1}$ 上の $K_{f}=K_{r}$ の最後の原始元として与えられた多項式のある根を選べる.

補題 4 全ての根
この$\alpha_{j}$は$\alpha_{n}$(特に$\cdots,$$\alpha_{1},$$\alpha\ell$) のうち, $K_{r-1}$ に属さない根$\alpha.\cdot$

もまた瓦-1 上の$K_{f}=I1_{\mathcal{T}}^{\nearrow}$が存在する. このとき,の逐次原始元である.

以上より, 部分体を計算するアルゴリズムが完成する. まず,

すなわち, 各原始元

る.

$\alpha_{j}$上の $K_{f}=IC_{r}$ の逐次原始元である. さらに, $G_{r-1}$ が $Go=G_{f}$ の正規部分群であ$I\zeta_{r-1}$

れば, 全ての根$\cdots,$$\alpha_{1},$に, 次の $I1’,+1$ の原始元$\beta_{j},$$1\leq i\leq$$\beta_{:+1}$

可よそれぞれ$f_{B_{j}}$$I\mathrm{f}_{1},$$\cdots,$$I\mathrm{t}^{r_{i}}$はすでに得られているとすの係数として得られているとする. このときを求める. 系 3 あるいは補魎 4 より.

$\beta_{+1}$の係数で瓦に属さは $f_{B_{:+1}}$

ないもの, あるいは, 瓦 に属さない根として選ばれる. そのような元を見つけるのには,$\beta:+1$$\beta_{1},$$\cdots,$$\beta_{i}$との候補となる係数あるいは根の間の代数関係求めればよい. これは,Gr\"obn.e 基底の方法を用い$\mathrm{r}$れば容易に計算できる. まとめると,アルゴリズム 1Next Successive Primitive Elemeni

Input: $G_{1+1},$
Output;1.

2.
S.

$f_{B_{\mathfrak{i}+1}}$$f_{B_{\iota+1}}$$\beta,$$\beta_{\tau+1},$.

$\beta_{1},$$\cdots,$$\beta.$.

$m_{+1}$ $(x;\beta_{1}, \cdots , \beta_{:})$.

を計算する.

の係数のうち瓦に含まれない係数の最小多項式を$K.\cdot$

上の

る.

すなわち,

$c$

$\beta_{1},$$\cdots,$$\beta$

: と

$c$

$c$

を見つける.

の間の最小次数 $d(=p.+1)$ の代数関係として求め$c^{d}+m_{d-1}(\beta 1, \cdots, \beta.\cdot)_{C^{d-1}}+\cdot$$+m_{0}(\beta_{1}, \cdot\cdot.\cdot,.\beta.\cdot)=0$,上のの多項式である.
ここで,m0, . . , $m_{d-1}$ はをとして, また $c^{d}+\cdots+m_{0}$ を $m_{i+1}(x_{i}; \beta 1, \cdots, \beta:)$ として出力.
$\cdot$

4.

.

$c$

$\mathrm{Q}$$\beta_{1},$$\cdots,$$\beta|$$\beta i+1$

$i=r-1$ のとき, ステッブ 1, 2 を次のステッブ 1’ で置き換えてもよい.
1’. $f(x)$ の全ての根のうち$K_{r-1}$に含まれない根$c$を見つける. .

絶対的原始元の場合も同じような手順で次の原始元を構成する方法$([4|\text{参照})^{\text{が考}えら}\prime\ovalbox{\tt\small REJECT} \text{れるが},’$

実際の

14

計算の効率は逐次表現の方が優れていることもあり, これ以降は逐次表現の方についてだけ述べることにする. 具体的な方法を述べる前にここで次を仮定する.

仮定 1 逐次原始元
上の$\mathrm{Q}$$j=1,$$y_{1},$$\cdots,$$\cdots,$$\beta_{1},$$\cdots,$$\beta:-\iota$は既に得られているとする.

の多項式である.

$y_{t}$

ここで, 各$K_{j-1}=\mathrm{Q}(\beta_{1}, \cdots, \beta|.-1)$$i-1$ に対して得られているとする.

$i=1,$$\beta_{j},$$\cdots,$$i-1$ は上の\beta j の最小多項式 $m_{j}(x)$ もまた
ここで$(m_{j}(X)=m_{j}(x, \beta:-1, \cdots, \beta 1).)$を逐次$m_{j}$

最小多項式という.
方法 $1i$ 番目のステップを考える. まず, ある原始元$\beta$を含むの軌道$G_{i}$

を求め対応する多項式$B_{i}$

を計算する. $f_{B_{1}}.(x)=x^{\mathfrak{n}_{i}}+f.,\mathfrak{n}.\cdot-\iota x^{n-\iota}:+\cdots+f:,1^{X}+f_{1},0$ とする.

$f_{B_{:}}$

原始元の候補となる元$\gamma$を係数人」あるいは $i=r$ ならばある根の原始元であるかどうか基底変換 (し, それぞれ$\beta_{1},$$\cdots,$$\beta|-1,$$\gamma$$\mathrm{b}\mathrm{a}s$$\alpha_{\mathrm{J}}$is-conversion) により決める.

から選ぶ.

$u_{1},$が瓦-1 上の$\gamma$$\cdots,$ $u|.-\iota,$$K_{\iota}$$v$

を新しい変数と$f\iota$で生成されるイに割り振る. すなわち,$j=1,$$u_{j}-\beta_{j}(y_{1}, \cdots, y_{t})=0$$i-1$$\cdots,$$v-\gamma(y1, \cdots, y_{t})=0$

多項式環$\mathrm{Q}[y1_{)}\ldots, y\mathrm{c}, u1, \cdots, y|-1, v]$の $u_{1}-\beta 1,$ $\cdots,$ $u:-1-\beta_{-1}.\cdot,$ $v-\gamma,$ $f1,$ $\cdots,$

デアルブを考える.
は$\overline{J}$$\mathrm{Q}[y_{1},$$\cdots,$と同型である.
$\beta_{i-1},$$y_{\ell},$$u_{1},$$\cdots,$$ui-\mathrm{l},$ $v1$の極大イデアルであり,$\mathrm{Q}[y_{1}, \cdots, y\iota, u1, \cdots, u_{i-}\mathrm{l}, v]/\overline{J}$また辞書式順序 $y_{1}\prec\cdot\cdot\cdot\prec y_{t}\prec u_{1}\prec\cdots\prec u_{-1}.\cdot\prec v$ について { $v-\gamma,$
は (そのままで)$f_{t},$$f_{1}\}$$\cdots,$ $u_{1}-\beta_{1},$$\cdots,$

方, 別の順 F\ell (block order)

基底を求めると,$\gamma$$\overline{J}$の$Gr\overline{o}bner$

はん f$u_{i-1}$-

基底である.

$\{\{u_{1}, \cdots, u_{-1}.\cdot.\}\prec v\}\prec\prec\{y_{1}, \cdots, y_{t}\}$について J の (簡約)$Gr\overline{o}bner$

が原始元であるかどうか決めることができ, 同時にその最小多項式も求まる.

この方法は以下の定理等によってその正当性が保証される (証明略. [4] 参照)
定理 5(1) 消去イデアル (elimination ideal)$m_{1}(u_{1}),$ $\cdots,$$m:-1(u:-1, u:-2, \cdots, u_{1})$(2) 消去イデアル$\overline{J}\cap \mathrm{Q}[u\iota,$$K:-\iota=\mathrm{Q}(\beta_{1}, \cdots, \beta_{i-1})$$\cdots,$$u:-1,$ $v1$$\overline{J}\cap \mathrm{Q}[u_{1},$$\cdots,$$u_{-1}.\cdot 1$は,$\mathrm{Q}$上の逐次最小多項式によって生成される極大イデアルと –致する.
は, 逐次最小多項式$m_{1},$ $\cdots,$$mi-1$と$\gamma$の上の最小多項式から生成されるイデアルと –致する.

Gr\"obner 基底の性質より,
系$6\overline{J}$の block ordering $\{u_{1}, \prec\cdots\prec u:-1\prec v\}\prec\prec\{y_{1}, \cdots, y_{\iota}\}$ .

についての簡略された $Gr\tilde{o}bner$

基底を $GB$ とする.
(1) 各 $j=1,$$\cdots,$$i-1$ に対して, $GB$ に $K_{j-1}$ 上の \beta , の逐次最小多項式と –致する多項式$m_{j}(u_{j}, u_{j}-1, \cdots, u_{1})$(2) $GB$ にが存在する.

$\mathrm{A}’.-1=\mathrm{Q}(\beta_{1}, \cdots, \beta:-1)$

上の\mbox{\boldmath $\gam a$} の最小多項式と –致する多項式 $h(v, u:-1, \cdot\cdot\phi, u_{1})$ が存在する.

よって, 変数の順序を変えると $K_{i-1}$ 上の

式が

$v$

$\gamma$の最小多項式が求まり,について 1 次でないかどうかで決定できる.

系 7 以下の (1)(2) は同値である.

$\gamma\in I\mathfrak{i}_{i-1}’$

かどうか\mbox{\boldmath $\gamma$} の最小多項

15

(1)

$\gamma$は上の$I\zeta_{1}-1$(2) $GB$ に上の$\mathrm{Q}$$K_{i}$$u_{1},$の逐次原始元である.
$\cdots,$$u_{i1}-,$

$v$

の多項式で

について非線形な元が存在する.

$v$

2.4 巡回拡大のべキ根表現
さて, 各原始元$\beta:,$$i=1,$$\cdot\vee\cdot,$のべ*根表現について考えるのであるが, この節ではまず–般の場$r$

合に Lagrange の分解式に基づいた巡回拡大のべ $*$ 根表現の方法について述べる. この方法は, 零でな

Lagrange の分解式を構成する部分と原始元を Lagrange の分解式とある 1 の原始

い

$P$

乗根の多項

式として表す部分からなる. 一般の素数次の巡回拡大について以下を設定する.
仮定 $2L$ を基礎体 $K$ の拡大次数が素数次

とする

$p$

の巡回拡大とする.

をその Galois 群とする. このとき, $L/K$ の原始元

$G$$\beta$$I\zeta$は,Q あるいはその有限次拡大とその全ての $K$ 上の共役元は与えられているとする.
これは,K 上の$\beta$の最小多項式 $f(x)$ が与えられ,$\beta$の全ての共役元は,

$L$

の表現

$L=K(\beta)\equiv I_{1}’[x]/(f(_{X}))$によって$\mathrm{A}’$上の$\beta$の多項式として表されていることを意味する. ここで, 変数$x$を$\beta$に割り当てている. また $\deg(f)=p$ .

2.4. 1 零でない Lagrange の分解式
$g_{0}(y)$

を

式とする.

上の 1 の原始$\mathrm{Q}$$L$と全ての 1 の$p$$P$乗根の最小多項式,g(y) を $L=K(\beta)$ 上の 1 の原始$P$乗根の最小多項乗根から生成される円分体 $K’$ の合成体 (composite field) $L’$ を構成する必要がある.
L$=\mathrm{L}\langle\zeta)$$/$$\backslash \mathrm{g}(\mathrm{y})$$\mathrm{L}=\mathrm{K}($$\mathrm{K}(\zeta)$$\mathrm{g}_{0}(\mathrm{y})\backslash /\mathrm{f}\langle \mathrm{x})$$\mathrm{K}$

そのために,$g\mathit{0}$を $L=\mathrm{A}’(\beta)$ 上で既約因子に因数分解する; $\mathit{9}\mathit{0}(y)=g_{1}(y)\cdots g_{s}(y)$ . このとき,補題 8(1) 各 1 の原始(2)$\mathrm{A}’$上の$g\mathit{0}$

$P$

乗根

$\zeta$に対して $K’=K(\zeta)$ and $L’=L(\zeta)$の各既約因子はまた $L=K(\beta)$ 上の既約因子である. さらに,K 上の g0 $(y)$ の全ての既約因子 $g.(y)$ は同じ次数を持つ.
補題 8(2) より各既約因子 $g.,$ $i=1,$$\cdots,$ $s$

について剰余環 $R:=\mathrm{A}’[x,$ $y|/(f(x), g_{i}(y))$ は, 合成体.

$I\mathfrak{i}’’$に同型な体になる. したがって, この剰余環 $R$ によって合成体 $L’$ を表せる. さらに, 次の分解が得

16

られる.
$R_{\mathrm{O}}=K[x, y]/(f(x), \mathit{9}o(y)\rangle=R_{1}\oplus\cdots\oplus R_{s}$各$\zeta$に対して Lagrange の分解式

で $u(x, y)$乗根を構成する. すなわち, 各剰余環 $R$$u(\beta, \zeta)$.

$=K[x, y]/(f(x), g:(y)\rangle$を構成する. Lagrange の分解式について

補題 9(1) $u(x, y)\neq 0\in R$: なる
$p$

.

$i$

が存在する. と \langle に,g0 が If 上既約であれば, 全ての 1 の原始について $u(\beta, \zeta)\neq 0$ .

$\zeta$(2) ある 1 の原始$P$

乗根 (について $u(\beta, \zeta)=0$ ならば,が存在する. ここで,\mbox{\boldmath $\zeta$}‘‘ もまた 1 の原始$P$$u(\beta, \zeta^{\epsilon})\neq 0$なる

より小さな正の整数$P$乗根である.

この補題 9 より必要な (零でない Lagrange の分解式を与えるような) 1 の原始見つかる.

ここでは (1) のような$\zeta$このとき, あるが見つかったとしよう.
そして,

解式 $u(x, y)$ に割り当てる.

において容易に計算でき,$y$$H(\zeta_{P})(=H(y))$$\mathrm{A}’(\beta)/K$

は $L’$

として得られる. $L’$ 上のの原始元なので,$\mathrm{A}’(\zeta_{p})$

上の

$z$

$z$

$z$

を

$L’$

$i$

$P$

乗根

$\zeta_{P}$は必ずに対し $g(y)=g_{i}(y)$における (零でない) Lagrange の分

で, $L’=R_{i}=$ ん [x, ] $/(f(x), g(y))$ となる.
$u(\beta, \zeta_{p})^{p}$$s$$\mathrm{A}’$上の$\zeta_{\mathrm{p}}(=y)$の多項式の最小多項式 $h(x, y, z)$ は $z-u(x, y)$ であり,

$z$

はまた

の最小多項式は $z^{p}-H(y)$ である. そして, このとき次が成り立つ.
$L’=R_{i}\equiv \mathrm{A}’1x,$ $y,$$Z]/(f(x), g(y),$ $h(x, y, z))\equiv K[y, z]/(g(y), z^{p}-H(y)\rangle$ .

2.4.2 ベキ根表現の具体的構成法
次に, 原始元を Lagrange の分解式とある 1 の原始$P$

乗根の多項式として表すことを考える. そのための方法としてはいくつか考えられる.
方法 2\S 1.2 で述べた方法を直接用いる方法が考えられる. これは,1 の$n$乗根のべ $*$ 根表現を構成する際に特に有効である ([2],/4/ 参照). この方法では, “ 求められたべ $*$ 根表現中に現れてくるいくつかの $p-1$ 乗根に対してどの値をとれば良いのか?

”という問題が起こる. すなわち, あるベキ根に対する任意の値付け (evaluation) が許されない場合がある.
一般に,$\sqrt[m]{a}$は多価函数であり, その値の選び方によってベキ根表現は他の元を表現するという場合がある. ここで, ベキ根表現に対して以下の概念を定義しておく.

定義 3 ある代数的元を$\xi$, その最小多項式を$\varphi$とする. このとき,に現れるベキ根の値のどの選び方に対しても最小多項式$R(\xi)$$\varphi$$\xi$のべ*, 根表現 $R(\xi)$ が, $R(\xi)$ の中の根を表すとする. このとき, ベキ根表現

は強ベキ根表現 (strong radical representation) という.

ここで, もう -度整理すると問題は $\mathrm{r}_{f(X),g(y),h}(x, y, Z)$ から

$x$

を

$y$

と

$z$

の多項式として表した$x=P(y, z)$ を求める.」 となる. この視点から,Gr6bner 基底の計算を用いた方法, 代数拡大体上のGCD 計算を用いた方法が考えられる. Gr\"obner 基底の計算における基底変換 (basis conversion) を用いた方法について述べる. 代数拡大体上の GCD 計算を用いた方法については [4] を参照.

17

仮定 31 の原始方法 3 この$S$$P$

乗根は既にベキ根表現されているとする.

つの多項式から得られる拡大体は$y)z]/(f(x), g(y),$ $h(x, y, z))$ .

$I\acute{\backslash }(\beta, \zeta_{p})\equiv I\acute{\backslash }1x,$このとき, $f(x),$ $g(y),$ $h(x, y, z)\text{はそのままでイデア})\mathrm{s}$. $(f(x), g(y),$ $h(x, y, Z))$ の辞書式順 F $x\prec y\prec z$
での簡約された $Gr\tilde{o}bner$ 基底になっている. (三角形式 iriangular form) 剰余環が体なので, このイ

デアルは極大イデアルであり, 根基に–致する.

$x\text{が}y-$との多項式で書けるというのは, 言い換え$z$

ると, $x-A(y, z)$ という形の元がイデアルに存在するということである (ここで,A は

$y$

と

$z$

の多項

式). よって, 辞書式順序 $z\prec y\prec x$ or $y\prec z\prec x$ (すなわち block order $\{z, y.\}$ \prec \prec x 刀で Gr\"obner

基底を計算すれば, $x-A(y, z)$ は $Gr\tilde{o}bner$ 基底による M- 簡約によって
ない.

$x$

$0$

に簡約されなければならは $x-A(y, z)$ の頭項 (head $te7m$) なので, この $Gr\overline{o}bner$ 基底に $x-P(y, z)$ という形の元が存在する. この元が$x$のべ $*$ 根表現を与える.

定理 10 $f(x),$ $g(y),$ $h(x, y, z)$ で生成されるイデアルの block order $\{y, z\}\prec\prec x$ での Gr\"obner 基底の中に元 $x-P(y, z)$ が存在する.

2.5 各原始元のべキ根表現
前節で–般的な形で述べた巡回拡大に対する方法を, 各拡大の原始元$\beta_{\mathrm{i}},$$i=1,$$\cdots,$ $r$のべキ根表現の構成に適用する. もちろん, 次を仮定する.
仮定 4 全ての原始元$\beta_{i}${よ計算されている.

2.5.1 強ベキ根表現
実際には強ベキ根表現を構或するのが目標であるので, ここで, 強ベキ根表現について触れておく.
$\mathrm{A}’$は$\mathrm{Q}$の有眼次拡大でその原始元$\beta’$と$\zeta_{P}$は上ベキ根表現されているとする.

$\mathrm{Q}$$/^{\mathrm{L}’=\mathrm{L}\mathrm{t}\zeta_{\mathrm{p}}}\backslash ^{)}$$\mathrm{K}(\beta)$.

$\mathrm{K}’=\mathrm{K}\langle\zeta \mathrm{P})$$\cdot$/’.

$\cdot$$\mathrm{g}_{0}(\mathrm{y})\backslash /\mathrm{f}(\mathrm{x})$$\mathrm{Q}(\zeta_{\mathrm{P}_{\backslash }})$$’.\cdot \text{ノ}\cdot \mathrm{K}=\mathrm{Q}(\beta.)$.

$\backslash ..\backslash .:_{\backslash }$$\prime’..\cdot’$.

前節の方法で$\mathrm{A}’$上のそれぞれそれらの$\mathrm{Q}$$\beta$の強ベキ根表現を求め, (

.-.-

.

$.\mathrm{Q}^{l}$$\beta’$と上の強ベキ根表現と置き換えると,$\zeta_{P}$$\mathrm{Q}$の多項式として求まっている)上の$\beta$$\beta’$と$\zeta_{p}$をのべキ根表現が得られる. 強ベキ

18

根表現について次が成立する.
補題$11\mathrm{Q}(\beta’)(=I\mathrm{f})$と$\mathrm{Q}(\zeta_{p})$は線形無関連 (linearly disjoint) だとする.(これは $go=g$ という条件と等しい) このとき,\beta のべキ根表現は,$\mathrm{Q}$上の$\zeta_{P}$の強ベキ根表現と$\mathrm{Q}$上の$\beta’$の強ベキ根表現のどの組に対しても, 強ベキ根表現となる.

2.5.2 強ベキ根表現の構成
各拡大において補題 11 の条件を満たす, すなわち根の強ベキ根表現を構成するには, 基礎体をある
円分体で置き換えればよい.

まず, 与えられた多項式
定義 4$q_{1},$$\cdots,$$q_{s}$

を$p_{1},$$f$$\cdots,$

によって決まる円分体$p_{r}$$\mathrm{Q}((_{q})$$\mathrm{Q}(\zeta_{q})$は全ての$q= \prod_{j=1}^{*}q\mathrm{j},$$\zeta_{P}.\cdot$$\zeta_{q}=\prod_{j=1}^{\epsilon}.\zeta_{q_{\mathrm{j}}}$とする.

そして $-1=(2$ を含む. この円分

は $f$ に対応する円分体という.

の (強) ベキ根表現は$\zeta_{q}$を以下のように決める.

の中の異なる奇素数だとする.

このとき,\mbox{\boldmath $\zeta$}q は 1 の原始 q 乗根であり, 円分体
体は$L$$(_{q_{1}},$$\cdots,$$\zeta_{q_{\iota}}$の (強) ベキ根表現の積として与えられることに注意する.

$(_{q}$のベキ根表現が必要だがそれについては次を仮定する.
仮定$5\zeta_{q}$変数$\ell$$z$の強ベキ根表現は得られている.
を$(_{q}$に割り当てる. $g(z;y_{1},$である. この多項式は$\mathrm{Q}$上の$(_{q}$$\cdots$, y のを$K_{J}$

上の$(_{q}$の最小多項式 g。を分解体の最小多項式とする. ここで, $t=n$ or$K_{f}$

上で因数分解することで得られる.

(この因数分解の効率化については [4] を参照) このとき, 全ての計算はの上で行なわれ,$I\mathrm{i}_{\int}^{r}(\zeta_{q})$$\mathrm{Q}(\alpha_{1}, \cdots, \alpha_{t}, \zeta q)=$A’f$(\zeta_{q}))$は剰余環$\mathrm{Q}[y_{1}, \cdots, y_{t}, z]/(f_{1}(y_{1}))\ldots,$$f_{\ell}(y_{1}, \cdots, y1),$$g(Z,$ $y_{1y))},$$\cdots,t$として表される.
$i$番目のステップについて考える. まず,$K_{i}$

を $L:=I\zeta_{i}(\zeta_{q})$ に換える. 変数にそれぞれ割り当てる. また Lagrange の分解式 $u(u:, z)$ に変数多項式を考えるのである.

$v$$u_{1},$$\cdots,$ $u|$を$\beta_{1},$$\cdots,$$\beta|$を割り当てる. すなわち, 以下の19$u_{j}-\beta_{j}(y_{1}, \cdots, y_{t})$$j=1,$$\cdots,$$f_{k}(x_{1}, \cdots, x_{k})$$k=1,$$\cdots,$

$i$

$t$

$v-u(u., z)$$\cdots,\mathrm{C}$$(\mathit{9}(_{Z};y_{1y)},$そして, ここで $L_{i-1}$ 上での$\beta_{1}$のべキ根表現を考える.

ベキ根表現を求める前に注意すべきことがある.

$|\mathrm{A}_{i}’$: $K:-1|(=p:)$ が素数であることから

$|L$

: :

あるいは $L:=L:-1$ が成立する. さらに, 次が成立する.

$L_{i-1}|=p_{i}$

補題 12

(1)

$L_{r}=I\acute{\mathrm{t}}_{f}(\zeta q)$

は上の Galois 拡大であり, また$\mathrm{Q}$(2) $L_{r}/L_{i}$ の Galois 群は(3)$\beta_{i}$の中の$G_{i}$

上の Galois 拡大.

$L_{0}=\mathrm{Q}(\zeta_{q})$の固定群である. すなわち,$\zeta_{q}$$\{\sigma\in G:|\sigma(\zeta_{q})=\zeta_{q}\}$.

上の翫の原始元.

は $L_{i-1}$(4) $L_{i-1}\neq L_{i}$ ならば,.

$L_{i}/L_{-1}.\cdot$

よって剰余群 $G_{i-1}/G$のGalois 群はの$\mathrm{A}_{i}’/I\mathrm{f}_{i-}1$

Galois 群と同型であり,と同型.

よって,L, $=L_{i-1}$ かどうかを決めなくてはいけない. これも,$\mathrm{G}\mathrm{r}6\mathrm{b}\mathrm{n}\mathrm{e}\mathrm{r}$基底の基底変換の技法を用いて実行できる. block order $\{z\prec u_{1}\prec\cdots\prec u:-1, \prec u\dot{.}\}\prec\prec\{y_{1}, \cdots, y_{t}\}$ で簡約された Gr\"obner 基
底を求めればよ補題 13$\mathrm{A}.\mathrm{a}$た,$\mathrm{Q}$

基底 $GB$ 中に, 変数$Gr\overline{o}bner$$P_{j}(u_{j}, u_{j}-\mathrm{l}, \cdot.

上の. これ (火 3 と同様の議論より成り立つ次の補題による.

, u_{1} , z)$が存在する.

の最小多項式$\zeta_{q}$$g\mathit{0}$$u_{j},$

この$z$$\cdots,$ $u_{1},$$P_{j}$の $u_{\mathrm{J}}(j=1, \cdots,\dot{\iota})$ について

は $L_{j-1}=h_{J}’-\mathrm{l}(\zeta_{q})$ 上の

なのは且が

.

すなわち

$u_{1}$.

$\beta_{\mathrm{i}}$は\beta b . . . ,$u$($P_{1},$$g\mathit{0},$と$\zeta_{q}$P. ).
$\cdot$$\cdots,$: について線形なときに限る. もし($\beta:\perp 1$の最小多項式である. ま$\beta_{j}$が $GB$ 中に現れる. よって,

$L:\equiv \mathrm{Q}[u_{-1}.\cdot, \cdots, u_{1}, Z]/$

$L.\cdot=L_{i-1}$

monic な多項式

$P.\cdot$の多項式として表されている.

が$\beta_{i}$$u$: について線形だとすると,のべキ根表現は得られている訳である. したがって,|L, : $L:-1|=p.\cdot$ のときに限りさらなる (基底変換を用いた) 手続きが必要になる.

まとめると,.

方法 $4L:=L:-1$ かどうかまず決め, $L:=L:-1$ であればそのステップは終了, $|L.$ : $L:-1|=p$ であれば, 以下の手続きを実行する.

多項式環$\mathrm{Q}[y_{1},$成されるイデアル等しい. また,fl ,...

$u_{i}\prec v$$u.\cdot\}\prec\prec$

.

. で,

$\cdots,$$yt,$ $Z,$

$J\tilde{J}$$\cdots,$.

$u_{1}-\beta 1,$ $\cdots,$ $u|$$-\beta.\cdot,$$v-u(u|’ Z),$$f_{i},$$\cdots,$$f_{t},$

$g$

によって生

は $\mathrm{Q}[y_{1}, \cdots, y_{t}, z, u_{1}, \cdots, u\dot{.}, v]$ の極大イデアルであり, その剰余環は$f_{1,g},$ $u_{1}-\beta_{1},$$Gr\overline{o}bner$$\{y_{1}, \cdots, yt\}$$\cdots,u1$ の$u_{1.:,v},$$u.\cdot-\beta.\cdot,$$\cdot\cdot,$$,$$I^{\mathrm{t}_{\mathrm{t}f}’}$に$v-u(ui, z)$ は辞書式順序 $y_{1}\prec\cdots\prec y_{t}\prec z\prec u_{1}\prec$

基底を作っている. このとき, ) 序を block order $\{\mathrm{t}z, u_{1}, \cdots, u:-1, v\}\prec$$\mathfrak{l}|$, に変えることで (基底変換), $u:\text{のベ}*$ 根表現が,して得られる.

注意 2 もちろん, 円分体の決め方は他にいくつか考えられる.

$u_{1},$$\cdots,$$u:-1,$ $v,$

$Z$

の多項式と

20

強ベキ根表現を与える他の方法としては, 各ステップで部分体に必要な原始元を添加する方法があ
る.

すなわち,

のステップで$L\mathrm{o}=R’\mathit{0}(\zeta_{p}1),$$L_{1-}\iota$

上の$\beta$.

$\cdots,$$L$.

$=L_{1-1}(\beta., \zeta_{p\mathfrak{i}+}\mathrm{l})$の最小多項式と$L_{i-1}(\beta_{i})$また, 強ベキ根表現を与えるとは限らないが, 各根の最小多項式, あるいは,$\mathrm{A}’(\beta|-\iota)$

上の 1 の原始上のとするのである. この方法では, 各$i$の最小多項式を求める必要がある.

$\zeta_{p}.\cdot$

番目のステップにおいて $Ii’$ 上の 1 の原始$i$.

$P\cdot$

番目$p_{\mathrm{t}}$乗乗根の最小多項式を用いても同様の方法が考えられる. これらは疑強ベキ根表現 (nearly strong radical representation) とでもいえる ([4/ 参照).

2.6 実験
実際に富士通情報研で開発中の$\mathrm{R}\mathrm{i}\mathrm{s}\mathrm{a}/\mathrm{A}\mathrm{s}\mathrm{i}\mathrm{r}[15]$にインプリメントしいくつかの例について計算した結果を示す. 計算時間のデータは秒で与えられている. 計算機は RISC NEWS (R4000$50\mathrm{M}\mathrm{h}\mathrm{z}$) を使用した. 例として以下の 10 個の可解な多項式を用いる. これらは,(4’) 以外は [3] において用いた多項式と同じものである. 以下の表で “ total ” は各拡大に対して結果を得るのに要する時間とその他必要な計算 (例えば $g(z)$ の構成など) に要する時間の合計である.
$(4’\rangle$$x^{5}-5x^{3}+5x-5$(10)$x+x\epsilon s+7$(11)$x^{6}-3x^{4}+1$(12)$x^{6}+x^{4}-9$(15)$x^{6}+x^{4}-8$(17)$x^{6}+x^{4}-x^{2}+\mathrm{s}_{x-}5$(19)$x^{7}+x^{6}-12x^{5}-7x^{4}+28x+134x^{2}-9x+1$(24)$x^{7}+7x^{s_{+x}}\tau+7x-21$(25)$x^{7}-14x^{5}+56x^{3}-56x+22$(26)$x^{7}-2$部分体を構成するのに要した時間を表 1 に示す. 表は左から, 群の位数各拡大の拡大次数逐次原始元を用いた場合 (方法 1) に要した時間, 絶対的原始元を用いた場合に要した時間を表す.

各原始元のべキ根表示を構成するのに要した時間を表 2 に示す. 表は左から, 逐次原始元を用いた
場合 (注意 2 の四強ベキ根表現を用いた) に要した時間, 絶対的原始元を用いた場合 (注意 2 の擬強ベ

キ根表現を用いた) に要した時間, 逐次原始元を用いた強ベキ根表現 (方法 4) に要した時間を表す.
ここで, “–,, は 1 時間で結果が得られなかったことを示す.

$”*$ ”

は, 体の列$L.\cdot$の contraction が起こっていることを示す. すなわち,Li-l $=L:$ . また,“ ” のついたステップでは contractible root が存$\triangleright$

在することを示す. (contractible case については [3] 参照) このとき, 前のステップで根のべキ根表

示は得られているので実はこの先は計算する必要はない.

21

表 2. ベキ根表現

表 1. 部分体$\mathrm{o}\mathrm{r}\mathrm{d}.$$\mathrm{o}\mathrm{r}\mathrm{d}.$$\mathrm{a}\mathrm{b}\mathrm{s}.$$\mathrm{d}\mathrm{e}\mathrm{g}.$$\mathrm{s}\mathrm{u}\mathrm{c}.$$\mathrm{a}\mathrm{b}\mathrm{s}.$$\mathrm{d}\mathrm{e}\mathrm{g}.$$\mathrm{s}\mathrm{u}\mathrm{c}.$strong$\ovalbox{\tt\small REJECT}_{30}^{()9}\mathrm{t}\mathrm{o}\mathrm{t}\mathrm{a}111182030_{23047}072911100330158$$\ovalbox{\tt\small REJECT}_{\mathrm{t}_{0}\mathrm{t}\mathrm{a}}^{3}(11)18168318*2060112025815329234781215417501273$$\ovalbox{\tt\small REJECT}_{20}^{(12)8}243012200112025111001402454$$\ovalbox{\tt\small REJECT}_{20}^{(12)3}2420_{11}2\mathrm{o}\mathrm{o}6201012\mathrm{o}\mathrm{o}28\triangleright 120_{7\triangleright 02}410440420289$$\ovalbox{\tt\small REJECT}_{\mathrm{t}\circ \mathrm{t}\mathrm{a}10}^{20}5211152174$$\ovalbox{\tt\small REJECT}_{1}\mathrm{t}\circ\iota \mathrm{a}]20_{032}2019265057\triangleright 029$$\ovalbox{\tt\small REJECT}_{2}(15)36164164$$\ovalbox{\tt\small
REJECT}_{0050}(15)36223029$
$36$
(15)

$2323$$|$$0..570.17011.648$

$|$

$|$

$\ovalbox{\tt\small REJECT}_{\iota_{0}\mathrm{t}}^{30}\mathrm{a}125618384130$$\ovalbox{\tt\small REJECT}_{\iota\circ\iota}^{31592}\mathrm{a}12436246\triangleright 04645107$$\ovalbox{\tt\small REJECT}_{2}(17)48151156$$\ovalbox{\tt\small
REJECT}_{(17})482017052053$
$48$
(17)

$32222$$|$$0_{19}0^{\cdot}.\cdot.2001.5241951$

$|$

$|$

$\ovalbox{\tt\small REJECT}_{2}^{20_{38}}\mathrm{t}\circ \mathrm{t}\mathrm{a}]2423117184$$\ovalbox{\tt\small REJECT}_{\mathrm{t}\circ \mathrm{t}\mathrm{a}1147}^{20}35364677\triangleright 1634903$$\ovalbox{\tt\small REJECT}_{32}^{(1}\mathrm{t}\mathrm{o}\mathrm{t}9)\mathrm{a}1115172251132211\iota 2432875244796681932555671349845322714657820$$\ovalbox{\tt\small REJECT}_{3}^{(19)3}\mathrm{t}\mathrm{o}\mathrm{t}\mathrm{r}41572205222319\iota 058\iota 28541-895520-7030_{84}/\triangleright 209666710803422150\overline{\prime}319409$

次に,10 個の多項式に対する時間データを表 3 に挙げておく. ただし, 部分体の計算は逐次原始元を用いた方法 1 を, ベキ根表現については, 逐次原始元を用いた場合 (注意 2 の腰強ベキ根表現を用いた) の方法を使った. これらの計算中で必要とされる Gr\"obner 基底の計算は辞書式順序で実行したが,

表3で$‘{}^{\mathrm{t}}\circ$”}X\S 5.2 で述べた block ordering を用いることで高速化を図れた.

22

表3$\mathrm{o}r\mathrm{d}.$$\mathrm{d}\mathrm{e}\mathrm{g}.$$\mathrm{s}\mathrm{u}$bfieIdradical$\mathrm{o}\mathrm{r}\mathrm{d}.$$\mathrm{d}\mathrm{e}\mathrm{g}.$$\mathrm{s}\mathrm{u}$bfieldradical$\ovalbox{\tt\small REJECT}_{\iota \mathrm{o}\mathrm{t}186}^{2}(4’)2022151\mathrm{a}544802044785269443030$$\ovalbox{\tt\small REJECT}_{2}^{(1}\iota\circ \mathrm{t}7)482151\mathrm{a}|23202024\mathrm{o}_{3}\mathrm{o}2190185027902001031447557$$\ovalbox{\tt\small REJECT}_{\iota_{\mathrm{O}}\iota}^{20}(10)\iota 2300_{7010}4\mathrm{a}12\mathrm{o}\mathrm{o}200600080041\mathrm{o}9$$\ovalbox{\tt\small REJECT}_{\iota\circ \mathrm{t}\mathrm{a}13}^{25}(19)721160_{8}521232312211\iota 514783852179260418815415813250$$\ovalbox{\tt\small REJECT}_{3}^{(1)}\mathrm{t}\circ \mathrm{t}\mathrm{a}\iota|01832020\iota_{9}0_{71}291320652369480$$\ovalbox{\tt\small REJECT}^{(24}\mathrm{t}\circ \mathrm{t}\mathrm{a}[723)1420670534192387238654\iota\iota 3$$\ovalbox{\tt\small REJECT}^{2}\mathrm{t}\circ \mathrm{t}\mathrm{a}|\mathrm{o}12052(12)24301806020\iota 1\mathrm{o}102\mathrm{o}_{20}\mathrm{o}1\mathrm{o}103\iota 21$$\ovalbox{\tt\small REJECT}_{\mathrm{t}\circ \mathrm{t}}(15)3620317065\mathrm{a}|21230_{5}065181400_{3}6702405916$$\ovalbox{\tt\small REJECT}_{\mathrm{t}_{\mathrm{o}\mathrm{t}[203}}^{()2}26\mathrm{a}423075220705751333033724964$

計算結果の例 (11) $x^{6}-3x^{4}+1$ を例にとる. 各ステップについてりスト [$\beta_{i},$$K_{1-1}$上の$\mathrm{A}’$

.

の原始元

り当てられている. 分解体$\beta:$$K_{f}$] が得られ 6. 変数
は 2 根 $a,$$f_{1}=a^{6}+a^{3}+7,$ $f_{2}=b^{3}+a^{3}+1$[405] series$<\mathrm{E}_{\mathrm{X}}\iota \mathrm{e}\mathrm{n}\mathrm{S}\mathrm{i}\mathrm{o}\mathrm{n}$[-v$\mathrm{p}\mathrm{e}$suct$\mathrm{G}\mathrm{S},\mathrm{T}\mathrm{p},\mathrm{R}\mathrm{S}$$b$$u_{-1}.,$ $v$

かゞ$\beta_{1},$$\cdots,$

添加で得られる $K_{f}=\mathrm{Q}(a, b)$ .

.

,PPP);

Step,l $>$$-3- 21^{*}\mathrm{v}^{-}2+609*\mathrm{v}+6461,- 6*\mathrm{b}*\mathrm{a}.2- 6*\mathrm{b}.2^{*}\mathrm{a}-7$$0.19\sec$$u_{1},$ $\cdots,$]$I\zeta_{-1}.$の逐次最小多項式$\beta:-\iota,$

$a$

と

$b$

$\beta$.

にそれぞれ割の定義多項式は

23

Step,2$<\mathrm{E}\mathrm{x}\mathrm{t}\mathrm{e}\mathrm{n}\mathrm{S}\mathrm{i}\mathrm{o}\mathrm{n}$$>$$[2*_{\mathrm{V}^{-}2- 2}*\mathrm{u}\iota’\mathrm{v}-13*1\mathrm{u}2- 1\epsilon 2*1\mathrm{u}+96Q3,-9*3+6^{*}\mathrm{b}*\mathrm{a}2-\iota 2^{*}\mathrm{b}2^{*}\mathrm{a}-8]\mathrm{a}$0. $23\sec$$<\mathrm{E}\mathrm{x}\mathrm{t}\mathrm{e}\mathrm{n}\mathrm{S}\mathrm{i}_{0}\mathrm{n}$[-vStep,3 $>$$3+\mathrm{u}2,- \mathrm{a}+2^{*}\mathrm{b}$]0. $29\sec$

gc :$710\mathrm{m}\sec+$$170\mathrm{m}\sec$

方法 4 によって得られた強ベキ根表現については結果だけ示す. ここで,q は 3 であり,g(z;.

$z- \frac{1}{3}a^{3}+\frac{1}{3}$$L_{1}(=K_{1}(\zeta_{3}))$

$a,$

$b$

)

$=$

は $L_{2}(=K_{2}((3))$ と –致する. よって, 第 2 ステップでは Lagrange 分解式を計算する必要はなく所要の結果はここで得られる.
$u_{1}$$=$$- \frac{1}{126}v^{2}1z-\frac{1}{378}v_{1}^{2}+\frac{1}{3}v_{1}-7$$u_{2}$$=$$( \frac{1}{9}u_{1}^{2}+\frac{11}{9}u_{1}-\frac{719}{9})z+\frac{1}{18}u_{1}^{2}+\frac{10}{9}u_{1}-\frac{719}{18}$$u_{3}$$=$

1$\overline{3}v_{3}$$v_{1}$$=$$\sqrt[3]{122472Z+81648}$$v_{3}$$=$$\sqrt[3]{(3u_{1}^{2}+33u1-2157)z+\frac{3}{2}u_{1}^{2}+3\mathrm{o}u_{1}-\frac{2157}{2}}$

$a$

$=$

$b$

$=$

.
$-(7u_{1}^{2}\underline{1}-2110u_{1}-22529)vsz+(44u_{1}^{2}-326u_{1}-38116)v_{3}$271674$\frac{1}{543348}(7u_{1}^{2}-2110u_{1}-22529)v3z+(44u_{1}^{2}-326u_{1}+52442)v_{3}$

参考文献[1] 穴井宏和, 横山和弘. (1992) 多項式の可解性の判定-

多項式の可解性とその可解性判定アルゴリズムーワークショツ

プ「数式処理」会議録 (於日本大学) 84-99.

[2] 穴井宏和, 横山和弘. (1993) ベキ根による方程式の解の構成 $-1$ の原始$n$乗根の構成-ISIS Research Report

93-5J.
$[3]\mathrm{A}\mathrm{n}\mathrm{a}\mathrm{i}$, H., Noro M., Yokoyama K. (1994). Computation of the splitting fields and the Galois groups ofpolynomials. presented at MEGA ’94 (also submitted to the proceedings).
$[4]\mathrm{A}\mathrm{n}\mathrm{a}\mathrm{i}$, H.,

Yokoyama K. (1994). Radical Representation of Polynomial Roots. ISIS Research Report94-13E.
$[5]\mathrm{A}\mathrm{t}\mathrm{k}\mathrm{i}\mathrm{n}\mathrm{S}\mathrm{o}\mathrm{n}$, M. D. (1975). An Algorithm for Finding the Blocks of a Permutation Group. Math. Comp.

29, 911-913.
$[6]\mathrm{B}\mathrm{e}\mathrm{c}\mathrm{k}\mathrm{e}\mathrm{r}$, T., Weispfenning, V. (1993). Gr\"obner Bases. Springer-Verlag, GTM 141.

24$[7]\mathrm{B}\mathrm{u}\mathrm{c}\mathrm{h}\mathrm{b}\mathrm{e}\Gamma \mathrm{g}\mathrm{e}\mathrm{r}$, B. (1985). Gr\"obner bases: an algo

$7\dot{\tau}thmiC$

method in polynomial ideal theory, Multidimen-

sional System Theory, Reidel Publ. Comp., pp. 184-232.
$[8]\mathrm{B}\mathrm{u}\mathrm{t}\mathrm{l}\mathrm{e}\mathrm{r}$, G. (1991). Fundamental Algo

$7\dot{\mathrm{t}}thms$

for Permutation Groups. Lect. Notes in Comp. Sc., 559,

Springer-Verlag.
$[9]\mathrm{D}\mathrm{i}\mathrm{x}\mathrm{o}\mathrm{n}$, J. (1990). Computing subfields in algebraic number fields. J. Austral. Math. Soc. (Series$A$)49, 434-448.
$\mathrm{D}.\mathrm{J}.,$$[10]\mathrm{F}\mathrm{o}\mathrm{r}\mathrm{d},$$\mathrm{M}\mathrm{c}\mathrm{K}\mathrm{a}\mathrm{y}$, J. (1989). Computation of Galois groups from polynomials over the rationals,

Computer Algebra, Lect. Notes in Pure Appl. Math., 113, pp. 145-150.
$[11]\mathrm{F}\mathrm{u}\mathrm{r}\mathrm{S}\mathrm{t}$, M., Hopcroft, J., Luks, E. (1980), Polynomial-Time Algorithm for Permutation Groups. Proc.

Twenty-first Annu. IEEE Sympos. Found. Comput. Sci. 1980, pp. 36-41.
$[12]\mathrm{K}_{0}|\mathrm{e}\mathrm{S}\mathrm{o}\mathrm{V}\mathrm{a}$, G.,$\mathrm{M}\mathrm{c}\mathrm{K}\mathrm{a}\mathrm{y}$, J. (1984). Practical strategies for computing Galois groups, Computational

Group Theory, Academic Press, pp. 297-299.
$[13]\mathrm{L}\mathrm{a}\mathrm{n}\mathrm{d}\mathrm{a}\mathrm{u}$, S.,$\mathrm{M}$iller, G. L. (1985). Solvability by radicals is in polynomial time. J. Comput. System Sci.

30, 179-208.
$[14]\mathrm{L}\mathrm{a}\mathrm{n}\mathrm{g}$, S. (1965). Algebra. Addison-Wesley.

$[15]\mathrm{N}\mathrm{o}\mathrm{r}\mathrm{o}$, M., Takeshima, T. (1992).

$\mathrm{R}\mathrm{i}\mathrm{s}\mathrm{a}/\mathrm{A}\mathrm{s}\mathrm{i}_{\Gamma-}$a computer algebra system. Proceedings of Intemational

Symposium on Symbolic and Algebraic Computation 1992. New York: ACM Press, pp. 387-396.
$[16]\mathrm{S}\mathrm{i}\mathrm{m}\mathrm{s}$, C. C. (1970). Computational methods in the study

or permutation grou ps. Compv tational Prob-

lems in A bstract Algebra, Pergamon, Elmsford, pp. 169-183.
$[17]\mathrm{S}\mathrm{o}\mathrm{i}_{\mathrm{C}}\mathrm{h}\mathrm{e}\mathrm{r}$, L. H. (1984).

An algorithm for computing Galois groups. Computational Group Theory,

Academic Press, pp. 291-296.
$[18]\mathrm{a}\mathrm{n}$der Waerden, B. L. (1991). Algebra I.

$[19]\mathrm{Y}\mathrm{o}\mathrm{k}\mathrm{o}\mathrm{y}\mathrm{a}\mathrm{m}\mathrm{a}$$\mathrm{S}\mathrm{p}\mathrm{r}\mathrm{i}\mathrm{n}\mathrm{g}\mathrm{e}\mathrm{r}-\mathrm{v}_{\mathrm{e}\Gamma}|\mathrm{a}\mathrm{g}$.

, K., Noro, M., Takeshima, T. (1989). Computing Primitive Elements of Extension Fields.

J. $Sym$ . Comp. 8, 553-380.