数理解析研究所講究録
第 1572 巻 2007 年 59-65

59$z/pz$ 上の因数分解と格子算法

山中亜希子
AKIKO YAMANAKA

神戸大学総合人間科学科
GRADUATE SCHOOL OF CULTURAL STUDIES AND HUMAN SCIENCES, KOBE UNIVERSITY*長坂耕作
KOSAKU NAGASAKA

神戸大学人間発達環境学研究科
GRADUATE SCHOOL OF HUMAN DEVELOPMENT AND ENVIRONMENT, KOBE UNIVERSITY \dag er

1

はじめに$z/pz$ 上の多項式の因数分解法には, 良く知られているものとして Berlekamp アルゴリズムと Niederreter

アルゴリズム [2] がある. そのどちらにも GCD を求めるステップがあるが, 何ら策を講じなければ,どちらもそのステップには膨大な因子の組合せがあるために時間がかかる. 今回の発表は, Niedeneiter アルゴリズムにおける, この GCD 計算を行い既約因子を求めるステップの改良に関する試験的な取り組みである. 具体的には, この部分に格子算法を用いることでアルゴリズムの高速化を目指している. まずは有名な
2 つのアルゴリズムの概要と GCD 計算のステップについて述べてから, 今回試みた改良方法についてと,実験結果について述べる.

2$z/pz$ 上の因数分解法の概要
因数分解すべき $z/pz$ 上の多項式を $f(x)$ として, 各アルゴリズムの概要を述べる.

2. 1Berlekamp アルゴリズムの概要
1. 次式を満たす行列 $Q=(q_{n-i,n-j})\in(z/pz)^{nxn}$ を構成する.
$x^{kp}\equiv q_{k,n-1}x^{n-1}+q_{k,n-2}x^{n-2}+\cdots+q_{k,1}x+q_{k,0}$2.

$I$を $n$ 次の単位行列として, $Q-I$ の零空聞の基底をなす$(i=1, \ldots, r)$に対応する$r$$r$$(mod p, f(x))$

個のベクトル$(g_{\mathfrak{n}-1}^{(i)}, \cdots, g_{0}^{(\dot{*})})^{t}\in(z/pz)^{n}$個の多項式 $g(x)^{(i)}=g_{n-1}^{(:)}x^{n-1}+\cdots+g_{0}^{(i)}$ を構成する.

3. $f(x)$ を $g(x)^{(i)}-s(s\in z/pz)$ との GCD を計算することにより既約因子に分解する.
$065f739f\copyright_{8}tu.kob\triangleright u$$\uparrow naga8ah\Phi main$. ac.jp. h.kobe-u. ac.jp

60
Niederreiter アルゴリズムの概要

2.2

Niederreiter アルゴリズムも Berlekamp アルゴリズムと同様に, 因数分解の問題を線形化することにより既約因子を求めており, 次の有理関数体上の微分方程式が用いられている.
$y^{(p-1)}+y^{p}=0$

この微分方程式は線形方程式となるため, Berlekamp での行列に似た行列を用いることで既約因子を求めていく.

1. 微分方程式に対応する線形方程式の行列
2.

$I$

を $n$ 次の単位行列として,$(\mathbb{Z}/p\mathbb{Z})^{n}(i=1, \ldots, r)$

3. $f(x)$ を3$M_{p}(f)\in(\mathbb{Z}/p\mathbb{Z})^{nxn}$を作成する.

$M_{p}(f)+I$ の零空間の基底をなす $r$ 個のベクトル $(h_{n-1}^{(i)}, \cdots, h_{0}^{(:)})^{t}\in$に対応する$\sum_{i=1}^{r}s_{i}h(x)^{(i)}(s_{i}\in \mathbb{Z}/p\mathbb{Z})$$r$個の多項式 $h(x)^{(i)}=h_{n-1}^{(i)}x^{\mathfrak{n}-1}+\cdots+h_{0}^{(i)}$ を構成する.との GCD を計算することにより既約因子に分解する.

GCD の取り方

どちらのアルゴリズムも最後に GCD をとって既約因子を求めるステップがある. Berlekamp の場合, 先に書いた総当りで求めるものと, 確率的なものがある. また, Niederreiter の場合も, 総当りのものや, 基底を変換することにより効率よく求めていく方法 [3] によるもの, 確率的なもの [1] などがある.

3.1

Berlekamp アルゴリズムの GCD のとり方 (総当り)Berlekamp アルゴリズムでは図 1 のように, $f(x)$ やその自明でない因子と $g(x)^{(:)}-s$ との GCD を計算することにより既約因子に分解していく. 零空間の全ての基底に対応する多項式との GCD を計算することで, 既約因子をすべて求めることができる. 従って,GCD 計算を最悪の場合に $O(pr)$ 回必要とする.

$m$fiti $\infty-----ggasX$

$-.$

&、

$1^{I_{\dot{s}^{\zeta\aleph f_{l}f^{-}\# l*varrow-\sim \text{灘}\pi \text{轡}\cdot xa}}^{\swarrow^{\swarrow\searrow}\searrow.\underline{\mu}}};\backslash \backslash$

se$Zi\ovalbox{\tt\small REJECT}$

rw $ll\beta$.

$\text{、_{}\wedge};$$r$$\epsilon\ddagger\theta’!*\cdot\dot{*}\iota aeXi\phi$

図 $1:$ BerlekamP アルゴリズムでの GCD の計算

61
3.2

Niederreiter アルゴリズムの GCD のとり方 (総当り)

Niederreiter アルゴリズムでは図 2 のように, $f(x)$ やその自明でない因子と, 零空間の基底に対応する個の多項式の線形和との GCD を計算することにより既約因子に分解していく. 全ての線形和との GCD を計算することで, 既約因子をすべて求めることができる. 従って, GCD 計算を最悪の場合に回必要$r$$O(p^{r})$とする.
$J\{l,\tilde{1}$.

$v**.–\sum_{*\cdot 1}^{l}\,Xff^{J}\Psi$$*aex_{f}$$\swarrow_{*}^{\triangleleft\delta}t_{\backslash \backslash }i\searrow\backslash r_{2}\{xl\swarrow\backslash _{\lambda# 8}$ae

図 2: Niederreiter アルゴリズムでの GCD の計算

この図からもわかるように,自明でない因子に分解することが可能な線形和を構成する : の組がわかれば GCD 計算の回数を減らすことができる. 後に述べるが, 実際に行った試みでは, そのようなを比較的簡単に検出することを目指した.
$S$$s_{i}$

3.3

Niederreiter アルゴリズムの GCD のとり方 (基底変換)

H. Niederreiter, R. Gottfert により 1995 年によって発表 [3] されているもので, 零空間の基底を元の基底 $B=\{h\neq,$に変換し, アルゴリズム 1 「 $Baeic$から簡約化した基底,,$SplittingStep\rfloor$ を用いることで, 必要となる GCD 計算の回数を $O(2r-3)$ 回に減らしている.
この方法は,$\cdots$$f^{h}\}$$B_{1}= \{\frac{u}{v}L1$$\frac{u}{v}\angle r\}$

アルゴリズム 1 (Basic Splitting Step(GCD 計算))入力 :$f(x)$ の因子 $w(x)$

出力 :$w(x)$ の既約因子

Step 1. $gcd(w, v_{i})$ を計算し, $w(x)$ の自明でない因子なら $w(x)$ を 2 つの因子に分割し, それぞれの因子に対して Basic Splitting Step を再帰的に適用する.

SteP 2. $I(w)=\{1\leq i\leq r :w|v_{i}\}$ を求め,
$w(x)$ を 2 つの因子に分割し,$\beta\in F_{p}$に対して $gcd(u_{1}+\beta\frac{w’v}{w}, v_{i})$ が自明でない因子ならそれぞれの因子に対して Basic Splitting Step を再帰的に適用する. 自明な因子であれば $w(x)$ は既約となる.

4GCD ステップの改良
総当りの場合,どちらのアルゴリズムもかなりの計算量が必要であるため, それらの改善を行ったアルゴリズムが提案されている. 今回の試みもそれらと同じく, Niederreiter アルゴリズムの GCD ステッブの改62
善の試みとなる. 先にも述べた通り, 自明でない因子を求めるのに必要な線形和を生成するの組み合わせを格子算法を使って簡単に検出することでの改善の試みである.
具体的な試みの内容は, 部分終結式写像と格子算法を用いることで, 複数の多項式の線形和との余因子候$s_{i}$補を見つけ出す. その際, 格子算法による 上の高速因数分解法と同じく, 格子算法をるようにすると共に, 複数の多項式の線形和に適用するため, Sylvester 行列を拡張する.
$\mathbb{Z}$$\mathbb{Z}/p\mathbb{Z}$で適用でき部分終結式写像
次の写像 $Syl_{r}(f,g)$ のことを,$f(x)$と $g(x)$ の$r$

次の部分終結式写像という ($n$を $f(x)$ の次数,$m$を $g(x)$このとき,この写の次数とする).

:$Syl_{r}(f,g)$$\mathcal{P}_{m-r-1}$$x$$\mathcal{P}_{n-r-1}$$(s(x) t(x))$

ここで. $r=0,$ $\ldots,$ $\min\{n, m\}-1$ であり,$\mathcal{P}_{d}$,$arrow$$\mathcal{P}_{n+m-r-1}$$rightarrow$$s(x)f(x)+t(x)g(x)$ ,は $d$ 次以下の多項式全体の集合とする.

像のカーネルの要素は $f(x)$ と $g(x)$ の余因子候補となっている. これを複数の多項式の未知の線形結合へ適用することで$s_{i}$を求めることを試みた. なお,$0$

次の部分終結式写像の行列表現が Sylvester 行列である

ことに注意されたい.

縦諦 $f$《幽+t《x 惣$\mathfrak{B}$難$u(\kappa bJ\zeta x)*-l\{\theta g(\kappa)$

格子算法の利用
上の因数分解で発生する試し割り
自明でない GCD を与える線形和 $\sum_{i=1}^{r}s_{i}h(x)^{(i)}$ を求めることは,上の因数分解の場合, 格子算法により効率良く組合せを求める方法が提案と同じ組合せの問題である.
$\mathbb{Z}$$\mathbb{Z}$されており, 本発表でも格子算法により $u(x)f(x)=-t(x) \sum_{i=1}^{r}s_{i}h(x)^{(i)}$ を満たす

$s_{i}$の組を求めることに取り組んだ. 繰り返しになるが, 線形和が求まれば $f(x)$ の自明でない因子が見つかることに相当する.

Sylvester 行列の拡張
GCD を計算する多項式を $f(x)=f_{n}x^{n}+\cdots+fix+f_{0}$ と $g(x)=g_{m}x^{m}+\cdots+g_{1}x+g_{0}$ とした場合,次の部分終結式写像 (即ち, 終結式) の行列表現となる Sylvester 行列は, 多項式の係数を図 3 のように並べたものになる. なお, Sylvester 行列は畳み込み行列 $C_{m}(f)$ と $C_{n}(g)$ で表すことができ, 対応する部分を図の左側に記載した. $f(x)$ の 次の畳み込み行列 $C_{k}(f)$ とは, $k-1$ 次の多項式との積を行列 $C_{k}(f)$ と縦$0$$k$ベクトルとの積で表現するのに使われる.
を求めるために, 図 4 の左側の行列のように, 零空聞の基底に対応する未知の線形結合上で格子算法を用いるために右側の行列多項式それぞれの畳み込み行列を縦に配置する. その上で,$\sum_{i=1}^{r}s_{i}h(x)^{(i)}$$\mathbb{Z}/p\mathbb{Z}$63

図 3: $s_{y1_{Ve8}ter}$ 行列のように行を追加する. この行列, ないしは更に拡張した行列に格子算法を適用することで, 未知の線形結合を求められないかの試みを行っている.
’I$|_{\backslash }\dot{|||i}\backslash$.

:$\star\ldots\sim\grave{*-=}\dot{\alpha}$$i^{\vee\theta}f\alpha^{c(t}\iota_{1}C_{\sim}^{\backslash r_{i}}\{f\}r- x_{ k^{*r:}}$$\frac{‘}{..\}..i!_{i}^{:}:\wedge..;‘:}\backslash \mu_{A}.\alpha I$:$a_{\vee^{\vee t}}\cdot\# e\theta.a_{\vee\prime}\dagger..\{J_{\chi}i^{-\nu}\{.\mu_{\delta}p*x:\wedge\backslash$$\check{\{z\wedge\vee i}$...

,$-’:$

ノ図 4: 行列の構成

4.1

実際の例

これまでに述べたことを実験した例として, $f(x)=x^{4}+2x^{3}+2x\in \mathbb{Z}/3\mathbb{Z}[x]$ の因数分解を考える.
Niederreiter アルゴリズムにより行列を求め, その零空間の基底から次の多項式が構成される.
$\{h_{1}(x)=x^{3}+2, h_{2}(x)=x^{2}, h_{3}(x)=x+2\}$

Sylverster 行列を拡張したのが左側の行列であり, 更に行を追加するなどしたものが右側の行列である.

64
このようにして得られた右側の行列に格子算法 (LLL アルゴリズム) を適用した結果が, 次の行列である.

この行列から$s_{i}$の組がわかる.

形結合の余因子, 次の 4 列がこの行列の前から 3 列が $f(x)$ に対する $h_{1}(x),$ $h_{2}(x),$ $h_{3}(x)$ の未知の線$h_{1}(x)$に対する $f(x)$ の余因子, その次の 4 列が $h_{2}(x)$ に対する $f(x)$ の余因子, その次の 4 列が $h_{3}(x)$ に対する $f(x)$ の余因子となる可能性のある多項式の係数となっている.の場合, 6 行目から$s_{1}$の組を求めることができ,$s_{1}=1,$ $s_{2}=-1,$ $s_{3}=0$となる.

この例

これから線形和を求めると, 次の多項式が求まる.
$\sum_{i\approx 1}^{r}s_{i}h(x)^{(:)}=1\cdot h_{1}(x)-1\cdot h_{2}(x)+0\cdot h_{3}(x)=x^{3}-x^{2}+2$

この多項式と $f(x)$ との GCD を再度計算するか, 上記の 6 行目から直接求めることで,$f(x)$ の自明でない因子が求まる.
$gcd(f(x), \sum_{i=1}^{r}s:h(x)^{(i)})=x^{3}+2x^{2}+2$5

まとめ
今回の試みでは, 行列を使ったシンプルな方法で線形和を求めることに取り組んでいる.

は,格子算法による結果から未知の線形結合を構成する$s_{i}$

実験においての組を簡単に見つけられたが, 確実に求まるはまだわかっていない. だが, この方法では線形独立な零空間の基底を扱うため, 行列の作成がうまくできれば, 一定の条件下においては証明ができるのではないかと思われる. また, 証明できれば,GCD 計算において今までと違ったアルゴリズムを提案できるかもしれないし, 確実に求められることが証明されれば旧来の方法より早いかを,

6

Niederreiter らの基底変換の方法との比較で調べてみたい.

発表後に判明したこと
本発表で取り組んだ試みは, 発表後の追試や研究により, 自明でない因子を求めるのに必要な未知の線形結合を穂実に検出することはできないことが判明している. 本発表は都度言及していたように, 格子算法の活用による Niederreiter アルゴリズムの GCD ステップの改善の試みであり, あくまでも 1 つの試みが失敗しただけであり, 引き続き可能性を探っていきたい.

65
参考文献[1] S. Gao and J. von zur Gathen. Berlekamp’s and Niederreiter’s polynomial factorization algorithms.
In Finite fields: theory, applications, and algorithms ($Las$ Vegas, $NV$, 1993), volume 168 of Contemp.
Math., pages 101-116. Amer. Math. Soc., Providence, RI, 1994.
[2] H. Niederreiter. A new efficient factorization algorithm for polynomials over small finite fields. Appl.
Algebra Engrg. Comm. Comput., $4(2):81-87$ , 1993.

[3] H. Niederreiter and R. G\"ottfert. On a new factorization algorithm for polynomials over finite fields.
Math. Comp., $64(209):347-353$ , 1995.