Go to the first, previous, next, last section, table of contents.


無平方分解, 因数分解

無平方分解は, 多項式とその微分との 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]]


Go to the first, previous, next, last section, table of contents.