多项式xn-1在有限域Fp上的因式分解

丁 洋,王永超

(上海大学理学院,上海200444)

多项式的因式分解问题是代数学的一个基本问题,并且在编码理论中有大量的应用.Berlekamp算法是非常经典的针对有限域Fp上多项式因式分解的算法[1].Lidl等[2]给出了二项式xn-a在域Fq上因式分解的方法,其中q≡3(mod 4)并且对n的任意一个素因子t,t|ordF∗q(a)但tłq−1ordF∗q(a).Meyn[3]考虑了形如x2n+1的分圆多项式在域Fq上的分解,其中q≡3(mod 4).Stichtenoth等[4]研究了形如bxqr+1-axqr+dx-c的多项式在域Fq上的因式分解问题,其中q为素数方幂.

本工作来源于文献[5-6].Ling等[5-6]研究了有限域上准循环码的代数结构.这种代数结构的描述依赖于多项式xn-1在域上的不可约分解.本工作着重研究了xn-1在域Fp上的因式分解问题,其中n=d(p+1),d|(p-1)且d

需要指出的是,已有研究中既有考虑Dickson多项式自身因式分解的[7-9],也有利用Dickson多项式的根来解决其他多项式分解问题的[2-3].区别于以上已知结果,本方法仅仅利用了Dickson多项式的递推关系.

1 预备知识

令p为一个奇素数.令n,p互素,包含i的模n的p-分圆陪集定义如下:

式中,r是令同余式i·pr≡i(mod n)成立的最小正整数.称子集S⊆{0,1,···,n-1}为一个模n的p-分圆陪集的完全代表集,如果它满足如下条件:对于任意不同的i,j∈S,集合Ci,Cj相交为空,并且

命题1说明了分圆陪集与多项式xn-1在域Fp上的不可约分解之间的关系.

命题1[10]令gcd(n,p)=1,α是Fp的代数闭域中的一个n次本原单位根.

(1)对任意整数s(0≤s

式中,Cs是包含s的模n的p-分圆陪集.

(2)进一步地，

是多项式xn-1在域Fp上的不可约分解,其中S是模n的p-分圆陪集的完全代表集.

定义1和定义2给出了Dickson多项式和互反多项式的概念.

定义1(Dickson多项式)[11]令R是一个有单位元的交换环.对于γ∈R,环R上的第n次Dickson多项式为

更进一步地,Dickson多项式具有如下递推形式:

式中,D0(x,γ)=2,D1(x,γ)=x.

命题2是Dickson多项式一个很有用的性质.

命题2[11]令x1,x2为未知变量,n为自然数,则

定义2(互反多项式) 设p(x)为任意数域上的n次多项式,即

那么p(x)的互反多项式p∗(x)定义为

特别地,若p∗(x)=p(x),则p(x)被称为自反多项式.互反多项式之间存在如下关系:p∗(x)=xnp(x−1).

2 多项式x n-1在域F p上的分解

令n=d(p+1),其中d|(p-1)且d

2.1 S的结构

引理1 S=S1∪S2.特别地,1∈S2.

证明 因为n|(p2-1),所以p2≡1(mod n).于是|Ci|=1或|Ci|=2,所以S=S1∪S2.另外,nł(p-1),所以p/≡1(mod n).因此|C1|=2,即1∈S2.

引理2

式中,v2(n):=max{e∈Z:2e|n},并且

证明 若|Ci|=1,则i p≡i(mod n),即n|i(p-1).于是有

(1)若v2(d)=v2(p-1),则gcd(n,p-1)=d,于是(p+1)|i.因为0≤i

(2)若v2(d)

证明完成.

现在S1的结构可由引理2完全给出,所以接下来的讨论主要着眼于S2.定义-Ci={-a:a∈Ci},可对集合S2做出更进一步的划分.

定义

式中,G:={i∈S2:Ci=-Ci},H∪H∗:=S2G,并且对任意的i∈H,有-i∈H∗.

引理3 若s∈G,则d|s.

证明 设s∈G.由集合G的定义,有s p≡-s(mod n),即d(p+1)|s(p+1).所以s必为d的倍数.

由引理3可知,任意的s∈G必为d的倍数.要确定集合G,需要先确定d的倍数中属于集合S1的元素,可以断言S1∩{0≤s

下面来证明v2(d)

从d的倍数中规避掉属于S1的元素之后,可知有p-1个d的倍数落入集合G中.又因为G中的每个元素对应于一个集合大小为2的分圆陪集,所以对于任意的,j dp≡-j d(mod n),所以j d∈G.因此有

引理5

并且集合H可由如下步骤生成.

步骤1 令H=∅,且

步骤2 若D=∅,输出H并结束步骤.否则,令i=min D,H:=H∪{i}.同时令

并重复步骤2.

证明 由集合S的定义可知,

又因为|H|=|H∗|,结合引理2和引理4可得|H|.若i∈H,则-i一定属于集合H∗.不失一般性地,可以假设对任意的i∈H,i

2.2 多项式x n-1在域F p上的分解

由命题1和集合S的结构可知,多项式xn-1在有限域Fp上的不可约分解必为如下形式:

式中,fi为一次多项式,gj为二次自反多项式,且和hk为二次首一多项式且彼此互反.

接下来就如何得到fi,gj和hk的具体形式分别展开讨论.

引理6

式中,a,b分别为域Fp中的d次和2d次本原单位根.

证明 只证明v2(d)=v2(p-1)的情形,另一种情形同理可证.由引理2可知,S1={j(p+1):j=0,1,···,d-1}.对任意的i∈S1,fi=(x-αi)=(x-αj(p+1)),令a=α(p+1),则a为Fp中的一个d次本原单位根.所以fi=(x-aj),进而

接下来考虑集合G∪H.对任意的i∈G∪H,有Ci={i,ip},并且对应于分圆陪集Ci的不可约因式为设Ti(x)=x2-Ai1x+Ai2,其中Ai1,Ai2∈Fp.目标是对任意的i∈G∪H,求解出Ti(x)的系数Ai1,Ai2.由引理1可知,1∈S2.事实上,Ti(x)可以由T1(x)求得,因此首先求解T1(x).

引理7 令T1(x)=x2-A11x+A12为对应于C1的不可约因式,F(x)=x2-a1x+a2为Fp上的本原不可约多项式,则

式中,Dn(·,·)表示第n次的Dickson多项式.

证明 令β为F(x)的一个根.因为F(x)为本原多项式,所以β是一个p2-1次的本原单位根,则必定为一个n次本原单位根.不失一般性地,令,由韦达定理和命题2可得,

并且

对Ti(x)(i≥2)的求解,有如下结论.

引理8 设T1(x)=x2-A11x+A12,则对任意的i∈G∪H,Ti(x)=x2-Ai1x+Ai2,有

证明 由韦达定理得

注2 对于任意的j∈G,Tj(x)必定为自反多项式,因此Aj2=1.

对于任意的i∈G∪H,不可约因式Ti(x)可以由本原多项式和Dickson多项式给出.对应于集合H∗的因式可以由hk求其首一互反多项式得到.于是完成对所有二次不可约因式的求解.

综上结果,可以给出如算法1所示的一个多项式xn-1在域Fp上的不可约分解的算法.关于本原多项式的选取,可以参考文献[2]中本原多项式的表格.

算法1 多项式xn-1在有限域Fp上的分解.

步骤1 令

并且利用引理5得到集合H.

步骤2 对任意的i∈S1,利用引理6得到因式fi.

步骤3 选取本原多项式F(x)=x2-a1x+a2∈Fp[x],利用引理7计算因式T1(x).

步骤4 对任意的j∈G,k∈H,利用T1(x)和引理8得到因式gj和hk.

步骤5 输出

3 实例

例1 多项式x24-1在域F7上的分解.

步骤1 这里d=3,p=7.因为v2(d)

步骤2 由引理6可知,需要找到一个F7中的6次本原单位根a.又因为|F∗7|=6,有

步骤3 取本原多项式x2+x+3.由引理7可知

则T1(x)=x2-2x+2.

步骤4 由引理8可得,

并且

因此,

步骤5 输出

例2 多项式x40-1在域F19上的分解.

步骤1 这里d=2,p=19.因为v2(d)=v2(p-1),有

步骤2 由引理6可知,需要找到一个F19中的2次本原单位根b.令b=-1,有

步骤3 取本原多项式x2+x+2.由引理7可知,

则T1(x)=x2-5x-1.

步骤4 由引理8可得,对任意的j∈G={2,4,···,18},有

式中,

对任意的k∈H={1,3,5,7,9},有

式中,

步骤5 输出