代数扩域上多元多项式的因式分解算法

曹学军

（天津职业技术师范大学理学院，中国 天津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.