多項(xiàng)式xn-1在有限域Fp上的因式分解

丁 洋,王永超

(上海大學(xué)理學(xué)院,上海200444)

多項(xiàng)式的因式分解問題是代數(shù)學(xué)的一個(gè)基本問題,并且在編碼理論中有大量的應(yīng)用.Berlekamp算法是非常經(jīng)典的針對(duì)有限域Fp上多項(xiàng)式因式分解的算法[1].Lidl等[2]給出了二項(xiàng)式xn-a在域Fq上因式分解的方法,其中q≡3(mod 4)并且對(duì)n的任意一個(gè)素因子t,t|ordF?q(a)但t?q?1ordF?q(a).Meyn[3]考慮了形如x2n+1的分圓多項(xiàng)式在域Fq上的分解,其中q≡3(mod 4).Stichtenoth等[4]研究了形如bxqr+1-axqr+dx-c的多項(xiàng)式在域Fq上的因式分解問題,其中q為素?cái)?shù)方冪.

本工作來源于文獻(xiàn)[5-6].Ling等[5-6]研究了有限域上準(zhǔn)循環(huán)碼的代數(shù)結(jié)構(gòu).這種代數(shù)結(jié)構(gòu)的描述依賴于多項(xiàng)式xn-1在域上的不可約分解.本工作著重研究了xn-1在域Fp上的因式分解問題,其中n=d(p+1),d|(p-1)且d

需要指出的是,已有研究中既有考慮Dickson多項(xiàng)式自身因式分解的[7-9],也有利用Dickson多項(xiàng)式的根來解決其他多項(xiàng)式分解問題的[2-3].區(qū)別于以上已知結(jié)果,本方法僅僅利用了Dickson多項(xiàng)式的遞推關(guān)系.

1 預(yù)備知識(shí)

令p為一個(gè)奇素?cái)?shù).令n,p互素,包含i的模n的p-分圓陪集定義如下:

式中,r是令同余式i·pr≡i(mod n)成立的最小正整數(shù).稱子集S?{0,1,···,n-1}為一個(gè)模n的p-分圓陪集的完全代表集,如果它滿足如下條件:對(duì)于任意不同的i,j∈S,集合Ci,Cj相交為空,并且

命題1說明了分圓陪集與多項(xiàng)式xn-1在域Fp上的不可約分解之間的關(guān)系.

命題1[10]令gcd(n,p)=1,α是Fp的代數(shù)閉域中的一個(gè)n次本原單位根.

(1)對(duì)任意整數(shù)s(0≤s

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

(2)進(jìn)一步地，

是多項(xiàng)式xn-1在域Fp上的不可約分解,其中S是模n的p-分圓陪集的完全代表集.

定義1和定義2給出了Dickson多項(xiàng)式和互反多項(xiàng)式的概念.

定義1(Dickson多項(xiàng)式)[11]令R是一個(gè)有單位元的交換環(huán).對(duì)于γ∈R,環(huán)R上的第n次Dickson多項(xiàng)式為

更進(jìn)一步地,Dickson多項(xiàng)式具有如下遞推形式:

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

命題2是Dickson多項(xiàng)式一個(gè)很有用的性質(zhì).

命題2[11]令x1,x2為未知變量,n為自然數(shù),則

定義2(互反多項(xiàng)式) 設(shè)p(x)為任意數(shù)域上的n次多項(xiàng)式,即

那么p(x)的互反多項(xiàng)式p?(x)定義為

特別地,若p?(x)=p(x),則p(x)被稱為自反多項(xiàng)式.互反多項(xiàng)式之間存在如下關(guān)系:p?(x)=xnp(x?1).

2 多項(xiàng)式x n-1在域F p上的分解

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

2.1 S的結(jié)構(gòu)

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

證明 因?yà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.因?yàn)?≤i

(2)若v2(d)

證明完成.

現(xiàn)在S1的結(jié)構(gòu)可由引理2完全給出,所以接下來的討論主要著眼于S2.定義-Ci={-a:a∈Ci},可對(duì)集合S2做出更進(jìn)一步的劃分.

定義

式中,G:={i∈S2:Ci=-Ci},H∪H?:=S2G,并且對(duì)任意的i∈H,有-i∈H?.

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

證明 設(shè)s∈G.由集合G的定義,有s p≡-s(mod n),即d(p+1)|s(p+1).所以s必為d的倍數(shù).

由引理3可知,任意的s∈G必為d的倍數(shù).要確定集合G,需要先確定d的倍數(shù)中屬于集合S1的元素,可以斷言S1∩{0≤s

下面來證明v2(d)

從d的倍數(shù)中規(guī)避掉屬于S1的元素之后,可知有p-1個(gè)d的倍數(shù)落入集合G中.又因?yàn)镚中的每個(gè)元素對(duì)應(yīng)于一個(gè)集合大小為2的分圓陪集,所以對(duì)于任意的,j dp≡-j d(mod n),所以j d∈G.因此有

引理5

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

步驟1 令H=?,且

步驟2 若D=?,輸出H并結(jié)束步驟.否則,令i=min D,H:=H∪{i}.同時(shí)令

并重復(fù)步驟2.

證明 由集合S的定義可知,

又因?yàn)閨H|=|H?|,結(jié)合引理2和引理4可得|H|.若i∈H,則-i一定屬于集合H?.不失一般性地,可以假設(shè)對(duì)任意的i∈H,i

2.2 多項(xiàng)式x n-1在域F p上的分解

由命題1和集合S的結(jié)構(gòu)可知,多項(xiàng)式xn-1在有限域Fp上的不可約分解必為如下形式:

式中,fi為一次多項(xiàng)式,gj為二次自反多項(xiàng)式,且和hk為二次首一多項(xiàng)式且彼此互反.

接下來就如何得到fi,gj和hk的具體形式分別展開討論.

引理6

式中,a,b分別為域Fp中的d次和2d次本原單位根.

證明 只證明v2(d)=v2(p-1)的情形,另一種情形同理可證.由引理2可知,S1={j(p+1):j=0,1,···,d-1}.對(duì)任意的i∈S1,fi=(x-αi)=(x-αj(p+1)),令a=α(p+1),則a為Fp中的一個(gè)d次本原單位根.所以fi=(x-aj),進(jìn)而

接下來考慮集合G∪H.對(duì)任意的i∈G∪H,有Ci={i,ip},并且對(duì)應(yīng)于分圓陪集Ci的不可約因式為設(shè)Ti(x)=x2-Ai1x+Ai2,其中Ai1,Ai2∈Fp.目標(biāo)是對(duì)任意的i∈G∪H,求解出Ti(x)的系數(shù)Ai1,Ai2.由引理1可知,1∈S2.事實(shí)上,Ti(x)可以由T1(x)求得,因此首先求解T1(x).

引理7 令T1(x)=x2-A11x+A12為對(duì)應(yīng)于C1的不可約因式,F(x)=x2-a1x+a2為Fp上的本原不可約多項(xiàng)式,則

式中,Dn(·,·)表示第n次的Dickson多項(xiàng)式.

證明 令β為F(x)的一個(gè)根.因?yàn)镕(x)為本原多項(xiàng)式,所以β是一個(gè)p2-1次的本原單位根,則必定為一個(gè)n次本原單位根.不失一般性地,令,由韋達(dá)定理和命題2可得,

并且

對(duì)Ti(x)(i≥2)的求解,有如下結(jié)論.

引理8 設(shè)T1(x)=x2-A11x+A12,則對(duì)任意的i∈G∪H,Ti(x)=x2-Ai1x+Ai2,有

證明 由韋達(dá)定理得

注2 對(duì)于任意的j∈G,Tj(x)必定為自反多項(xiàng)式,因此Aj2=1.

對(duì)于任意的i∈G∪H,不可約因式Ti(x)可以由本原多項(xiàng)式和Dickson多項(xiàng)式給出.對(duì)應(yīng)于集合H?的因式可以由hk求其首一互反多項(xiàng)式得到.于是完成對(duì)所有二次不可約因式的求解.

綜上結(jié)果,可以給出如算法1所示的一個(gè)多項(xiàng)式xn-1在域Fp上的不可約分解的算法.關(guān)于本原多項(xiàng)式的選取,可以參考文獻(xiàn)[2]中本原多項(xiàng)式的表格.

算法1 多項(xiàng)式xn-1在有限域Fp上的分解.

步驟1 令

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

步驟2 對(duì)任意的i∈S1,利用引理6得到因式fi.

步驟3 選取本原多項(xiàng)式F(x)=x2-a1x+a2∈Fp[x],利用引理7計(jì)算因式T1(x).

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

步驟5 輸出

3 實(shí)例

例1 多項(xiàng)式x24-1在域F7上的分解.

步驟1 這里d=3,p=7.因?yàn)関2(d)

步驟2 由引理6可知,需要找到一個(gè)F7中的6次本原單位根a.又因?yàn)閨F?7|=6,有

步驟3 取本原多項(xiàng)式x2+x+3.由引理7可知

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

步驟4 由引理8可得,

并且

因此,

步驟5 輸出

例2 多項(xiàng)式x40-1在域F19上的分解.

步驟1 這里d=2,p=19.因?yàn)関2(d)=v2(p-1),有

步驟2 由引理6可知,需要找到一個(gè)F19中的2次本原單位根b.令b=-1,有

步驟3 取本原多項(xiàng)式x2+x+2.由引理7可知,

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

步驟4 由引理8可得,對(duì)任意的j∈G={2,4,···,18},有

式中,

對(duì)任意的k∈H={1,3,5,7,9},有

式中,

步驟5 輸出