数理解析研究所講究録920 巻 1995 年 133-148

133

15.
$\mathrm{Z}_{p}$–上の多項式の因数分解

高速化技法ベクトル処理並列処理–

村尾裕– (東京大学)

15.1 はじめに多項式の因数分解は, 今や, 数式処理システムには必要不可欠な機能であり, また, 数式処理の様々な基本アルゴリズム中においても必要となる最も基本的な演算である.
そのような基本アルゴリズムのひとつとして, 多項式の補間法による決定があげられる. 多項式補間とは, 未知の多項式の多数の数値群から目的とする多項式を構成する方法だが,その数値群の計算には, ベクトル処理や (超) 並列処理が適用可能な場合が多く, 効率上, 実際に適用することが望まれる. 補間法のアルゴリズムとしては,Lagrange や Newton によるものが古くから知られているが,れら古典的な方法は, 実際上は, 疎な多項式に対しては使いものにならない. 近年, 疎な (多項式を決定するための効率の良いアルゴリズムが$\mathrm{B}\mathrm{e}\mathrm{n}\mathrm{O}\mathrm{r}$$\mathrm{Z}$

こ

係数の)

と Tiwari により発見され [2], 以降, 幾

つかのその発展形が発表されている:(Kaltofen&Lakshman) Toeplitz 方程式と Vandermonde 方程式の解法部分への, より効率の良い既知の算法の適用 [6]; (Kaltofen 他) 数係数膨張を抑止するための $p$-adic なアルゴリズムと$\mathrm{Q}$係数の場合への拡張 [7]; (Murao&Fujise) 数値群のデータ並列による計算を念頭においた, 複数の法 (大きな素数) の利用 [12]. いずれのアルゴリズムにおいても, -変数多項式の因数分解 (前二者では$\mathrm{Z}_{\mathrm{P}}$$\mathrm{Z}$上, 後二者では$\mathrm{Z}_{P}$上) が必要となる. この–変数多項式は,$\mathrm{Z}$或は上で完全に線形因子にまで分解されることは既知であり, また, その次数は, 補間により決定する

多項式中の単項式の個数に等しい. よって, 行列式の展開等で巨大な多項式を求める場合には, 因数分解する多項式はかなり高次となる. 実際, 上記の我々のアルゴリズムの開発実用化において,の因数分解がネックとなる (ことが$\mathrm{R}\mathrm{E}\mathrm{D}\mathrm{U}\mathrm{C}\mathrm{E}/\mathrm{R}\mathrm{l}\mathrm{i}\mathrm{s}\mathrm{p}$による実験で明かとなっている) [12].

こ

134

筆者は, この困難を実際実用上いかに克服しうるか目すべぎかを明かにするために, 問題をより一般化し, 表題のとおりの因数分解について, 様々な実験を行っている. 即ち, 各種のアルゴリズムについて,「インプリメント上どのようなことが問題となるのか?」,「実行性能はどのアルゴリズムが優れ, また, どこまで得られるのか?」, [ $13|$ にも指摘があるとおり 「$\mathrm{B}\mathrm{e}\mathrm{r}\mathrm{l}\mathrm{e}\mathrm{k}\mathrm{a}\mathrm{m}\mathrm{p}$の因数分解アルゴリズ

ムは, 基本的に行列の処理ゆえベクトル処理が可能だが, どの程度の効果があるのか?」, さらに–般に「ベクトル処理や並列処理を如何に用いるのか? また, その効果は?」等の知見をうることが, その目的である.
本稿は, この計算機実験の, 主にベクトル処理についての, 現時点までの結果報告である. 以降では, 先ず, 既存のアルゴリズムとその complexity 等のまとめを行い, その後, ベクトル処理の仕方等について論じ, その効果を計測結果と共に示す. その実験結果についての簡単な考察を行った後, 最後に, 並列処理についても言及する. 並列処理の具体的方法や結果については, [12] や [18] を参照されたい.

15.2 アルゴリズムのまとめ$\mathrm{Z}_{P}$上の無平方 (square-free) で monic な多項式 $U(x)$ を因数分解する

約因子の個数とする. 勿論嫁よ未知である.

$x^{\mathrm{p}k}$

mod $U(x)$ の

$x$

但し,

の係数を

$n=\deg(U),$

,, を既

とおき,

$n\cross n$$q.\cdot k\in \mathrm{Z}_{\mathrm{P}}$

行列 $Q$ を以下のとおり定義する:$Q=$$\blacksquare$(1).

Berlekamp のアルゴリズム [3]$Q-I$ の零空間を求める. 但し, 月よ $n\cross n$ の単位行列. より具体的には, 行列 $Q-I$ の列の消去を行い:(a)rank $(Q-I)=n-\Gamma$ を求め, 因子の個数(b)$Qv_{j}arrow=v_{j}arrow$する.

を満たすベクトル

ここで,$V_{j}(x)$$r$を決定する.

$v_{j}\sim=(v_{j\mathrm{O}}, v_{j1}, \ldots, v_{jn-1})^{T}$を求め,$V_{j}(x)= \sum_{=0}^{n-1}.\cdot v_{ji}x^{i}$とが次の合同式を満たすことに注意:$V_{j}(x)^{p}\equiv V_{j}(x)$

(2)

$r$

個の因子が求まるまで, 各 $V_{i}(x)$ に対し,はその因子との GCD 計算を繰り返す.

mod $U(x)$ .

$\alpha=0,1,$ $\ldots,p-1$

に対し $V_{J}(x)-\alpha$ と $U(x)$ また135$\blacksquare$

Zassenhaus

有用な–の決定 [17]$\mathrm{a}$上記 Berlekamp のアルゴリズムでは, 最悪の場合, GCD 計算を全てのなるが,な (因子の得られない) 計算である.
$v(x)^{k}$に対して繰り返すことにの場合, その繰り返しの回数が問題となるばかりでなく, 殆んどの GCD 計算が無駄$p\gg 1$..
.

$\alpha$しかし, いずれの $v(x)=V_{j}(x)$ についても,

mod $U(x),$ $k=0,1,$$w(v(x))\equiv 0$$\ldots,$は線形従属ゆえ,$r$

mod $U(x)$ を満たす多項式 $w(X)$ が存在する$w(X)=0$ の解$\alpha\in \mathrm{Z}_{\mathrm{P}}$

最低次の $w(X)$ を求めれば,が GCD 計算で non-trivial な因子を与える.

より具体的には以下の行列消去を行い零空間ベクトル f(1)

mod $U(x)$ の係数を第$v(x)^{k}$

(b)

その第

(c)

線形従属であることが判明した時点で終了.

(2)

$k$

の全解

$w(X)$$w(X)= \sum_{k}w_{k}X^{k}$

とおく.

列の列べクトルとする行列を順次構成し,

(a)

$k$

を求め,

$=(w\mathit{0}, w_{1}, \ldots)^{T}$

列を $0\sim(k-1)$ 列により消去する.

$(\in \mathrm{Z}_{P})$を求める.

上記の 2 つのアルゴリズムにおいて注意すべき事柄を列挙する.
を全て求める必要はない.

。

必ずしも

。

Berlekamp のアルゴリズムで,返しは,。

$U(x)$$v_{j}arrow$

$r$

と

$P$

$P$

が大きい場合,$V_{j}(x)$に関する繰り返しと a に対する繰りの $i$の大きさにより適宜入れ換えて実行すべきである.

の既約でない因子 $u(x)$ の中には, 上記の巧 $(x)$ を用いた GCD 計算では分解できないものがあることに注意する必要がある.

$V_{j}(x)$modの場合である.

$u(x)\in \mathrm{Z}_{P}$

次数別因数分解 (Distinct Degree Factorization: 以下 DDF)
$H_{k}(x)$$U(x)$を,$U(x)$の因子のうち次数がとおき, $k=1,2,$$\ldots$$k$である全ての既約因子の積とする. 各 $H_{k}(x)$ は,$U^{(1)}(x)=$に対し (小さい順に) $U^{(k+1)}(x)=1$ となるまで次式を計算することにより求められる.
$H_{k}(x)$$U^{\langle k+1)}(x)$$d_{k}=\deg(H_{k})$とすると,$H_{k}(x)$以下のアルゴリズムでは,$\Leftarrow$$\Leftarrow$$\mathrm{g}\mathrm{c}\mathrm{d}(x^{p^{k}}-x, U^{(k)}(x))$$U^{(k)}(x)/H_{k}(x)$,.

の既約因子の個数は $d_{k}/k$ である.

この $H_{k}(x)$ の因数分解を行う.

各 $H_{k}(x)$ の既約因子の次数と個数が既知ゆえ, 完全な分解が得られたか否かの判定は容易にできるが, 以下でアルゴリズムが「確率的」 というのは, 全ての既約因子を得るまでの手続きが非決定的,ということである.

136

DDF

$\blacksquare$&Zassenhaus のアルゴリズム [4]$+\mathrm{C}\mathrm{a}\mathrm{n}\mathrm{t}\mathrm{o}\mathrm{r}$

任意の多項式–に対し, 次式が成り立つことを利用する.

$A(x)\in \mathrm{Z}_{p}[x|$$A(x^{p^{k}})-A(x)\equiv A(x)^{p^{k}}-A(x)\equiv A(x)(C-1)(C+1)\equiv 0$ mod

但し,

確率的

$H_{k}(x)$,mod $H_{k}(x)$ . アルゴリズムとしては, $A(x)$ を random に生成し,$C=A(x)^{(p^{k}-1)/2}$$H_{k}(x)$又はその因子と $C-1$ との GCD 計算を繰り返す.

DDF$\blacksquare$

operator$\mathrm{M}\mathrm{c}\mathrm{E}\mathrm{l}\mathrm{i}\mathrm{e}\mathrm{c}\mathrm{e}$のアルゴリズム [1]$+\mathrm{B}\mathrm{e}\mathrm{n}\mathrm{O}\mathrm{r}$$T_{k}$–

確率的は, 各 $H_{k}(x)$ に対し, 次式により定義される [9]:$T_{k}(y)=y^{p^{0}}+y^{p^{1}}+\cdots+f^{k-1}$$T_{k}(y)^{p}-T_{k}(y)=y^{p^{k}}-y$

ゆえ, 任意の$T_{k}(A)^{p}-T_{k}(A)$mod $H_{k}(x)$アルゴリズムは,(2)$\alpha\in \mathrm{Z}_{P}$

(3)

$B$

(4)

充分に多くの

ここで,

$0$

$=$

$T_{k}(A)(T_{k}(A)^{(p-1)/2}-1)(T_{k}(A)^{(p-1)/2}+1)(= \prod_{\alpha=0}^{\mathrm{p}-1}(T_{k}(A)-\alpha))$を random に生成し,$U(x)$.

またはその因子が完全に分解されるまで, 以下の手順を繰り返す:を random に生成し,$A\in \mathrm{Z}_{p}[x]$と$\equiv$$H_{k}(x)$(1)

に対し次式が成り立つ.

$A\in \mathrm{Z}_{\mathrm{p}}[x]$$T_{k}(A)$を計算する.

$B=(T_{k}(A)+\alpha)^{(p-1)/2}\pm 1$を計算する.

またはその因子との GCD を計算する.
$\alpha$に対し, (2) 及び (3) を繰り返す.

ひとつの $A$ によって $H_{k}(x)$ の因子を完全に分離しうるかは,その確率が $p\gg d_{k}/k$ の場

合非常に高いとはいえ, あくまでも確率的であることに注意.

$\blacksquare$

(1)

DDF
$g_{i}(x)$$+\mathrm{S}\mathrm{h}\mathrm{o}\mathrm{u}\mathrm{p}$を,のアルゴリズム [14]$(Y-x^{p^{0}})(Y-x^{p^{1}})\cdots(Y-x^{p^{k-1}})$の$Y^{i}$の係数とする:.-.
$(Y-x^{p^{0}})(Y-x^{p^{1}})\cdots(Y-x^{p^{k-1}})=Y^{k}+g_{k-1}(x)Y^{k}$$+\cdots+g_{0}(x)$ .

(2)

全ての

$\alpha\in \mathrm{Z}_{P}$及び各 $g.(x),$ $i=0,1,$$\ldots,$$k-1$ に対し,

$H_{k}(x)$またはその因子と,$g_{i}(x)+\alpha$および $(g|(x)+\alpha)^{\langle p-1)/2}-1$ との GCD 計算を, 全ての因子が求まるまで繰り返す.
ここで, (2) のステップ中,$\alpha$についての繰り返しと $g:(x)$ についての繰り返しのいずれを, 如何なる場合に優先させるべきかは, [15] に詳しい.

137

15.3 計算の複雑さや撫法について
本節では, より具体的な計算法について言及すると同時に, 各アルゴリズムの計算量とメモリ所要量をまとめる. 後節では, 実行時間の計測結果の検討を計算量に基づいて行う.

インプリメントの際に, 実際にどれくらいのメモリが必要になるのか,
るのか,

また,

また,

メモリ所要量は,メモリはどのように使い回せ

どの程度の規模まで計算できるのかを知る上で必要となる.

計算量

多項式の乗算に FFT や Karatsuba 等の技法を用いない場合の各アルゴリズムのステップ毎の計算量を, 表 1 に [15] より引用する.

行列 $Q$ の構成について

表 1 中 2 つの計算量を併記してあるのは, 次の算法の違いによる.

mod $U(x)$ を, shift-add により, $k=1,2,$。

$O(n^{2}p)\cdots x^{k}$。

$O(n^{3}+n_{!}^{2}\log p)\cdots F$に対し$p\gg 1$$x^{j}$

mod$\ldots$, $(n-1)p$と順次計算していく.

を $U(x)$ 又は $H_{k}(x)$ とし, 但し $n=\deg(F),$ $i=n,$ $n+1,$$F= \sum_{=0}^{n-1}.\cdot R_{ji^{X}}$の場合後者が優れるが, 表$\ldots,$$2n-2$の表 $(R_{j}.)$ を用意し, 高次の幕乗の計算を 2 進法的に行う.

$\{R_{\mathrm{J}}.\}$の分だけ余分なメモリが必要となる. 但し, この表は様々な部分で利用可能・必要となる. 本稿のインプリメントでは, $p<n$ の場合に前者を, そうでない場合に後者を用いている.

高次の二乗の計算について.

DDF 及び DDF 後のアルゴリズムでは, 多項式の高次の幕乗
任意の $A(x)\in \mathrm{Z}_{P}[x]$ について,$\sum_{i=0}^{n-1}A:x^{i}$.

の $P$ 乗 $A(x)^{p}$

算される. 当然,

$A(x)^{p^{k+1}}$

Cantor &Zassenhaus の$\text{ア}$$A(x)^{p}\equiv A(x^{p})$modの係数は, 行列 $Q$ を用いて,$(\mathrm{m}\mathrm{o}\mathrm{d} F)$$p$の計算が必要となる.

が成り立つ

よって,

$Q(A\mathit{0}, A_{1}, \ldots, A_{n-1})^{T}$$A(x)=$

により計

も $A(x)^{p^{k+1}}\equiv A(x^{p^{k}})^{p}$ により, 行列 $Q$ を用いて計算する.

ルゴリズムで用いる $A(x)^{(p^{k}-1)/2}$ は, $p^{k}-1=(1+p+p^{2}+$138. . . $+p^{k-1}$ ) $(p-1)$ に注意し, 次式により行列$A(x)^{\langle p^{k}-1)/2}=$.

$Q$を用いて計算する.

$(_{J} \prod_{=0}^{k-1}A(x^{p^{j}}))^{(p-1)/2}$

但し, DDF 以後のアルゴリズムで必要となる $Q$ -行列は, 各 $H_{k}(x)$ に対する行列 Q(りぞある行列$Q^{(k)}$は,$P$や改が大きい場合, DDF の際に用いた,$U(x)$

に対する $Q$ から (各列の$H_{k}$

による剰余として) 計算すると良い.
線形因子の積の分解について$L(x)\in \mathrm{Z}_{P}[x]$

を異なる

$d$

個の線形因子の積 $L(x)$ とする. この分解は, 次のいずれかにより行う.

$p-1$ の代入\Rightarrow 計算量は $O(dp)$ だが, その係数は小さ(a)$x=0,1,$(b)$\mathrm{g}\mathrm{c}\mathrm{d}(L(x), (x-\alpha)^{\{p-1)/2}\pm 1)$

また,$x^{k}$$\ldots,$$n$, 計算も容易.

による二分探索\Rightarrow 計算量は, 表 1 から,

mod $L(x)$ の係数の表 (大きさはメモリ所要量について . . . 次数
Berlekamp : 総量$\langle$$d^{2}$) が必要.

について 2 乗以上のもののみをまとめる.

$2n^{2}$Zassenhaus : 総量 $5/2n^{2}\sim 3n^{2}|$ DDF も行う場合はCantor&Zassenhaus 及び Ben-Or : 総量

$3n^{2}$$Q$の保存のために$+n^{2}$$O(d^{3}+d^{3}\log p)$

.

139

15.4 ベクトル処理の可能性と必要性
前節までで, 実際の計算において行列演算を多用することは述べたので, いずれのアルゴリズム中にも, ベクトル処理に適合する処理が多々存在することは, 既に明かであろう. 以下に, ベクトル処理

..
..
.

に関する事柄を, より具体的に列挙する.
$P$を –語に納まる程度の大きさに選び,$\mathrm{Z}_{P}$

要素の演算を倍精度で行った後, 剰余の計算を行う $[11|$ .

-変数多項式は密であるとし, 配列 (ベクトル) で表現する. その演算はベクトル処理可能.
行列$Q$

に関する処理は, 多項式の高次幕乗計算も含め, ベクトル処理が可能.

計算量における
但し,

$n$

$n$

の因子の指数が, 実際の効果として, 小さく見えるようになることが期待される.

が大きくなければ実効性能は上がらない. よって,$n$が–定である GCD 計算より前の段

階まではベクトル処理の効果が上がるが, 扱う多項式の次数が次第に低下する GCD 計算の部分
では, 上記の多項式演算のベクトル処理が可能とは言え, ベクトル処理の効果はあまり期待でき.

ないであろう. 後述のとおり, GCD 計算の繰り返しは基本的に探索ゆえ, 並列処理向きである.

線形因子のみの積の分解 (求解) では, 多数の$\alpha$に対する (代入が) ベクトル処理可能.

15.5 ベクトル処理の実験と計測結果
これまでに, 15.2 節に示したアルゴリズム (Shoup のアルゴリズム:2 変数多項式の演算が必要) を

FORTRAN 77 でインプリメントし, (ベクトル処理型) スーパーコンピュ $-$ タ HITAC S-3800 : HIOSF/I-MJ (@東京大学大型計算機センター) 上で実験と計測を行っている. ソースの量は, 注釈行を含め, 共通して用いる副プログラム群が 2000 行,

各アルゴリズムのドライバーが 500 行程度である.

S-3800 の処理性能は, ベクトル演算器はの性能を有するが, スカラー演算器のみを使用す

.
.
.
.

$8\mathrm{G}\mathrm{f}\mathrm{l}\mathrm{o}\mathrm{p}/\mathrm{s}$る通常の数式処理システムの実行では SparcStation 2 の数倍程度である.
現時点で,
$Q$

Berlekamp, Zassenhaus 及び DDF で得られた各因子に対するより計算), Cantor&Zassenhaus, Ben-Or ($Q^{(k)}$$\mathrm{Z}\mathrm{a}s\mathrm{s}\mathrm{e}\iota\iota \mathrm{h}\mathrm{a}\mathrm{u}\mathrm{s}(Q^{(k)}$はは作成し直す) アルゴリズムを実現済み.

Berlekamp と Zassenhaus のアルゴリズムでは, Q-行列の作成により得られる$x^{p}$

mod $U(x)$ を用いて, 線形因子だけを最初に除去.

線形因子の分離は,$P$の大きさによって代入または二分探索を行う. 実験結果より, $P>$ 20000 の場合に二分探索とした.

実行用のベクトル化プログラムは, 各ループの実行直前にベクトル長が充分に大きいかを検査し,小さい場合にはスカラー処理を行うようにコンパイルした (そのオーバーヘッドを予想し改良も試みたが, 結果的に無視しうる程度であった).

140

いくつかの例題による実行時間を示す. 時間の単位は, 特に示さない限りマイクロ秒である. 但し,
表中に記載のないアルゴリズムは, 長大な実行時間を要したために計測を中断した場合である.

[15] 中の問題:(1)(表 2) $f_{1}(x)$$=$$x^{8}+x^{6}+10x^{4}+10x^{3}+8x^{2}+2x+8$$(\text{表}3)f_{2}(x)$$=$$x^{18}+9x^{17}+45x^{16}+126x^{15}+180x^{14}+27x^{13}-540x^{12}-1215x^{11}$$+1377x^{10}+15444x^{9}+46899x^{8}+90153x^{7}+133893x^{6}+125388x^{5}$$+29160x^{4}-32076x^{3}+26244x^{2}-8748x+2916$

次数が比較的高い場合 $(n=100)\cdots p=43$ , 1979, 227951 に対し, random に生成した(2).

の 100 次の多項式の因数\leftrightarrow L.
.

$v=43$ : 既約因子の個数は. 1. 2. 3. 4. 5. 7. 9. 10 次が各 5.

$\mathrm{D}=1979$$\mathrm{D}=$: 既約因子の個数は. 1. 2. 3. 4. 6. 8.

$\mathrm{g}$$7_{-}$

$2$

.

10-

$2_{-}1_{-}1$ .

$\rceil$ずつ.

次が各 6. 13. 3. $3_{-}2.1$ . ; ずつ.
$.’$

227951 : 既約因子の個数は. 1. 2. 3- 5. 6. 8. 10 次が各 5. 8. 3. 4. 2. 1, 3 ずつ.

$\mathrm{Z}_{P}$

上

141

142

表3

$f_{2}(x)$の因数分解の計算時間 (単位はマイクロ秒)

143$\blacksquare$.

実験結果に関して以上の計測結果に関して, 簡単なまとめを行う.

本稿では数値データを省略するが, 行列 $Q$ の構成と消去および DDF のステップではベクトル処理の効果は著しく, 特に行列 $Q$ に関するステップでは, 上記 $n=100$ の場合に, ベクトル処理.
.
.

を行った場合と行わない場合とでは計算時間に 10 倍程度の違いの生ずることが観測されている.
その結果, ステップ毎の計算量の比較からだけでは判然としないが, 実際の計算時間では GCD 計

算の繰り返しが支配的である.
この点で, 確率的アルゴリズムである Cantor&Zassenhaus では, 計算時間が乱数の生成に強く依存する –方,この点で Ben-Or アルゴリズムは安定している. その結果,[15] の結果と異なり,

Ben-Or のアルゴリズムは有用と思われる.
それ以上に注目すべきは, Zassenhaus のアルゴリズムがどの場合にも安定して速いことである.
特に, Berlekamp のアルゴリズムより確実に高速であることが観測されているが, この点は, 線

形従属関係を導く際と線形因子への分解におけるベクトル処理が功を奏しているのであろう.
$\circ$.

$Q$の消去の計算量と DDF の (最悪の場合の) 計算量は同等だが,$n$が大きい場合, DDF の途中

で多項式の次数が落ちていくことにより計算量が減ることがある.
このことから, 特に$n$が大きい場合, DDF の後 Zassenhaus のアルゴリズムを用いるという方法が有望と思われる. この方法も実際にインプリメントし, その計測結果を表中におさめた. しかし,

DDF のために必要となる計算時間とメモリ所要量は必ずしも小さくなく, 一般的な結論は

出せない.
さらに

Zassenhaus のアルゴリズムの優位性を確認するために, より高次の random に生成した多項式の因数分解も試みた. 図 1 に, 各アルゴリズムによる実行時間 (ベクトル処理を行った場合のSPU 時間) をグラフで示す. ここで用いた大部分の例では, 全ての既約因子の次数は異なっており (確率的なアルゴリズムでは DDF までで因数分解が求まる), 同じ次数の因子があった場合でも高々 3 個である.

これらの場合も Zassenhaus のアルゴリズムが高速であり,しかも注目すべきは, ここで試みた程度の次数では, 全体の計算時間が, ベクトル処理の結果, 計算量の$n^{3}$から$n^{2}$

程度にまで減少して見える点である. このことをより明確にするために, ベクトル長 $(=n)$ の変化しない行列$Q$の構成と消去の各ステップの計算時間を, ベクトル処理を行わない場合と行った場合 (の SPU 時間.

VPU 時間は SPU 時間にほぼ比例) の両方について, 図 2 にグラフとして示す. 図では, ベクトル処理を行わなかった場合にグラフの傾きが計算量と -致しているのに対し, ベクトル処理を行った場合,

あたかも計算量における$n$の指数が 1 程度減ったように見える.

いるこれらの処理では, VPU において確実にが$n^{2}$

又は$n$$n^{3}$

又は$n^{2}$

しかし, 完全にベクトル化されて個の要素が処理されており, その計算時間に比例することは説明がつかない. この点に関しては, 田中輝雄氏 (日立中研) より次の指摘があった: ベクトル長がベクトル演算としては小さく, しかもループ中の$\mathrm{Z}_{P}$

演算が極めて単純なため, ベクトル長に対する性能の立ち上がりが現れていない, 即ち, 計算時間中におけるオーバー

144

time
in
msec

$\perp\cup$$‘ \mathrm{U}$$\angle,\mathrm{U}\mathrm{U}$$\mathrm{d}\cup \mathrm{d}\mathrm{e}\mathrm{g}\mathrm{r}\mathrm{e}\mathrm{e}$図1$(n)\perp \mathrm{U}\mathrm{U}$アルゴリズムによる実行時間の比較 : 時間$\mathrm{v}\mathrm{s}$. 次数$o\cup\cup$

145

time
in

msec

time
in

msec

図2

行列 $Q$ の構成と消去の計算時間 : 時間$\mathrm{v}\mathrm{s}$. 次数

ヘッドの割合が大きく, その傾きに演算回数が現れていないものと思われる.

場合を試みた. 問題としては, 下記の [81 の例題を用いた (但し,$(x\mathrm{r}n/2\rceil+x+1)(x^{\lfloor \mathfrak{n}/2\rfloor}+x+1)$

そこで,さらに高次の$n=$ 1025, 2049, 4097):

mod

$p$

.

表 4 に, Zassenhaus のアルゴリズムによる計算時間を示す. 表中には, 計算量が正確に$n^{3}$に比例

146

高次多項式の Zassenhaus のアルゴリズムによる計算時間 (単位はミリ秒)

表4する零空間を求めるステップの計算時間の, 次数への依存度 (次数の比による幕乗の指数) も示した.
その数値を見る限り, この程度の大きな次数になると,$\log \text{次数^{}(}$i 什算時間) が 3 に近付いており, 上

記指摘の正しいことが確認される. いずれにせよ, 特にベクトル処理を行った場合, 従来から広く行われているような計算量及びそれによるアルゴリズムの比較が, あまり意味がないものと思われる.

15.6 並列処理の試み
高速化は, 残すところ GCD 計算による因子の分離のみ (Zassenhaus では, $w(X)=0$ の求根. 冒頭に記したとおり, 高速化の当初の目的に同じ) である.
間は, 次数よりも$P$

しかも, 本稿に示したような問題では, 計算時の大きさに強く依存する. この分離は基本的に探索の問題であるから, 並列処理による高速化が有望であろう. 通常, 前掲のアルゴリズムにおけるように, 次式に基づく二分探索を行うのが普通だが, $p-1$ が因子 $G$ を持つ場合,

より -般的な式を用いることも可能である $[10][4|$ .

$v(x)(v(x)^{(p-1)/2}-1)(v(x)^{(p-1)/2}+1)\equiv 0$ mod $U(x)$または $H_{k}(x)$ ,ここでは, 線形因子の積を分解する場合として, 次式による Distinct Order Factorization について触れておく.

$G$を $p-1$ の因子,$\xi$

を 1 の原始 $(p-1)$ 乗根とする.

$x^{p}-X \equiv\prod_{k=0}^{G-1}(x^{(p-1)/G}-\xi^{k(p-1)/G})$

mod

$p$

.

我々の行った実験は以下のとおり. 詳細及び実験結果については, [12] や [18] を参照されたい.
$G-1$ のループを分割並列化し,。

$k=0,1,$。

通信: あるプロセッサで non-trivial な $g=\mathrm{g}\mathrm{c}\mathrm{d}(w(x), x^{(p-1)/G}-\xi^{k(\mathrm{p}-1)/G})$ が見つかった場合$\ldots,$を通知し, 受信した各プロセッサ上で, 分解すべき多項式と$\mathrm{o}$$p-1=G_{1}G_{2}\cdots$

が多数の因子を持つ場合, 上記の処理を,$x^{\langle p-1\rangle/G}$$G_{1},$ $G_{2},$$\ldots$

とを

$g$

$g$

により簡約化.

間でパイプライン化する.

147

15.7 今後の課題
ベクトル処理の試みについては, 本稿で示した実測結果に見られるとおり, 予想以上に高速なソフト
ウェア部品が完成し, また, 特に次数 $\gg 1$ の場合に, ベクトル処理が非常に効果的であることが確認された. 実際 従来は殆んど試みることすら諦められていたような規模の (高次の) 多項式の因数分
解も, 容易に得られるようになっている. この状況を踏まえ, 今後さらに (1) 実用化, (2) さらに高次の多項式への対応, (3) 並列処理の進展等について, 検討を続けていく予定である.
実用化にあたっては,$\mathrm{Z}$上での因数分解及び多変数の場合への拡張は必須であろう. これらについて

は, Hensel 構成のベクトル処理や並列処理を検討実現していくことが必要であるし, また, 極めて高次の多項式が扱えるようになったために, 非常に多くの$\mathrm{Z}_{\mathrm{p}}$上の因子が得られた場合の trial division の組合せの問題についても検討する必要が生じてきている. これについては, 組合せの並列処理や, 多項式計算量の$L^{3}$

アルゴリズムの適用も考慮する必要がある. また, 多変数多項式に対しては, Kroneckerのトリック等についても検討の必要があるかもしれない.

さらに, こうして作られたソフトウェアを本当の意味で実用化するには, 既存の数式処理システム (たとえば$\mathrm{R}\mathrm{i}\mathrm{s}\mathrm{a}/\mathrm{A}\mathrm{s}\mathrm{i}\mathrm{r}$) とも, プロセス間通信等の技術を用いて, 影訃統合していく必要がある. より高次の多項式を扱う場合や並列処理については, アルゴリズムに関する研究が必要である. 152 節に示した各種のアルゴリズムから明らかなように, 因数分解は (1) 因子の個数の決定, (2) 適切な separating 多項式からなる.

$(v)arrow$の選択, (3) 探索の 3 つ

この点に関し, これらの組合せとして未だ発表されていない様々なアルゴリズムが可能であることと, 探索の部分において Zassenhaus のアルゴリズムが有用であることを指摘しておく. また, 高次 $(n\gg 1)$ の場合, 並列処理のための算法として, 反復法 (Wiedemann のアルゴリズム) に基づく [5] や, 直接解法のインプリメント法についても検討しなければならない. これらは, 主として (1) 及び (2) の段階を扱うものであるが,高次の場合には, 何等かの方法により (必ずしも既約でない) 因子へと分解し, 問題を break-down する必要がある$\mathrm{r}\mathrm{a}\mathrm{n}\mathrm{g}\mathrm{e}$

これに関しては, DDF を –般化した

decomposition [16] が有効と思われる. こうしたアルゴリズムの改良についても検討中である.

参考文献$[1]\mathrm{M}$. Ben-Or.

Probabilistic algorithms in finite fields. In Proc.

$\mathit{2}\mathit{2}nd$

IEEE Symposium on

Foundation of Computer Science, pp. 394-398, 1982.
$[2]\mathrm{M}$. Ben-Or and P. Tiwari.

A deterministic algorithm for sparse multivariate polynomialinterpolation. In Proceedings of 20th Symposium on the Theory of Computing, pp. 301-309,

Chicago, Illinois, May2-41988.

148$[3]\mathrm{E}$. R. Berlekamp. Factoring polynomials over finite fields. Bell System Technical Journal,

46:1853-1859, 1967.
$[4]\mathrm{D}$. G. Cantor and H. Zassenhaus. A new algorithm for factoring polynomials over finite fields.

Mathematics of Computation, 36:587-592, 1981.
$[5]\mathrm{E}$. Kaltofen. Analysis of Coppersmith’s block Wiedemann algorithm for tlze parallel solutionof sparse linear systems. Mathematics of Computation, 1995. (to appear).
$[6]\mathrm{E}$. Kaltofen and Y. Lakshman. Improved sparse multivariate polynomial interpolation algo-rithms. In P. Gianni, editor, Symbolic and Algebraic Computation, ISSA

$C’ \mathit{8}\mathit{8}$, number 358

in LNCS, pp. 467-474, Rome, Italy, July 4-81988. Springer-Verlag.
$[7]\mathrm{E}$. Kaltofen, Y. N. Lakshman, and J.-M. Wiley. Modular rational sparse multivariate poly-

nomial interpolation. In S. Watanabe and M. Nagata, editors, Proceedings of ISSA

$C’ \mathit{9}\mathit{0}$, pp.

135-139, Tokyo, Japan, Aug. 20-241990.
$[8]\mathrm{E}$

Factoring. Kaltofen and A. Lobo.

$\mathrm{h}\mathrm{i}\mathrm{g}$-degree polynomials by the black box Berlekamp

algorithm. In J. von zur Gathen and M. Giesbrecht, editors, Proceedings of ISSA

$C’ \mathit{9}\mathit{4}$, pp.

90-98, Oxford, England, July 20-221994.
$[9]\mathrm{R}$. J.

$\mathrm{M}\mathrm{c}\mathrm{E}\mathrm{l}\mathrm{i}\mathrm{e}\mathrm{c}\mathrm{e}$. Factorization of polynomials over finite fields. Mathematics of Computation,

23:861-867, 1969.
[10]R. T. Moenck.

On the efficiency of algorithms for polynomial factoring. Mathematics ofComputation, 31 $(137):235-250$ , Jan. 1977.
[11]H. Murao.

Vectorization of symbolic determinant calculation.

SUPER COMPUTER,VIII (3) $:36-48$ , May 1991.
[12]H. Murao and T. Fujise. Modular algorithm for sparse multivariate polynomial interpolationand its parallel implementation. In H. Hong, editor, Proceedings of PASCO ’94, pp. 304-315,
Linz, Austria, Sept. 26-281994.

[13]A. C. Norman and J. Mitchel.

Factorization in a functional language. In J. Della Doraand J. Fitch, editors, Computer Algebra and Parallelism, Computational Mathematics andApplications, pp. 133-141. Academic Press, 1989.
[14]V. Shoup. On the deterministic complexity of factoring polynomials over finite fields. Infor-

mation Processing Letters, $33(5):261-267$ , Jan. 1990.
[15]V. Trevisan and P. Wang. Practical factorization of univariate polynomials over finite fields.

In S. M. Watt, editor, Proceedings of ISSA

$C’ \mathit{9}\mathit{1}$, pp. 22-31, Bonn, Germany, July 15-171991.

[16]J. von zur Gathen and V. Shoup. Computing Frobenius maps and factoring polynomials.

Computational Complexity, 2:187-224, 1992.
[17]H. Zassenhaus. On Hensel factorization. J. Number Theory, 1:291-311, 1969.
$[18]\ovalbox{\tt\small REJECT}$.

$\backslash \Phi F|\mathrm{J}_{\mathrm{p}\hslash 8}^{\overline{--}\mathrm{A}}\text{理^{}*}\Rightarrow\overline{=}|1_{\mathrm{D}^{-}}^{---\mathrm{x}\text{処理}w/}\overline{\mathrm{Q}}\mathrm{D}$

’

KLIC

$l_{\sim}^{}‘ \mathrm{k}\text{る}$PARI$\text{の}\backslash \Phi F^{1}\mathrm{I}4\mathrm{b}$, 1985.

.

$(\text{本}\hat{\overline{- i}}\mathfrak{F}_{X}^{\mathrm{A}}\backslash \not\in\overline{\mathfrak{X}})$