% $OpenXM: OpenXM/doc/Papers/rims2001-noro.tex,v 1.2 2001/11/19 00:53:58 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}}

\title{\tc 小標数有限体上の多変数多項式の因数分解について}

\author{野呂 正行 (神戸大・理)\\ 横山 和弘 (九州大・数理)}
\begin{document}
\large
\setlength{\parskip}{0pt}
\maketitle

\begin{slide}{}
\begin{center}
\fbox{\fbc \large なぜ (いまさら)有限体上の多変数多項式の因数分解?}
\end{center}

\begin{itemize}
\item Risa/Asir に実装されていない

なぜないのか, と自分で思うことはしばしばあった

\item 正標数準素分解に必要

下山-横山算法 : $\sqrt{I}$ の素イデアル分解 $\Rightarrow$ $I$ の準素分解

$\sqrt{I}$ の分解には, 多変数の因数分解が必要

ひょっとしたら代数幾何符号への応用があるかもしれない

\item Reed-Solomon 符号の list decoding への応用あり

\item それ自体おもしろい

標数が小さい場合 (2,3,5,7 など) 特有の困難がある.

無平方分解での困難

evaluation point が足りない場合
\end{itemize}
\end{slide}

\begin{slide}{}
\begin{center}
\fbox{\fbc \large アルゴリズムの概要 I : 無平方分解}
\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 Bernardin の方法との比較}
\end{center}
標数 0 における Yun の方法 : 重複度の効率的計算

重複度が高い場合に有利

Bernardin : 正標数の場合にも Yun の方法を修正して適用

$\Rightarrow$ 重複度が $p$ より大きい場合に複雑化

$\Rightarrow$ $p$ が小さい場合には, 単純に除算の繰り返しで重複度を求
める

(詳細な比較はまだ行っていない)
\end{slide}

\begin{slide}{}
\begin{center}
\fbox{\fbc \large アルゴリズムの概要 II : 二変数への帰着}
\end{center}

\begin{itemize}
\item 整数係数多変数多項式の場合

$n$ の内 $n-1$ 個の変数を fix $\Rightarrow$ 1 変数で因子のタネを作る

ニセ因子はほとんど出ない

\item 有限体係数の場合

一変数に落すとニセ因子だらけ

$\Rightarrow$ $Z[x]$ に相当するのは $F[y][x]$

\end{itemize}

\end{slide}

\begin{slide}{}
\begin{center}
\fbox{\fbc \large 現在の実装}

\begin{itemize}
\item 無平方分解のボトルネックは $GCD(f,f')$

Brown's algorithm で計算 $\Rightarrow$ evaluation point の不足
が問題 $\Rightarrow$ $F$ の拡大体を使う (後述)

\item 2 変数以外は全て Asir で記述

\item 2 変数のみ builtin

効率上 critical のため $\Rightarrow$ やはり $F$ の拡大体が必要

整数上一変数多項式の因数分解と極めて類似

\item 2 変数でタネを作って, 一変数から改めて Hensel 構成

EEZ アルゴリズムを書けていないため
\end{itemize}
\end{center}
\end{slide}

\begin{slide}{}
\begin{center}
\fbox{\fbc \large 有限体の代数拡大の効率的表現}
\end{center}

evaluation point の確保のため, 有限体の代数拡大が必要

$F=GF(q)$ の $m$ 次拡大 $F_m$ を
$h(x) \in F[x]$ : $m$ 次既約 により $F_m = F[x]/(h(x))$
で表現

$\Rightarrow$ 計算が大変

$q$ は小で, $\#(F_m)$ がそれなりに大きければよい

$\Rightarrow$ $F_m$ を原始根表現すればよい

\end{slide}

\begin{slide}{}
\begin{center}
\fbox{\fbc \large 原始根表現 $F_m^{\times} = \{\alpha^i | ( 0 \le i \le q-2) \}$}
\end{center}
\begin{itemize}
\item かけ算, 割算, べき乗は容易

$\alpha^i \cdot \alpha^j = \alpha^{i+j \bmod q-1}$

\item 足し算, 引き算はテーブル参照 (Faug\`ere GB で用いられた)

$\alpha^i + 1 = \alpha^{a_i}$ なる $a_i$ を計算し, 
$(i,a_i)$ をテーブルで保持

$\alpha^i+\alpha^j = \alpha^j(\alpha^{i-j}+1)$ として計算

\item $F_m$ のサイズが $2^{16}$ 程度までなら実用的

体を拡大しても, 計算速度はほとんど変わらない. 

\end{itemize}
\end{slide}

\begin{slide}{}
\begin{center}
\fbox{\fbc \large 2 変数の Hensel 構成 }
\end{center}

$f(x,y) = \prod_{i=1}^l f_i(x) \bmod y$

$\Rightarrow$ $f(x,y) = \prod_{i=1}^l f_{k,i}(x) \bmod y^k$ への Hensel 構成は

$f(x,y) = f_{k,1} \cdot F_1 \bmod y^k$

$\Rightarrow$ $F_1(x,y) = f_{k,2} \cdot F_2 \bmod y^k$

$\Rightarrow$ $F_2(x,y) = f_{k,3} \cdot F_3 \bmod y^k$

$\cdots$

と計算していく $\cdots$ 単純かつ高速


\end{slide}

\begin{slide}{}
\begin{center}
\fbox{\fbc \large Finding true factors}
\end{center}

\begin{itemize}
\item combination $\Rightarrow$ trial division

bound より少し多めに Hensel 構成

$\Rightarrow$ $d-1$ test (佐々木, Abbott et al.) がよく効く

しかし, 組み合わせ爆発は克服できない

\item ``funny factorization''

change of ordering により true factor を見つける

ニセ因子が多い場合に効果的

\end{itemize}
\end{slide}

\begin{slide}{}
\begin{center}
\fbox{\fbc \large Funny factorization}
\end{center}

$f(x,y)$ : $x$ について monic とする.

$f(x,y) \simeq g_k(x,y) h_k(x,y) \bmod y^k$

に対し, $I=Id(g_k,y^k)$ を考えると $\{g_k,y^k\}$ は
$x<_l y$ なる lex order でのグレブナ基底

$g_k| g \bmod y^k$, $g|f$ なる既約因子 $g$ は $g\in I$.

\underline{定理}

$k$ が十分大きいとき, $g$ は $I$ の degree compatible order $<$ でのグ
レブナ基底の順序最小の元

[証明] もし $g' < g$, $g'\in I$ があれば $Id(g',g)$ は 0 次元で, 

$\#V(Id(g',g)) \le tdeg(g')\cdot tdeg(g)$ (B\'ezout) だが, 

$\#V(I) = k\deg_x(g_k) \le \#V(Id(g',g))$

より $k$ を大きくとれば矛盾. 
\end{slide}

\begin{slide}{}
\begin{center}
\fbox{\fbc \large Funny factorization つづき}
\end{center}

$I$ の $<_l$ でのグレブナ基底が分かっている

$\Rightarrow$ change of ordering で $g$ が計算できる

$k > tdeg(f)^2/\deg_x(g_k)$ なら deterministic

小さい次数の因子を期待して $k$ を小さくとる

特に, $\bmod y$ での因子が多い場合に有効

\end{slide}

\begin{slide}{}
\begin{center}
\fbox{\fbc \large 元の体での因子の計算}
\end{center}

$F = GF(q)$ 上の既約因子が $F_m$ 上で分解する可能性あり

$f \in F[x_1,\ldots,x_n]$, $f$ : $F$ 上既約で 

$f = \prod f_i$, $f_i$ : $F_m$ 上既約とする.

$F_m/F$ は Galois 拡大で, $G=Gal(F_m/F) = \langle \sigma \rangle$ 

ただし $\sigma : \beta \mapsto \beta^q$

$S$ を $f_1$ の $G$-orbit とすると $\prod_{s\in S}s$ は $G$-不変だから

$\prod_{s\in S}s \in F[x_1,\ldots,x_n]$. 

$f$ は $F$ 上既約だから $f = \prod_{s\in S}s$.

$\Rightarrow$ $F$ 上の既約因子 = $F_m$ 上の既約因子の $G$-orbit 

$\sigma(h)$ は係数を $q$ 乗すればよいから容易. 

\end{slide}

\begin{slide}{}
\begin{center}
\fbox{\fbc \large タイミングデータ --- [BM97] からの例}
\end{center}

\underline{ 2 変数多項式}
\begin{center}
{\normalsize
\begin{tabular}{|c|c|c|c|c|c|c|} \hline
 & $f_2$ & $f_7$ & $f_{11}$ & $f_{13}$ & $f_{17}$ & $f_{17,y\rightarrow y^2}$ \\ \hline
$\deg_x,\deg_y$ & 7,5 & 100,100 & 300,300 & $10^3,10^3$ & 32,16 & 32,32 \\ \hline
\#factors & 2 & 2 & 1 & 2 & 1 & 2 \\ \hline
Maple7 & 4.2 & 30 & 68 & $>$1day & 36 & 32 \\ \hline
Asir & 0 ($2^3$) & 2.6($7^2$)  & 34  & 5040 & 0.24 & 0.57  \\ \hline
%Hensel & 0  &  & & 2965 &  &   \\ \hline
\end{tabular}
}
\end{center}
$f_p$ を $GF(p)$ 上で因数分解

Asir の $(p^m)$ : $GF(p^m)$ まで拡大する必要があった
\end{slide}

\begin{slide}{}
\fbox{\fbc \large Maple との比較}

\begin{itemize}
\item Hensel 構成の性能比較

$f_{11}$ は Hensel 構成がほとんど $\Rightarrow$ Hensel 構成
自体の性能は大差ない

[BM97] によれば, 素体上の多項式は kernel で特別に実装されている
(Asir と同じ)

\item 解探索部の性能比較

$f_{17}$ の場合, Maple の計算時間のほとんどは bad combination の
排除 $\Rightarrow$ 何か特別なことをしていて遅い?

\item 拡大が必要な場合の比較

Maple では, 体の拡大が必要な場合には, Domains package (一般の有限体を
扱う generic な実装) を使うため, $f_2$, $f_7$ で差が出た
\end{itemize}
\end{slide}


\begin{slide}{}
\begin{center}
\fbox{\fbc \large タイミングデータ --- 体の拡大と効率}
\end{center}

\begin{center}
{\normalsize
\begin{tabular}{|c|c|c|c|c|c|c|c|} \hline
拡大次数  & 1 & 2 & 3 & 4 & 5 & 6 & 7 \\ \hline
$f_7$ & ---  & 2.6 & 2.9 & 2.7 & 2.6 & 5.8 & 9.1 \\ \hline
$f_{17,y\rightarrow y^2}$ & 0.57 & 0.78 & 0.55 & 2.3 & --- & --- & --- \\ \hline
\end{tabular}
}
\end{center}

\underline{考察}

\begin{itemize}
\item 体が小さいうちは, 拡大しても効率は落ちない

もちろん, 拡大により因子が増える場合は除く

\item 体のサイズが大きくなると, 急激に効率が落ちる

参照するテーブルが大きくなる $\Rightarrow$ キャッシュサイズに関係?
\end{itemize}
\end{slide}

\begin{slide}{}
\begin{center}
\fbox{\fbc \large 組み合わせ爆発を起こす場合}
\end{center}

$f(x,y) = f_{17}(x,y^2)f_{17}(x+1,y^2)$

真の因子は 4 個, $\bmod y$ での因子 32 個

\underline{通常の Belrekamp-Zassenhaus 型で計算した場合}

\begin{itemize}
\item 処理した組み合わせ : 3852356
\item 次数チェックで排除 : 3734707
\item 計算時間 : 162sec
\end{itemize}

\underline{Funny factorization で計算した場合}
\begin{itemize}
\item bound = 16 (これは甘すぎ)         2.6sec
\item bound = 32 (少なくとも因子は出る) 17sec
\end{itemize}
\end{slide}

\begin{slide}{}
\begin{center}
\fbox{\fbc \large 今後の予定}
\end{center}

\begin{itemize}
\item 無平方分解部の改良, engine 組み込み

\item 3 変数以上への Hensel 構成を EEZ 化

\item 2 変数多項式の積の, Karatsuba による高速化

\item Zassenhaus, Funny の OpenXM による並列化

\item knapsack 型のアルゴリズムの適用可能性の検討
\end{itemize}
\end{slide}

\end{document}