代數擴域上多元多項式的因式分解算法

曹學軍

（天津職業技術師范大學理學院，中國 天津300222）

0 引言

多項式的因式分解不僅是計算機代數系統中是解決許多數學問題的有力工具，而且在許多其他的領域里，多項式的因式分解也是不可或缺的。已有的Kronecker和Trager算法都有一定的局限性。20世紀60年代以來出現了不少因式分解方面的工作，如文獻[5]中只給出了一元多項式的因式分解方法，而在多元多項式的因式分解中，范數的計算不僅相當繁瑣，而且計算量也非常的大。在文獻[7]中，首先將多項式哎足夠大的環上進行分解，這個環由某一素數pk決定，然后構造格使得因式的系數在代數數域上是同構的，但是這種方法僅限于能夠找到這樣滿足條件的格。上述方法雖然在某一程度上解決了多項式的因式分解問題，但是效率仍然不高，且不便于實行。我們受文獻[4]的啟發，給出了有理數擴域上多項式因式分解的一種算法。算法首先通過賦值將多元多項式轉化為單變元多項式，接著根據Wang P S的方法將一元多項式在代數擴域上進行分解，最后根據Hensel引理提升多項式的多元因式，最終得到多元多項式的一個完全分解。

1 預備知識

我們用Q表示有理數域，Z表示整數集合，令F=Q（α）為Q上添加代數元 α 的代數擴域，其中 α 滿足 f（α）=0，f（x）∈Z[x]稱為 α 的極小多項式且[F：Q]=m=deg（f）。 設 U（x1，x2，…，xt）∈F[x1，x2，…，xt]為一個無平方因子的非零多項式，我們考慮的問題是計算出U1，…，Us，使得U=U1×U2×…×Us，其中 Ui∈F[x1，x2，…，xt]為不可約多項式。

定義1 ?β∈F稱為代數整數，如果存在一個首一多項式g（x），使得 g（β）=0。

F中的代數整數構成一個環，記作A，顯然Z?A。

證明由高等代數可知，全體整數作成的集合對于普通加法和乘法來說作成一個環，而Z?A，所以A對于普通加法和乘法作成一個環。

定義2 稱集合{1/D，α/D，…，αm-1/D}為A的整數基。

定義 3 極小多項式 f（x）的判別式 discr（f）=Re s（f（x），f′（x）），其中 f′（x）為 f（x）的導數。

命題1 正整數D為滿足△2｜discr（f）的最大的整數△。

定理 1 （多元 Hensel引理）[8]設 F∈Z[x，x2，…，xn]（n≥2）為一給定多項式，而理想 Φ=（x2-a2，x3-a3，…，xn-an），又設 G1（x），H1（x）使得 F（x，x2，…，xn）≡G1（x）H1（x） mod（Φ），且（G1（x），H1（x））=1，那么對?k≥1，都存在多元多項式 Gk（x，x2，…，xn）和 Hk（x，x2，…，xn）使得F（x，x2，…，xn）≡Gk（x）Hk（x） mod（Φk），而且 Gk≡G1mod（Φ）， Hk≡H1mod（Φ）。

2 算法分析

設 U（x1，x2，…，xt）∈F[x1，x2，…，xt]，f（x）∈Z[x]為一給定的極小多項式，且deg（f）=m。根據以下算法步驟我們可以得到U的不可約分解。

2.1 主變元的選取

不妨設 x1為主變元，以下記為 x，則 U（x，x2，…，xt）∈A[x，x2，…，xt]，U（x，x2，…，xt）aixi，其中 ai∈A[x2，…，xt]，an≠0 為 U 的首項系數，記為 lc（U）。令 contx（U）=gcd（a0，a1，…，an），pp（U）=U/contx（U）。如果contx（U）=1，U是本原的，如果U沒有重因式，U稱為無平方因子的。任意的contx（U）或U的重因式可以經過gcd的計算提出來，這樣我們可以假設U是本原的無平方因子的多項式。

對于整系數多項式的分解，在分解的過程中，首項系數有著重要的作用[3]。如果首項系數為1，分解過程相對容易的多，且U的每一個因式都是首一的。但如果U非首一，我們則要通過更為復雜的計算來決定各個因式的首項系數。因此，我們選取U的主變元，使得lc（U）=1或最小。如果同時存在幾個變元使得lc（U）=1，那么我們選取次數最小的變元。

2.2 整數基的計算

由定義 3 和命題 1，discr（f）=Re s（f（x），f ′（x）），設△是滿足△2｜discr（f）的最大整數，那么很容易就可以知道集合{1/△，α/△，…，αm-1/△}為A的整數基。

2.3 賦值

對于多元多項式因式分解，我們通常是在選取主變元后對剩余的變元進行賦值運算。找到一個整數集合{b2，b3，…，bt}（不必要是互異的）滿足一下條件：

（1）U（x，b2，…，bt）仍是無平方因子的；

（2）degxU（x，b2，…，bt）=degxU（x，x2，…，xt）

由文獻[3]，這里的bi，i=2，3，…，t盡可能選取絕對值最小的整數，如 0，±1等。

2.4 一元多項式的分解

設 U（x，α）為 A 上的多項式，f（x）∈Z[x]是由 α 定義的極小多項式。 因為 deg（f）=m，那么存在 α 的 m 個共軛，α1，α2，…，αm，定義 Norm（U（x，α））=U（x，αi）為 U（x，α）的范數。 Norm（U（x，α））∈Z[x]，且Norm（U（x，α））=Re s（U（x，α），f（α），α）。 根據以下步驟我們可以得到 U（x，α）在 F 上的完全分解。

（1）在 Z 上計算 V（x，y）=Re s（U（x-yα），f（α）），使得 V（x，y）為無平方因子的；

（2）在 Z 上分解 V（x，y）=V1（x，y）V2（x，y）…Vs（x，y）[4]；

（3）計算 ci（x，α）=cont（Vi（x+yα，y））；

步驟（1）中y的選取是無限多的，為了解決這問題，我們有以下定理。

定理2[5]如果f（x）是Q上無平方因子多項式，那么只有有限個y∈Q，使得 Norm（f（x-yα））有重根。

證明：設 f（x）所有互異的根為 β1，β2，…，βm，那么 f（x-yαj）的根為β1+αj，β2+αj，…，βm+αj。令 G（x）=Norm（f（x-yα））（x-yαi），因此對1≤k≤n，1≤i≤m，G（x）的根為 βi+yαk，假設 G（x）有重根，則 y=又因為f（x）是Q上無平方因子多項式，所以k≠m。因此只有有限個 y∈Q，使得 Norm（f（x-yα））有重根。

引理3[5]如果f（x，α）為Q（α）上無平方因子多項式，那么存在Q上無平方因子多項式 g（x），使得 f｜g。證明：設i為G的無平方分解，那么g（x）=（x）為Q上的多項式。因為f為無平方因子的，我們只需要消去 G（x）=（x）i中的重因子就有 f｜g。

推論4[5]如果f（x，α）為Q（α）上無平方因子多項式，那么只有有限個 y∈Q，使得 Norm（f（x-yα））有重根。

2.5 Hensel提升

由 2.4 我們得到了 U（x）的完全分解 U（x）=U1（x）U2（x）…Us（x） （1）

令 yi=xi-bi，i=2，…，n，W=U（x，y2+b2，…，yn+bn），由（1）得 W=U1（x）U2（x）…Us（x） mod（Φ），其中理想 Φ=（y2，y3，…，yn）。 從上述同余關系可得 Wi（x，y2，…，yn），i=1，2，…，s使得 Wi（x）≡Ui（x） mod（Φ），且 W≡W1（x，y2，…，yn）…Ws（x，y2，…，yn） mod（Φh），其中 h=1+degxiU。 令≡△Wimod（Φh），Ui=W*i/△，這樣就得到了U在F上的完全分解。

［1］Hans Zassenhaus.On Hensel Factorizaion[J].Journal of Number Theory,1969,1:291-311.

［2］David R.Musser.Multivariate Polynomial Factorization[J].Technical Report-11,1973.

［3］Wang PS,Rothschild L P.Factoring Multivariate Polynomials over the Integers[J].Mathematics of Computation,1975,29(131):935-950.

［4］Wang PS.Factoring Multivariate Polynomials over Algebraic Number Fields[J].Mathematics of Computation,1976,30(134):324-336.

［5］Trager B M.Algebraic Factoring and Rational Function Integration[J].Proc.ACM SYMSAC,1976:219-226.

［6］Weinberger P J,Rothschild L P.Factoring Polynomials over Algebraic Number Fields[J].ACM Trans.Math.Software,1979,2:335-350.

［7］A.K.Lenstra.Lattices and Factorization of Polynomials over Algebraic Number Fields[J].Mathematisch Centrum,1981:32-39.

［8］Zhi L H.An Optimal Method for Algebraic Factoring[J].Jof Computer Science and Technology,1997,12:1-9.