9.4 代数体上での 1 変数多項式の演算

‘sp’ では, 1 変数多項式に限り, GCD, 因数分解およびそれらの応用として 最小分解体を求める函数を提供している.

9.4.1 GCD

代数体上での GCD は cr_gcda() により計算される. この函数はモジュラ演算および中国剰余定理により代数体上の GCD を 計算するもので, 逐次拡大に対しても有効である.

[63] A=newalg(t^9-15*t^6-87*t^3-125);
(#0)
[64] B=newalg(75*s^2+(10*A^7-175*A^4-470*A)*s+3*A^8-45*A^5-261*A^2);
(#1)
[65] P1=75*x^2+(150*B+10*A^7-175*A^4-395*A)*x
+(75*B^2+(10*A^7-175*A^4-395*A)*B+13*A^8-220*A^5-581*A^2)$
[66] P2=x^2+A*x+A^2$
[67] cr_gcda(P1,P2);
27*x+((#0^6-19*#0^3-65)*#1-#0^7+19*#0^4+38*#0)

9.4.2 無平方分解, 因数分解

無平方分解は, 多項式とその微分との GCD の計算から始まるもっとも一般的な アルゴリズムを採用している. 函数は asq() である.

[116] A=newalg(x^2+x+1);                           
(#4)
[117] T=simpalg((x+A+1)*(x^2-2*A-3)^2*(x^3-x-A)^2);
x^11+(#4+1)*x^10+(-4*#4-8)*x^9+(-10*#4-4)*x^8+(16*#4+20)*x^7
+(24*#4-6)*x^6+(-29*#4-31)*x^5+(-15*#4+28)*x^4+(38*#4+29)*x^3
+(#4-23)*x^2+(-21*#4-7)*x+(3*#4+8)
[118] asq(T);
[[x^5+(-2*#4-4)*x^3+(-#4)*x^2+(2*#4+3)*x+(#4-2),2],[x+(#4+1),1]]

結果は通常と同様に, [因子, 重複度] のリストとなるが, 全ての因子 の積は, もとの多項式と定数倍の差はあり得る. これは, 因子を整数係数にし て見やすくするためで, 因数分解でも同様である.

代数体上での因数分解は, Trager によるノルム法を改良したもので, 特に ある多項式に対し, その根を添加した体上でその多項式自身を因数分解する 場合に特に有効である.

[119] af(T,[A]);
[[x^3-x+(-#4),2],[x^2+(-2*#4-3),2],[x+(#4+1),1]]

引数は 2 つで, 第 2 引数は, root のリストである. 因数分解は 有理数体に, それらの root を添加した体上で行われる. root の順序には制限がある. すなわち, 後で定義されたものほど 前の方にこなければ ならない. 並べ換えは, 自動的には行われない. ユーザの責任となる.

ノルムを用いた因数分解においては, ノルムの計算と整数係数 1 変数多項式の 因数分解の効率が, 全体の効率を左右する. このうち, 特に高次の多項式 の場合に後者において組合せ爆発により計算不能になる場合がしばしば生ずる.

[120] B=newalg(x^2-2*A-3);
(#5)
[121] af(T,[B,A]);
[[x+(#5),2],[x^3-x+(-#4),2],[x+(-#5),2],[x+(#4+1),1]]

9.4.3 最小分解体

やや特殊な演算ではあるが, 前節の因数分解を反復適用することにより, 多項式の最小分解体を求めることができる. 函数は sp() である.

[103] sp(x^5-2);
[[x+(-#1),2*x+(#0^3*#1^3+#0^4*#1^2+2*#1+2*#0),2*x+(-#0^4*#1^2),
2*x+(-#0^3*#1^3),x+(-#0)],
[[(#1),t#1^4+t#0*t#1^3+t#0^2*t#1^2+t#0^3*t#1+t#0^4],[(#0),t#0^5-2]]]

sp() は 1 引数で, 結果は [1 次因子のリスト, [[root, algptorat(定義多項式)] のリスト] なるリストである. 第 2 要素の [root,algptorat(定義多項式)] のリストは, 右から順に, 最小分解体が得られるまで添加していった root を示す. その定義多項式は, その直前までの root を添加した体上で既約であること が保証されている.

結果の第 1 要素である 1 次因子のリストは, 第 2 要素の root を全て 添加した体上での, sp() の引数の多項式の全ての因子を表す. その体は 最小分解体となっているので, 因子は全て 1 次となるわけである. af() と同様, 全ての因子の積は, もとの多項式と定数倍の差はあり得る.

この文書は4月 19, 2024にtexi2html 5.0を用いて生成されました。