% $OpenXM: OpenXM/doc/Papers/rims-2002-noro-ja.tex,v 1.2 2002/12/06 09:23:42 noro Exp $ \documentclass[theorem]{jarticle} \usepackage{jssac} \def\HT{{\rm HT}} \def\HC{{\rm HC}} \def\GCD{{\rm GCD}} \def\tdeg{{\rm tdeg}} \def\pp{{\rm pp}} \def\lc{{\rm lc}} \def\Z{{\bf Z}} \title{有限体上の多変数多項式の因数分解について (その 2)} \author{野呂 正行 (神戸大・理)} \begin{document} \maketitle \section{はじめに} 本稿では, \cite{funny01} で述べた, 有限体上での 2 変数多項式の因数分解 を基礎として, 一般の多変数多項式の GCD, 無平方分解, 因数分解アルゴリズム およびその実装について述べる. \section{多変数多項式の無平方分解と GCD} 現在 Risa/Asir で用いているアルゴリズムは, 以下に述べるように, Bernardin の無平方分解アルゴリズム \cite{B97-2} を modify したものである. $F$ を標数 $p$ の有限体とし, $f \in F[x_1,\ldots,x_n]$ と する. $'$ が $d/dx_1$ を表すとする. $$f = FGH, F=\prod f_i^{a_i}, G=\prod g_j^{b_j}, H=\prod h_k^{c_k}$$ ($f_i, g_j, h_k$ は無平方, 互いに素で, $f_i' \neq 0$, $p \not{|}a_j$, $p | b_j$, $h_k' = 0$) と書くと $f' = F'GH$ が成り立つ. すると $$\GCD(f,f') = \GCD(F,F')GH$$ で, $\GCD(F,F') = \prod f_i^{a_i-1}$ だから $$f/\GCD(f,f')=\prod f_i.$$ $\prod f_i$ で $f$ を繰り返し割り, 割り切れなくなった 段階で, その商と $\prod f_i$ の GCD を計算することで, $F$ 中の重複度最小の因子 $f_1$ が求まる. これを繰り返すと $F$ が全て無平方分解できる. 残りの $f$ は $f = GH$ と書ける. ここで $f' = 0$ が 成り立つことに注意する. 以上の手続きを 各 $x_i$ について繰り返して残った $f$ は, $$df/dx_1 = \ldots = df/dx_n = 0$$ を満たす. これは, 全ての指数が $p$ で割り切れることを意味する. すると, $F$ は標数 $p$ の 有限体だから, $f = g^p$ と書けることになる. この $g$ に対して, 以上の手続きを再帰的に適用する ことで, $f$ の無平方分解が得られる. このアルゴリズムにおいて, $g=\GCD(f,f')$ の計算が必要となる. 標数が 0 の場合, $\GCD(g,f'/g)=1$ が 保証されるため, この計算に多変数の Hensel 構成を用いることができる. しかし, 正標数の場合には, $\GCD(g,f'/g) = \GCD(\GCD(F,F')GH,F'/\GCD(F,F'))$ となり, 因子 $GH$ の存在のため, この GCD が 1 とは限らない. このため, やむなく Brown のアルゴリズム (中国剰余定理による GCD の計算) を用いている. \begin{tabbing} GCD の計算 \\ 入力 : $f_1,\ldots,f_m \in K[X]$ ($K$ は体, $X$ は変数の集合)\\ 出力 : $\GCD(f_1,\ldots,f_m)$\\ $y \leftarrow$ 適当な変数; $Z \leftarrow X\setminus \{y\}$\\ $< \leftarrow K[Z]$ の適当な項順序; 以下 $f_i \in K[y][Z]$ とみなす\\ $h_i(y) \leftarrow \HT_<(f_i)$; $h_g(y) \leftarrow \GCD(h_1,\ldots,h_m)$\\ $g \leftarrow 0$; $M \leftarrow 1$\\ do \= \\ \> $a \leftarrow $ 未使用の $K$ の元\\ \> $g_a \leftarrow \GCD(f_1|_{y=a},\ldots,f_m|_{y=a})$\\ \> if \= $g \neq 0$ かつ $\HT_<(g) = \HT_<(g_a)$ then \\ \> \> $adj \leftarrow \cdot h_g(a)/\HC_<(g_a)\cdot g_a - g(a))$\\ \> \> if \= $adj = 0$ かつ, すべての $f_i$ に対し $g | hg\cdot f_i$ then \\ \> \> \> return $\pp(g)$\\ \> \> endif\\ \> \> $g \leftarrow g+adj \cdot M(a)^{-1} \cdot M$; $M \leftarrow M\cdot (y-a)$\\ \> else if $\tdeg(\HT_<(g)) > \tdeg(\HT_<(g_a)$ then \\ \> \> $g \leftarrow g_a$; $M \leftarrow y-a$\\ \> else if $\tdeg(\HT_<(g)) = \tdeg(\HT_<(g_a))$ then \\ \> \> $g \leftarrow 0$; $M \leftarrow 1$\\ \> endif\\ end do \end{tabbing} $\HT$ は頭項, $\HC$ は頭係数, $\tdeg$ は全次数, $\pp$ は原始的部分 を表す. このアルゴリズムでは, $f_1, \ldots, f_m$ に対し, ある変数 $y$ にさまざまな 値 $a$ を代入してGCD $g_a$ を計算し, それらを中国剰余定理で結合する. その際, 残りの変数 $Z$ に関して適当な項順序 $<$ を設定し, その項順序に関する頭 項が等しい間は, 真の GCD の正しい射影になっていると 仮定する. それまでと異なる頭項を持つ $g_a$ が得られた場合, その頭項の全次数が, それまでの頭項の全次数より真に大きい場合には, 明らかに正しくないので, 捨てる. また, 真に小さい場合には, これまで の結果は正しくないことになり, 新たに $g_a$ からリスタートする. もし, 全次数が等しければ, 両方の結果が正しくないことになり, 両方を捨ててリスタートする. また, 真の GCD の $<$ に関する頭係数が $f_i$ の頭係数の GCD である $h_g$ の因子になっていることを用い, 中国剰余定理を 適用する際, 頭係数が $h_g$ になるように調節している. 新たな $a$ で得た $g_a$ と, これまで得た $g$ の $a$ での値が 等しい場合に, 実際に $g$ が $h_gf_i$ をすべて割り切るかチェックを 行っている. 実際の実装においては, 適当な $f_i$ を選んでおき, cofactor のほうも中国剰余定理で構成していき, そちらでも割算チェック を行うことで, GCD, cofactor いずれかが復元できた時点でアルゴリズム が終了できる. このアルゴリズムでは, GCD の $y$ に関する次数より多い $K$ の元が必要 になる. $K$ の位数がこれに満たない場合には, $K$ を拡大する. これに ついては後で述べる. \section{無平方多項式の因数分解} 以下, $f \in K[X]$ は無平方とする. $f$ の因数分解は次のように行う. \subsection{主変数 $x$ の選択} $f$ の因数分解は, ある変数 $x$ 以外の変数に適当な値を代入して得られた $x$ の一変数多項式の因数分解をタネから順次 Hensel 構成により計算する (EZ 法). $x$ は, $x$ に関する微分が消えないように選ぶ必要がある. また, $x$ に関する次数が大きい程, タネとなる因子の数が大きくなる可能性が あるため, なるべく次数が小さいような $x$ を選んでいる. \subsection{従変数 $y$ の選択} 従変数とは妙な用語であるが, ここでは, 多変数の因数分解を, 2 変数の因数 分解から Hensel 構成により得るため, そのための変数をもう一つ選んでおく 必要がある. すなわち, ある変数 $y$ を選び, $x$, $y$ 以外の変数に 適当な値を代入した 2 変数多項式の因数分解を \cite{funny01} で述べた 方法により計算する. それを基に, 残りの変数に関して Hensel 構成を 行う. ここで, Hensel 構成は $K[X] = K[y][x,Z]$ ($Z=X\setminus\{x,y\} = \{z_1,\ldots,z_{n-2}\}$) とみなして 行う. すなわち, 一変数多項式環 $K[y]$ を, 有理数体上の多変数多項式 の因数分解における, 整数環の類似とみなすわけである. こうすることに より, 1 変数の分解から出発した場合に生ずる大量のニセ因子による困難を 避けることができる. あとで示すように, Hensel 構成自体も, 整数上の 場合の類似の方法により行うことができる. \subsection{2 変数の因数分解} $x$, $y$ が決まったら, $f_a(x,y) = f(x,y,a)$ が, 無平方になるように $Z$ に代入する値のベクトル $a = (a_1,\ldots,a_{n-2}) \in K^{n-2}$ を選び, $f_a$ を因数分解する. ここで, $f_a$ の $x$ に関する主係数 (これは $y$ の多項式) の定数項が 0 でなく, かつ $f_a|_{y=0}$ が無平方であるよう, 必要があれば $y\rightarrow y+c$ という平行移動を行う. \subsection{$K[y]$ 上での Hensel 構成 (前処理)} $f_a(x,y)$ の因数分解の結果より, 因子を 2 組にわけ $f_a(x,y) = g_0(x,y)h_0(x,y)$ とした上で, $K[y]$ 上で Hensel 構成を 行う. この際, 問題となるのが $g_0$, $h_0$ の $x$ に関する主係数の 決め方である. いわゆる主係数問題を回避するために, 真の因子の主係数 となるべく近いものをあらかじめ固定しておくのがよい. 少なくとも, それは, $f$ の, $x$ に関する主係数 $\lc_x(f)$ の因子ではあるが, $\lc_x(f)$ そのものをとることは一般に overestimate である. 有理数体上の場合, P. S. Wang により主係数の決定方法が提案されて いるが, ここでは次のように見積もる: \begin{enumerate} \item $\lc_x(f) = \prod u_i^{n_i}$ と因数分解する ($u_i \in K[y,Z]$ : 既約). \item 各 $i$ に対し, $u_i(a) \in K[y]$ が $\lc_x(g_0)$ を割り切る回数を 数える. それを $m_i$ としたとき, $\lc_g = \prod u_i^{m_i}$ とする. 同様に $h_0$ に対しても $\lc_h$ を求める. もし, $\lc_x(g_0) \not{|}\, \lc_g(a)$ または $\lc_x(h_0) \not{|}\, \lc_h(a)$ または, $\lc_x(f) \not{|}\, \lc_g \cdot \lc_h$ ならば, それは, $f_a$ の因子の組合せが正しくないことを意味するので, $g_0$, $h_0$ をとり直す. \item $g_0 \leftarrow \lc_g(a)/\lc_x(g_0)\cdot g_0$ の主係数を $\lc_g$ で置き換えたもの $h_0 \leftarrow \lc_h(a)/\lc_x(h_0)\cdot h_0$ の主係数を $\lc_h$ で置き換えたもの $f \leftarrow \lc_g\cdot \lc_h/\lc_x(f) \cdot f$ とする. この時, $f = g_0h_0$ となっている. \end{enumerate} この段階で, もし $g_0$ が真の因子の射影となっていれば, Hensel 構成 により, $f$ の因子に持ち上るはずであり, $\lc_x(g_0)$ は既に, 真の因子 の主係数に等しくなっている. この場合, $h_0$ も同様の性質を満たす. \subsection{$K[y]$ 上での Hensel 構成} 前項により, $f=g_0h_0$ において, $g_0$ が正しい因子の射影ならば, $\lc_x(g_0)$ は 既に真の因子の主係数に等しい. ここでは, $g_0$, $h_0$ から $K[y]$ 上の Hensel 構成により, $f=g_kh_k \bmod I^{k+1}$, ただし $I = $, となる $g_k$, $h_k$ を EZ 法に より計算する. まず, $z_i \rightarrow z_i+a_i$ なる平行移動により, $I=$ としておく. 通常の EZ 法では, 係数に分数が 現れるのを避けるため, 因子の係数の大きさの評価から定められる, ある大きな素数巾 $p^l$ を法として $\Z/(p^l)$ 上で計算する. ここでは, $f$ の $y$ に関する次数を越える整数 $d$ に対し, $K[y]/(y^d)$ での演算を導入することで, $K[y]$ での商体での演算を避ける. すなわち, $u g_0(a)+v h_0(a)=1 \bmod y^d$ となる $u, v \in K[y]$ を 計算しておき, Hensel 構成の係数の計算は $u, v$ を用いて $\bmod\, y^d$ で行うのである. このとき, $f = g_kh_k \bmod (I^{k+1},y^d)$ だが, $d$ が十分大きいため, $g_0$ が真の因子の射影ならば, Hensel 構成の一意 性により, 十分大きい $k$ に対し $f = g_kh_k$ となる. $u$, $v$ の計算は, $g_0(a)|_{y=0}$, $h_0(a)_{y=0}$ が互いに素であることを利用して, やはり Hensel 構成により計算できる. $K[y]$ 上の Hensel 構成は次のように行う. \begin{enumerate} \item $f-g_{k-1}h_{k-1} = \sum_t F_t t \bmod (I^k,y^d)$ と書く. ここで $t \in I^k$ は単項式, $F_t \in K[y][x]$. \item $G_th_0+H_tg_0 = F_t \bmod y^d$ となる $G_t, H_t \in K[y][x]$ を計算する. これは $u$, $v$ を使って作れる. \item $g_{k+1} \leftarrow g_k + \sum_t G_t t$, $h_{k+1} \leftarrow h_k + \sum_t H_t t$ とすれば $f = g_{k+1}h_{k+1} \bmod (I^{k+1},y^d)$. \end{enumerate} この操作において, $\sum_t G_t t$ または $\sum_t H_t t$ が 0 となった場合に $g_k$ または $h_k$ で $f$ を割ってみることで, 次数の上限まで Hensel 構成 せずに, 真の因子を検出することができる. \section{実装について} \subsection{有限体の表現について} ここで述べた各アルゴリズムにおいては, 係数体の位数が十分大きい必要があ る. \cite{funny01} で述べたように, 代入する点の数が不足する場合のため に, 代数拡大しても計算効率が落ちないような, 原始根を用いた表現を実装し, その有効性を示した. 欠点としては, この表現において, 実用的な 位数が $2^{16}$ 程度に限られることであった. 今回, その改良として, 標数 が $2^{14}$ 以下の場合には, 原始根表現を許し, それ以上の場合には, 通常の 表現をとることにした. これは, 後者では実用上十分に代入する点が得られる からである. これにより, 位数が $2^{29}$ 程度までの素体上で, 多変数多項式 の因数分解が行えるようになった. \subsection{係数環としての $K[y]/(y^d)$ について} Hensel 構成においては, $K[y]/(y^d)$ を, 多項式の係数環として 扱う必要がある. Asir においては, 既に, 小位数有限体 $K$ の代数拡大 を表現する型があるが, これは, $K[y]/(m(y))$ ($m(y)$ は最小多項式) として表現されているため, $m(y)=y^d$ とすれば, 加減乗算は流用 できる. また, 除算に現れる逆元計算については, 0 でない定数項を持つ 多項式で表現される元に限れば, それは $y^d$ と互いに素なので 逆元を持ち, 互除法で計算できる. 既に述べたように, $x$ に関する主係数 が 0 でない定数項を持つように平行移動してあるので, $K[y]/(y^d)$ の 計算を, ここで述べた方法で行うことができる. 多変数多項式は, Hensel 構成の最初で, この 型の係数を持つ多項式に変換される. あらかじめ $d$ をセットして おくことにより, 演算は自動的に $\bmod \, y^d$ されるため, 通常の多項式演算の呼び出しを行うだけで, $K[y]/(y^d)$ 係数の 多項式演算が実行できる. \section{タイミングデータ} 有限体上の多変数多項式の因数分解を提供しているシステムは数少ない. 筆者の知る唯一のものは Maple なので, Maple と比較を行う. Maple は, この機能に関しては, kernel において専用の特殊なデータ型を多用して 効率を上げているため, 比較することはアンフェアではないと考える. \section{おわりに} 今後の予定として, 次のようなことを考えている. \begin{itemize} \item 正標数の準素分解 \item 体の位数が足りない場合に, 自動的に基礎体を拡大する \item 各部分の効率化 \end{itemize} \begin{thebibliography}{99} \bibitem{B97-2} Bernardin, L. (1997). On square-free factorization of multivariate polynomials over a finite field. {\em Theoret.\ Comput.\ Sci.\/} {\bf 187}, 105--116. \bibitem{funny01} M. Noro and K. Yokoyama (2002). Yet Another Practical Implementation of Polynomial Factorization over Finite Fields. Proceedings of ISSAC2002, ACM Press, 200--206. \end{thebibliography} \end{document}