数理解析研究所講究録 1295 巻 2002 年 75-79

75

有限体上の多変数多項式の因数分解について
野呂正行 (神戸大・理)横山和弘 (九州大・数理)

1有限体上の多変数多項式の因数分解

正標数での準素イデアル分解を実装しようとすると, 有限体上の多変数多項式の因数分解が必要となる.
また, Reed-Solomon 符号の復号法の一つである list decoding においては, 有限体上の二変数多項式の因数分解が用いられる. あるいは, 標数 0 の問題においても, いわゆる楽屋裏の計算として, 有限体上の多変数多においては, 有限体上の項式の因数分解が必要となることはしばしばある. しかし , 残念ながら,$\mathrm{R}\mathrm{i}\mathrm{s}\mathrm{a}/\mathrm{A}\mathrm{s}\mathrm{i}\mathrm{r}$因数分解としては, 一変数の場合の実装しかなかった. これは, 通常の無平方分解アルゴリズムがそのままでは適用できないことと, 体の位数が小さい場合特有の困難があるためであった. しかし, 前者に関しては,Bernardin [3] により, 有限体上での無平方分解アルゴリズムが提案された. 後者の困難とは, 無平方分解,既約因数分解に必要となる evaluation point が不足することだが, これも, 本稿で提案するように, 体を原始根で表現し , 必要なら代数拡大することにより, 効率を落さずに e luation point を増やすことができる.
上に, 有限体上の二変数多項式の因数分解の効率よい実装を行うことができた.
これらにより,現時点では, 位数の小さい有限体上における多変数の無平方分解および二変数の因数分解の実装が完成し$\mathrm{R}\mathrm{i}\mathrm{s}\mathrm{a}/\mathrm{A}\mathrm{s}\mathrm{i}\mathrm{r}$さらに, 因数分解の困難なタイプの多項式に適用できる, あたらしい多項式時間アルゴリズムも得ており, その実装実験結果についても述べる.ている.

2

多変数多項式の無平方分解
現在$\mathrm{R}\mathrm{i}\mathrm{s}\mathrm{a}/\mathrm{A}\mathrm{s}\mathrm{i}\mathrm{r}$で用いているアルゴリズムは, 以下に述べるように, Bernardin の無平方分解アルゴリズ

ムを modify したものである.
$F$を標数$p$の有限体とし, $f\in F[x_{1}, \ldots,x_{n}]$ とする. ’ が $d/dx_{1}$ を表すとする.

$f=FGH,$ $F= \prod f_{1}^{a:}.,$($f_{\dot{l}},$$g_{j},$$h_{k}$

は無平方, 互いに素で,$f_{\dot{l}}’\neq 0,$$p\parallel a_{j},$$p|b_{j},$$G= \prod g_{j}^{b_{j}},$ $H= \prod h_{k}^{c_{k}}$$h_{k}’=0$) と書くと $f’=F’GH$ が成り立つ. すると$GCD(f, f’)=GCD(F, F’)GH$
で, $GCD(F, F’)= \prod f_{i}^{a:-1}$ だから$f/GCD(f, f’)= \prod f_{\dot{\iota}}$$\prod f_{\dot{l}}$で $f$ を繰り返し割り, 割り切れなくなった段階で, その商と.
$\prod f_{\dot{l}}$のGCD を計算することで,が全て無平方分解できる. 残りの重複度最小の因子 $f1$ が求まる. これを繰り返すとについて繰り返して残ったける. ここで $f’=0$ が成り立つことに注意する. 以上の手続きを各$F$$f$$x_{i}$$df/dx_{1}=\ldots=df/dx_{n}=0$

XI-1

$F$

中のは $f=GH$ と書$f$は,76を満たす. これは, 全ての指数が$f=g^{p}$ と書けることになる. この$p$$g$で割り切れることを意味する. すると, $F$ は標数の有限体だから,に対して, 以上の手続きを再帰的に適用することで, の無平方分解が$p$$f$得られる.

Bernardin のオリジナルアルゴリズムは, 標数 0 における Yun の方法, すなわち重複度を効率的に計算するアルゴリズムを正標数に応用したもので, 重複度が高い場合に有利であるが, 重複度が より大きい場合に複雑化するという欠点がある. ここでは, 単純に除算の繰り返しで重複度を求めることとした. 我々は,位数が小さい, 従って, 標数も必然的に小さい楊合に効率よく動くアルゴリズムが必要だったため, このよう$p$な形のアルゴリズムを用いた.

無平方分解のボトルネックは $GCD(f, f’)$ の計算である. これを Brown のアルゴリズムで計算しているが, $F$ の位数が小さい場合には evaluation point の不足を招く. この場合には, $F$ の拡大体を使うことになる.

3二変数への帰着法では, の内 $n-1$ 個の変数に値を代入し, 一変数で因子
整数係数多変数多項式の因数分解の場合,のタネを作って, 変数に Hensel 構成する. ここで, 一変数に落しても, ニセ因子はほとんどでないことを期待している. しかし, 有限体の場合, 一変数に落すと有限体上での一変数多項式の因数分解となり, 一般に$n$$\mathrm{E}\mathrm{Z}$$n$ニセ因子が大量に発生する. この困難は, $Z[x]$ に相当するのは $F[y][x]$ であると考えることにより克服できる. すなわち, $n-2$ 変数に値を代入して, 二変数多項式の因数分解によりタネを作り Hensel 構成を行うのである. これは, $Z$ 上での多変数の Hensel 構成とほぼ同様に行うことができる.

4

有限体の代数拡大の効率的表現

これまで述べたように, evaluation point の確保のため, 有限体の代数拡大が必要となる楊合がある. 例えを $F$ 上既約な $m$ 次多項式 $h(x)\in F[x]$ により $F_{m}=F[x]/(h(x))$ で表現ば, $F=GF(q)$ の $m$ 次拡大$F_{m}$の元に対する基本演算に $F$ の基本演算を多数行わなければならず, 計算力吠変になる. ここで,すると,を原始根の位数ががそれなりに大きければ evaluation point は確保できる. このような場合には,$F_{m}$$F_{m}$$F_{m}$

表現すれば,$F_{m}$での演算も効率がよいものとなる. すなわち,$F_{m}^{\mathrm{x}}=\{\alpha^{i}|(0\leq i\leq q^{m}-2)\}$が存在するので,算できる. たとえば乗算は,となるような$\alpha$$F_{m}^{\mathrm{x}}$の元は, 指数$i$により表現できる. この場合, 乗除算, 幕乗は容易に計$\alpha^{:}\cdot\alpha^{j}=\alpha^{:+j\mathrm{m}\mathrm{o}\mathrm{d} q^{\mathrm{m}}-1}$の位数が小さいことを利用して, テーブル参照によって計算する. すなわち,
鬟董璽屮離譴琶飮 しておき,: を\equiv D-+算し, ( , aとすればよい. 加減算は,$\alpha:+1=\alpha^{a:}$

なる

$a$

$F_{m}$$i$$\alpha^{i}+\alpha^{j}=\alpha^{j}(\alpha^{j-j}+1)$のサイズが程度までなら実用的といえる. すなとして計算すればよい. これまでの実験により,わち, この大きさまで体を拡大しても, 計算速度はほとんど変わらない. これにより, 計算効率を落さずに,evaluation point を確保することができる.
$F_{m}$

XI-2$2^{16}$

775

二変数の Hensel 構成および真の因子の探索

二変数多項式の因数分解は, 一方の変数に値を代入して得た一変数多項式を因数分解した因子をタネに,Hensel 構成を行う. 現在の実装では, ある因子とその cofactor の組に対して Hensel 構成を行っている. 簡単のため, $y=0$ での evaluation 結果から Hensel 構成をする場合を考える.
$f(x,y)= \prod_{i=1}^{l}f_{i}(x)\mathrm{m}\mathrm{o}\mathrm{d} y$と分解したとすると,$f(x, y)=\square ^{l}f_{k,:}(x)\mathrm{m}\mathrm{o}\mathrm{d} y^{k}$$:=1$

ヘのHensel 構成は$f(x,y)=f_{k,1}\cdot F_{1}\mathrm{m}\mathrm{o}\mathrm{d} y^{k}\Rightarrow F_{1}(x, y)=f_{k,2}\cdot F_{2}\mathrm{m}\mathrm{o}\mathrm{d} y^{k}\Rightarrow F_{2}(x,y)=f_{k,3}\cdot F_{3}\mathrm{m}\mathrm{o}\mathrm{d} y^{k}\cdots$と計算していく. これは, 全ての因子を一度に Hensel 構成する場合と比較して単純かつ十分に高速である.

Hensel 構成の後, 真の因子の探索に入るが, degree bound より少し多めに Hensel 構成することで, いわゆる $d-1$ test [1] がよく効く. しかし, 組み合わせ爆発は克服できない. これは, あとで触れる, 多項式時間アルゴリズムによれば, 効率よく因数分解できる場合がある.

6

全次数最小の元の探索による多項式時間因数分解
ここでは, 一変数でのニセ因子が多い場合に効率よく真の因子を見つけることができる多項式時間因数分解法について簡単に述べる. 詳しくは [5] を参照してほしい.
$f(x, y)$ は $x$ [こついて monicとする.
$f(x,y)\simeq g_{k}(x,y)h_{k}(x, y)\mathrm{m}\mathrm{o}\mathrm{d} y^{k}$

に対し , イデアノレ $I=<g_{k},y^{k}>$ を考えるとている. ここで,$g_{k}|g\mathrm{m}\mathrm{o}\mathrm{d} y^{k},$$g|f$$\{g_{k}, y^{k}\}$は $y<\iota_{ex}x$ なる$\mathrm{l}\mathrm{e}\mathrm{x}$order でのグレブナー基底となっなる既約因子 9 は $g\in I$ をみたす.

定理 1$k$が十分大きいとき,
証明

もし

$g$

$g’<_{d\mathrm{r}l}g,$は $I$ の degree compatible order $<$ でのグレブナー基底の順序最小の元である.
$g’\in I$があれば $Id(g’, g)$ は 0 次元で, B\’ezout の定理により$\# V(Id(g’,g))\leq tdeg(g’)$ .tdeg(g)だが,$\# V(I)=k\deg_{x}(g_{k})\leq\# V(Id(g’,g))$

より$k$を大きくとれば矛盾.

定理により, 十分大きな に対し , の元の中で, 全次数の小さいものを見つけることができればそれががの既約因子となる. ここで,に関するグレブナー基底だから, へのメンバーシップは未定係数法によりきめることができる. 問題となるのは の大きさである. 確定的なアルゴリズムとするにはとして $k>tdeg(f)^{2}/\deg_{x}(g_{k})$ を満たす値を選ぶ必要があるが, 小さい次数の因子の存在が期待できる場合には, を小さくとって, heuristic なアノレゴリズムとすることもできる.
$k$

$f$

$I$

$\{g_{k},y^{k}\}$$I$$<_{lex}$

$k$

$k$

XI-3

$k$

78
7

元の体での因子の計算上に拡大した場合, $F$ 上の既約因子がevaluation point を増やすために, 体を $F=GF(q)$ からはで分解する可能性がある. $f\in F[x_{1}, \ldots, x_{n}],$ は $F$ 上既約で $f= \prod f_{i},$上既約, と分解したとする. $F_{m}/F$ は Galois 拡大で,
$F_{m}$$F_{m}$$f$$f_{i}$$G=Gal(F_{m}/F)=\langle\sigma\rangle$

ただし$\sigma$:$\beta$}$arrow\beta^{q}$である. $S$ を $f1$ の $G$ -orbit とすると$\prod_{s\in S}s$$\prod s\in F[x_{1}, \ldots, x_{n}]$$F_{m}$,は G-不変だから.

$s\in S$$f$

は $F$ 上既約だから積である.

$\sigma(h)$$f= \prod_{s\in S}s$の計算は係数を$q$. よって,$F$上の既約因子は$F_{m}$上の既約因子の $G$-orbit に属する元の乗すればよいから容易である. このようにして,$F_{m}$上での因子から, $F$上の因子を得ることができる.

8タイミングデータ
まず, [4] で扱われている種々の二変数多項式の因数分解について, タイミングデータを示す.

は $GF(p)$ 上の二変数多項式である.

Maple7, Asir による PentiumIII lGHz 上での計算時間をは $GF(p^{m})$ まで拡大する必要があったことを示す. [2] によれば, 素体上秒で表示してある. Asir のの多項式演算は, Maple kemel で特別な実装が行われており, Maple と Asir の計算時間を比較することはunfair ではないと考える. Maple との比較でみると, 次のようなことがわかる.
表で$f_{p}$$(p^{m})$.

Hensel 構成の性能比較$f11,$ $f13$

は Hensel 構成がほとんどを占めている. このことから Hensel 構成自体の性能は大差ないとみてよいであろう.

・解探索部の性能比較については, 計算時間のほとんどは bad combination の排除である. これは $d-1$ testがうまくいっている例と考えられる.
$f1_{7},$$f1_{7}(x, y^{2})$・体の拡大が必要な場合の比較

Maple では, 体の拡大が必要な場合には, Domains package (一般の有限体を扱う generic な実装) をで差が出たと考えられる.
使うため,$f_{2},$$f_{7}$

つぎに, 体の拡大と効率の関係について示す. 表は,た場合の計算時間を示す.

$f_{7}$XI-4

および, $f17(x, y^{2})$ について, 拡大次数を上げていっ79

表より次のようなことが観察される.
・体が小さいうちは, 拡大しても効率は落ちない

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

・体のサイズが大きくなると, 急激に効率が落ちる
参照するテーブルが大きくなるせいと考えられる.
最後に, 一変数でのニセ因子が多く, 真の因子の探索において組み合わせ爆発を起こす場合について, 今回提案した多項式時間アルゴリズムの効果を示す.
$f(x, y)=f_{17}(x,y^{2})f_{17}(x+1,y^{2})$は, 真の因子は 4 個だが,$\mathrm{m}\mathrm{o}\mathrm{d} y$での因子は 32 個である. これを, 通常の Belrekamp-Zassenhaus 型で計算した場合には,.

・処理した組み合わせ :6626138$d-1$ test で排除 :6234991

・計算時間 :558 秒
一方, 新アルゴリズムで計算した場合, 次数の上限を 16 とした場合 28 , 32 とした場合 46 秒であった.
前者は甘すぎる bound だが, 後者は少なくとも因子は得られる bound であり, 新アルゴリズムが実用的で$\mathrm{P}_{\grave{J}}^{\mathrm{J}}$あることがわかる.

9

今後の予定
現在, 多変数の因数分解を実装中であり, 完成後は正標数の準素イデアル分解の実装を行う予定である.

参考文献[1] Abbott, J., Shoup, V., Zimmermann, P. (2000). Factorization in$ISSAC\mathit{2}\theta\theta\theta,$$1-7$$\mathbb{Z}[x]$: the searching phase. Proc.

.

[2] Bernardin, L., Monagan,. (1997). Efficient multivariate factorization over finite fields. AppliedAlgebra, Algebraic Algorithms and Error-Correcting Codes (AAECC-12). Lecture Notes in Computer
Science 1255, 15-28.
$\mathrm{M}.\mathrm{B}$[3] Bernardin,L.

$\mathrm{b}\mathrm{e}\mathrm{r}\mathrm{n}\mathrm{a}\mathrm{r}\mathrm{d}\mathrm{i}/\mathrm{f}\mathrm{a}\mathrm{c}\mathrm{t}\mathrm{o}\mathrm{r}/$(1997).

Factorization

Examples.

http:$// \mathrm{w}\mathrm{w}\mathrm{w}.\inf$.ethz.

$\mathrm{c}\mathrm{h}/\mathrm{p}\mathrm{e}\mathrm{r}\mathrm{s}\mathrm{o}\mathrm{n}\mathrm{a}\mathrm{l}/$.

[4] Bernardin, L. (1997). On square-free factorization of multivariate polynomials over afinite field.
Theoret. Comput. Sci. 187, 105-116.
[5] Noro, M. and Yokoyama, K. (2002). Yet Another Practical Implementation of Polynomial Factorization over Finite Fields. Proc. ISSAC2002, 2002-206.

XI-5