%$OpenXM: OpenXM/doc/compalg/factor.tex,v 1.6 2001/02/27 08:07:24 noro Exp $ \chapter{多項式の因数分解} \section{有限体} 計算機代数においては, 整数に関する演算を効率よく行うことを目的として, 適当な素数 $p$ を選んで, $p$ を法とする演算 (modular 演算) を行ったの ち, 整数に関する結果を得るという手法がしばしば用いられる. また, 暗号に 関する計算のように, 有限体における計算そのものが対象となっている場合も ある. 本節では, 有限体に関する基本的事項に関し, なるべく self contained な 形で述べる. \begin{df} 有限個の元からなる体を有限体と呼ぶ. $q$ 個の元からなる体を $GF(q)$ と書く. \end{df} \begin{pr} $GF(q)$ の標数はある素数 $p$ で, $q=p^n$. ここで, $n=[GF(q):GF(p)]$. \end{pr} \proof 標数 0 ならば $\Q \subset GF(q)$ となるから標数は正. $p>0$ を標数とすると, $GF(p) \subset GF(q)$ より $GF(q)/GF(p)$ は有限次代数拡大. その拡大次数を $n$ とおけば, $\{w_1,\cdots,w_n\} \subset GF(q)$ なる $GF(p)$ 上線形 独立な基底が存在して, $$GF(q)=GF(p)w_1\oplus\cdots \oplus GF(p)w_n$$ よって, $|GF(q)|=(|GF(p)|)^n=p^n$. \qed \begin{pr} $GF(q)$ \quad ($q=p^n$) は $x^{q-1}-1$, $x^q-x$ の最小分解体で, $\displaystyle x^q-x=\prod_{\alpha \in GF(q)}(x-\alpha).$ \end{pr} \proof 乗法群 $GF(q)^{\times}$ は有限群で, その位数は $q-1$ より, 全ての元 $\alpha \in GF(q)^{\times}$ に対し $\alpha^{q-1}=1$ すなわち $\alpha$ は $x^{q-1}-1$ の根. $x^{q-1}-1$ の根はこれで尽くされるから, $$x^{q-1}-1=\prod_{\alpha \in GF(q)^{\times}}(x-\alpha), \quad x^q-x = \prod_{\alpha \in GF(q)}(x-\alpha).$$ \qed \begin{co} $GF(q)$ の標数が奇数とする. $$F_{+}=\{\alpha \in GF(q) \mid \alpha^{(q-1)/2}=1\}, \quad F_{-}=\{\alpha \in GF(q) \mid \alpha^{(q-1)/2}=-1\}$$ とおけば, $GF(q)=F_{+} \cup F_{-} \cup \{0\}$ で $|F_{+}|=|F_{-}|=(q-1)/2.$ \end{co} \proof $x^q-x = x(x^{(q-1)/2}-1)(x^{(q-1)/2}+1)$ なる分解が成り立つから, $GF(q)$ が上のように分解されることがわかる. $F_{+}$ は $x^{(q-1)/2}-1$ の根全体で, 次数から $|F_{+}|=(q-1)/2$ がわかる. $F_{-}$ も同様. \qed \begin{pr} 一つの体 $K$ に含まれる $GF(q)$ ($q=p^n$), $GF(q')$ ($q'=p^{n'}$) に対し $$ GF(q) \subset GF(q') \Leftrightarrow n | n'.$$ \end{pr} \proof $GF(q) \subset GF(q')$ とすれば,$[GF(q):GF(p)]|[GF(q'):GF(p)]$ より $n|n'.$ 逆に $n|n'$ とする. $GF(q')$ は $K$ に含まれる, $x^{q'}-x$ の最小分解 体だから, $$GF(q')=\{\alpha \in K \mid \alpha^{q'}-\alpha=0\}$$ 同様に, $$GF(q)=\{\alpha \in K \mid \alpha^{q}-\alpha=0\}$$ $n|n'$ より $(q-1)|(q'-1)$ が言えるから, $x^q-x|x^{q'}-x.$ よって, $\alpha \in GF(q) \Rightarrow \alpha \in GF(q').$ \qed \begin{co} $GF(p)$ の代数的閉包 $\Omega$ を一つ定めれば, $GF(q) \subset \Omega$ は, $\Omega$ における $x^q-x$ の最小分解体として一意に定まる. \end{co} \begin{pr} $GF(q)^{\times}$ は位数 $q-1$ の巡回群. \end{pr} \proof $G=GF(q)^{\times}$ は有限アーベル群より, $1 < n_i \in \Z$ ($i=1,\cdots,l$), $n_i | n_j$ ($i1$ とすれば, 少なくとも $n_1^2$ 個 の元が $x^{n_1}-1=0$ の根となるが, これは不可能. よって $$l=1,\quad G\simeq \Z/(n_1).$$ \qed \begin{pr} $f$ を $GF(q)$ 上既約とすると, $$f | x^{q^n}-x \Leftrightarrow \deg(f) | n$$ \end{pr} \proof $GF(q)$ の代数的閉包 $\Omega$ を一つ固定する. $f$ が $GF(q)$ 上既約とする. $f$ の $\Omega$ における根を $\alpha$ とする.\\ \underline{$\Rightarrow$)} \quad $f|x^{q^n}-x$ とする. このとき $f(\alpha)=0$ より $\alpha^{q^n}-\alpha=0.$ よって, $\alpha \in GF(q^n)\subset \Omega.$ これから $GF(q)(\alpha)\subset GF(q^n).$ ゆえに $$\deg(f)=[GF(q)(\alpha):GF(q)]|[GF(q^n):GF(q)]=n.$$\\ \underline{$\Leftarrow$)} $\deg(f)|n$ とする. $GF(q)(\alpha)$, $GF(q^n)$ は一つの体 $\Omega$ に含まれる から, $GF(q)(\alpha) \subset GF(q^n)$ これより $\alpha^{q^n}-\alpha=0$. $f$ は $\alpha$ の最小多項式だから $$f|x^{q^n}-x.$$ \qed\\ $x^{q^n}-x$ は重根を持たないから, 次が成り立つ. \begin{co} \label{irred_mod} $F = \{ f | f : GF(q)$ 上既約, モニックで $\deg(f)|n\}$ とおけば $x^{q^n}-x = \prod_{f\in F} f.$ \end{co} \section{無平方分解} 以下で述べるさまざまな因数分解アルゴリズムは, 入力が重複因子をもつこと を許さない. よって, 以下に述べる無平方分解を行なっておく必要がある. \begin{df} 重複因子を持たない多項式を{\bf 無平方 (squarefree)} という. $f \in K[x]$ に対し, $$f = \prod g_1^{n_i}$$で各 $g_i$ は無平方かつ互いに素な多項 式で $n_1 while \= ( $flat | f$ ) \{\\ \>\>$f \leftarrow f/flat,\quad m \leftarrow m + 1$\\ \>\}\\ {\rm(b)}\> $flat_1 \leftarrow \GCD(flat,f)$\\ \>$g \leftarrow flat/flat_1,\quad flat \leftarrow flat_1$\\ {\rm(c)}\>$F \leftarrow F\cdot g^m, \quad counter \leftarrow counter+1$\\ \}\\ return $F$\\ \end{tabbing} \end{al} \begin{pr} \label{valid_sqfr} アルゴリズム \ref{sqfr} は $f$ の無平方分解を出力する. \end{pr} \proof (a) において $counter = k$ の時, \begin{center} $f = g_k^{n_k-n_{k-1}}g_{k+1}^{n_{k+1}-n_{k-1}}\cdots$, \quad $flat = g_k g_{k+1}\cdots$, \quad $m = n_{k-1}\quad (n_0 = 0)$ \end{center} あることを帰納法により示す. $k = 1$ の時は補題より正しい. $k$ まで正しいとする. 仮定より, $flat^{n_k-n_{k-1}} | f\quad$ かつ $flat^{n_k-n_{k-1}+1}{\not|} f$ より(b) において $$m = n_{k-1}+(n_k-n_{k-1}) = n_k, \quad f = g_{k+1}^{n_{k+1}-n_k}\cdots$$ となる. よって, (c) においては $$flat = flat_1 = g_{k+1}\cdots$$ となり $k+1$ でも正しい. また (c) において $g = g_k$, $m = n_k$ となっているからこのアルゴリズムは正しく無平方分解を出力する. \qed\\ 標数 $p>0$ の体 $K$ 上では微分して 0 になる多項式が存在するため注意を要する. \begin{lm} $K$ を標数 $p>0$ の有限体とする. $K$ 上の一変数多項式 $f$ に対し, $f'=0 \Leftrightarrow$ ある多項式 $g$ が存在して $f = g^p.$ \end{lm} \begin{lm} $K$ を標数 $p>0$ の有限体とする. $h$ を, $f$ の因子のうち, 重複度が $p$ で割り切れるものの積とし, $g= f/h = \prod g_i^{n_i}$ とする. このとき, $$\GCD(f,f')=h\, \GCD(g,g')=h\prod g_i^{n_i-1}.$$ \end{lm} \proof $h'=0$ より $f'=g'h+gh'=g'h$. よって, $\GCD(f,f')=h\, \GCD(g,g').$ $$\GCD(g,g') = \prod_i g_i^{n_i-1} \GCD(\prod_k g_k,\sum_i n_i g'_i \prod_{k\neq i}g_k)$$ 仮定により $n_i \neq 0$. また $g_i$ は無平方だから, 前補題により $g'_i \neq 0$ だから, $$\GCD(\prod_k g_k,\sum_i n_i g'_i \prod_{k\neq i}g_k) = \prod_k \GCD(g_k,\sum_i n_i g'_i \prod_{k\neq i}g_k) = \prod_k \GCD(g_k,g'_k)$$ ここで $g_k$ が無平方より, $g_k$ を既約分解して考えれば $\GCD(g_k,g'_k)=1$. よって, $$\GCD(g,g') = \prod_i g_i^{n_i-1}.$$ \qed \begin{al}(無平方分解) \label{sqfrmod} \begin{tabbing} Input : $f(x) \in K[x]$ ($K$ は標数 $p>0$ の有限体)\\ Output : $f$ の無平方分解 $f= g_1^{n_1}g_2^{n_2}\cdots$\\ $F \leftarrow 1$\\ if \= $f'\neq 0$ \{\\ \> $flat \leftarrow f/\GCD(f,f'),\quad m \leftarrow 0,\quad counter \leftarrow 1$\\ \>while\= ( $flat \neq constant$ ) \{\\ {\rm(a)}\>\> while \= ( $flat | f$ ) \{\\ \>\>\>$f \leftarrow f/flat,\quad m \leftarrow m + 1$\\ \>\>\}\\ {\rm(b)}\>\> $flat_1 \leftarrow \GCD(flat,f)$\\ \>\>$g \leftarrow flat/flat_1,\quad flat \leftarrow flat_1$\\ {\rm(c)}\>\>$F \leftarrow F\cdot g^m, \quad counter \leftarrow counter+1$\\ \>\}\\ \}\\ if $f \neq constant$ \{\\ \> $g \leftarrow f^{1/p}$\\ \> $g = g_1^{n_1}g_2^{n_2}\cdots$ と無平方分解\\ \> $F = F\cdot g_1^{pn_1}g_2^{pn_2}\cdots$\\ \}\\ return $F$ \end{tabbing} \end{al} この場合, $flat$ が, $f$ の重複度が $p$ で割り切れない因子の積となるから, $flat$ が定数となった時点で $f$ の各因子の重複度は $p$ で割り切れる. よって, $1/p$ 乗が計算でき, その無平方分解を $p$ 乗すれば, $f$ の無平方 分解が計算できたことになる. ここでは, 係数を体としたが, UFD 上では, あらかじめ $f$ に対し $cont(f)$を計算し, それで $f$ を割って原始的多項式としてから行なう. 整 数上の場合には, この操作は単に係数の GCD を計算することを意味するが, 多変数多項式の場合, 多項式の GCD が必要となる. さらに, 係数環上での無平方 分解も要求されているならば, このアルゴリズムを再帰的に用いる必要がある. このアルゴリズムの Yun による改良も知られている. また, この素朴な方法 は, 重複度の大きな因子をもつ場合には, 最初のGCD 計算で多大な時間を必要 とする場合が多く, 実用的に問題がある. これを避けるため, 重複度最大の因 子から順に直接求めていく方法が Wang-Trager \cite{SQFR} により考案されている. この方法は, 後述する Hensel 構成と の組合せにより大きな効果を発揮する. これについては \ref{wangtrager} 節で述べる. \section{Berlekamp アルゴリズム} $p$ を素数とし, $q$ 元体 $K=GF(q)$ ($q=p^n$) を係数とする一変数多項式 環$R = K[x]$ における既約因子分解を考える. $f(x) \in R$ が無平方であるとする. $f = \prod_{i=1}^{r}f_i$ と既約分解 すると, 中国剰余定理により, $$R/(f) \simeq \bigoplus R/(f_i).$$ $R/(f), R/(f_i)$ 上に次の$K$-準同型 (Frobenius 写像) を考える. $$\pi : f \mapsto f^q \bmod f$$ $$\pi_i : f \mapsto f^q \bmod {f_i}$$ すると, $$\Ker(\pi-I) \simeq \bigoplus \Ker(\pi_i-I)$$ である. ここで, $f_i$ は既約より $R/f_i$ は体である. また $x^q-x$ は, $K$ のすべての元を根にもつが, 体 $R/f_i$ 上 で考えれば, 根はすべてこれで尽くされている. よって $\Ker(\pi_i-I) = K$.結局 $$\Ker(\pi-I) \simeq \bigoplus K$$ すなわち, $f$ の既約多項式の個数を $r$ とすると, $\Ker(\pi-I)$ は, $r$ 個の $K$ の直和となる. さらに, これは次のように言い替えられる. \begin{pr} \begin{enumerate} \item $f|(g^q-g) \Rightarrow$ ある $(s_1,\cdots,s_r) \in K^r$ が存在して $f_i|(g-s_i)$ \item すべての $(s_1,\cdots,s_r) \in K^r$ に対し, ある $g$ が存在して $f|(g^q-g), f_i|(g-s_i)$ \end{enumerate} \end{pr} $g$ は, $\deg(g)<\deg(f)$ としてよいから, $g\in \Ker(\pi-I)$ をとると, 適当な $s$ に対し $\GCD(g-s,f)$ は自明でない $f$ の因子を与える. 次のアルゴリズムは有限体上の一変数多項式の因数分解を行う. \begin{al}(Berlekamp{\rm\cite{BERL}}) \begin{tabbing} Input : $f(x) \in R$; $f$ は無平方\\ Output : $\{f_1,f_2,\cdots\}$ $f = f_1 f_2 \cdots$ は $f$ の既約分解\\ $F = \{f\}$\\ $Q \leftarrow \pi$ の行列表現\\ $\{e_1 = 1, e_2, \cdots, e_r\} \leftarrow \Ker(Q-I)$ の $K$-基底\\ if ($r = 1$) then return $F$\\ $k \leftarrow 2$\\ do \=\{\\ \> $F_1 \leftarrow \emptyset$\\ \> while \= $F \neq \emptyset$ do \{\\ \>\> $g \leftarrow$ $F$ の一つの元 \\ \>\> $F \leftarrow F \backslash \{g\}$\\ \>\> $F_g \leftarrow \{\GCD(g,e_k-s)(s \in GF(q))$ のうち, 定数でないもの\}\\ \>\> $g \leftarrow g/\prod_{h\in F_g} h$\\ \>\> $F_1 \leftarrow F_1 \cup F_g$ \\ \>\> if ( $g \neq 1$ ) $F_1 \leftarrow F_1 \cup \{g\}$\\ \>\> if \= ($|(F \cup F_1)| = r$) return $F \cup F_1$\\ \>\}\\ \> $k \leftarrow k+1$ \\ \> $F \leftarrow F_1$ \\ \}\\ return F \end{tabbing} \end{al} 基底により全ての既約因子が分離できることは次の命題よりわかる. \begin{pr} $\{e_1,\cdots,e_r\}$ を $\Ker(\pi-I)$ の$K$-基底とすると すべての $i\neq j$ なる $i,j$ に対し, ある $k,s$ が存在して $f_i|(e_k-s), f_j{\not|}(e_k-s)$ \end{pr} \proof この主張が偽ならば \begin{center} ある $i,j$ が存在して, すべての $e_k, s$ に対し ($(f_i|(e_k-s)\Rightarrow f_j|(e_k-s))$) \end{center} となる. この時, 各 $k$ に対し, $f_i|(e_k-s_k)$ なる $s_k$ をとれば, $\{e_k\}$ が基底であることより \begin{center} すべての $g \in \Ker(\pi-I)$ に対し, ある $s$ が存在して $f_i|(g-s), f_j|(g-s).$ \end{center} ところが, $\Ker(\pi-I)$ の中には $f_i, f_j$ を分離するものがあるから矛盾. \qed 以上述べたアルゴリズムは, $q$ が小さい時に用いられる最も原始的な形であ る. このアルゴリズムでは, 最悪 $q$ 回 GCD を繰り返す必要が生ずる. しか し, 実際には $\GCD(g,e-s)$ が $1$ または $g$ 以外の値を取るような $s$ の値は限られていて, その値は $s$ のある多項式の根となっている. \begin{pr} $e \in \Ker(\pi-I)$ に対し, $$S=\{s \in GF(q) \mid \GCD(e-s,f) \neq 1\}$$ とおく. このとき $m(x)=\prod_{s\in S}(x-s)$ とおけば, $m(x)$ は $e$ の $R/(f)$ における最小多項式. すなわち, $f|m(e)$ となるような, 最小次数の多項式. \end{pr} \proof $f$ の各因子 $f_i$ に対し $e \equiv s_i \bmod f_i$ となるような $s_i$ が存在する. このとき $s_i \in S$ で $$f_i | (e-s_i) | m(e).$$ $f$ は 無平方より $f | m(e).$ 逆に, $M(x)$ を, $e$ の $R/(f)$ における最小多項式とする. もし $\deg(M)<\deg(m)$ ならば, ある $s\in S$ が存在して $$m=(x-s)q+r, \quad r \in GF(q) \backslash \{0\}$$ と書ける. この時, $f$ の因子 $f_i$ が存在して, $f_i |(e-s)$ となるから, $f_i | r$. これは矛盾. \qed $e$ の最小多項式は, $e^k$ が $\{1,e,e^2,\cdots,e^{k-1}\}$ で 張られているか否かを $k=1$ から順に調べることにより決定できる. 最小多項式 $m(x)$ を用いれば, $m$ の根を求めさえすれば, それらに 対しのみ GCD を実行すればよいことになる. \section{Cantor-Zassenhaus アルゴリズム} 前節で述べた Berlekamp アルゴリズムおよび最小多項式を用いる改良によって $q$ が小さい場合には十分効率よく因数分解できる. しかし, $q$ が大きい 場合には以下で述べるような確率的アルゴリズムを用いなければ, 効率よい 因数分解は難しい. 以下, 前節と同様の記号を用いる. \begin{pr} 標数 $p$ が奇数とする. $e \in \Ker(\pi-I)$ とすれば, $$\GCD(e^{(q-1)/2}-1,f) \neq 1, f$$ となる確率は, $k$ を $f$ の既約因子の個数とするとき $$1-({{q-1}\over{2q}})^k-({{q+1}\over{2q}})^k.$$ \end{pr} \proof $f_i$ ($i=1,\cdots,k$) を $f$ の既約因子とし, $e \equiv s_i \bmod f_i$ ($s_i \in GF(q)$) とする. $$e^{(q-1)/2} \equiv s_i^{(q-1)/2} \equiv 0, \pm 1 \bmod f_i$$ より, \begin{center} $\GCD(e^{(q-1)/2}-1,f) = f \Leftrightarrow$ すべての $i$ に対し $s_i^{(q-1)/2} \equiv 1 \bmod f_i$ \end{center} \begin{center} $\GCD(e^{(q-1)/2}-1,f) = 1 \Leftrightarrow$ すべての $i$ に対し $s_i^{(q-1)/2} \equiv 0, -1 \bmod f_i$ \end{center} $s \in GF(q)$ とする時, $s^{(q-1)/2} \equiv 1$ なる元は $(q-1)/2$ 個, $s^{(q-1)/2} \equiv 0, -1$ なる元は $(q+1)/2$ 個. よって, $\GCD(e^{(q-1)/2}-1,f) = f$, $\GCD(e^{(q-1)/2}-1,f) = 1$ なる確率 はそれぞれ $$({{q-1}\over{2q}})^k,\quad ({{q+1}\over{2q}})^k$$ となる. \qed 標数 2 の場合を扱うために, $GF(2^n)$ 上の多項式 $f$ の trace $\Tr(f)$ を 定義する. \begin{df} $GF(2^n)$ において, $\Tr(x) \in GF(2^n)[x]$ を $$\Tr(x) = \sum_{i=0}^{n-1}x^{2^i}$$ と定義する. \end{df} \begin{lm} $x^{2^n}-x=\Tr(x)(\Tr(x)+1).$ \end{lm} \begin{co} \begin{enumerate} \item $a \in GF(2^n) \Rightarrow \Tr(a) \in GF(2)$ \item $|\{ s \in GF(2^n) \mid \Tr(s)=0\}| = |\{ s \in GF(2^n) \mid \Tr(s)=1 \}| = 2^{n-1}$ \end{enumerate} \end{co} \begin{pr} 標数 $p=2$ とする. $e \in \Ker(\pi-I)$ とすれば, $$\GCD(\Tr(e),f) \neq 1, f$$ となる確率は, $k$ を $f$ の既約因子の個数とするとき $1-1/2^{k-1}.$ \end{pr} \proof $f_i$ ($i=1,\cdots,k$) を $f$ の既約因子とし, $e \equiv s_i \bmod f_i$ ($s_i \in GF(q)$) とする. $$\Tr(e) \equiv \Tr(s_i) \equiv 0, 1 \bmod f_i$$ より, \begin{center} $\GCD(\Tr(e),f) = f \Leftrightarrow$ すべての $i$ に対し $\Tr(s_i) \equiv 0 \bmod f_i$ \end{center} \begin{center} $\GCD(\Tr(e),f) = 1 \Leftrightarrow$ すべての $i$ に対し $\Tr(s_i) \equiv 1 \bmod f_i$ \end{center} $s \in GF(q)$ とする時, $\Tr(s) \equiv 0, 1$ なる元はそれぞれ $q/2$ 個. よって, $\GCD(\Tr(e),f) = f$, $\GCD(\Tr(e),f) = 1$ なる確率 はそれぞれ $1/2^k$ となる. \qed\\ これらをもとに, 次のようなアルゴリズムを得る. \begin{al}(Cantor-Zassenhaus{\rm\cite{CZ}}) \begin{tabbing} Input : $f(x) \in GF(q)[x]$, $q=p^n$, $f$ は無平方\\ Output: $\{f_1,f_2,\cdots\}$ $f = f_1 f_2 \cdots$ は $f$ の既約分解\\ $F = \{f\}$\\ $Q \leftarrow \pi$ の行列表現\\ $\{e_1 = 1, e_2, \cdots, e_r\} \leftarrow \Ker(Q-I)$ の $K$-基底\\ if ($r = 1$) then return $F$\\ while\= ($|F| < r$) do \{\\ \> $(c_1,\cdots,c_r) \leftarrow$ 乱数ベクトル ($c_i \in GF(q)$)\\ \> $e \leftarrow \sum c_ie_i$ \\ \> if \= $p=2$\\ \>\> $E \leftarrow \Tr(e) \bmod f$\\ \>else\\ \>\> $E \leftarrow e^{(q-1)/2}-1 \bmod f$\\ \> $F_1 \leftarrow \emptyset$\\ \> while \= ($F \neq \emptyset$) do \{\\ \> \> $g \leftarrow F$ の元, \quad $F \leftarrow F \backslash \{g\}$\\ \> \> $h \leftarrow \GCD(g,E)$\\ \> \> if \= $h \neq 1,g$\\ \> \> \> $F_1 \leftarrow F_1 \cup \{h,g/h\}$\\ \> \> else \\ \> \> \> $F_1 \leftarrow F_1 \cup \{g\}$\\ \> \}\\ \> $F \leftarrow F_1$ \\ \}\\ return F \end{tabbing} \end{al} \section{DDF (distinct degree factorization)} 有限体上の多項式に対しては, GCD のみによる DDF (distinct degree factorization;次数別因子分解) とよばれる予備的な分解が可能である. DDF で得られる各因子は, それぞれ同一次数の既約因子の積からなる. これにより, 各次数の既約因子が 1 つの場合には GCD のみにより既約因子が得られる. また, 分解成分の既約因子が同一次数であることを利用して, 特殊な手法 により既約分解をすることも可能になる. 系 \ref{irred_mod}より, 次のアルゴリズムが得られる. \begin{al} \begin{tabbing} \\ Input : $f(x) \in GF(q)[x]$, $f$ は無平方\\ Output : $f(x) = \prod f_i$, $f_i$ は $f$ の $i$ 次既約因子の積\\ $w \leftarrow x$,\quad $i \leftarrow 1$\\ while\= ($i \le \deg(f)/2$) do \{\\ \> $w \leftarrow w^q \bmod f$\\ \> $f_i \leftarrow \GCD(f,w-x)$\\ \> if \= $f_i \neq 1$ \{\\ \>\> $f \leftarrow f/f_i$\\ \>\> $w \leftarrow w \bmod f$\\ \>\> $E \leftarrow e^{(q-1)/2}-1$\\ \>\}\\ \}\\ while ( $i < \deg(f)$ )\\ \> $f_i \leftarrow 1$\\ $f_{\deg(f)} \leftarrow f$\\ return $\prod f_i$ \end{tabbing} \end{al} $i$ 回目においては, $i$ の真の約数を次数に持つ因子は既に除かれて いるため, $i$ 次の因子のみが取り出せる. また, $i \ge \deg(f)/2$ となった時点で, $f$ が既約な $\deg(f)$ 次因子であることは明らかである. このアルゴリズムにおいて, $w^q \bmod f$ の計算を繰り返す必要がある. しかし, 一般に $$g = \sum_{i=0}^m a_ix^i \Rightarrow g^q \bmod f = \sum_{i=0}^m a_ix^{iq} \bmod f$$ より, $w_0 = x^q \bmod f$ の計算結果から $w_i = w_0^i \bmod f = w_{i-1}w_0 \bmod f$ の計算を $i=1,\cdots,\deg(f)-1$ に対して行っておけば, $w^q \bmod f$ の 計算は効率よく計算できる. \section{次数別因子の分解} $f$ は無平方で, $d$ 次の既約因子の積であるとする. $f$ はもちろん Berlekamp アルゴリズムにより既約分解できるが, 含まれる既約因子の次数が全て等しい ことを利用して分解を行うことを考える. \begin{pr} $q=p^n$ で $p$ が奇素数とする. $f=f_1f_2$ で$f_1$, $f_2$ が $f$ の 2 つの $d$ 次既約因子とする. $GF(q)$ 上の 高々 $2d-1$ 次式 $g$ をランダムに選 ぶとき, $\GCD(g^{(q^d-1)/2}-1,f)=f_1$ または $f_2$ となる確率は $1/2-1/(2q^d)$. \end{pr} \proof $f_1$, $f_2$ が $d$ 次既約より, $$GF(q)[x]/(f_1) \simeq GF(q)[x]/(f_2) \simeq GF(q^d).$$ よって, 任意の $g \in GF(q)[x]$ に対し, $$s_1=(g \bmod f_1)^{(q^d-1)/2} = 0, \pm 1,\quad s_2=(g \bmod f_2)^{(q^d-1)/2} = 0, \pm 1.$$ $GF(q)$ の元のうち $(q^d-1)/2$ 乗して 1 になるものは $(q^d-1)/2$ 個, そうでないものは $(q^d+1)/2$ 個ある. $\GCD(g^{(q^d-1)/2}-1,f)=f_1$ または $f_2$ となるのは, $s_1$, $s_2$ の 一方のみが 1 になる場合である. ここで, 中国剰余定理により, $$GF(q)[x]/(f_1f_2) \simeq GF(q)[x]/(f_1)\bigoplus GF(q)[x]/(f_2) \simeq GF(q^d)\bigoplus GF(q^d)$$だから, 任意の $(a_1,a_2) \in GF(q^d)\bigoplus GF(q^d)$ の元に対し, 多項式の組に対し, $a_1 = g \equiv g \bmod f_1$, $a_2 = g \equiv g \bmod f_2$ なる$2d-1$ 次以下の 多項式 $g$ が一意的に対応する. よって, $2d-1$ 以下の多項式 $q^{2d}$ 個のうち, $\GCD(g^{(q^d-1)/2}-1,f)=f_1$ または $f_2$ となるのは, $$2(q^d-1)/2\cdot (q^d+1)/2 = (q^{2d}-1)/2$$ 個であり, 確率は $1/2-1/(2q^{2d}).$ \qed \begin{pr} $q=2^n$ とする. $f=f_1f_2$ で$f_1$, $f_2$ が $f$ の 2 つの $d$ 次既約因子とし, $$\Tr(x) = \sum_{i=0}^{nd-1}x^{2^i}$$ とする. $GF(q)$ 上の 高々 $2d-1$ 次式 $g$ をランダムに選ぶとき, $\GCD(\Tr(x),f)=f_1$ または $f_2$ となる確率は $1/2$. \end{pr} \proof $f_1$, $f_2$ が $d$ 次既約より, $$GF(q)[x]/(f_1) \simeq GF(q)[x]/(f_2) \simeq GF(2^{nd}).$$ よって, 任意の $g \in GF(q)[x]$ に対し, $$s_1=\Tr(g \bmod f_1) = 0,1,\quad s_2=\Tr(g \bmod f_2) = 0,1.$$ $GF(2^{nd})$ の元のうち $\Tr$ の値が 0, 1 になるものは それぞれ $2^{nd-1}$ 個 ずつある. \\ $\GCD(\Tr(x),f)=f_1$ または $f_2$ となるのは, $s_1$, $s_2$ の 一方のみが 0 になる場合である. ここで, 中国剰余定理により, $$GF(q)[x]/(f_1f_2) \simeq GF(q)[x]/(f_1)\bigoplus GF(q)[x]/(f_2) \simeq GF(2^{nd})\bigoplus GF(2^{nd})$$だから, 任意の $(a_1,a_2) \in GF(2^{nd})\bigoplus GF(2^{nd})$ の元に対し, 多項式の組に対し, $a_1 = g \equiv g \bmod f_1$, $a_2 = g \equiv g \bmod f_2$ なる$2d-1$ 次以下の 多項式 $g$ が一意的に対応する. よって, $2d-1$ 以下の多項式 $2^{2nd}$ 個のうち, $\GCD(\Tr(x),f)=f_1$ または $f_2$ となるのは, $2 \cdot (2^{nd-1})^2 = 2^{2nd-1}$ 個であり, 確率は $1/2.$ \qed\\ これらの命題は, ランダムに選んだ $g$ により, $f$ の 2 つの因子が確率 1/2 以上で分離できることを意味している. これにより, 以下のような, Cantor-Zassenhaus アルゴリズムの変形版が適用できる. \begin{al} \begin{tabbing} \\ Input : $f(x) \in GF(q)[x]$, $q=p^n$, $f$ は無平方で $d$ 次既約因子の積\\ Output : $f(x) = \prod f_i$, $f$ の 既約因子分解\\ $r \leftarrow \deg(f)/d,\quad F \leftarrow \{f\}$\\ while\= ($|F| < r$) do \{\\ \> $g \leftarrow 2d-1$ 次のランダムな多項式\\ \> if \= $p=2$\\ \>\>$G \leftarrow \sum_{j=0}^{rd-1}g^{2^i} \bmod f$\\ \> else\\ \>\> $G \leftarrow g^{(q^d-1)/2}-1 \bmod f$\\ \> $F_1 \leftarrow \emptyset$\\ \> while \= ($F \neq \emptyset$) do \{\\ \> \> $h \leftarrow F$ の $\deg(h)>d$ なる元,\quad $F \leftarrow F \backslash \{h\}$\\ \> \> $z \leftarrow \GCD(h,G)$\\ \> \> if \= $z \neq 1,h$\\ \> \> \> $F_1 \leftarrow F_1 \cup \{z,h/z\}$\\ \> \> else \\ \> \> \> $F_1 \leftarrow F_1 \cup \{h\}$\\ \> \}\\ \> $F \leftarrow F_1$ \\ \}\\ return $F$\\ \end{tabbing} \end{al} \section{整数係数一変数多項式の因数分解} 計算機代数システムにおいて用いられている因数分解アルゴリズムは, 何らかの準同型により多項式をより扱いやすい空間に写像し, その 空間で, 多項式の像を因数分解し, なんらかの方法によりその分解された 像からもとの空間における因子を構成する, という方法によるものが多い. 特に, 二変数以上の多項式の因数分解は一変数多項式に帰着されるなど, 一変数多項式の因数分解は, 因数分解アルゴリズムにおいて重要な位置を 占める. ここでは, もっとも普通に用いられている Zassenhaus による アルゴリズムについて述べる. 無平方な $f \in \Z[x]$ の因数分解アルゴリズムは, 有限体上の因数分解, Hensel 構成, 試し割りの三つの部分からなる. \begin{pr}(Hensel) $f \in \Z[x], p \in \N$ は素数で, $$f \equiv \prod f_{1i} \bmod p,\quad f_{1i} \in GF(p)[x], \quad \deg(f) = \deg(\prod_i f_{1i})$$ $f_{1i}$ は $GF(p)$ 上で互い に素とする. この時, 任意の $k$ に対し, $f_{ki} \in \Z/(p^k)[x]$ が存在 して, $$f \equiv \prod_i f_{ki} \bmod {p^k},\quad f_{1i} \equiv f_{ki} \bmod p, \quad \deg(f_{1i}) = \deg(f_{ki}).$$ \end{pr} \proof $k$ に関する帰納法で示す. $k$ が 1 の時は正しい. $k$ まで正しいとする. $$f_{(k+1)i}=f_{ki}+p^k h_i$$ なる形を仮定すると, $$\prod_i f_{(k+1)i} \equiv \prod_i f_{ki} + p^k\sum_i h_i\prod_{j\neq i}f_{kj} \bmod {p^{k+1}}$$ 一方, $f \equiv \prod_i f_{ki} \bmod {p^k}$ より, $$f = \prod_i f_{ki} + p^k h \bmod {p^{k+1}}$$ と書ける. よって, $$h \equiv \sum_i h_i\prod_{j\neq i}f_{kj} \equiv \sum_i h_i\prod_{j\neq i}f_{1j} \bmod p$$ となるように, $h_i \in GF(p)[x], \deg(h_i)\le \deg(f_{1i})$ を決めることができること を示せばよい. これは, 命題 \ref{exteuc} により言える. \qed \begin{pr} $f \in \Z[x], p \in \N$ は素数, $$f \equiv g_0 h_0 \bmod p, \quad g_0, h_0 \in GF(p)[x],\quad \deg(f) = \deg(g_0 h_0),\quad \GCD(g_0,h_0) = 1$$ とする. この時, $f \equiv gh \equiv g'h' \bmod {p^k}$ かつ $g \equiv g' \equiv g_0 \bmod p,$ $\deg(g) = \deg(g') = \deg(g_0), \quad \deg(h) = \deg(h') = \deg(h_0),\quad \lc(g) \equiv \lc(g') \bmod {p^k}$ ならば, $$g \equiv g' \bmod {p^k}, \quad h \equiv h' \bmod {p^k}.$$ \end{pr} \proof $k$ に関する帰納法で示す. $k$ まで正しいとする. $k+1$ のとき, 帰納法の 仮定により, $$g' - g = p^k r,\quad h' - h = p^k s$$ と書ける. 一方, $gh \equiv g'h' \bmod {p^{k+1}}$ から $r h_0 + s g_0 \equiv 0 \bmod p$ が成り立つ. もし $s \equiv 0 \bmod p$ ならば $r h_0 \equiv 0 \bmod p$ より $k+1$ で正しい. もし $s {\not\equiv} 0$ ならば $g_0 | r$. ここで, $\lc(g) \equiv \lc(g') \bmod {p^{k+1}}$ より, $\deg(r \bmod p) < \deg(g_0).$ よって $r \equiv 0 \bmod p$ となり, この場合も $k+1$ で正しい. \qed \begin{df} $f = \sum_{i=0}^n a_i x^i \in C[x]$ に対し, $f$ のノルム $\parallel f \parallel_1$, $\parallel f \parallel_2$ を それぞれ, $$\parallel f \parallel_1 = \sum_{i=0}^n |a_i|, \quad \parallel f \parallel_2 = \sqrt{\sum_{i=0}^n |a_i|^2}$$ ($|a|$ は $a$ の絶対値) で定義する. \end{df} \begin{pr}(Landau-Mignotte\cite{MIG}) $f = \sum_{i=0}^n a_i x^i \in \Z[x], g = \sum_{i=0}^m b_i x^i \in \Z[x]$ とする. この時 $g|f$ ならば, $\parallel g\parallel_1 \le |b_m/a_n|2^m \parallel f\parallel_2$ \end{pr} \begin{co} \label{mig} $f, g \in \Z[x]$, $g|f$ ならば, $\parallel \lc(f)/\lc(g)\cdot g\parallel_1 \le 2^{\deg(g)} \parallel f\parallel_2$ \end{co} \begin{pr} $f \in \Z[x]$ が無平方ならば, 有限個の素数 $p$ を除いて $\deg(f \bmod p) = \deg(f)$ かつ $f \bmod p$ は無平方. \end{pr} 証明は, $f$ の無平方性が, $f$ と $f'$ の終結式が 0 でないことと同値で あることから明らか.\\ 以上により $\Z[x]$ における因数分解は次のように行なわれる. \begin{al}(Zassenhaus{\rm \cite{ZASS}}) \label{zassenhaus} \begin{tabbing} Input : $f(x) \in \Z[x]$; $f$ は無平方\\ Output : $\{f_1,f_2,\cdots\}$ $f = f_1 f_2 \cdots$ は $f$ の既約分解 \\ $p \leftarrow \deg(f) = \deg(f \bmod p)$ かつ $f \bmod p$ が無平方となるような $p$\\ $a \leftarrow f$ の主係数\\ $F_1\leftarrow f/a \bmod p$ の $GF(p)$ 上のモニックな既約因子全体 (有限体上の因数分解)\\ if $|F_1| = 1$ then return $\{f\}$\\ $F_1 = \{ f_{11},\cdots,f_{1m}\}$ とする. \\ $k \leftarrow p^k > \parallel f\parallel_2\cdot 2^{\deg(f)+1}$ なる整数\\ $f \equiv \prod_i f_{1i} \bmod p$ から $f \equiv \prod_i f_{ki} \bmod {p^k}$ なる $F_k=\{f_{k1},\cdots,f_{km}\} $ を\\ Hensel 構成で求める\\ $l \leftarrow 1$\\ $F \leftarrow \emptyset$\\ while \= ( $2l \le m$ ) \{\\ (a)\> $S \leftarrow S \subset F_k$, $|S|=l$ なる新しい部分集合\\ \> if \= $S$ が存在しない then $l \leftarrow l+1$\\ \> else \= \{\\ \>\> $g \leftarrow a\cdots \prod_{s\in S}s$\\ (b)\>\> $g \leftarrow g$ の各係数に $p^k$ の整数倍を加えて絶対値が $p^k/2$ 以下としたもの\\ \> if $g|af$ \{\\ \>\> $g\leftarrow \pp(g)$ (primitive part),\quad $f \leftarrow f/g$,\quad $F_k \leftarrow F_k \backslash S$\\ \> \}\\ \}\\ if ($f \neq 1$) then $F \leftarrow F \cup \{f\}$\\ return $F$ \end{tabbing} \end{al} \begin{pr} アルゴリズム \ref{zassenhaus} は $f$ の既約因子分解を出力する. \end{pr} \proof (a) において, $S$ が真の因子 $G$ の法 $p$ での因子から Hensel 構成に より構成された法 $p^k$ での因子とする. すると, 法 $p^k$ での一意性 により, (b) において $$a/\lc(G)\cdot G \equiv g \bmod p^k.$$ ここで, 系 \ref{mig} および $k$ のとり方により, $$\parallel a/\lc(G)\cdot G\parallel_1 \le 2^{\deg(G)}\parallel f\parallel_2 \le 2^{\deg(f)}\parallel f\parallel_2 < p^k/2.$$ また, $\parallel g \parallel_1\le p^k/2$ より $$\parallel g-a/\lc(G)\cdot G\parallel_1 \le \parallel g \parallel_1+\parallel a/\lc(G)\cdot G\parallel_1 < 2\cdot p^k/2=p^k.$$ 以上により, $a/\lc(G)\cdot G = g$. アルゴリズム \ref{zassenhaus} では, 法 $p$ での因子の個数が小さい順に試しているため, 割り切れた時点で 既約性が成り立つ. \qed このアルゴリズムでは, \begin{center} $g$ が $f$ の因子ならば, $\lc(f)/\lc(g)\cdot g$ は $\lc(f)f$ の因子 \end{center} という簡単な事実が使われている. そして, 予め候補の主係数を $\lc(f)$ に しておけば, もし真の因子ならば, 上記の理由により必ずそれは $\lc(f)f$ を 割り切るのである. さて, 実際にこのアルゴリズムを計算機上で実現する場合, 効率向上のため に注意する点は数多くある. それらのいくつかを述べる. \begin{enumerate} \item $p$ の選択 $f \bmod p$ が無平方でさえあれば, アルゴリズムは進行するが, 有限体上で の因数分解の出力する $\bmod p$ での因子の個数は $p$ により一般に異なる. 特に, ある $p$ に対し $f \bmod p$ が既約ならば $f$ 自身既約と判定でき るが, 他の $f \bmod p$ が既約でない $p$ を選ぶことによって無駄な Hensel 構成をする場合もある. このため, 通常はいくつかの $p$ を選んで有 限体上での因数分解を複数回起動し, 最も因子の個数が少ない$p$ を選ぶ. \item Hensel 構成 ここで述べた Hensel 構成は linear lifting と呼ばれるもので, $p$ の冪が 1 次のオーダでしか増えない. 特に $p$ が小さい場合, 目的の評価値に到達 するのに多くの段数を必要とする. このため, $p$ の冪を 2 次のオーダで上 げていく quadratic lifting というアルゴリズムが考案されている. ただし これは, $\sum_i a_i \prod_{k\neq i}f_k = 1$ における $a_i$ も同時に Hensel 構成しなければならないため, $p^k$ がマシン整数程度のうちは quadratic lifting し, マシン整数を越えたあたりで linear lifting に切替 えるということが行なわれる. \item 試し割り この部分の計算量は最悪で $2^{\deg(f)}$ のオーダとなる. これは, 因子の候補 のあらゆる組合せをとって試し割りを行なっているからである. これを避ける 多項式時間計算量アルゴリズムは Lenstra 等により lattice アルゴリズムと して提案されているが, あくまで漸近計算量における効率化であり, ここでは 述べない. 実際には, この試し割りが使われるため, 一回の試し割りを少しで も高速にすることは重要である. これは, 試し割りの前処理として, \begin{center} $g|f$ ならば, 整数 $a$ に対し $g(a) | f(a)$ \end{center} を利用して, \begin{itemize} \item 定数項どうしの試し割り ($g|f$ ならば $g(0) | f(0)$) \item 係数の和どうしの試し割り ($g|f$ ならば $g(1) | f(1)$) \end{itemize} などによる前処理が考案されており, それぞれ効果を発揮している. \end{enumerate} \section{多変数多項式の因数分解, GCD, 無平方分解} \subsection{一般化された Hensel 構成} 2 変数以上の多項式 (以下, 多変数多項式と呼ぶ) の場合, 因数分解, 無平方 分解, GCD は複雑かつ再帰的に結び付いていて, その全体像を把握するのは容 易ではない. 例えば, 多変数多項式 $f$ の無平方分解は, 原理的には 1 変数 の場合と全く同様に計算できるが, ある主変数を固定した時, 1 変数の時には 単なる整数であった $cont(f)$ が, 多変数の場合には 1 変数少ない多項式と なり, $cont(f)$ の無平方分解が必要となり, また, $cont(f)$ 自身を求める 際に, やはり 1 変数少ない多項式の GCD を実行する必要がある. この事情は 因数分解についても同じである. 多項式の GCD については Euclid の互除法 およびその改良版である PRS 法を用いれば原理的に可能ではあるが, この方 法は, GCD が 1 の場合に最も時間がかかり, かつ実際に現れるほとんどの場 合は GCD が 1 であることを考えると, サブアルゴリズムとして PRS を用い ることは避けたい. これに代わるものとして, 一般化された Hensel 構成があ る. この方法は, 1 変数多項式の因数分解と同様, ある準同型による像から因 子の 「タネ」を求め, それから Hensel 構成により因子の候補を求めるもの である. しかも, この方法は, 「タネ」を求めさえすればその後の計算は 同一であるため, 因数分解に限らず, GCD, 無平方分解にも応用できる. 以下では, $$R = \Z[x_1,\cdots,x_n],\quad I = (x_2-a_2,\cdots,x_n-a_n)$$ ($x_i-a_i$で生成される $R$ のイデアル) とする. $I$ に対し $\phi_I : R \rightarrow \Z[x_1]$ を $$\phi_I(f) = f(x_1,a_2,\cdots,a_n)$$ で定義する. $f \in R$ に対し, $\lc(f)$ は, $x_1$ を主変数とみた時の 主係数を表すとする. \begin{pr}(Moses-Yun{\rm\cite{YUN}}) \label{yun} $f \in R, p \in \Z$ は素数, $$f \equiv \prod_i f_{1i} \bmod {(p^l,I)},\quad f_{1i} \in \Z_{p^l}[x_1],\quad \deg(f) = \sum_i \deg(f_{1i})$$ $f_{1i}$ は GF(p) 上互いに素, $\phi_I(\lc(f)) \neq 0 \bmod p$ とする. この時, 任意 の $k$ に対し, $f_{ki} \in \Z_{p^l}[x_1,\cdots,x_n]$ が存在して, $f \equiv \prod f_{ki} \bmod {(p^l,I^k)}$ かつ $f_{ki} \equiv f_{1i} \bmod {(p^l,I)},\quad \deg(f_{ki}) = \deg(f_{1i}).$ \end{pr} \proof $k$ に関する帰納法で示す. $k$ が 1 の時は正しい. $k$ まで正しいとする. $$f_{(k+1)i}=f_{ki}+h_i\quad (h_i \in (p^l,I^k))$$ なる形を仮定すると, $$\prod_i f_{(k+1)i} \equiv \prod_i f_{ki} + \sum_i h_i\prod_{j\neq i}f_{kj} \bmod {(p^l,I^{k+1})}$$ 一方, $f \equiv \prod_i f_{ki} \bmod {(p^l,I^k)}$ より, $$f = \prod_i f_{ki} + h\quad (h \in (p^l,I^k))$$ と書ける. よって, $$h \equiv \sum_i h_i\prod_{j\neq i}f_{kj} \equiv \sum_i h_i\prod_{j\neq i}f_{1j} \bmod {(p^l,I^{k+1})}$$ となるように, $h_i \in (p^l,I^k), \deg(h_i)\le \deg(f_{1i})$ を決めることができること を示せばよい. \\ $$h = \sum_{\alpha}h_{\alpha}(x_1)\prod_{j\ge 2}(x_j-a_j)^{\alpha_j} \bmod {I^{k+1}}$$ $$h_i = \sum_{\alpha}h_{i \alpha}(x_1)\prod_{j\ge 2}(x_j-a_j)^{\alpha_j} \bmod {I^{k+1}}$$ と書くと, 各係数に対して\\ $$h_{\alpha} \equiv \sum_i h_{i \alpha}\prod_{j\neq i}f_{1j} \bmod {p^l}$$ となるように $h_{i \alpha}$ を選べればよいが, これは, 次の命題により次数の 条件を込めて可能である. \qed \begin{pr} $f_i \in \Z[x]$, $p$ は素数, $p {\not|}\lc(f_i)$, $f_i \bmod p$ は互いに素とする. この時, 任意の $k$, 任意 の $c \in \Z[x]$に対し, $c_i \in \Z[x]$ が存在して, $$\sum_i c_i \prod_{j\neq i}f_j \equiv c \bmod {p^k},\quad \deg(c_i) < \deg(f_i) (i \ge 2).$$ さらに, $\deg(c) < \sum_i \deg(f_i)$ ならば, $\deg(c_1) < \deg(f_1)$ かつ, このような $c_i$ は $p^k$ を法として一意的. \end{pr} \proof $\bmod p$ における条件から, $e_{1i} \in GF(p)[x]$ が存在して, $\sum_i e_{1i} f_i \equiv 1 \bmod p.$ これを再帰的に用いると, 任意の $k$ に対して $e_{ki} \in \Z_{p^k}[x]$ が存在して $\sum_i e_{ki} f_i \equiv 1 \bmod {p^k}.$ 各 $f_i$ の主係数が $p$ で割り切れないことから, $p^k$ を法とす る多項式除算が可能となるから, この式の両辺に $c$ を掛けて, $i \ge 2$ に対し, $c\cdot e_{ki}$ を $f_i$ で割った余りを $c_i$ とし, 残りを $\prod_{j\neq 1}f_j$ の係数にまとめればよい. ここで, $\deg(c) < \sum_i \deg(f_i)$ならば, $\deg(c_1)+\sum_{j\neq 1}\deg(f_i) < \sum_i \deg(f_i)$ より$\deg(c_1) < \deg(f_1)$ で, 一意性は, $k = 1$ における一意性から帰納 法で証明できる. \qed \begin{pr} {\rm 命題 \ref{yun}} において, 主係数が $(p^l,I^k)$ を法として等しい $f_{ki}$ は $(p^l,I^k)$ を法として一意的である. \end{pr} 証明は, 前二つの命題を用いれば, 一変数の場合と同様にできる. \begin{pr}(Gel'fond{\rm\cite{GEL}}) $f \in \C[x_1,\cdots,x_n]$ に対し, 各変数に対する次数を $d_i$ とすると $|f$ の因子の係数$|$ $\le e^{d_1+\cdots+d_n}\cdot \max$($|f$ の係数$|$). \end{pr} \begin{pr} $f \in R$ が無平方ならば, 無限に多くの $I$ に対し $\lc(\phi_I(f)) \neq 0$ かつ $\phi_I(f)$ は無平方. \end{pr} 証明は, $f$ の無平方性が, $f$ と $f'$ の $x_1$ に関する終結式が 0 でな いことと同値であることから明らか. \subsection{多変数多項式の因数分解} 以上により, $R$ における因数分解は次のように行なわれる. \begin{al} \begin{tabbing} \\ Input : $f(x) \in R$; $f$ は無平方かつ $x_1$ について原始的\\ Output : $\{f_1,f_2,\cdots\}$ $f = f_1 f_2 \cdots$ は $f$ の既約分解\\ $a \leftarrow \deg(f) = \deg(f_a(x_1))$ かつ $f_a(x_1)=f(x_1,a_2,\cdots,a_n)$ が 無平方な\\ $a=(a_2,\cdots,a_n) \in \Z^{n-1}$\\ $F_1 \leftarrow \{f_{1i}\} \leftarrow f_a(x_1)$ の $\Z$ 上での既約分解\\ if $|F_1| = 1$ then return $\{f\}$\\ $p \leftarrow f_a(x_1)$ の既約分解で用いた $p$\\ $F_1 = \{f_{11},\cdots,f_{1m}\}$ とする\\ $l \leftarrow 1$\\ $F \leftarrow \emptyset$\\ while \= ( $2l \le m$ ) \{\\ \> $S \leftarrow S \subset F_1$, $|S|=l$ なる新しい部分集合\\ \> if \= $S$ が存在しない then $l \leftarrow l+1$\\ \> else \= \{\\ \>\> $g_1 \leftarrow \prod_{s\in S}s$,\quad $h_1 \leftarrow \prod_{s\in F_1 \backslash S}s$\\ \>\> $g_1 \leftarrow \lc(f_a)/\lc(g_1)\cdot g_1$,\quad $\lc(g_1) \leftarrow \lc(f)$\\ \>\> $h_1 \leftarrow \lc(f_a)/\lc(h_1)\cdot h_1$,\quad $\lc(h_1) \leftarrow \lc(f)$\\ \>\> $B \leftarrow \lc(f)f$ の Gel'fond bound\\ \>\> $l \leftarrow p^l > 2B$ なる整数 $l$\\ \>\> $k \leftarrow f$ の $x_2,\cdots,x_n$ に関する全次数 $+1$\\ \>\> $\lc(f)f_a = g_1 h_1 \bmod {I}$ から $\lc(f)f = g_k h_k \bmod {p^l,I^k}$ なる $g_k, h_k$ を\\ \>\> Hensel 構成で求める.\\ \>\> $g \leftarrow g$ の各係数に $p^l$ の整数倍を加えて絶対値が $p^l/2$ 以下としたもの\\ \>\> if\= $g|\lc(f)f$ \{\\ \>\>\> $g\leftarrow \pp(g)$ (primitive part),\quad $f \leftarrow f/g$,\quad $F_1 \leftarrow F_1 \backslash S$\\ \>\> \}\\ \> \}\\ \}\\ if ($f \neq 1$) then $F \leftarrow F \cup \{f\}$\\ return $F$ \end{tabbing} \end{al} このアルゴリズムを実現する場合, 一変数の場合とは異なる問題がいくつか生ずる. \begin{enumerate} \item {\bf 非零代入問題} Hensel 構成の手順を見ると, $x_i-a_i$ に関する同次成分を取り出す操作が 必要になることがわかる. $a_i$ が全て 0 ならば, 再帰表現された多項式の いくつかの項の取り出しに過ぎないが, 0 でない $a_i$ がある場合, あらかじめ 平行移動により $a_i$ を 0 とするか, 微分, 代入の操作を用いて, 必要な 係数を計算する必要がある. 元の多項式が疎でも平行移動を行なうと密な多項式 となるため, $a_i$ のうち 0 をなるべく多く選びたいが, $a_i$ に対する 条件を満たすためにやむなく 0 でない $a_i$ を用いることがあり得る. \item {\bf 主係数問題} 主係数が 1 でない場合を扱えるよう, 1 変数の場合と同様に, 因子の候補の 主係数を与えられた多項式の主係数と等しくしてある. これにより, Hensel 構成の際に, 不必要な項の増加を押えられるが, 主係数が大きな多項式の場合 必要な Hensel 構成の段数の増加を招く. このため, あらかじめ因子の候補に 対応する主係数を何らかの方法により決めてしまう方法が Wang \cite{WANG} に より提案されている. \item {\bf ニセ因子の問題} ここで述べたアルゴリズムにおいては, 2 つの因子を Hensel 構成するという 手順にしてある. これは, \begin{itemize} \item 多くの因子を同時に Hensel 構成する場合, 主係数をモニックのまま 行なうことは, 不必要な項の増加を招き, 全ての因子の主係数を与えられた 多項式の主係数に合わせることは, Hensel 構成の段数の増加につながる. \item 候補が真の因子のイメージであることを期待している. 真の因子の 場合, 次数の評価で得られる段数より前に候補が安定するので, その時点 で試し割りをして Hensel 構成を切り上げることもできる. \end{itemize} などの理由による. ニセ因子により Hensel 構成を行なった場合, 評価で 得られる段数まで Hensel 構成が進行し, 巨大な候補を生成してしまう. これは, 大きな無駄となるため, 各変数の次数を常にチェックして, 候補のどれかの変数に関する次数が与えられた多項式の次数を越えた時点で Hensel 構成を中断するなどの操作が必要となる. \end{enumerate} ここで述べた方法は, EZ 法と呼ばれ, $n$ 変数を 一変数に落して候補を計算 するものであった. しかし, 一度に一変数に落すことは非零代入問題や, ニセ 因子の出現の確率を大きする. このため, 変数の個数を一つずつ落していく EEZ法 \cite{WANG} が考案された. この方法によれば, 非零代入問題も, 一変 数ずつに対するものになるため項の数が指数的に増加することはなく, 変数を 一つ増やして Hensel 構成を行なう際, ニセ因子は次第に排除されていくため, ニセ因子に対して強いアルゴリズムとなる. \subsection{多変数多項式の無平方分解及び GCD} \label{wangtrager} 一般化された Hensel 構成は, 多変数多項式の無平方分解, GCD にも応用でき る. このとき問題となるのは, Hensel 構成の出発点となる因子 (命題 \ref{yun} の$f_{1i}$) が, 法 $p$ で互いに素であるという条件である. $\GCD(g,h)$ の計算においては, $f_{1i}$ として $$\{\GCD(\phi_I(g),\phi_I(h)),\phi_I(g)/\GCD(\phi_I(g),\phi_I(h))\}$$ をとれれば自然であるが, 一般にこれらが法 $p$ で互いに素であることは期待で きない. しかし, $g$ の既約因子を全て含む無平方因子 $g_s = g/\GCD(g,g')$ を求める際に必要な $g_1=\GCD(g,g')$ は, $$\GCD(g_1,g'/g_1) = 1$$より, $g'$ の因子として, 一般化された Hensel 構 成で計算である. また, 一般に, $g$ が 無平方ならば可能である. よって $\GCD(g_s,h)$ は 一般化された Hensel 構成で計算でき, $\GCD(g,h)$ の既約 因子を全て含む無平方な多項式となり, これを用いて $\GCD(g,h)$ を求めるこ とができる. また, $g_s$ さえ求まれば, $g$ の無平方分解自身も一般化さ れた Hensel 構成で求めることができる. しかし, 無平方分解において, $g$ が重複度の大きい因子を含んでいるとき, $g_s$ の計算に多くの時間がかかる. これを避けるため, 重複度の最も高い 因子から求めていく方法が考案された. これは, 次の命題に基づく. \begin{pr} $f \in K[x]$ に対し, $f = hg^e \quad (h,g \in K[x]),\quad \GCD(h,g)=1$ かつ $g$ が無平方 ならば $g|(d/dx)^{e-1}f$ で $$\GCD(g,((d/dx)^{e-1}f)/g) = 1$$ \end{pr} \proof $e = 1$ のとき明らか. $e\ge 2$ のとき, $(d/dx)^{e-1}(g^e) \equiv e!gg'^{e-1} \bmod{g^2}$ がいえる. よって, $(d/dx)^{e-1}f \equiv h(d/dx)^{e-1}(g^e) \equiv e!hgg'^{e-1} \bmod{g^2}$ となり, $g|(d/dx)^{e-1}f$. さらに, $((d/dx)^{e-1}f)/g \equiv e!hg'^{e-1} \bmod{g}$ で, $\GCD(g,h) = 1$, $\GCD(g,g')=1$ より $\GCD(g,((d/dx)^{e-1}f)/g) = 1.$ \qed \cite{SQFR} のアルゴリズムは, 多変数の場合, まず, 代入により一変数に落した 多項式を無平方分解する. 得られた無平方分解の, 重複度の最も高い因子 $g_0$ と, $f$ の $e-1$ 回微分から, 一般化された Hensel 構成により $f$ の, 重複度 の最も高い因子 $g$ を復元するのである. そして, この Hensel 構成が失敗した 場合には, 代入した値が妥当なものではなかったとして, 値を取り直す. 妥当な値が存在することは, 無平方な多変数多項式に対する妥当な代入値の存在 と同様に言える. この方法のよい点は, \begin{itemize} \item (重複度 -1) だけ多項式の次数が落せる \item 無平方因子を直接求めることができるため, $f$ の既約因子すべての積を求 める場合に比較して計算の手間を減らすことができる \item 全体に対して妥当でない代入でも, 重複度最大の因子には影響がない場合がある. \item ある多項式の冪になっている場合に高速に分解できる. \end{itemize} などがある. さらに, この方法は, 一変数多項式の無平方分解にも応用できる. すなわち, 一変数多項式に対しては, 法 $p$ での無平方分解を用いて整数上 の無平方因子を, 重複度最大の因子から復元していく. この際, 復元方法として は, \cite{SQFR} では中国剰余定理による方法を提案しているが, Hensel 構成 によるものも可能である. 以上, 一般化された Hensel 構成の応用について述べたが, これらを計算機上 にインプリメントすることはかなりの大仕事となる. これは, 最初に述べたよう に, 因数分解, GCD, 無平方分解が再帰的に結合し, かつそれらは様々に付帯状況 の異なる Hensel 構成により計算されなければならない. さらに, これらを 効率よく計算するための種々の工夫を入れれば, プログラムは相当に大きなもの となり, 当然 debug も困難なものになる. \section{代数体上の因数分解} この節では, $K$ を $Q$ の有限次拡大体とし, $K[x]$ における因数分解を考 える. ここで述べるのは, Trager \cite{TRAGER} による, ノルムを用いる方 法である. $K=\Q(\alpha)$ という単拡大に対しては, この他に, Hensel 構成 を用いる方法がいくつか提案されているがここでは述べない. Trager の方法 は, $K(\alpha)$ 上での因数分解を, $K$ 上の因数分解に帰着させるもので, $\Q$ 上の因数分解さえ完備していれば, $K=\Q(\alpha_1,\cdots,\alpha_r)$ 上 での因数分解が可能になる. 以下, $K$ を, その上で多項式因数分解が可能な体, $g \in K[t]$ を $\deg(g) = m$ なる既約多項式, $\alpha$ を $g$ の一つの根とする. $K(\alpha)=K[\alpha]=K[t]/(g)$ である. $L\supset K$ を $g$ の最小分解 体とする. $\alpha_1=\alpha,\alpha_2,\cdots,\alpha_m$ を $g$ の相異なる 根とすると, $L=K(\alpha_1,\cdots,\alpha_m)$ とかける. \begin{df} $f\in K(\alpha)[x]$ に対し, $\Norm(f)$ を $$\Norm(f) = \prod_i f(x,\alpha_i)$$ で定義する. $L/K$ の $\Norm$ の性質 により, $\Norm(f) \in K[x]$. また, $$\Norm(f) = \res_t(f(x,t),g(t)).$$ \end{df} \begin{pr} $f\in K(\alpha)[x]$ が既約ならば, ある既約多項式 $h \in K[x]$ が存在して, $$\Norm(f) = h^l.$$ \end{pr} \proof $\Norm(f) = ab,\quad a,b \in K[x],\quad \GCD(a,b)=1$ と書けたとする. $f | \Norm(f)$ で, $f$ は $K(\alpha)$ 上既約より, $f|a$ としてよい. この 時 $$\Norm(f)|\Norm(a) = a^m.$$よって $\GCD(\Norm(f),b) = 1$ となり, $b|\Norm(f)$ だから, $b=1$. よって, $\Norm(f)$ は 2 つ以上の異なる既約因 子を含み得ない. \qed \begin{co} $f\in K(\alpha)[x]$ が無平方とする時, $\Norm(f)$ が無平方ならば, $\Norm(f) = \prod f_i$ を $K[x]$ における既約分解とするとき, $f = \prod \GCD(f,f_i)$ は $f$ の $K(\alpha)[x]$ における既約分解を与える. \end{co} \proof $h$ を $f$ の $K(\alpha)[x]$ における既約因子とする. $h$ はある $f_i$ を割り切る. $\Norm(h)$ は $K[x]$ の既約多項式の冪で, $\Norm(h)$ は無平方な $\Norm(f)$ を割り切るから, $\Norm(h)$ 自身が $\Norm(f)$ の既約因子. $\Norm(h)$ は $\Norm(f_i)$ の因子でもあるから, $f_i = \Norm(h).$ 今, $h$ と異なる因子 $h_1$ が $f_i$ を割れば, 同様に $f_i = \Norm(h_1)$. $hh_1|f$ より $$\Norm(hh_1)={f_i}^2|\Norm(f).$$ これは $\Norm(f)$ が無平方であることに反する. よって $f_i$ は $f$ のただ一つの 既約因子を含む. \qed 以上により, $\Norm(f)$ が無平方のときには, GCD により $f$ の既約因子が $K[x]$ における既約分解により得られることがわかった. $\Norm(f)$が無平方 でない場合にも, 適当な変数変換により無平方化できることが次の命題より わかる. \begin{pr} $f\in K(\alpha)[x]$ が無平方ならば, $\Norm(f(x-s\alpha))$ が無平方と ならない $s \in K$ は有限個. \end{pr} \proof $f$ の根を $\beta_1,\cdots,\beta_m$ とすると, 仮定よりこれ らは相異なる. すると, $f(x-s\alpha_i)$ の根は, $$\beta_1+s\alpha_i,\cdots,\beta_m+s\alpha_i$$ となる. これより $\Norm(f(x-s\alpha))$ が無平方でないのは, ある $i, j, k, l$ に対して, $$\beta_j+s\alpha_i = \beta_k+s\alpha_l$$ の場合に限る. このような条件を満たす $s$ は有限個しかない. \qed 以上により, 次のアルゴリズムが得られる. \begin{al} \label{trager} \begin{tabbing} \\ Input : 無平方な $f(x,\alpha)\in K(\alpha)[x]$, $s \in \Z$\\ Output : $f$ の $K(\alpha)$ 上の既約因子 $\{f_1,\cdots,f_r\}$\\ again:\\ $r \leftarrow \res_t(f(x-st,t),g(t))$\\ if \= ( $r$ が無平方でない ) then\\ \> $s \leftarrow s+1$; goto again\\ $r(x) = \prod r_i(x)$ : $r$ の $K$ 上での既約分解\\ $z \leftarrow f$\\ for each $i$ do \{\\ \> $f_i \leftarrow \GCD(h(x+s\alpha),z(x,\alpha))$\\ \> $t \leftarrow z/f_i$\\ \} \end{tabbing} \end{al} このアルゴリズムにおいて, ボトルネックとなり得る部分が数多くある. \begin{enumerate} \item 終結式の計算 終結式の計算は, 部分終結式, 行列式の modular 演算などを組み合わせて行な うが, 実際の計算時間を反映する計算量が与えられていないため, アルゴリズ ムの選択が困難である. また, いずれにしても, 終結式の計算は一般に時間が かかり, しかもその終結式が無平方でなければ捨てられるため, そのコストの 大きさは問題である. \item $K$ 上での既約分解 $K$ がまたある拡大体になっている場合にはこのアルゴリズムが再帰的に 用いられることになる. この際, ノルムをとることは, 次数が拡大次数倍 されるため, 因数分解すべき多項式の次数が急速に増大する. 最終的に $\Q$ 上の因数分解を行なうことになるが, $\Q$ 上の因数分解自体のコスト の問題がある. \item $K(\alpha)$ 上での GCD 計算 一般に, 拡大体上での GCD の計算は, 整数上でのそれに比較して極めて困難 である. 特に, Euclid 互除法を用いる場合, 中間式膨張は, 定義多項式 $g$ が大きい場合, 極めて激しい. これをさけるためいくつかの modular 計算法 が提案されている. \end{enumerate} この中で, 2 および 3 は止むを得ない問題であるが, 1 に関しては, 無平方 でないノルムを利用することにより, ある程度回避できる. \begin{pr} $f \in K(\alpha)[x]$ が無平方, $$\Norm(f) = \prod_i {f_i}^{n_i}$$ ($f_i \in K[x]$ は既約, $n_i$ は 1 とは限らない) とすると, $\GCD(f,f_i)$ は $f$ の定数でない因子で, $$f = \prod \GCD(f,f_i).$$ 特に, $\Norm(f)$ の重複度 1 の因子 $f_i$ に対しては, $\GCD(f,f_i)$ は既約. \end{pr} \proof $h$ を $f$ の任意の既約因子とすると, ある $f_i$ が存在して $h|f_i$ より $h | \prod \GCD(f,f_i).$ $f$ は無平方より $f | \prod \GCD(f,f_i).$ $\GCD(f,f_i)$ は互いに素より, $f = \prod \GCD(f,f_i).$ さて, $f$ の 既約因子のノルムはある既約多項式の冪より, 任意の $f_i$ に対して, その適当な冪は $f$ の既約因子のノルムとなっている. よって, $f_i$ は ある $f$ の既約因子を含むので, $\GCD(f,f_i)$ は定数でない. 特に, $f_i$ が $\Norm(f)$ の重複度 1 の因子ならば, それ自身 $f$ のある 既約因子 $h$ のノルムとなる. これは, 前の系と同様にして, $f_i$ は $h$ 以外の因子を含まない \qed この命題により, ノルム (終結式) が, 二つ以上の既約因子を持てば, その分 解は, $f$ の自明でない因数分解を与えることがわかる. もし, ノルムが無平 方でなければ, ここで生成した因子に対し, $s$ を取り直してこのアルゴリズ ムを再帰的に適用することになるが, 問題のサイズは小さくなっている. 特に, ノルム自体が無平方でなくても重複度が 1 の因子に対しては, GCD が既約因 子であることが保証されている. また, ノルムが無平方でない場合にも, $K$ 上での因数分解の前に, 無平方分解によりノルムを分解できるため, $K$ 上の 因数分解の計算時間も短縮できる. この改良を採り入れたアルゴリズムを次に 示す. \begin{al} \label{modtrager} \begin{tabbing} \\ Input : 無平方な $f(x,\alpha)\in K(\alpha)[x]$, $s \in \Z$\\ Output : $f$ の $K(\alpha)$ 上の既約因子 $\{f_1,\cdots,f_r\}$\\ $r \leftarrow \res_t(f(x-st,t),g(t))$\\ $r(x) = \prod r_i(x)^{m_i}$ : $r$ の $K$ 上での既約分解\\ $z \leftarrow f$\\ for \= each $i$ do \{\\ \> $g_i \leftarrow \GCD(r_i(x+s\alpha),z(x,\alpha))$\\ \> if $m_i = 1$ then $g_i$ は既約\\ \> else $(g_i,s+1)$ にこのアルゴリズムを適用\\ \> $t \leftarrow z/g_i$\\ \} \end{tabbing} \end{al} \begin{ex} \cite{ABBOTT} \begin{eqnarray*} f(x) &=& x^{16}-136x^{14}+6476x^{12}-141912x^{10}+1513334x^8-7453176x^6+13950764x^4\\ & & -5596840x^2+46225 \end{eqnarray*} $f(x)$ は $\alpha = \sqrt{2}+\sqrt{3}+\sqrt{5}+\sqrt{7}$ の $\Q$ 上の 最小多項式である. $\Q(\alpha)/\Q$ はガロア拡大であり, $f(x)$ は $\Q(\alpha)$上一次式の積に分解する. この因数分解をアルゴリズム \ref{trager} で求める場合, $F(x)=\Norm(f(x-s\alpha))$ が無平方となる $s\in \Z$ を見つけて $F(x)$ を有理数体上で因数分解する必要があるが, こ のような $F(x)$ は, 全ての素数 $p$ に対し一次または二次式に分解してしまう. 例えば 二次因子の積128 個に分解した場合, 有理数体上の一つの既約因子 (16 次) は, 128 個から 8 個を選んで得られることになるが, これは明らか に組合せ爆発を起こしていて計算不可能である. 一方で, 例えば $s=-1$ の場 合 $F(x)$ は無平方にならないが, 16 個の異なる既約因子が無平方分解 およびそれに続く既約因子分解により容易に得られる. \begin{eqnarray*} F(x) &=& x^{16} (x^2-28)^8 (x^2-20)^8 (x^2-8)^8 (x^2-12)^8\\ & & \cdot (x^4-64x^2+64)^4 (x^4-40x^2+16)^4\\ & & \cdot (x^4-80x^2+256)^4 (x^4-56x^2+144)^4\\ & & \cdot (x^4-72x^2+400)^4 (x^4-96x^2+64)^4\\ & & \cdot (x^8-240x^6+12512x^4-203520x^2+891136)^2\\ & & \cdot (x^8-192x^6+8576x^4-110592x^2+102400)^2\\ & & \cdot (x^8-224x^6+11264x^4-143360x^2+409600)^2\\ & & \cdot (x^8-160x^6+5632x^4-61440x^2+147456)^2\\ & & \cdot (x^{16}-544x^{14}+103616x^{12}-9082368x^{10}+387413504x^8-7632052224x^6\\ & & +57142329344x^4-91698626560x^2+3029401600) \end{eqnarray*} これらの各因子から $f(x)$ の全ての一次因子が得られる. 一般に, 最小分解体を求めるための因数分解など, 多項式を, その根を添加した 体上で因数分解する場合に アルゴリズム \ref{modtrager} が有効となる場合がある. \end{ex} \section{応用 --- 有理関数の不定積分} 代数体上の GCD を用いて, 有理関数の不定積分を, 積分記号を含まない形 で表示する方法について述べる. 一般に, 有理関数 $f(x)=n(x)/d(x)$ ($n,d \in \Q[x]$) の不定積分は, $f$ の部分分数分解により計算できる. しかし, そのために分母 $d$ を 1 次因子の積に分解するには $d$ の最小分解体を求めることが必要となる. また, 不定積分自体に, $d$ の分解により現れた代数的数が現れるとは 限らない. \begin{ex} $f=d'/d$ ならば $\displaystyle \int f dx = \log d.$ \end{ex} このことから, 最小の代数的数の添加で不定積分を表示することを考える. \subsection{有理部分の計算} $f=n/d$, $n,d \in \Q[x]$ とする. もし $\deg(n)\ge \deg(d)$ ならば, $$n = qd+r, \quad q,d \in \Q[x], \deg(r) < \deg(d)$$ により, $f=q+r/d$ と書ける. このとき $\int f dx = \int q dx + \int r/d dx$ で, 多項式の不定積分は自明だから, あらかじめ $\deg(n) < \deg(d)$ としてよい. \begin{pr} $\deg(n)<\deg(d)$ とする. $d_r = \GCD(d,d')$, $d_l = d/d_r$ とおくと, $\deg(n_r)<\deg(d_r)$, $\deg(n_l)<\deg(d_l)$ なる $n_r, n_l \in \Q[x]$ が一意 的に存在して, $$\int {n\over d} dx = {{n_r}\over {d_r}} + \int {{n_l}\over{d_l}} dx$$ \end{pr} \proof $d=\prod_i d_i^i$ なる無平方分解に対応して, $${n\over d} = \sum_i \sum_j {{n_{ij}}\over{d_i^j}}\quad (\deg(r_{ij}) < \deg(d_i))$$ なる部分分数分解が命題 \ref{parfrac} により存在する. $d_r=\prod_i d_i^{i-1}$, $d_l=\prod_i d_i$ である. $d_i$ は無平方だから, $\GCD(d_i,d_i')=1.$ よって, 各 $n_{ij}$ に対し, $s_{ij}, t_{ij} \in \Q[x]$ ($\deg(s_{ij})< \deg(d_i)-1$, $\deg(t_{ij})< \deg(d_i)$) が存在して, $$s_{ij}d_i+t_{ij}d_i'=n_{ij}.$$ これを用いて, $j>1$ のとき $$\int {{n_{ij}}\over{d_i^j}} dx = \int {{s_{ij}}\over {d_i^{j-1}}}dx + \int {{t_{ij}d_i'}\over {d_i^j}}dx$$ ここで, $$({1\over {1-j}}\cdot {1\over{d^{j-1}}})'={{d_i'}\over {d_i^j}}$$ より, $$\int {{t_{ij}d_i'}\over {d_i^j}}dx= {1\over {1-j}}\cdot {1\over{d_i^{j-1}}}\cdot t_{ij} - \int {1\over {1-j}}\cdot {1\over{d_i^{j-1}}} t_{ij}' dx.$$ よって $$\int {{n_{ij}}\over{d_i^j}} dx = {t_{ij}\over {(1-j)d_i^{j-1}}} +\int {{s_{ij}+{{t_{ij}'}\over{j-1}}}\over {d_i^{j-1}}} dx$$ $\deg({s_{ij}+{{t_{ij}'}\over{j-1}}}) < \deg(d_i)-1$ より, この積分の第 2 項を $\int {{n_{i,j-1}}\over{d_i^{j-1}}}dx$ に加えても, 分子の次数は増大しない. よって, この操作を $j>1$ なる項に対して繰り返す ことにより, $$\int {n\over d}dx = \sum_i\sum_{j>1}{t_{ij}\over {(1-j)d_i^{j-1}}} +\sum_i \int {{u_i}\over {d_i}} dx \quad (\deg(u_i)<\deg(d_i))$$ なる形に変形できる. 第 1 項, 第 2 項の披積分関数をまとめて それぞれ ${{n_r}\over {d_r}}$, ${{n_l}\over{d_l}}$ とおけば次数の 条件を満たす. 一意性は明らか. \qed この命題で保証された $n_r$, $n_l$ は, 未定係数法で決定することができる. \begin{al} \begin{tabbing} \\ Input: $f(x)=n(x)/d(x)\in \Q(x)$, $\deg(n)<\deg(d)$\\ Output: $\displaystyle \int f(x)dx = {{n_r(x)}\over{d_r(x)}}+\int {{n_l(x)}\over{d_l(x)}}dx$, $d_l$ は無平方で $n_r, d_r, n_l, d_l \in \Q[x]$ なる分解\\ ただし $\deg(n_r)<\deg(d_r)$, $\deg(n_l)<\deg(d_l)$\\ $d_r \leftarrow \GCD(d,d')$, \quad $d_l \leftarrow d/d_r$\\ $m_r \leftarrow \deg(d_r)$, \quad $m_l \leftarrow \deg(d_l)$\\ $n_r \leftarrow \sum_{i=0}^{m_r-1}a_i x^i$, \quad $n_l \leftarrow \sum_{i=0}^{m_l-1}b_i x^i$\\ $n=n_r'd_l-({{d_ld_r'}\over{d_r}})n_r+d_rn_l$ から $a_i$, $b_i$を求める\\ return $\displaystyle \int f(x)dx = {{n_r(x)}\over{d_r(x)}}+\int {{n_l(x)}\over{d_l(x)}}dx$ \end{tabbing} \end{al} \subsection{対数部分の計算} $f(x)=n(x)/d(x)$, $\GCD(n,d)=1$, $\deg(n)<\deg(d)$ で $d$ は無平方とする. このとき $$\int f dx = \sum_i c_i\log r_i$$ と書ける. 一般に $c_i \in \Q, r_i \in \Q[x]$ とは限らず, 何らかの代数的数を含む 可能性があるが, この代数拡大を最小限にするような表示を求めたい. \begin{pr}(Rothstein{\rm\cite{DAV}}) $K$ を複素数体 $\C$ の部分体とし, $f(x)=n(x)/d(x)$, $n,d \in K[x]$, $\GCD(n,d)=1$, $\deg(n)<\deg(d)$ で $d$ は無平方, 無平方とする. このとき, $$n/d = \sum_{i=1}^n c_i v_i'/v_i$$ ただし $c_i \in \C$ は相異なり, $v_i \in \C[x]$, $v_i$ はモニック, 無平方で互いに素, と書けたならば, $c_i$ は $$R(z)=\res_x(n-zd',d) \in K[z]$$ の根で, $$v_i=\GCD(n-c_id',d).$$ \end{pr} \proof \underline{claim 1} $v=d.$ $v=\prod_{i=1}^n$ とおくと, $$nv = d\sum_{i=1}^nc_iv_i'(v/v_i).$$ $\GCD(n,d)=1$ より $d|v.$ 一方で, $v_i|$右辺より, もし $v_i{\not |}d$ ならば $v_i|c_iv_i'(v/v_i)$ となるが, これは $v_i$ に関する条件より不可能. よって $v_i|d.$ 結局 $v|d$ となり $v=d.$ \qed\\ \underline{claim 2} $v_i=\GCD(n-c_id',d).$ claim 1 より $n = \sum_{i=1}^n c_iv_i'(v/v_i).$ $d'=\sum_{i=1}^n v_i'(v/v_i)$ より, $$n-c_id'=\sum_{j\neq i} (c_j-c_i)v_j'(v/v_j).$$ これから $v_i | n-c_id'$ がわかる. よって $v_i | \GCD(n-c_id',d).$ 一方で, $j\neq i$ のとき, $$\GCD(n-c_id',v_j)=\GCD((c_j-c_i)v_j'(v/v_j),v_j)=1$$ より, $v_i=\GCD(n-c_id',d).$ \qed claim 2 より, $c_i$ が $R(z)$ の根でなければならないこともわかる. \\ \underline{claim 3} $\{c_1,\cdots,c_n\} = R(z)$ の根全体 $c$ が $R(z)$ の根ならば, $v_0=\GCD(n-cd',d)$ は自明でない $d$ の因子. よって $v_0$ の既約因子 $g$ を一つとれば, ある $v_i$ が存在して $g|v_i.$ $$g|(n-cd')=\sum_{j=1}^n (c_j-c)v_j'(v/v_j)$$ より, $g|(c_i-c)v_i'(v/v_i).$ これは $c_i=c$ のときのみ可能. \qed \begin{co} $K$ を複素数体 $\C$ の部分体とし, $f(x)=n(x)/d(x)$, $n,d \in K[x]$, $\GCD(n,d)=1$, $\deg(n)<\deg(d)$ で $d$ は無平方, モニックとし, $$R(z)=\res_x(n-zd',d) \in K[z]$$ とする. $K_R$ を $R(z)$ の最小分解体とすれば, $K_R$ が $\int n/d dx$ を表示するための最小の $K$ の拡大. \end{co} \proof $F$ を $K$ の拡大体とし, $c_i \in F$, $v_i \in F[x]$ による $n/d = \sum_i c_i v_i'/v_i$ なる表示をとると, 体の拡大なしに, 前命題の $c_i$ $v_i$ に対する条件が満たされるようにできる. このとき, $c_i$ は $R(z)$ の根で $c_i \in F$ だから, $K_R \subset F$. $K_R$ 上でこの表示 ができることは前命題で保証されている. \qed