% $OpenXM: OpenXM/doc/Papers/rims2002-noro.tex,v 1.2 2002/12/09 04:23:05 noro Exp $ \documentclass{slides} \usepackage{color} \usepackage{rgb} \usepackage{graphicx} \usepackage{epsfig} \newcommand{\qed}{$\Box$} \newcommand{\mred}[1]{\smash{\mathop{\hbox{\rightarrowfill}}\limits_{\scriptstyle #1}}} \newcommand{\tmred}[1]{\smash{\mathop{\hbox{\rightarrowfill}}\limits_{\scriptstyle #1}\limits^{\scriptstyle *}}} \def\gr{Gr\"obner basis } \def\st{\, s.t. \,} \def\ni{\noindent} \def\ve{\vfill\eject} \textwidth 9.2in \textheight 7.2in \columnsep 0.33in \topmargin -1in \def\tc{\color{red}} \def\fbc{\bf\color{MediumBlue}} \def\itc{\color{brown}} \def\urlc{\bf\color{DarkGreen}} \def\bc{\color{LightGoldenrod1}} \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{\tc 小標数有限体上の多変数多項式の因数分解について (その 2)} \author{野呂 正行 (神戸大・理)} \begin{document} \large \setlength{\parskip}{0pt} \maketitle \begin{slide}{} \begin{center} \fbox{\fbc \large 無平方分解 (復習)} \end{center} modification of Bernardin's algorithm [Ber97] $f \in F[x_1,\ldots,x_n]$, $F$ : 有限体 $Char(F) = p$ $f = FGH$, where $F=\prod f_i^{a_i}$, $G=\prod g_j^{b_j}$, $H=\prod h_k^{c_k}$ $f_i, g_j, h_k$ : 無平方, 互いに素. $'$ を $d/dx_1$ として $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$ を繰り返し割ることで, $f_1$ (重複度最小) が求まる $\Rightarrow$ $F$ が全て分解できる \end{slide} \begin{slide}{} \begin{center} \fbox{\fbc \large 無平方分解 (つづき) } \end{center} 残り $f = GH$ で, $f' = 0$ これを $x_i$ について繰り返して残った $f$ $\Rightarrow$ $df/dx_1 = \ldots = df/dx_n = 0$ $\Rightarrow$ これは, 全ての指数が $p$ で割り切れることを意味する $\Rightarrow$ $F$ は有限体だから $f = g^p$ と書ける $\Rightarrow$ $g$ に対してアルゴリズムを適用 \end{slide} \begin{slide}{} \begin{center} \fbox{\fbc \large 実装上の困難 : $\GCD(f,f')$ の計算} \end{center} 標数が 0 の場合 $\GCD(g,f'/g)=1$ $\Rightarrow$ 多変数の Hensel 構成が 使える 正標数の場合 $$\GCD(g,f'/g) = \GCD(\GCD(F,F')GH,F'/\GCD(F,F'))$$ $\Rightarrow$ $GH$ の存在のため GCD が 1 とは限らない. $\Rightarrow$ やむなく Brown のアルゴリズム (中国剰余定理による GCD の 計算) を用いている. \end{slide} \begin{slide}{} \begin{center} \fbox{\fbc \large GCD の計算} \end{center} \begin{tabbing} 入力 : $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 h_g(a)/\HC_<(g_a)\cdot g_a - g(a)$ \end{tabbing} \end{slide} \begin{slide}{} \begin{tabbing} do \= if \= \kill \> \> if \= $adj = 0$ かつ, すべての $f_i$ に対し $g | h_g\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} \end{slide} \begin{slide}{} \begin{center} \fbox{\fbc \large 二変数への帰着} \end{center} \begin{itemize} \item 主変数 $x$ の選択 $x$ に関する微分が消えないように選ぶ. \item 従変数 $y$ の選択 $K[x,y]$ で因数分解して, $Z=X\setminus \{x,y\}$ に関して Hensel 構成 (一変数まで落すとニセ因子が大量発生) \item それ以外の変数 $Z$ への代入値の選択 $f_a(x,y) = f(x,y,a)$ が無平方になるように選ぶ. さらに, $f_a|_{y=0}$ も無平方になるように, $y\leftarrow y+c$ と 平行移動. \end{itemize} \end{slide} \begin{slide}{} \begin{center} \fbox{\fbc \large $K[y]$ 上での Hensel 構成 (前処理)} \end{center} $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$ に関する主係数の決め方 主係数問題の回避 : 真の因子の主係数となるべく近いものをあらかじめ固定 真の因子の主係数は $\lc_x(f)$ の因子であることを使った見積り \end{slide} \begin{slide}{} \begin{center} \fbox{\fbc \large 主係数の見積り} \end{center} \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} \end{slide} \begin{slide}{} \begin{center} \fbox{\fbc \large $K[y]$ 上での Hensel 構成} \end{center} $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 = \langle z_1-a_1,\ldots,z_{n-2}-a_{n-2} \rangle$). $z_i \rightarrow z_i+a_i$ なる平行移動により, $I=\langle z_1,\ldots,z_{n-2} \rangle$ 通常の EZ 法 : $\Z/(p^l)$ で計算 (係数に分数が現れるのを避ける) 今回の実装 : $\deg_y(f) > d$ なる $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 構成は $\bmod\, y^d$ で行う. \end{slide} \begin{slide}{} \begin{center} \fbox{\fbc \large Hensel 構成} \end{center} $f = g_kh_k \bmod (I^{k+1},y^d)$ だが, 十分大きい $k$ に対し $f = g_kh_k$ $u$, $v$ の計算 : Hensel 構成 ($g_0(a)|_{y=0}$, $h_0(a)_{y=0}$ が互いに素) $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 = 0$ または $\sum_t H_t t = 0$ $\Rightarrow$ 試し割り $g_k$ または $h_k$ で $f$ を割ってみることで, 次数の上限まで Hensel 構成 せずに, 真の因子を検出できる. \end{slide} \begin{slide}{} \begin{center} \fbox{\fbc \large 有限体の表現について} \end{center} 各アルゴリズムにおいて, 係数体の位数が十分大きい必要あり. 代入する点の数が不足する $\Rightarrow$ 代数拡大 計算効率が落ちないよう, 原始根を用いた表現を実装 欠点 : 実用的な位数が $2^{16}$ 程度に限られる 改良 : 標数が $2^{14}$ 以下の場合には, 原始根表現 それ以上の場合には, 通常の表現 (実用上十分に代入する点が得られるから) $\Rightarrow$ 位数が $2^{29}$ 程度までの素体上で, 多変数多項式 の因数分解が可能 \end{slide} \begin{slide} \begin{center} \fbox{\fbc \large 係数環としての $K[y]/(y^d)$ について} \end{center} Hensel 構成において $K[y]/(y^d)$ を係数環として扱う Asir : 小位数有限体 $K$ の代数拡大を表現する型 (GFSN) がある $K[y]/(m(y))$ として表現 $\Rightarrow$ $m(y)=y^d$ として流用 逆元計算については, 0 でない定数項を持つ多項式は可逆 (互除法) $\lc_x \neq 0$ より $K[y]/(y^d)$ がこの方法でできる. 多変数多項式 : Hensel 構成の最初で, この型の係数を持つ多項式に変換 $d$ をセットしておく $\Rightarrow$ 結果は自動的に $\bmod \, y^d$ される $\Rightarrow$ 通常の多項式演算により $K[y]/(y^d)$ 係数の 多項式演算が実行できる. \end{slide} \begin{slide}{} \begin{center} \fbox{\fbc \large Timing data (Wang の例)} \end{center} {\tt OpenXM\_contrib2/asir2000/lib/fctrdata} の {\tt Wang[1],\ldots,Wang[15]} でテスト. マシン : Athlon 1900+ Maple7 と比較 --- Maple7 も Kernel で諸演算をサポートしているので, アンフェアではないだろう 結果 : 一部 ({\tt Wang[8]}) を除いて良好 \end{slide} \begin{slide}{} \begin{center} \fbox{\fbc \large Timing data (Maple7)} \end{center} \begin{center} % & & & & & & & & & & & & & & & \\ \hline {\small \begin{tabular}{c|ccccccccc} \hline $p$ & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 \\ \hline 2 & N & F & F & F & N & N & 0.01 & 1 & 0.01 \\ \hline 3 & 0.07 & 0.1 & 0.07 & N & 0.4 & N & 0.01 & 0.02 & 0.06 \\ \hline 5 & N & 0.05 & 0.08 & 3.5 & 0.2 & 0.4 & 0.01 & 0.6 & 0.1 \\ \hline 7 & 0.08 & 0.1 & 0.1 & 0.25 & 0.6 & 0.5 & 0.02 & 1 & F \\ \hline \end{tabular} \begin{tabular}{c|cccccc} \hline $p$ & 10 & 11 & 12 & 13 & 14 & 15 \\ \hline 2 & F & N & 0.005 & 0.006 & 0.008 & F \\ \hline 3 & 4 & N & 0.004 & 0.007 & 0.14 & 0.02 \\ \hline 5 & 0.2 & F & 0.005 & 0.006 & 0.03 & 0.4 \\ \hline 7 & 0.6 & 14 & 0.005 & 0.16 & 0.04 & 0.6 \\ \hline \end{tabular} \begin{tabular}{c|ccccccccc} \hline $p$ & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 \\ \hline 547 & 0.2& 0.2& 0.1& 0.3& 1& 1.2& 0.02& 6& F\\ \hline 32003& 0.2& 0.2& 0.2& 0.4 & 1 & 1 & 0.02 & 4.2 & F \\ \hline 99981793 & 0.5 & 0.6 & 0.5 & 3 & 3 & 4.5 & 0.02 & N & F\\ \hline \end{tabular} \begin{tabular}{c|cccccc} \hline $p$ & 10 & 11 & 12 & 13 & 14 & 15 \\ \hline 547 & 0.9 &3.3 & 0.005 & 0.2 & 0.1 & 0.4 \\ \hline 32003 & 1.8 & 4.9 &0.006 & 0.3 & 0.1 & 0.4 \\ \hline 99981793 & 2.6 & 11 & 0.006 & 0.9 & 0.5 & 1.4 \\ \hline \end{tabular} } \end{center} \end{slide} \begin{slide}{} \begin{center} \fbox{\fbc \large Timing data (Asir)} \end{center} \begin{center} % & & & & & & & & & & & & & & & \\ \hline {\small \begin{tabular}{c|ccccccccc} \hline $p$ & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 \\ \hline 2(5) & 0.003 & 0.003 & 0.004 & 0.01 & 0.02 & 0.05 & 0.001 & 0.01 & 0.0003 \\ \hline 3(5) & 0.003 & 0.002 & 0.005 & 0.003 & 0.003 & 0.1 & 0.002 & 0.001 & 0.003 \\ \hline 5(2) & 0.004 & 0.003 & 0.004 & 0.02 & 0.06 & 0.4 & 0.002 & 0.4 & 0.005 \\ \hline 7(2) & 0.004 & 0.004 & 0.005 & 0.03 & 0.1 & 0.1 & 0.004 & 1.8 & 0.2 \\ \hline \end{tabular} \begin{tabular}{c|cccccc} \hline $p$ & 10 & 11 & 12 & 13 & 14 & 15 \\ \hline 2(5) & 0.03 & 0.07 & 0.0006 & 0.001 & 0.002 & 0.001 \\ \hline 3(5) & 0.04 & 0.2 & 0.0001 & 0.0005 & 0.02 & 0.001 \\ \hline 5(2) & 0.01 & 0.2 & 0.001 & 0.001 & 0.004 & 0.01 \\ \hline 7(2) & 0.02 & 0.6 & 0.001 & 0.007 & 0.005 & 0.01 \\ \hline \end{tabular} \begin{tabular}{c|ccccccccc} \hline $p$ & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 \\ \hline 547 & 0.004 & 0.004 & 0.005 & 0.03 & 0.05 & 0.2 & 0.02& 2& 0.2\\ \hline 32003 & 0.004 & 0.004 & 0.005 &0.04 &0.07 & 0.2 & 0.004 & 2 & 0.2 \\ \hline 99981793& 0.004 & 0.004& 0.005 & 0.03 & 0.03 & 0.2 & 0.004 & 4 & 0.2 \\ \hline \end{tabular} \begin{tabular}{c|cccccc} \hline $p$ & 10 & 11 & 12 & 13 & 14 & 15 \\ \hline 547 & 0.04 & 0.3 & 0.001 &0.006 & 0.006 & 0.01 \\ \hline 32003 & 0.04 &0.2 &0.001 &0.007 & 0.006 & 0.03 \\ \hline 99981793 & 0.04 & 0.3 &0.001 & 0.008 & 0.008 & 0.01 \\ \hline \end{tabular} } \end{center} \end{slide} \begin{slide}{} \begin{center} \fbox{\fbc \large 今後の予定} \end{center} \begin{itemize} \item 正標数の準素分解の実装. \item 体の位数が足りない場合に, 自動的に基礎体を拡大する. \item 体の標数が十分大きい場合に, 無平方分解を標数 0 と 同様の Hensel 構成で行うようにする. \item 2 変数の因数分解において, \cite{funny01} で述べた, 多項式 時間アルゴリズムを自動的に選択して実行する. \end{itemize} \end{slide} \end{document} \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}