無平方分解する. 得られた無平方分解の, 重複度の最も高い因子 g0 と, f の e−1回 微分から, 一般化された Hensel 構成により f の, 重複度の最も高い因子 g を復元す るのである. そして, このHensel 構成が失敗した場合には, 代入した値が妥当なもの ではなかったとして,値を取り直す. 妥当な値が存在することは, 無平方な多変数多項 式に対する妥当な代入値の存在と同様に言える. この方法のよい点は,
• (重複度 -1) だけ多項式の次数が落せる
• 無平方因子を直接求めることができるため, f の既約因子すべての積を求める 場合に比較して計算の手間を減らすことができる
• 全体に対して妥当でない代入でも,重複度最大の因子には影響がない場合がある.
• ある多項式の冪になっている場合に高速に分解できる.
などがある. さらに,この方法は, 一変数多項式の無平方分解にも応用できる. すなわ ち,一変数多項式に対しては,法 pでの無平方分解を用いて整数上の無平方因子を,重 複度最大の因子から復元していく. この際, 復元方法としては, [46]では中国剰余定理 による方法を提案しているが, Hensel 構成によるものも可能である.
以上, 一般化された Hensel 構成の応用について述べたが, これらを計算機上にイ ンプリメントすることはかなりの大仕事となる. これは,最初に述べたように,因数分 解, GCD,無平方分解が再帰的に結合し,かつそれらは様々に付帯状況の異なるHensel 構成により計算されなければならない. さらに,これらを効率よく計算するための種々 の工夫を入れれば,プログラムは相当に大きなものとなり, 当然debug も困難なもの になる.
6.9 代数体上の因数分解
この節では, K を Q の有限次拡大体とし, K[x] における因数分解を考える. ここで 述べるのは, Trager [42] による, ノルムを用いる方法である. K = Q(α) という単拡 大に対しては, この他に, Hensel 構成を用いる方法がいくつか提案されているがここ では述べない. Trager の方法は, K(α) 上での因数分解を, K 上の因数分解に帰着さ せるもので, Q 上の因数分解さえ完備していれば, K = Q(α1,· · ·, αr) 上での因数分 解が可能になる.
以下,K を,その上で多項式因数分解が可能な体,g ∈K[t]をdeg(g) = mなる既約 多項式,αをg の一つの根とする. K(α) = K[α] =K[t]/(g)である. L⊃K をg の最
小分解体とする. α1 =α, α2,· · ·, αm を g の相異なる根とすると, L=K(α1,· · ·, αm) とかける.
定義 6.46 f ∈K(α)[x] に対し, Norm(f) を Norm(f) =Y
i
f(x, αi)
で定義する. L/K の Norm の性質により, Norm(f)∈K[x]. また, Norm(f) = rest(f(x, t), g(t)).
命題 6.47 f ∈K(α)[x] が既約ならば, ある既約多項式 h∈K[x]が存在して, Norm(f) =hl.
[証明] Norm(f) = ab, a, b∈K[x], GCD(a, b) = 1 と書けたとする. f|Norm(f)で, f は K(α) 上既約より, f|a としてよい. この時
Norm(f)|Norm(a) = am.
よってGCD(Norm(f), b) = 1 となり, b|Norm(f) だから,b = 1. よって, Norm(f)は 2つ以上の異なる既約因子を含み得ない. 2
系 6.48 f ∈ K(α)[x] が無平方とする時, Norm(f) が無平方ならば, Norm(f) = Qfi を K[x] における既約分解とするとき, f = QGCD(f, fi) は f の K(α)[x] における 既約分解を与える.
[証明]hをfのK(α)[x]における既約因子とする. hはあるfi を割り切る. Norm(h)は K[x]の既約多項式の冪で, Norm(h)は無平方なNorm(f)を割り切るから, Norm(h)自 身がNorm(f)の既約因子. Norm(h)はNorm(fi)の因子でもあるから,fi = Norm(h).
今, h と異なる因子h1 が fi を割れば,同様に fi = Norm(h1). hh1|f より Norm(hh1) =fi2|Norm(f).
これは Norm(f) が無平方であることに反する. よって fi は f のただ一つの既約因
子を含む. 2
以上により, Norm(f)が無平方のときには, GCD によりf の既約因子がK[x]に おける既約分解により得られることがわかった. Norm(f)が無平方でない場合にも, 適当な変数変換により無平方化できることが次の命題よりわかる.
6.9. 代数体上の因数分解 67 命題 6.49 f ∈K(α)[x]が無平方ならば, Norm(f(x−sα))が無平方とならないs∈K は有限個.
[証明]f の根を β1,· · ·, βm とすると, 仮定よりこれらは相異なる. すると, f(x−sαi) の根は,
β1+sαi,· · ·, βm+sαi
となる. これより Norm(f(x−sα)) が無平方でないのは, あるi, j, k, l に対して, βj+sαi =βk+sαl
の場合に限る. このような条件を満たすs は有限個しかない. 2 以上により, 次のアルゴリズムが得られる.
アルゴリズム 6.50
Input : 無平方なf(x, α)∈K(α)[x],s ∈Z Output : f の K(α)上の既約因子 {f1,· · ·, fr} again:
r←rest(f(x−st, t), g(t)) if (r が無平方でない) then
s←s+ 1; goto again
r(x) =Qri(x) : r の K 上での既約分解 z ←f
for each i do{
fi ←GCD(h(x+sα), z(x, α)) t←z/fi
}
このアルゴリズムにおいて,ボトルネックとなり得る部分が数多くある.
1. 終結式の計算
終結式の計算は, 部分終結式, 行列式の modular 演算などを組み合わせて行な うが,実際の計算時間を反映する計算量が与えられていないため, アルゴリズム の選択が困難である. また, いずれにしても, 終結式の計算は一般に時間がかか り,しかもその終結式が無平方でなければ捨てられるため,そのコストの大きさ は問題である.
2. K 上での既約分解
K がまたある拡大体になっている場合にはこのアルゴリズムが再帰的に用いら れることになる. この際,ノルムをとることは,次数が拡大次数倍されるため,因 数分解すべき多項式の次数が急速に増大する. 最終的にQ 上の因数分解を行な うことになるが, Q 上の因数分解自体のコストの問題がある.
3. K(α) 上でのGCD 計算
一般に, 拡大体上でのGCD の計算は, 整数上でのそれに比較して極めて困難で ある. 特に, Euclid 互除法を用いる場合, 中間式膨張は,定義多項式 g が大きい 場合, 極めて激しい. これをさけるためいくつかの modular 計算法が提案され ている.
この中で, 2 および 3 は止むを得ない問題であるが, 1 に関しては, 無平方でない ノルムを利用することにより, ある程度回避できる.
命題 6.51 f ∈K(α)[x] が無平方,
Norm(f) = Y
i
fini
(fi ∈K[x] は既約, ni は 1とは限らない)とすると, GCD(f, fi) はf の定数でない因 子で,
f =YGCD(f, fi).
特に, Norm(f)の重複度 1 の因子fi に対しては, GCD(f, fi) は既約.
[証明]hをf の任意の既約因子とすると,あるfi が存在してh|fiよりh|QGCD(f, fi).
f は無平方よりf|QGCD(f, fi). GCD(f, fi) は互いに素より, f = QGCD(f, fi). さ て, f の既約因子のノルムはある既約多項式の冪より, 任意の fi に対して, その適当 な冪はf の既約因子のノルムとなっている. よって,fi はある f の既約因子を含むの で, GCD(f, fi) は定数でない. 特に,fi がNorm(f) の重複度1の因子ならば, それ自 身f のある既約因子 hのノルムとなる. これは,前の系と同様にして,fi はh 以外の 因子を含まない2
この命題により, ノルム (終結式) が, 二つ以上の既約因子を持てば, その分解は, f の自明でない因数分解を与えることがわかる. もし, ノルムが無平方でなければ,こ こで生成した因子に対し, s を取り直してこのアルゴリズムを再帰的に適用すること になるが,問題のサイズは小さくなっている. 特に,ノルム自体が無平方でなくても重
6.9. 代数体上の因数分解 69 複度が1の因子に対しては, GCD が既約因子であることが保証されている. また,ノ ルムが無平方でない場合にも, K 上での因数分解の前に,無平方分解によりノルムを 分解できるため, K 上の因数分解の計算時間も短縮できる. この改良を採り入れたア ルゴリズムを次に示す.
アルゴリズム 6.52
Input : 無平方なf(x, α)∈K(α)[x],s ∈Z Output : f の K(α)上の既約因子 {f1,· · ·, fr} r←rest(f(x−st, t), g(t))
r(x) =Qri(x)mi : r の K 上での既約分解 z ←f
for each i do{
gi ←GCD(ri(x+sα), z(x, α)) if mi = 1 then gi は既約
else (gi, s+ 1) にこのアルゴリズムを適用 t ←z/gi
}
例 6.53 [1]
f(x) = x16−136x14+ 6476x12−141912x10+ 1513334x8−7453176x6+ 13950764x4
−5596840x2+ 46225 f(x) は α =√
2 +√ 3 +√
5 +√
7 の Q 上の最小多項式である. Q(α)/Q はガロア拡 大であり, f(x) はQ(α)上一次式の積に分解する. この因数分解をアルゴリズム6.50 で求める場合,F(x) = Norm(f(x−sα))が無平方となるs∈Z を見つけて F(x)を有 理数体上で因数分解する必要があるが, このような F(x) は, 全ての素数 p に対し一 次または二次式に分解してしまう. 例えば 二次因子の積128 個に分解した場合,有理 数体上の一つの既約因子(16 次) は, 128個から 8個を選んで得られることになるが, これは明らかに組合せ爆発を起こしていて計算不可能である. 一方で,例えば s=−1 の場合F(x) は無平方にならないが, 16 個の異なる既約因子が無平方分解およびそれ に続く既約因子分解により容易に得られる.
F(x) = x16(x2−28)8(x2−20)8(x2−8)8(x2 −12)8
·(x4−64x2 + 64)4(x4 −40x2+ 16)4
·(x4−80x2 + 256)4(x4−56x2+ 144)4
·(x4−72x2 + 400)4(x4−96x2+ 64)4
·(x8−240x6+ 12512x4−203520x2+ 891136)2
·(x8−192x6+ 8576x4−110592x2+ 102400)2
·(x8−224x6+ 11264x4−143360x2+ 409600)2
·(x8−160x6+ 5632x4−61440x2+ 147456)2
·(x16−544x14+ 103616x12−9082368x10+ 387413504x8−7632052224x6 +57142329344x4−91698626560x2+ 3029401600)
これらの各因子からf(x)の全ての一次因子が得られる. 一般に,最小分解体を求める ための因数分解など, 多項式を, その根を添加した体上で因数分解する場合にアルゴ リズム6.52 が有効となる場合がある.