数理解析研究所講究録920 巻 1995 年 1-8

11.
逐次代数拡大体上での 1 変数多項式の

GCD について

富士通情報研野呂正行

1.1 はじめに有理数凧上の単拡大上での 1 変数多項式の GCD をモジュラ計算法は, [$7|$により与えられ, [8] により改良された. しかし, 逐次拡大の形で与えられた係数体上での 1 変数多項式の GCD 計算を行なう

ために逐次拡大を単拡大に変換することは, 定義多項式の次数, 係数の増大を招き, 結果として, GCD

計算に多大な時間, 空間を必要とすることになる. 本稿では, 逐次拡大のまま, GCD のモジュラ計算を行なう方法を述べる.

(発表後, [6] で既に同様のアルゴリズムが発表されていることが判明した. [6] では, 漸近計算量を良くする目的で, [2] による dynamic evaluation を用いたアルゴリズムを提案しているが, 基本とす
る, 判別式に関する性質は我々と同じものを用いていて, しかも, その性質は, 田により既に得られていることも判明した. )1.2 判別式$I_{1_{0}}’=Q,$$\alpha.\cdot(i=1, \cdots, n)$$Q[\alpha:, \cdots, \alpha_{1}]$である.

$I\mathrm{i}_{n}^{r}$を,$I\mathrm{i}’.-1$の整数環を上代数的とし, A’i $=I\iota’|-1(\alpha_{i})$ とする.
$R_{n}$$\mathrm{A}’,$とし, $K=K_{n},$ $R=R_{n}$ とする.

有限次代数拡大 $K/F$ に対し, $\beta\in K$ の $K/F$ に関するノルムを $N_{K/F}(\beta)$ と書く.
$I\mathrm{i}^{r}/Q$

を $m$ 次拡大とするとき$?n$個の共役写像$\sigma_{l}$による $\alpha\in F$ の像を$\alpha^{(l)}$と書く.

$=I\iota^{r}i-1[\alpha|]=$2$\{\beta_{1}, \cdots, \beta_{m}\}\subset K$に対し,$D(\beta_{1}, \cdots, \beta_{m})=$と定義する.
$\alpha_{i}$の瓦_1 上のモニックな最小多項式を$m_{i}(x)\in Q[\alpha_{\mathfrak{i}-1}, \cdots.

’\alpha_{1}][x]$とする.

このとき, $m_{i}(x)$ において, $x\mapsto t;,$ $\alpha_{j}rightarrow t_{j}(j=1, \cdots, i-1)$ という置き換えを行ったものを$M_{i}(t., \cdots, t_{1})$と書けば,$K_{i}=Q[t_{i}, \cdots, t_{1}]/I_{\iota}$$(I|=Ideal(M_{i}(ti, \cdots, t_{1}), \cdot\cdot, , M_{1}(t_{1})))$

以下では, $M$.

$\in Z[t_{i}, \cdots, t_{1}]$.

なる場合を考える. このとき,l\iota i$(x)\in Z[\alpha_{\iota-}\downarrow,$$\cdots,$$\alpha_{1}$) $[x]$ で, モニックな多項式となる.
命題$1\alpha$

Proof
よって

.

は代数的整数.

.

$\alpha\iota,$$\alpha$$\cdots,$ $\alpha.-1$

が代数的整数ならば, $m_{i}(x)$ の各係数はの元だから代数的整数.

は, 代数的整数を係数とするモニック多項式の根となり, 代数的整数 口

命題 $2e_{i}=deg(m.(x)),$$\frac{1}{D}Z[\alpha_{n1}, \cdots, \alpha]$

Proof$Z[\alpha_{\mathrm{i}-1}, \cdot\cdot, , \alpha_{1}]$$D= \prod_{\mathrm{i}=\downarrow}^{n}N_{\mathrm{A}_{\iota-1/}}\cdot \mathrm{Q}(d_{\mathrm{i}})^{\prod_{j=+}^{\mathrm{n}}e_{j}}\mathrm{t}1$$d_{2}=disc_{\backslash _{\mathfrak{i}}/\downarrow}’\prime K_{\iota-}(\alpha_{\mathrm{i}}),$とおけば$R\subset$.

$G= \{\prod_{j=1}^{\mathfrak{n}}\alpha_{j}^{n_{j}}|0\leq n_{j}<e_{j}\}\subset R$

当に整列したベクトルを$(\gamma_{1}, \cdots, \gamma_{m})$は $K/Q$ の $Q$ ベクトル空間としての基底より、 ’ を適
$C,$

とすると,

$\theta\in R$

は, 適当な$c_{\mathrm{J}}\in Q$

により $\theta=\sum_{J}(:,$$\gamma$

, と書

ける.

これより,
$\theta^{(1)}=\sum_{j}c_{j}\gamma_{j}^{(1})$$\theta^{(m)}=\sum_{j}c_{j}\gamma_{j}^{(\iota)}\eta$

これを,$(c_{1}, \cdots , c_{m})$に関する方程式と見て解くと,$c_{\mathrm{J}}=\triangle_{\mathrm{J}}/\triangle=\triangle\triangle_{\mathrm{J}}/\triangle^{2}$.

ここで,$\triangle_{j}=det(D(\gamma 1, \cdots, \gamma j-1, \theta, \gamma_{\mathrm{J}}+1, \cdots, \gamma m))$$\triangle=det(D(\gamma \mathrm{l}, \cdots, \gamma_{m}))$

一般に\beta 1, . . ,$\cdot$つ$\triangle,$$\triangle_{j}$$\beta_{m}\in R$,.

ならば, $d_{e}t(D(\beta_{1}, \cdots, \beta_{m}))^{2}\in Z$ より

は代数的整数だから,$\{\prod_{j=1}^{n-}1\alpha_{j}^{n_{\mathrm{j}}}|0\leq n_{j}<e_{j}\}\subset R$$\triangle\triangle_{j}\in Z$. よって,$Cj\in\overline{\Delta}^{\mathrm{V}}1$

Z.

$\triangle^{2}\in Z.$$\theta$を適当に整列したものを改めて大次数) とする. 見やすくするため,$\alpha_{\mathfrak{n}}$$\triangle=det(D(\Gamma, \alpha\Gamma, \alpha\Gamma 2, \cdots,\mathrm{G}\alpha-1\Gamma))$を$\alpha,$, を$e_{\iota}$$e,$$I\mathrm{i}’,\iota-1$

よって,は任意だから$\triangle\triangle_{J}=\triangle^{\gamma}\sim c,$$\in Q$か,.

$R\subset-\triangle^{\mathrm{T}}Z1|\alpha_{\iota)},\cdots$$\Gamma=(\gamma_{1}, \cdots, \gamma l)(\mathit{1}$$\alpha\iota|$

ま $I_{1}’n-1/Q$ の拡

を $F,$ $?n,‘(x)$ を,l\sim (x) と書く.

3$\sigma$$K$を$I\acute{\backslash }/Q$の共役写像とすれば,$\sigma|F$

は $F/Q$ の共役写像より, その個数は嫁固. そのそれぞれに対し,への拡張力\sim 個ずつある.

$\sigma(\Gamma)=\Gamma^{(t)}$

とすれば,

なる

$e$

個の

$\sigma$による$\{\alpha_{\ell s}|(S=1, \cdots, e.)\}$$\alpha$の像を $\alpha_{ts}(s=1, \cdots, e)$ とする.

は $m^{(t)}(x)= \sum_{i}$ ci$(\Gamma^{(t)})x^{\mathfrak{i}}$この時, 7’$l(. \mathrm{f})=\sum_{\iota}c_{\ell}(\Gamma).\iota^{[]}$の根全体となる.

$D(\Gamma, \alpha\Gamma, \alpha^{2}\Gamma, \cdots, \alpha-1\Gamma \mathrm{e})=$

ただし,$G_{k}=$$\triangle$を計算する際各$G_{k}$

に対し,$\Gamma^{(k)}$を係数と見なして, vandermonde 行列に対するのと同様な掃き出しを行なうことができる. すなわち行に対する基本変形により,$G_{k}$

は次の行列$\delta_{k}H_{k}$に変形できる.

ただし,$H_{k}=$$\delta_{k}=$よって,$H_{1}$$H_{2}$$\triangle=\prod_{k}\delta_{k}$.

$=$士 $\prod_{k}\delta_{k}det(D(\Gamma))^{\epsilon}$$H_{l}$

既に述べたことより, $\{\alpha_{k\epsilon}|(S=1, \cdots, e)\}\}$ ま $?n^{(k)}(x)$ の根全体だから,.

$\sim$

4$\delta_{k}^{2}$$=$$di_{Sc_{K/F}}m((k)X)$$=$$\gamma eSultant_{x}(m^{\langle k)}(x), \frac{d}{dx}?)\tau(k)(x))$$=$$(di_{SC_{\mathit{1}}}F^{?}?\iota(\backslash \cdot/x))\mathrm{t}k)$よって,$\triangle^{2}=N_{F/\mathrm{O}}(diSc\kappa/Fm(X))det(D(\Gamma))^{2}$”よって帰納法により$\triangle^{2}=\prod_{=1}^{n}.\cdot N_{I\backslash /Q}.(:-1\kappa di_{S}c/i\kappa.\cdot-1^{\cdot}(_{X)}m.)=\prod_{j}^{n}i+1\epsilon_{j}$補題

口$3[S\mathit{1}$$a\in Z,$$f \in\frac{1}{a}R[x],$$f=gh,$ $f,$ $g,$系4$f \in\frac{1}{a}Z[\alpha_{n}, \cdots, \alpha_{1}][x|,$系5$f_{1} \in\frac{1}{a}Z[\alpha_{\mathfrak{n})}, \cdots\alpha 1][X],$$h$$a\in Z,$

: モニックならば,$f=gh,$ $f,$ $g,$$h$$g,$ $h \in\frac{1}{a}R[x]$.

: モニックならば,$f_{2} \in\frac{1}{b}Z[\alpha_{\mathfrak{n}}, \cdots, \alpha_{1}][_{X]},$

$a,$

$g,$

$\mathit{1}\iota\in\frac{\mathrm{l}}{aO}Z[c\mathrm{y}_{\mathrm{t}},,$$b\in Z,$ $g=GCD(f_{1}, f_{2}),$$f_{1},$$\cdots,$$f’\underline{)},$$.(/$$\mathrm{C})_{\downarrow}|[x|$

.

: モニツ

クならば,
$g \in\frac{1}{GCD(ab)1D}Z[\alpha_{n}, \cdots, \alpha_{1}][x]$.

1.3 モジュ 計算$\text{フ}-$補題$6\alpha$

.

の

$Q$

上の最小多項式を $h(x)$ とすれば,$N_{F_{\backslash }’/Q}i(x-\alpha_{i})$は $f\iota(x)$ の羅となる.

Proof 既約多項式のノルムが, 既約多項式の幕になることからわかる.

口

を素数とする.

$P\in Z$

$S=Z[tn’\cdots, t_{1}]$ ,$\overline{S}=z_{p}\iota t_{n},$

$S$

から

$\overline{S}$$\cdot$. . , ],
$t_{1}$

への標準的射影による $f$ の像を$\overline{f}$と書く.

$I_{Q}=Ideal(M_{n}(t_{\mathfrak{n}}, \cdots, t_{1}), \cdots, M_{1}(t_{1}))\subset Q1^{t_{n},\cdots,t_{1}}]$$I=Idea\iota(M\hslash(t_{\mathfrak{n}}, \cdots, t_{1}), \cdots, M_{1}(t_{1}))\subset S$,,$\overline{I}=Idea\iota(\overline{M}n(t_{n}, \cdots, t_{1}), \cdots,\overline{M}_{1}(t_{1}))\subset\overline{S}$$\phi$:$\overline{S}[x]arrow(\overline{S}/\overline{I})[X]$

とおく.

補題

$7\alpha$

.

の $Q$

(標準的射影)上の最小多項式を $h.(x)\in Z[x]$ とすれば, $h_{1}(t.)\in I$ .

Proof $h:(\alpha_{i})=0$ で,$I$

は極大イデアルだから$h_{i}(t_{i})\in I_{\mathrm{Q}}$

順序に関するグレブナ基底となっていて, $h.(t.)$ の$0$.

$M_{1}$

よ$I_{\mathrm{Q}}$の, $t_{n}>\cdots>t_{\iota}$ なる辞書式への正規化を考えれば,$M_{i}$の頭項が 1 で, 整数5係数であることより正規化に現れる係数は全て整数. よって $h_{i}(t.)\in I.$ 口
命題 $8p\parallel disC(h.\cdot(x))(i=1, \cdots, n)$ ならば,

Proof $h.(t.)\in I$ より$\overline{h}_{i}$

なちの 1 変数多項式が$\overline{I}$$(t_{i})\in I.$

は極大イデアルの交わり。特に$\overline{I}$$di_{SC}(\overline{h}|(x))=disc(h.(x))$の中に存在する.

$\overline{I}$は$\overline{I}$ま.

$\tau\cdot \mathit{0}.di_{C}al$

mod $p\neq 0$ より, 各ち に対し, 無平方次元だから, Seidenberg の補題 92 [4] により$0$$\overline{I}$は極大イデアルの交わりとなる. 口
補題
る.

$9\overline{I}=\cap J_{k}$(は相異る極大イデア)) とし,$J_{k}$

この時次の性質を満たすが$g$$\overline{S}/\overline{I}$かつ $lc(fi),$ $lc(f_{2})$ は単元とす$f_{1},$ $f_{2}\in(\overline{S}/\overline{I})[x]$の単元倍を除いて–意的に存在する.

この $g$ を$GC’ D(fi, f_{\sim}\gamma)$と定義する.
(1) $g|f_{1},$$g|f_{2}$(2) $h|fi,$$h|f_{2}$ならば $h|g$

Proof $j\neq k$ ならば $J_{j}+J_{k}=\overline{S}$ より, 中国剰余定理により$(\overline{S}/\overline{I})[_{X}1\simeq\oplus_{k(\overline{S}}/J_{k})[_{X}1$$\psi_{k}$::$\psi$$\overline{S}/\overline{I}\simeq\oplus_{k}\overline{S}/J_{k}$

.

よって,

$\psi’$:.
を標準的射影とする.

$(\overline{S}/\overline{I})[x]arrow(\overline{S}/J_{k})[x]$$f\cdot\in(\overline{S}/\overline{I})[.\iota\cdot|$に$t,\mathrm{J}\text{し},$$f\cdot=()\Leftrightarrow\forall \mathrm{A}\iota\cdot((f)=$

$()$

が成

り立つ.

は単元より, $\psi_{k}(fi),$ $\psi_{k}(f_{2})\neq 0$ . よって,

$lc(fi),$ $lc(f2)$における $fi,$のモニックな GCD が–意的に存在する. それを$f_{2}$と定義する. この時(1) :$g|fi$(2) :$g|f_{2}$は体上の多項式環より,$g_{k}$

とおき, $g=\psi^{-1}(g_{1},$$(\overline{S}/J\wedge\cdot)[.\cdot\iota\cdot]$$\cdots,$$g(\cdot, \cdots)$が (1), (2) を満たすことを示す.

$g$$\exists h_{k}.\in(\overline{S}/J_{k})[x]$. 同様に$(\overline{S}/J_{k})[x1$$\mathrm{s}.\mathrm{t}$.

$\psi_{k}(fi)=\psi_{k}(\mathit{9})hk\cdot h=\psi^{-1}(h_{1}, \cdots, f\iota_{k}, \cdots)$

とすれば,

, より

$fi=\prime c\mathit{1}$.

$\psi_{k}(h)|\psi_{k()}g$が$(\overline{S}/J_{k})[x]$における GCD の存在と $-$ 意性によりいえるから, (1) と司様に /1 I

となる.

意性 :

よって,

$g_{1}$が (1) を満たすとすると, $g|g_{1}$ かつ $g_{1}|g$ .

$\exists c_{k}\in\overline{S}/J_{k}\backslash \{0\}$$\mathrm{s}.\mathrm{t}$.

$\psi_{k}(g_{1})=c_{k}\psi_{(}\mathit{9})$これより$\psi_{k}(g)|\psi_{k}(g1)$かつ娠 $(g_{1})|\psi_{k}(g)$ .

. よって, $c=\psi^{-1}(C_{1}, \cdots, C_{k}, \cdots)$ とおけば,$c$は$\overline{S}/\overline{I}$の単元で, $g_{1}=cg$ . 口$fi \in\frac{1}{a}Z1\alpha_{n},$$\cdots,$$f_{2} \in\frac{1}{b}Z[\alpha_{n}, \cdots, \alpha_{1}][x],$$\alpha_{1}1[X],$$a,$$b\in Z,$

$g=cCD(fi, f_{2}),$ $fi,$$f_{2},$ $g$: モニックとする.
$f1=gh_{1}$なる$h_{1}$

をとれば, $g,$

これより

$h_{1} \in\frac{1}{aD}Z[\alpha n’\cdots, \alpha 1][x1\cdot$$F_{1}=(aD)^{2}fi,$ $G_{1}=aDg,$ $H_{1}=aDh_{1}$とおけば,$F_{1},$$G_{1},$ $H_{1}\in Z[\alpha_{n} , \cdots, \alpha_{1}][x|$で, fi $=G{}_{1}H_{1}$ .

この等式を $Q[t_{n}, \cdots , t_{1}][x]$ 上で見れば, 両辺が IlloclIQ で等しいことを意味するが, ||. 規化操作を考えれば$\mathrm{m}\mathrm{o}\mathrm{d} I$

で等しいことがわかる. よって,$\phi(\overline{F}_{1})=\phi(\overline{c}_{1})\emptyset(\overline{H}_{1})$.

同様に, $F_{2}=(bD)^{2}f_{2},$ $G_{2}=bDg,$ $H_{2}=bDf_{l_{2}}$ とおけば,$\emptyset(\overline{F}_{2})=\phi(\overline{c}_{2})\emptyset(\overline{H}_{2})$仮定 10 素数補題 11 素数

$P$

$P$

が,

$p\parallel a,$$F_{2},$$G_{2},$ $H_{2}\in Z[\circ_{1},, \cdots, O\downarrow][.\iota\cdot]$.
$p\parallel b,$$p\parallel diSc(h_{i(}x))(i=1, \cdots, n)$が, $P\chi_{d}i_{S}c(h:(X))(i=1, \cdots, n)$ ならばを満たす.

$p\parallel D$

で,6

Proof $D$より$\alpha_{i}$.

は\alpha i の共役の差の重複度付きの積である.

$=N_{K},-1/Q(disc\kappa_{i}/\kappa:-1(\alpha_{\mathfrak{i}}))$の共役は全て $h_{:}(x)$ の根. $di_{SC}(h_{i(x}))$ は,$\alpha_{1}$の共役すべての差積の 2 乗だから, 自然数

在して, 代数的整数として $D_{i}|diSc(h_{i}(X))E$ . 両辺は有理整数だから, 有理整数としてよって $D$ の素因子はいずれかの $di_{S}c(h.(x))$ の素因子となる.

この補題により,$P$が仮定 10 を満たせば, $D$ が補題 $12p$ が仮定 10 を満たす時, go

は $/1_{1}(x)$ の根$\mathrm{o}j$$\mathrm{m}\mathrm{o}\mathrm{d} p$

$E$

が存

$D_{\mathrm{i}}|di_{SC}.(h_{i}(x))^{b}$.

口で単元であることがいえる.

が存在して$=GCD(\phi(\overline{F}_{1}), \phi(\overline{F}_{2}))$かつ$\emptyset(\overline{G}_{1})|g\mathit{0}$$deg(g_{0})\geq$$deg(g)$ .

Proof
より

の主係数が単元だから, 補題 9 より GCD が–意的に存在する.

$\emptyset(\overline{F}_{k})$$\emptyset(\overline{G}_{1})|g\mathit{0}$が言えるが,$\emptyset(\overline{G}_{1})$の主係数が単元より

補題 13 仮定 10 の元で, $deg(g)=deg(g\mathit{0})$ ならば
Proof $deg(g\mathrm{o})=MAX$ ($deg(g\mathit{0})$

ならば,

. よって

$g\mathit{0}k$

.

$-$

方で,

$\emptyset(\overline{G}_{1})$と$g\mathit{0}$

は同作

. 口

は同伴.

$g\mathit{0}$$\psi_{k}(\phi(\overline{G}_{1}))|g\mathit{0}k$の主係数は単元となり$\emptyset(\overline{C_{2},}’\cdot)$$deg(\mathit{9}0)\geq d_{e_{\mathit{9}}}(\phi(\overline{G}_{1}))=deg(g)$(go $k=\psi_{k}$ $(go)=GCD(\psi_{k(\emptyset}(\overline{F}_{1})),$$\forall kdeg(\mathit{9}\mathit{0}k)\leq deg(g)$$deg(g\mathit{0}k)=deg(g)$$h_{\mathrm{O}}$$deg(g\mathit{0}k)$$\phi(\overline{G}\downarrow),$より$\psi k(\emptyset(\overline{F}\underline{.,})))$)$\rfloor;\text{り},$$deg(g)\leq deg(g_{0\wedge}\cdot)$の主係数も単元.

$cleg(g)=$. よって$go=\emptyset(\overline{G}_{1})h_{0}$$\forall k$とすれば,は単元. 口$fi,$ $f_{2}\in S[x]$

に対し,

$p$

が仮定 10 を満たすとする.

$J_{Q}=Ideal(f1, f_{2}, M_{\mathfrak{n}} , \cdot.

.

, M_{1})\subset Q[t_{n}, \cdots, t_{1}][x]$$J=Ideal(fi, f_{2}, M_{n}, \cdots, M1)\subset S[x]$$\overline{J}=Ideal(\overline{f}\iota,\overline{f}_{2},\overline{M}_{n}, \cdots,\overline{M}_{1})\subset S[x]$とお$\langle$.

補題 $14\exists g(X, t_{n}, \cdots, t_{\iota})\in S[x|,$ $lC_{x}(g)\in Z$$s.t$$=ccD(f_{1}(_{X,\alpha}n, \cdots, \alpha_{1}), f_{2}(X, \alpha_{l},, \cdots, \alpha_{1}))$

.

補題

$s.t$

$15\exists g\in\overline{S}[X]$$\emptyset(\overline{f}_{1}),\phi(\overline{f}_{2})$

.

. また,

$GB(I_{Q})=\{g, M_{\mathrm{t}1})\ldots,/pI_{1} \}$$\overline{J}=Ideal(g, Mn’\cdots, M_{1})$

ならば,

.

$g(,I^{\cdot},$$C\gamma_{1\prime},$$\cdots,$$(\mathrm{t}\downarrow)$$\phi(g)=GC’ D(\phi(\overline{f}1), \phi(\overline{f}\underline{\circ}))$即ちに対し, 補題 9 の (1), (2) を満たす.

Proof $\overline{J}=Idea\iota(g, Mn’\cdots, M_{1})X\text{り},$$\mathrm{O}\mathrm{K}$.

$\exists a_{1},$$\exists a_{2},$$\exists h_{1},$$g\equiv a_{1}\overline{f}_{\text{】}}+a_{2}\overline{f}_{2}\mathrm{m}\mathrm{o}\mathrm{d} \overline{I}$

補題 $16g$ を補題 14 の$g$とすると, 有限個の$\exists h_{2},\overline{f}_{1}\equiv gh_{1}$より (2) も$p$

を除いて$\mathrm{O}\mathrm{K}$Inod$\overline{I},\overline{f}\underline{\circ}\equiv gh_{2}$

mod

) (1)

$\overline{I}X\ell$$\downarrow 3$;. 口$GB(\overline{J})=\{\overline{g},\overline{M}_{1},, \cdots, \lambda/I\downarrow-\}$.

以上により次の定理が成立する.
定理 $17p$ が仮定 10 を満たすとき,$deg(\mathit{9}0)\geq deg(ccD(f\iota, f2))$$g(x, t_{n}, \cdots, t_{1})\in S[x|$$GB(\overline{J})=\{go, \overline{M}_{\iota},, \cdots , \overline{M}_{1}\}$

ならば,

.

を $g(x, \alpha_{n}, \cdot , . , \alpha_{1})=GCD(f_{i}, f_{2})$ かつ $lc_{x}(\mathit{9})\in Z,$

すると, 仮定 10 を満たす

$P$のうち有限個を除いて$p\parallel c_{x}(g)$$GB(\overline{J})=\{go, \overline{M}_{\iota)},\cdots,\overline{M}_{1}\}$

かつ$’\overline{(}$なる多項式とと 9。は同伴で, $deg(g\mathit{0})=deg(ccD(f_{1}, f\underline{\prime)}))$ .

この定理により, 仮定 10 を満たす素数$P$を十分多く用意すればそれらは全て,$GCD(\mathit{1}^{\cdot}\mathrm{I}, f\cdot\underline{\circ})$の$1\mathrm{I}\cdot$.

$\text{し}$いモジュライメージになっている. よって, これらを中国剰余定理により合成して, 有理数上に係数を引き戻し, 試し割りを行なうことにより $GCD(f_{i,f_{2}})$ を得る.

7

1.4 タイミングデータ
最小分解体の計算に現れる, 2 根以上添加された体上での GCD 計算を例にとる.
$f=x^{6}+10x^{5}+55x^{4}+140x^{3}+175x^{2}-3019x+25$$\alpha_{1}=$$\alpha_{2}=$.

$\alpha_{\mathrm{J}}$$=$aroot of $m_{1}(x)=f(x)$aroot of $m_{2}(x)=m_{1}(x)/(x-\alpha_{1})$a root of $m_{3}(x)=m_{2}(x\cdot)/$ ( $x-$ O2)

単位 : 秒
旧: グレブナ基底による GCD 計算

mod : モジュラ$+$

中国剰余定理版

候補 : モジュラにおいて, GCD 候補生成にかかった時間

check : 試し割り
段数 : 使った素数の個数 (素数は 8 桁の素数を用いている)
単拡大 : 原始元により単拡大に変換の後, モジュラで計算 (変換時間は除く;
が求まらなかったため, 例 3, 例 6 は略)$I_{13}’$に対する単拡大表現

8

参考文献$[1]\mathrm{A}\mathrm{b}\mathrm{b}\mathrm{o}\mathrm{t}\mathrm{t}$, J. A., Factorization of Polynomials Over Algebraic Number Fields.

$\mathrm{P}\mathrm{h}\mathrm{D}$thesis, Ulli-

versity of Bath(1989).
[2|$\mathrm{D}\mathrm{u}\mathrm{V}\mathrm{a}\mathrm{l}$, D., Diverse questions relatives au CALCUL FORMEL AVEC DES NOMBRESALG\’EBRIQUES.

$\mathrm{P}\mathrm{h}\mathrm{D}$thesis, L’universit\’e scientifique, technologique, et m\’edicale de Grello-ble(1987).

[, P. J., Rothschild, L. P., Factoring polynomials over algebraic number fields. ACM$31^{\mathrm{w}\mathrm{e}\mathrm{i}}\mathrm{n}\mathrm{b}\mathrm{e}\mathrm{r}\mathrm{g}\mathrm{e}\mathrm{r}$Trans. Math. Softw, $2/4(1976)$ , 335-350.
$[4]\mathrm{S}\mathrm{e}\mathrm{i}\mathrm{d}\mathrm{e}\mathrm{n}\mathrm{b}\mathrm{e}\mathrm{r}\mathrm{g}$, A., Constructions in algebra. Trans. Amer. Math. Soc. 197 (1974), 272-313.

, L., Algorithms for a Multiple Algebraic Extension. MEGA-90(1990), 235-248.

$[5]\mathrm{L}\mathrm{a}\mathrm{n}\mathrm{g}\mathrm{e}\mathrm{m}\mathrm{y}\mathrm{r}$, L., Algorithms for a Multiple Algebraic Extension II. AAECC-9(1991), 224-233.

$[6]\mathrm{L}\mathrm{a}\mathrm{n}\mathrm{g}\mathrm{e}\mathrm{m}\mathrm{y}\mathrm{r}$[$7\mathrm{l}\mathrm{L}\mathrm{a}\mathrm{n}\mathrm{g}\mathrm{e}\mathrm{m}\mathrm{y}\mathrm{r}$, L.,, S., The computation of polynomial greatest common divisors ovel$\mathrm{M}\mathrm{a}\mathrm{c}\mathrm{C}\mathrm{a}\mathrm{l}\mathrm{l}\mathrm{u}\mathrm{m}$an algebraic number field. J. Sylnb. Comp. 8(1989), 429-448.
$[8]\mathrm{E}\mathrm{n}\mathrm{C}\mathrm{a}\mathrm{r}\mathrm{n}\mathrm{a}\mathrm{C}\mathrm{i}\mathrm{o}\mathrm{n}$, M., J., On a Modular

Algebraic Number Fields. Proc.

$\mathrm{A}\mathrm{l}\mathrm{g}\mathrm{o}\mathrm{I}^{\cdot}\mathrm{i}\mathrm{t}$)$\mathrm{I}\mathrm{S}\mathrm{S}\mathrm{A}\mathrm{c}$}$\mathrm{l}\mathrm{I}\mathrm{l}$)for$\mathrm{C}^{\mathrm{t}}\mathrm{o}1111^{y}1\mathrm{c}\mathrm{i}\iota$$94(1994)$ , 58-65.

GCDs of$\mathrm{P}\mathrm{o}1$}’$110\iota 111\dot{c}1[.\backslash ()\backslash \prime \mathrm{c}1$