数理解析研究所講究録
第 1572 巻 2007 年 50-58

50

整数係数多項式の近似 GCD II
長坂耕作
KOSAKU NAGASAKA

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

1

はじめに
本発表では, 第 16 回日本数式処理学会大会で発表し, その後証明等を行い雑誌に投稿した 「整数係数多

項式の近似 $GCD$ 」 を多変数多項式に拡張する予備実験を行った結果を取り扱っています. 従って, 整数係数多項式の近似 GCD について一変数多項式の結果を簡単に紹介した上で, 多変数多項式に対する整数上の近似 GCD にっいての実験の報告を行います.

一変数多項式の整数係数の近似 GCD

2

一変数多項式や多変数多項式の複素数体上での近似 GCD を求める研究は非常多くの成果が発表 [9, 4, 2,
13, 26, 25, 3, 27, 19, 29, 28, 21, 10, 18, 6, 20, 5, 15, 17, 22, 24] されています. しかしながら, 係数を整数に限定した近似 GCD, 即ち係数部が離散的に変化する場合の近似 GCD を求める問題に取り組んだ例はありませんでした. 一見すると, 浮動小数点数であるゆえに誤差が問題になるための近似 GCD であり, 係数部が整数で近似 GCD を求める意義はないように思えますが, 整数計画問題などに代表されるように, 実際の社会の問題の多くは離散的な数を扱わなければなりません. 本発表では, 係数部の変化が整数上に制限される近似 GCD を次のように定義します.

定義 1(一変数の整数係数多項式の整数上の近似 GCD)

を小さな正整数とする. このとき, ある一変数多項式あ-9-, ,が次式を満たすならば, 次式を満たす多項式 $h(x)$ を整数係数多$f(x)$ と $g(x)$$\Delta_{9}\in Z[x]$ が存在して,$f(x)$ と $g(x)$ を $Z$ 上の一変数多項式とし,$\Delta_{f},$$h$$\epsilon$

項式の整数上の近似 GCD という.
$f(x)=\overline{f}(x)h(x)+\Delta_{f}(x),$ $g(x)=\overline{g}(x)h(x)+\Delta_{g}(x),$また, 多項式$\overline{f}(x)$と$\overline{g}(x)$$\epsilon=\max\{||\Delta_{f}||, \Vert\Delta_{g}\Vert\}$を整数係数多項式の整数上の近似余因子と,は多項式 $p(x)$ の適当なノルムとする$\epsilon$.

をその許容度と呼ぶ. なお,(1)$||p||$$\triangleleft$

この定義から整数上の近似 GCD も通常の近似 GCD と同じく, 同じ許容度でも一意に定まらないことがわ

本稿では許容度の最小化などは扱いません. 例えば次の 2 つの問題は今後の課題とします. 即
ち, 本稿での許容度は後退誤差になります.

かりますが,*nagasal@main. h.kobbu. ac.jp

51
問題 1(一変数の整数係数多項式の整数上の最近近似 GCD)
一変数の整数係数多項式 $f(x)$ と $g(x)$ に対し,を最小化する (1) 式を満たす定数でない整数係数多項式 $h(x)$ を求めよ. そのような $h(x)$ を整数係数多項式の整数上の最近近似 GCD と呼ぶ.
$\epsilon=\max\{\Vert\Delta_{f}\Vert, \Vert\Delta_{g}\Vert\}$$\triangleleft$

問題 2(一変数の整数係数多項式の整数上の最良近似 GCD)
かつ (1) 式を満たす定
一変数の整数係数多項式 $f(x)$ と $g(x)$ , 閾値に対し,数でない整数係数多項式 $h(x)$ を求めよ. そのような $h(x)$ を整数係数多項式の整数上の最良近似 GCD と呼$\epsilon\in N$ぶ.

この定義では,$\max\{\Vert\Delta_{f}\Vert, \Vert\Delta_{9}\Vert\}\leq\epsilon$$h(x)$ の次数を最大化していないことに注意されたい$\triangleleft$

例 1(互いに素な整数係数多項式の近似 GCD)
$f(x)$ と $g(x)$ を次の互いに素な整数係数多項式とします.
$f(x)$$=$$54x^{6}-36x^{5}-192x^{4}+42x^{3}+76x^{2}-62x+15$ ,$g(x)$$=$$73x^{5}+36x^{4}-103x^{3}-70x^{2}-48x+35$.

この多項式の組は次のような近似 GCD を持ちます.
$f(x)$$g(x)$

この例では,$\approx$$(6x^{4}-10x^{3}-8x^{2}+7x-3)(9x^{2}+9x-5)$$=$$54x^{6}-36x^{5}-192x^{4}+4\underline{1}x^{3}+76x^{2}-62x+15$$\approx$$(8x^{3}-4x^{2}-3x-7)(9x^{2}+9x-5)$$=$$7\underline{2}x^{6}+36x^{4}-103x^{3}-70x^{2}-48x+35$$\Delta_{f}=-x^{3},$ $\Delta_{9}=-x^{5},$ $\epsilon=1$に素な多項式の許容度$\epsilon=1$,.

になっており, 最近近似 GCD であることがわかります. 互いの近似 GCD は常に最近近似 GCD になります.

$\triangleleft$

整数は複素数に含まれるので, 一見すると従来の近似 GCD アルゴリズムで, 整数上の近似 GCD を求めることが出来るように思えます. 実際, 係数部に含まれる誤差が小さい (簡単な実験では, 相対的に $10^{-10}$程度であれば十分) 場合, 従来の方法でも計算できることが多いです.

しかしながら, 前述の例 1 における程度になっており, 非常に大きいことがわかります. 更に, 従多項式では, 相対的な誤差の大きさは$10^{-3}$

来のアルゴリズムを使った場合には,どのようにして複素数を整数に丸めれば良いかという新たな問題もあります. 具体的に問題を確認するために, 前述の例 1 の多項式を Kaltofen らのアルゴリズム [8] を用いて近似 GCD を計算したのが次の式になります (Kaltofen らによるアルゴリズムの実装を用いて実験を行っています).
$f(x)$$(1.00x^{2}+0.99x-0.55)(54.34x^{4}-90.20x^{3}-72.20x^{2}+63.65x-27.07)$ ,$g(x)$$(1.00x^{2}+0.99x-0.55)(72.84x^{3}-36.20x^{2}-26.83x-63.33)$ .

この例では後退誤差が $10^{-8}$ という非常に小さい結果が得られていますが, どのようにして整数に丸めれば良いかが問題となります. 単純な四捨五入では例 1 の結果は得られないことが確認できます. そのため, 本発表やその先行研究 [16] では複素数体に係数環を拡大することなく, 整数の範囲で直接計算する方法を提案しています. 一連の方法は非常に簡単で, 格子算法 [23, 12, 1] により部分終結式の写像の零空間を計算するだけです.

2.1

格子算法による GCD 計算

近似を考えない厳密な GCD 計算では, 多項式剰余列による Euchd の互除法が使われますし, 近似 GCD
計算においても同じ性質を QR 分解や特異値分解を行って求めます (もちろん, 最近のアルゴリズムはよ52
り複雑になっていますので, あくまでも概要です). これらのアルゴリズムは言い替えれば, ほとんどが部
分終結式写像に基づいています. 本発表とその先行研究においても, 部分終結式写像の性質を格子算法で求めることで, 整数係数多項式の近似 GCD を求めています. そこで, まずは部分終結式写像と格子算法による厳密な多項式 GCD の計算方法について簡単に説明します.

211

部分終結式写像$f(x)$ と $g(x)$ を次の整数係数多項式とします.
$f(x)=f_{n}x^{n}+f_{n-1}x^{n-1}+\cdots+f_{0},$ $g(x)=g_{m}x^{m}+g_{m-1}x^{m-1}+\cdots+g_{0}$

また, $f(x)$ の$k$

次の畳み込み行列を $C_{k}(f)$ とします.

.

$C_{k}(f)=\{\begin{array}{llll}f_{0} 0 0| f_{0} \ddots |f_{n} | \ddots 00 f_{n} f_{0}| \ddots \ddots |0 0 f_{n}\end{array}\}\in Z^{(n+k)xk}$

次の写像 $Syl_{r}(f, g)$ のことを,$f(x)$$Syl_{r}(f,g)$

ここで, $r=0,$$\ldots$:と $g(x)$ の$\mathcal{P}_{m-r-1}$$r$$\cross$$r$

次の部分終結式写像といいます.
$\mathcal{P}_{n-r-1}$$(s(x) t(x))$, $\min\{n, m\}-1$ であり,られる性質としては.
$g(x)$ の,$\mathcal{P}_{d}$$arrow$$rightarrow$,$s(x)f(x)+t(x)g(x)$ ,$\mathcal{P}_{n+m-r-1}$

は $d$ 次以下の多項式全体の集合とします.

GCD 計算に用いを写像が単射とならない最大整数としたとき, $f(x)/t(x)$ と $g(x)/s(x)$ が $f(x)$ とGCD になるというのがあります.

畳み込み行列を用いることで, この部分集結式写像の行列表現である $Syl_{r}(f,g)=(C_{m-r}(f)C_{n-r}(g))$と $t(x)$ を求めることを得られます. そして, $Syl_{r}(f, g)$ の零空間を求めることで GCD 計算に必要な$Syl_{0}(f,g)^{t}$の QR 分解を用いていができます. 実際, 近似 GCD のアルゴリズムのいくつか $[3, 25]$ では,$\epsilon(x)$ます (厳密な GCD 計算の場合など, 詳細な情報については [11, 9, 21] などを参照のこと).

格子算法による GCD 算法

212

近似 GCD アルゴリズムでは QR 分解で零ベクトルを計算しますが, 本発表と先行研究では良く知られている LLL アルゴリズム [12] を使って求めます. 格子算法と呼ばれるもので, 与えられた整数格子 $L=$$\{r_{1}\tilde{v}_{1}+\cdots+r_{d}v_{d}arrow|r_{1}\in Z\}\subseteq Z^{k}$に含まれるベクトルの中から, 次を満たす短いベクトル奮を捜し出すことができます.
$||u \urcorner|\leq 2^{(d-1)/2}\min\{\Vert v\urcorner||0\sim\neq v\sim\in L\},\tilde{u}\in L$$2^{(d-1)/2}$という上限はかなり大きいように思えますが,.

LLL アルゴリズムはほとんどの場合,

この上限に比べてはるかに短いベクトルを発見することができます (格子算法については [23, 12, 1] を参照のこと).
$E_{i}$

を $ixi$ の単位行列,$c_{B}$$(E_{\mathfrak{n}+m-2r}|c_{B}xSyl_{r}^{t}(f, g))$照のこと) .

を整数とし,$(n+m-2r)x(2n+2m-3r)$ の大きさの行列$Syl_{r}^{B}(f,g)$をと定義します. このとき次の補題が成り立ちます (証明については [16] を参

53
補題 2
$B$

を $f(x)$ と $g(x)$ の Landau-Migno $tte$ の上限 $lI4j$ のうち大きい方とし, $c_{B}=2^{(n+m-2r-1)/2}\sqrt{n+m-2r}B$を部分集結式写像が単射とならない最大整数とすれば, LLL アルゴリズムにより $Syl_{r}^{E}(f, g)$ の短いベクトルを求めることができ, その最初の $(n+m-2r)$ 個の要素は $f(x)$ と $g(x)$ の GCD の余因子の
とする.

$r$

係数ベクトルのスカラー倍になっている
この補題での$c_{B}$$\triangleleft$

は, Landau-Mignotte の上限を使っていることもあり非常に大きくなっていますが,とんどの場合, LLL は小さな

$c_{B}$

ほに対しても必要となる短いベクトルを計算してくれます例 2(格子算法による GCD 計算の例)
次の互いに素でない非常に簡単な多項式の GCD を求めてみます.
$f(x)$$=$

49x2 $-25$$=$$g(x)$$=$$49x^{2}+70x+25$$=$$(7x-5)(7x+5))$$(7x+5)(7x+5)$ .

まず, 次のように行列 $Syl_{0}^{E}(f,g)$ を作ります. 補題は非常に大きな$c_{B}$

に対してのみ保証されていますが,計算効率の面から $c_{B}=1$ としています. そして, この行列に LLL アルゴリズムを適用すると, 右側の行列が得られます.

($0001$$0001$$0001$$0001|-252500$$-2570250$$4949700$$494900)arrow(-5-2-20$$-1-3-7-2$$-1-2-5-2$$3371|-25000$$-20-15100$$2114140$$49000)$.

最初の行ベクトルが余因子に対応しており, 実際, $7x-5$ と $7x+5$ の係数ベクトルが表れているのが確認できます. その結果, 元の多項式を除することで多項式 GCD である $7x+5$ を得られます.
2 における大きな

213$c_{B}$

でなくとも, 必要な短いベクトルが小さな$c_{B}$

この例は補題でも見付かることも示唆しています.

$\triangleleft$

格子算法による近似 GCD 算法

整数上の近似 GCD を求める場合, 実際には互いに素な多項式同士になるため. 近似余因子の係数ベクト
ルが部分集結式写像の行列表現の零空間に含まれなくなります. しかし, 係数部の摂動により互いに素でなくなることから, 近似余因子の係数ベクトルの零ベクトルからの差の大きさは小さいと考えられます. 即ち,
補題 2 と同様に, 近似余因子の係数ベクトルを格子算法による $Syl_{r}(f, g)$ からの短いベクトルの検出に置き換えることができます. これにより, $s(x)f(x)+t(x)g(x)\approx O$ を満たす近似余因子候補である $s(x),$ $t(x)$$\in Z[x]$ も求められます. 近似 GCD を $h(x)$ とすれば, $f(x)\approx t(x)h(x)$ と $g(x)\approx-s(x)h(x)$ なる関係が成り立っています.
厳密な場合, 余因子候補から GCD である $h(x)$ を求めるには, 単純に $f(x)$ を $t(x)$ で除すれば良いだけですが, 近似 GCD では $f(x)\approx t(x)h(x)$ と $g(x)\approx-s(x)h(x)$ なる関係しかありませんので, 単純に除すを整数として, 大きさ
るだけでは近似 GCD を求めることはできません. そこで, 先行研究 [16] では,$c_{H}$が $(r+2)x(n+m+r+4)$ なる次の行列 $H(f,g, t, s)$ を使って計算しています ($\vec{f}$と $g(x)$ の係数ベクトルです).

$H(f,g,t,s)=(E_{r+2}|$$c_{H}\cross C_{r+1}(-t)^{t}c_{H}xf^{-}$$c_{H}xC_{r+1}(s)^{t}c_{H}\cross\vec{g}$$)$.

と互はそれぞれ $f(x)$

54
補題 3
$B$

を $f(x)$ と $g(x)$ の Landau-Mignotte の上限のうち大きい方とし,$c_{H}=2^{(r+1)/2}\sqrt{r+2}B$

とする.

を部

$r$

分集結式写像が単射とならない最大整数とすれば, LLL アルゴリズムにより $H(f,g, t, s)$ の短いベクトルを求めることができ, その 2 番目から $(r+2)$ 番目までの要素は $f(x)$ と $g(x)$ の係数ベクトルのスカラー倍になっている$\triangleleft$

この補題は厳密な場合の話ですが, 近似 GCD の計算についても十分機能することを次の例で確認します.

例 3(格子算法による近似 GCD 計算の例)

前出の例の多項式を少しだけ変動させた次の互いに素な多項式の近似 GCD を求めてみます.
$f(x)$$=$

49x2 $-24$$g(x)$$=$$49x^{2}+70x+25$$=$$(7x-5)(7x+5)-1$ ,$=$$(7x+5)(7x+5)$ .

まず, 次のように行列 $Syl_{0}^{B}(f,g)$ を作ります $(cB=1)$ . そして,ると, 右側の行列が得られます.

($0001$$0001$$0001$$0001|-242500$$-2425700$$4970490$$494900)arrow(-5-237$$-7-395$

この行列に LLL アルゴリズムを適用す$-5-263$$-4-973|-18-2-53$$-10-21-77$$141407$$49000)$.

右側半分の係数ベクトルに対応していた部分の大きさが最も小さい 2 行目を近似余因子候補として取り出
し, 次のように行列 $H(f,g, t, s)$ を作ります $(c_{H}=1)$ . そして, この行列に LLL アルゴリズムを適用す
ると, 右側の行列が得られます.

(

$001$

$001$

$001|-2450$$-705$$-7490$$-5250$$-7490)arrow(001$$-7-570$$051$$071|051$$-705$$-700$$\frac{0}{0}5$$-7-50$$-700)$.

1 行目のベクトルに近似 GCD である $7x+5$ と変動に対応する係数ベクトルが出現しているのがわかると思います.

この例では, $7x-5$ と $7x+5$ が整数上の近似余因子, 許容度が 1 になっています.

ここまでの議論をまとめたものが次のアルゴリズムになります.
アルゴリズム 1(1 変数版の整数上の近似 GCD アルゴリズム)

InPut: $f(x),$ $g(x)\in Z[x]$ , of degrees$n$and $m$ , resPectively.

Output;and $g(x)\approx t(x)h(x)$ .
; while1.
do 2-8
2. $r arrow\min\{n, m\}-1$ ; while $r\geq 0$ do 3-7$carrow 1$ ; while3.
do4.
construct a matrix $Syl_{r}^{B}(f,g)$ vvith , apply the LLL algoritbm anfor each short vector do 55.
construct a matrix $H(f, g, t, s)$ , apply the LLL algorithm,
let $h(x),t(x),$ $s(x)$ be candidate approximate GCD and cofactors, andoutput $s(x),t(x),$ $h(x)$ if $\max\{\Vert f(x)-t(x)h(x)\Vert, \Vert g(x)-s(x)h(x)||\}\leq\epsilon$$carrow cx10$6.
$s(x),$ $t(x),$ $h(x)\in Z[x]satis\theta ingf(x)\approx s(x)h(x)$$\epsilonarrow 1$$\epsilon<\min\{\Vert f\Vert, \Vert g\Vert\}$$c\leq c_{B}$$4\triangleleft$$\backslash$

$c$

7.

$rarrow r-1$

$d$

55
8.

$\epsilonarrow\epsilon\cross 10$

9. output “not found”.

$\triangleleft$

このアルゴリズムの詳細については触れませんが, ステップ 1 での
$1$,$\epsilon=1$, ステップ 2 での $r= \min\{n, m\}-$ステップ 3 での $c=1$ など, 近似 GCD 計算ゆえのパラメータ設定や LLL アルゴリズムの特性を考えた

計算効率上の配慮などを行っています. 従って, これらの値を変化させることでアルゴリズムの効率や結果は大きく変わることになります.

3

多変数多項式の整数係数の近似 GCD

多変数多項式の整数上の近似 GCD についても, 基本的な考え方や方法は同じです. 単純に, 部分終結式
写像とその行列表現を多変数の場合のものを用いて, 格子算法で近似余因子候補を求め, 再度格子算法により近似 GCD を求めることになります. 多変数多項式の近似 GCD や厳密な GCD 計算にも複数のアルゴ
リズムが知られていますが, 本研究で取り上げる部分終結式写像の行列は Gao らによる近似 GCD[7] で用いられているものと同じです. まずは, 多変数多項式に関する近似 GCD の定義を行っておきます.

定義 4(多変数の整数係数多項式の整数上の近似 GCD)
$f(\tilde{x})$と$g(\tilde{x})$と同が存在して,を整数係数多項式の整数上の近似 GCD という.

変数多項式
$h(\vec{x})$を $Z[x\urcorner=Z[x_{1}, \ldots, x_{\ell}]$ 上の多変数多項式とし,$\overline{f},\overline{g},$$h,$$\Delta_{f},$$\Delta_{g}\in Z$$f(\tilde{x})$$f(\vec{x})=\overline{f}(\tilde{x})h(\tilde{x})+\Delta_{f}(\tilde{x}),$

また, 多項式は多項式$f(\tilde{x})$$p(x\neg)$$\overline{f}(\vec{x})$と$\overline{g}(\vec{x})$$g(\tilde{x})$$\epsilon$

を小さな正整数とする. このとき, ある多が次式を満たすならば, 次式を満たす多項式$g(\vec{x})=\overline{g}(\vec{x})h(\vec{x})+\Delta_{g}(\vec{x}),$$\epsilon=\max\{||\Delta_{f}||, ||\Delta_{g}||\}$

を整数係数多項式の整数上の近似余因子と,$\epsilon$.

(2)をその許容度と呼ぶ. なお,$||p\Vert$の適当なノルムとする$\triangleleft$と $g(X)$ を整数係数多項式とし, それぞれの全次数を $n=t\deg(f)$ と $m=t\deg(g)$ とします. 本発表

では, 次の写像 $Syl_{r}(f,g)$ のことを,$f(\vec{x})$と$g(\vec{x})$の $r$ 次の部分終結式写像として 1 変数多項式と同じように扱います.
$Syl_{r}(f,g):\mathcal{P}_{m-r-1}(s(\tilde{x}) x \mathcal{P}_{n-r-1}t(\vec{x}))$

ここで, $r=0,$$\ldots$, $\min\{n, m\}-1$ であり,多項式の場合と同様に,$g(\tilde{x})$の$r$$\mathcal{P}_{d}$$-arrow$

は全次数が

$d$

$\mathcal{P}_{n+m-r-1}s(\vec{x})f(\vec{x})+t(\tilde{x})g(d)$,次以下の多項式全体の集合とします. 1 変数を写像が単射とならない最大整数としたとき,$f(\tilde{x})/t(\vec{x})$と $g(\vec{x})/s(\vec{x})$ が$f(\vec{x})$とGCD になります.

多項式
す. 即ち,$p(\vec{x})$の係数ベクトル$f(\vec{x})$$\vec{P}$の係数ベクトルは,$\tilde{f}$その多項式の全次数以下の単項式を辞書式順序で並べたものを用いまは, 全次数 $n$ 次以下の単項式の辞書式順序で並べたもの,$g(\tilde{x})$の係数ベクトルすは, 全次数 $m$ 次以下の単項式の辞書式順序で並べたものになります. 多変数版のを満たす行列として定義します. この畳に対し
み行列 $C_{k}(f)$ は, 全次数が の多項式
み込み行列を用いることで, この部分集結式写像の行列表現である $Syl_{r}(f,g)=(C_{m-r}(f)C_{n-r}(g))$ を得をとられます. そして, 1 変数と同様に $Syl_{r}(f, g)$ の零空間を求めることで GCD 計算に必要な
$k$

$k$

$p(\vec{x})$次の畳み込$C_{k}(f)p^{arrow}=\vec{fp}$$s(\vec{x})$求めることができます. 後の処理は 1 変数多項式の場合と同じく,$Syl_{r}^{B}(f, g)$$c_{B}$$t(\vec{x})$倍を行って単位行列を付加した行列に対して LLL アルゴリズムを適用し, 求まった近似余因子候補から行列 $H(f,g, t, s)$ を作り近似 GCD を求めます.

56
例 4(多変数多項式の近似 GCD 計算の例)
次の簡単な多項式で, 多変数の場合の整数上の近似 GCD を求めてみます.
$f(x, y)$$=$$49x^{2}-24y^{2}-1$$=$$(7x-5y)(7x+5y)-1+y^{2}$ ,$g(x, y)$$=$49x2 $-70xy+25y^{2}$$=$$(7x-5y)(7x-5y)$ .

まず, 次のように行列 $Syl_{0}^{E}(f,g)$ を作ります$[000001$

そして,$000001$$000001$$000001$$000001$$000001$$-100000$$(c_{B}=1)$$-24250000$$\frac{0}{0,000}1$.

$-24250000$$-100000$$-7000000$$-24-7025000$$49490000$$49490000]$$-704949000$

この行列に LLL アルゴリズムを適用すると, 次の行列が得られます.

$(-100001$$-7-93050$$-2 \frac{507}{0}3$$000001$$-2 \frac{560}{0}3$$\frac{000}{0,1}1$$-3 \frac{907}{0}4$$-24490000$$-5-72030$$-2 \frac{-50}{0}318$$-3 \frac{907}{0}5$$-7000000$$-10-7-72100$$4900000$$-141400704900000]$

近似 GCD の場合, 右側半分の係数ベクトルに対応していた部分の大きさが最も小さいベクトルが近似余因子とは限らず, 小さい順に試行する必要があります. 順次試行することで結果として 2 行目が近似余因子に対応していることがわかるので, その場合の処理についてのみ紹介します. 2 行目を取り出し, 次のように
行列 $H(f, g, t, s)$ を作ります$(0001$

そして,$0001$$0001$$(c_{H}=1)$$0001|-1000$.

$0050$$-24005$$49007$$0075$$0007$$0000$$\frac{0}{0,0}5$$\frac{20}{0}55$$0070$$-70-507$$49007)$

この行列に LLL アルゴリズムを適用すると, 次の行列が得られます.

$(0001$$0001$$0501$$-7001|-1000$$0050$$0051$$0070$$0057$$0007$$0000$$\frac{0}{00}5$$\frac{00}{0}5$$0070$$-5007$$0007)$

1 行目のベクトルに近似 GCD である $7x-5y$ と変動に対応する係数ベクトルが出現しているのがわかると思います. この例では, $7x+5y$ と $7x-5y$ が整数上の近似余因子, 摂動多項式力\sim 2--1 になっています.

4

まとめ
本発表では, 1 変数多項式の場合と同様に多変数多項式の整数上の近似 GCD を計算する方法の取り組みについて取り上げました. 1 変数多項式の厳密な場合の補題等, 多変数多項式の場合にも自然に拡張できる
ものの証明を与えていない点など未着手の部分もありますが, 同じ方法で計算できる可能性を示せました.

57
今後の課題としては, 本方法における近似 GCD の発見が LLL アルゴリズムに直接依存しすぎしていることの改善 (ナップザック法による因数分解ではそうではない) と, 多変数多項式の場合には計算時間が非常にかかることの改善などを考えています. なお, 実験に使用した Mathematica のプログラムは, SNAP
パッケージとして公開予定ですが, 現在のコードは古い Mathematica 用になっているため, これも今後の課題となっています.

参考文献[1] W. Backes and S. Wetzel. Heuristics on lattice basis reduction in practice. ACM J.

$E\varphi$. Algorithmics,

7:21 pp. (electronic), 2002. Fourth Workshop on Algorithm Engineering (Saarbr\"ucken, 2000).
[2] D. Christou and M. Mitrouli. Estimation of the greatest common divisor of many polynomials
using hybrid computations performed by the ERES method. Appl. Numer. Anat. Comput. Math.,$2(3):293-305$ , 2005.
[3] R. M. Corless, S. M. Watt, and L. Zhi. $QR$ factoring to compute thepolynomials. IEEE }$uns$ . Signal Process., $52(12):3394-3402$ , 2004.

$G$

CD of univariate approximate$?$[4] G. M. Diaz-Toca and L. Gonzalez-Vega. Computing greatest common divisors and squarefree decompositions through matrix methods: the parametric and approximate cases. Linear Algebra Appl.,$412(2- 3):222-246$ , 2006.
[5] I. Z. Emiris, A. Galligo, and H. Lombardi. Numerical univariate polynomial GCD. In The mathematics of numerical analysis (Park City, $UT$, 1995), volume 32 of Lectures in Appl. Math., pages
323-343. Amer. Math. Soc., Providence, RJ, 1996.

[6] I. Z. Emiris, A. Galligo, and H. Lombardi. Certified approximate univariate GCDs. J. Pure Appl.
Algebra, 117/118:229-251, 1997. Algorithms for algebra (Eindhoven, 1996).
[7] S. Gao, E. Kaltofen, J. May, Z. Yang, and L. Zhi. Approximate factorization of multivariate polynomials via differential equations. In ISSAC 2004, pages 167-174. ACM, New York, 2004.

[8] E. Kaltofen, Z. Yang, and L. Zhi. APproximate greatest common divisors of several polynomials
with linearly constrained coefficients and singular polynomials. In ISSAC 2006, pages 169-176.
ACM, 2006.
[9] N. Karcanias, S. Fatouros, M. Mitrouli, and G. H. Halikias. Approximate greatest common divisorof many polynomials, generalised resultants, and strength of approximation. Comput. Math. Appl.,$51(12):1817-1830$ , 2006.

[10] N. K. Karmarkar and Y. N. Lakshman. On approximate GCDs of univariate polynomials. J. Symbolic
Comput., $26(6):653-666$ , 1998. Symbolic numeric algebra for polynomials.

[11] M. A. LaidaCker. Another theorem relating Sylvester’s matrix and the greatest common divisor.
Math. Mag., 42:126-128, 1969.
[12] A. K. Lenstra, H. W. Lenstra, Jr., and L. Lov\’asz. Factoring polynomials with rational coefflcients.
Math. Ann., $261(4):515-534$ , 1982.
[13] T. Y. Li and Z. Zeng. A rank-revealing method with updating, downdating, and applications. SIAM
J. Matrix Anal. Appl., $26(4):918-946$ (electronic), 2005.

58[14] M. Mignotte. An inequality about factors of polynomials. Math. Comp., 28:1153-1157, 1974.
[15] M. Mitrouli and N. Karcanias. Computation of the GCD of polynomials using Gaussian transformations and shifting. Intemat. J. Control, $58(1):211-228$ , 1993.

[16] K. Nagasaka. APproximate gcd of two univariate polynomials over integers. (submitted), 2007.

[17] M.-a. Ochi, M.-T. Noda, and T. Sasaki. Approximate greatest common divisor of multivariate
polynomials and its application to ill-conditioned systems of algebraic equations. J. Info $rm$ . Process.,$14(3):292-300$ , 1991.
[18] V. Y. Pan. Approximate polynomial gcds, Pad\’e approximation, polynomial zeros and bipartite
graphs. In Prvceedings of the Ninth Annual ACM-SIAM Symposium on Discrete Algorithms $(San$$fi\}nncisco,$ $CA$ , 1998), pages 68-77, New York, 1998. ACM.

[19] V. Y. Pan. Computation of approximate polynomial GCDs and an extension. Infom. and Comput.,$167(2):71-85$ , 2001.

[20] C. R\"ossner and J.-P. Seifert. The complexity of approximate optima for greatest common divisor
computations. In Algo nithmic number theory (Talence, 1996), volume 1122 of Lecture Notes in
Comput. Sci., pages 307-322. Springer, Berlin, 1996.

[21] D. Rupprecht. An algorithm for computing certified approximate GCD of univariate polynomials.
J. Pure Appl. Algebm, $139(1- 3):255-284$ , 1999. Effective methods in algebraic geometry (Saint-Malo,$n$1998).

[22] T. Sasaki and M.-T. Noda. Approximate square-free decomposition and root-finding of ill-conditioned
algebraic equations. J. Inform. Process., 12(2):159-168, 1989.

[23] C.-P. Schnorr and M. Euchner. Lattice basis reduction: improved practical algorithms and solving
8ubset sum problems. Math. Prvgramming, 66(2, Ser. ) $:181-199$ , 1994.
$A$[24] A. Sch\"onhage. Quasi-gcd computations. J. Complexity, $1(1):118-137$ , 1985.
[25] C. J. Zarowski, X. Ma, and F. W. Fairman. QR-factorization method for computing the greatest
common divisor of polynomials with inexact coefficients. IEEE ttuns. Signal Prooess., $48(11):3042-$
3051, 2000.
[26] Z. Zeng and B. H. Dayton. The approximate GCD of inexact polynomials. II. A multivariate
algorithm. In ISSAC 2004, pages 320-327. ACM, New York, 2004.
Displacement structure in computing approximate GCD of univariate polynomials.

In
Computer mathematics, volume 10 of Lecture Notes Ser. Comput., pages 288-298. World Sci. Publ.,[27] L. Zhi.

River Edge, NJ, 2003.

[28] L. Zhi and M.-T. Noda. Approximate GCD of multivariate polynomials. Surekaisekikenkyusho
Kokyeirohu, $(1138):64-76$ , 2000. Research on the theory and applications of computer algebra(Japanese) (Kyoto, 1999).
[29] L. H. Zhi and M.-T. Noda. Approximate GCD of multivariate polynomials. In Computer mathematics(Chiang $Mai$, 2000), volume 8 of Lecture Notes Ser. Comput., pages 9-18. World Sci. Publ., River
Edge, NJ, 2000.