王 鑫 ， 王新梅 ，韋寶典

(1.西安電子科技大學(xué)綜合業(yè)務(wù)網(wǎng)國(guó)家重點(diǎn)實(shí)驗(yàn)室, 陜西 西安 710071;2.中山大學(xué)電子與通信工程系, 廣東 廣州 510275)

有限域上的不可約多項(xiàng)式與本原多項(xiàng)式在密碼，編碼理論及隨機(jī)數(shù)的產(chǎn)生等方面有著廣泛的應(yīng)用。這是由于在擴(kuò)頻通信與序列密碼中被廣泛應(yīng)用的偽隨機(jī)序列，可在連續(xù)波雷達(dá)中用作測(cè)距信號(hào)，在遙控系統(tǒng)中用作遙控信號(hào)，在多址通信中用作地址信號(hào)，在數(shù)字通信中用作群同步信號(hào)，還可用作噪聲源在保密通信中起加密作用。這些偽隨機(jī)序列大部分是利用有限域上的不可約多項(xiàng)式和本原多項(xiàng)式通過反饋移位寄存器和其它非線性邏輯產(chǎn)生的。另一方面，多項(xiàng)式理論尤其是不可約多項(xiàng)式和本原多項(xiàng)式又是分析偽隨機(jī)性能和密碼體制的一種有效工具，因此研究有限域上的不可約多項(xiàng)式與本原多項(xiàng)式具有重要意義[1-4]。

設(shè)GF(q)為一個(gè)含q個(gè)元素的有限域，其中q=pk，p為一素?cái)?shù)，k為正整數(shù)，那么對(duì)于任一正整數(shù)n，一定存在GF(q)上的n次不可約多項(xiàng)式[5]。目前，判定有限域上一個(gè)n次多項(xiàng)式是否不可約的方法一般有確定性(構(gòu)造性)和概率性兩種算法[6]。確定性算法由于檢驗(yàn)的步驟多，計(jì)算量大，技術(shù)實(shí)現(xiàn)上比較復(fù)雜[7-9]，而概率性算法則是對(duì)隨機(jī)給出的一個(gè)多項(xiàng)式，判別其是否為不可約多項(xiàng)式，重復(fù)某一過程直到給出肯定性判斷為止，這便涉及算法成功的可能性有多大[10]。文[11]給出了一種新方案，但遺憾的是僅適用于少數(shù)特殊類型的多項(xiàng)式，即多項(xiàng)式的次數(shù)為素?cái)?shù)或兩個(gè)素?cái)?shù)之積。本文通過對(duì)多項(xiàng)式的次數(shù)與其不可約因式之間的內(nèi)在聯(lián)系進(jìn)行分析，給出了有限域上任意n次多項(xiàng)式為不可約多項(xiàng)式和本原多項(xiàng)式的充要條件。采用多項(xiàng)式快速模運(yùn)算及歐幾里德算法，該算法復(fù)雜度為O((log2n)n3)，屬于多項(xiàng)式時(shí)間，易于硬件實(shí)現(xiàn)。

本文所研究的多項(xiàng)式均為首一，非首一多項(xiàng)式可通過乘以非零常數(shù)化為首一，不影響其不可約性。我們用deg(f)表示多項(xiàng)式f(x)的次數(shù)；gcd(f(x),g(x))表示f(x)和g(x)的最大公因式；以Sn表示自然數(shù)n的所有正因子的集合；符號(hào)|表示整除，? 表示不能整除。

1 不可約與本原多項(xiàng)式的判定

定義1[6]設(shè)有限域Fq=GF(q)，F(xiàn)q[x]為GF(q)上的多項(xiàng)式環(huán)，f(x)稱為不可約多項(xiàng)式是指f(x)在Fq[x]中除了常數(shù)c∈Fq和cf(x)外沒有其它因式。

引理1[5]Fq為一有限域，其中|Fq|=q=pm，則:

其中Vd[x]是Fq[x]上所有d次首一不可約多項(xiàng)式的乘積。

該引理表明：xqn-x實(shí)際上是由Fq[x]上次數(shù)整除n的所有(相異，沒有重復(fù)的)首一不可約多項(xiàng)式的乘積所構(gòu)成。例如：當(dāng)n=6，xq6-x就等于Fq上的所有的1、2、3和6次首一不可約多項(xiàng)式的乘積。

下述定理更進(jìn)一步的揭示出f(x)與其不可約因式之間的聯(lián)系。

定理1n(≥1)次多項(xiàng)式f(x)∈Fq[x]，設(shè)f(x)的所有不可約因式為fi(x)(i=1,…,s)，則f(x)|xqn-x當(dāng)且僅當(dāng)(f(x),f′(x))=1，且對(duì)所有i(=1,…,s)均有deg(fi)|n。

證明由(xqn-x,(xqn-x)′)=1知xqn-x沒有重因式，再由引理1，該結(jié)論成立。

由于一次多項(xiàng)式總是不可約多項(xiàng)式，因此，下面只討論二次以上的多項(xiàng)式的不可約性。

設(shè)自然數(shù)n的因式分解為n=p1e1p2e2…ptet，pi為素?cái)?shù)，ei是正整數(shù)(i=1,…,t)，用ni表示對(duì)應(yīng)的n/pi。令M={n/p1,…,n/pt}，則有：

定理2Fq上的n(≥2)次多項(xiàng)式f(x)為不可約多項(xiàng)式的充要條件是：

(1)f(x)|xqn-1-1；

(2) 對(duì)任意c∈Fq，f(c)≠0；

(3) 對(duì)任意的ni∈M，均有g(shù)cd(xqni-1-1,f(x))=1。

首先簡(jiǎn)要解釋上述三個(gè)條件。條件(1)旨在說明f(x)是由以n的因子為次數(shù)的不可約多項(xiàng)式之積；(2)表明f(x)無一次因式；(3)是為了說明f(x)事實(shí)上并不含有次數(shù)小于n的不可約因式。因此f(x)只能為一n次不可約因式。

(必要性) 由定理1和f(x)不可約分別可知(1)，(2)成立。又對(duì)任意的ni∈M， gcd(xqni-1-1,f(x)) = 1成立。否則，設(shè)p(x) = gcd(xqni-1-1,f(x))，deg(p)≥1。因?yàn)閒(x)是不可約多項(xiàng)式，且p(x)|f(x)，故有p(x)=f(x)，從而f(x)|xqni-1-1，再由定理1，deg(f)|ni，這與deg(f)=n矛盾。故(3)成立。

判斷gcd(xqni-1-1,f(x))是否為1，并不直接運(yùn)用歐幾里得算法，而是分兩步：①先按下述快速模指數(shù)算法(即對(duì)多項(xiàng)式平方以使指數(shù)翻倍)求出(xqni-1-1)modf(x)的余式r(x)；②再運(yùn)用歐幾里德算法求最大公因式gcd(f(x),r(x))。

r(x)=1

fori=s-1 to 0 step(-1)

r(x)=r(x)*r(x)modf(x)

ifli=1

thenr(x)=x*r(x)modf(x)

returnr(x)

該算法需O(ln2)次Fq上乘法運(yùn)算，其中l(wèi)=[log2t]。這里t=qni-1，故指數(shù)模多項(xiàng)式運(yùn)算為O(n3)次域上乘法。由于事先把qni-1次和n次多項(xiàng)式的最大公因式轉(zhuǎn)換成求兩個(gè)不超過n次的多項(xiàng)式f(x)和r(x)的最大公因式，因此運(yùn)用歐幾里德算法只需O(n2)次域上乘法，所以，完成對(duì)一個(gè)ni的判斷需O(n3)次域上乘法。而n所含素因子數(shù)不超過log2n，故判斷一個(gè)n次多項(xiàng)式是否為不可約多項(xiàng)式共需O((log2n)n3)次Fq上乘法，該算法屬于多項(xiàng)式時(shí)間，易于硬件實(shí)現(xiàn)。

推論1 設(shè)f(x)是Fq[x]的一個(gè)n次多項(xiàng)式，n為素?cái)?shù)，則f(x)為不可約多項(xiàng)式的充要條件為：

(1) 對(duì)任意的c∈Fq，f(c)≠0；

(2)f(x)|xqn-1-1。

證明注意到n為素?cái)?shù)，由定理2，易見結(jié)論成立。

推論2f(x)是Fq[x]上的一個(gè)n次多項(xiàng)式，n=n1·n2(n1，n2均為素?cái)?shù))，則f(x)為不可約多項(xiàng)式的充要條件為：

(1) 對(duì)任意c∈Fq，f(c)≠0；

(2)f(x)|xqn-1-1；

(3)f(x)?xqn1-1-1，且f(x)?xqn2-1-1。

證明當(dāng)n1=n2，易見結(jié)論成立。當(dāng)n1≠n2，由定理2得出的f(x)為不可約多項(xiàng)式的充要條件為：(1′)對(duì)任意c∈Fq，f(c)≠0；(2′)f(x)|xqn-1-1；(3′)gcd(f(x),xqn1-1-1)=1，gcd(f(x),xqn2-1-1)=1。即需證明：條件(1′)，(2′)，(3′)與條件(1)，(2)，(3)等價(jià)。 (必要性) 注意到ni(i=1, 2)為素?cái)?shù)即得。(充分性) 由(1)，(2)，(3)知f(x)沒有一次因式，只能有n1、n2或n次不可約因式。而事實(shí)上f(x)并不含有n1(或n2)次的不可約多項(xiàng)式。否則，設(shè)f(x)是由k個(gè)n1次和l個(gè)n2次不可約多項(xiàng)式構(gòu)成，則有二元一次不定方程：n=kn1+ln2，解出其所有正整數(shù)解為：k=n2,l=0和k=0,l=n1，均與條件(3)矛盾，因此f(x)不含n1(或n2)次的不可約多項(xiàng)式，從而gcd(f(x),xqni-1-1)=1(i=1,2)。

文[11]所給出的算法即為上述推論。判斷素?cái)?shù)次或素?cái)?shù)乘積次的多項(xiàng)式f(x)是否可約至多需要3次形如xqn-1modf(x)的值是否為1來確定。故只需進(jìn)行O(n3)次Fq上的乘法運(yùn)算。

定義2 設(shè)f(x)是Fq[x]上n次不可約多項(xiàng)式，如果滿足f(x)|xl-1的最小正整數(shù)為qn-1，則稱f(x)為Fq[x]上的本原多項(xiàng)式。

定理3Fq上的n(≥2)次多項(xiàng)式f(x)為本原多項(xiàng)式的充要條件是：

(1)f(x)|xqn-1-1；

(2) 對(duì)任意c∈Fq，f(c)≠0；

(3) 對(duì)任意ni∈M，均有g(shù)cd(xqni-1-1,f(x))=1；

證明必要性顯然，下證充分性。

2 結(jié) 語

不可約多項(xiàng)式及本原多項(xiàng)式在密碼和編碼中有重要的應(yīng)用。本文對(duì)任意正整數(shù)n，給出了判定n次多項(xiàng)式為不可約多項(xiàng)式及本原多項(xiàng)式的一種實(shí)用、高效的確定性算法，該算法僅需做O((log2n)n3)次Fq上乘法，屬于多項(xiàng)式時(shí)間算法，易于硬件實(shí)現(xiàn)。

參考文獻(xiàn)：

[1] 肖國(guó)鎮(zhèn). 偽隨機(jī)序列及其應(yīng)用 [M]. 北京: 國(guó)防工業(yè)出版社, 1985.

[2] 萬哲先. 代數(shù)和編碼 [M]. 北京: 科學(xué)出版社, 1980.

[3] UDAR S, KAGARIS D. LFSR reseeding with irreducible polynomials [C]. 13th IEEE International Online Testing Symposium, IEEE Computer Society, 2007, 293-297.

[4] IMANA J L, HERMIDA R, TIRADO F. Low complexity bit-parallel multipliers based on a class of irreducible pentanomials [J]. IEEE Transactions on VLSI Systems, 2006, 14 (12): 1388-1393.

[5] MCELIECE R J. Finite field for computer scientists and engineers [M]. Boston: Kluwer Academic Publisher, 1987.

[6] 裴定一, 祝躍飛. 算法數(shù)論 [M]. 北京: 科學(xué)出版社, 2002.

[7] SHPARLINSKI I. Finding irreducible and primitive polynomials [J]. Appl Alg Eng Comm Comp, 1993 (4): 263-268.

[8] RIFA J, BORRELL J. A fast algorithm to compute irreducible and primitive polynomials in finite fields [J]. Math Systems Theory, 1995 (28): 13-20.

[9] 郭寶安，蔡長(zhǎng)年. 有限域上的不可約多項(xiàng)式 [J]. 北京郵電大學(xué)學(xué)報(bào)，1994, 17 (1): 23-26.

GUO B A, CAI C N. The irreducible polynomials over finite fields [J]. Journal of Beijing University of Posts and Telecommunications, 1994, 17 (1): 23-26.

[10] 曹涵, 陳恭亮. 基于素性檢驗(yàn)思想的不可約多項(xiàng)式判斷[J]. 信息安全與通信保密, 2006 (3): 73-74.

CAO H, CHEN G L. Test of irreducible polynomials based on primality test [J]. China Information Security, 2006 (3):73-74.

[11] 王澤輝, 方小洵.Fp上不可約與本原多項(xiàng)式的高效確定算法[J]. 中山大學(xué)學(xué)報(bào):自然科學(xué)版, 2004, 43 (6): 89-92.

WANG Z H, FANG X X. Highly efficient deriving calculation method of irreducible polynomial and primitive polynomial overFp[J]. Acta Scientiarum Naturalium Universitatis Sunyatseni, 2004, 43 (6): 89-92.