代數(shù)擴域上多元多項式的因式分解算法

曹學(xué)軍

（天津職業(yè)技術(shù)師范大學(xué)理學(xué)院，中國 天津300222）

0 引言

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

1 預(yù)備知識

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

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

F中的代數(shù)整數(shù)構(gòu)成一個環(huán)，記作A，顯然Z?A。

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

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

定義 3 極小多項式 f（x）的判別式 discr（f）=Re s（f（x），f′（x）），其中 f′（x）為 f（x）的導(dǎo)數(shù)。

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

定理 1 （多元 Hensel引理）[8]設(shè) F∈Z[x，x2，…，xn]（n≥2）為一給定多項式，而理想 Φ=（x2-a2，x3-a3，…，xn-an），又設(shè) 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 算法分析

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

2.1 主變元的選取

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

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

2.2 整數(shù)基的計算

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

2.3 賦值

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

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

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

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

2.4 一元多項式的分解

設(shè) U（x，α）為 A 上的多項式，f（x）∈Z[x]是由 α 定義的極小多項式。 因為 deg（f）=m，那么存在 α 的 m 個共軛，α1，α2，…，αm，定義 Norm（U（x，α））=U（x，αi）為 U（x，α）的范數(shù)。 Norm（U（x，α））∈Z[x]，且Norm（U（x，α））=Re s（U（x，α），f（α），α）。 根據(jù)以下步驟我們可以得到 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α））有重根。

證明：設(shè) 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，假設(shè) G（x）有重根，則 y=又因為f（x）是Q上無平方因子多項式，所以k≠m。因此只有有限個 y∈Q，使得 Norm（f（x-yα））有重根。

引理3[5]如果f（x，α）為Q（α）上無平方因子多項式，那么存在Q上無平方因子多項式 g（x），使得 f｜g。證明：設(shè)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）。 從上述同余關(guān)系可得 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.