判定有限域上不可約多項式及本原多項式的一種高效算法*

王 鑫 ， 王新梅 ，韋寶典

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

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

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

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

1 不可約與本原多項式的判定

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

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

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

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

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

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

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

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

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

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

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

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

(3) 對任意的ni∈M，均有gcd(xqni-1-1,f(x))=1。

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

(必要性) 由定理1和f(x)不可約分別可知(1)，(2)成立。又對任意的ni∈M， gcd(xqni-1-1,f(x)) = 1成立。否則，設p(x) = gcd(xqni-1-1,f(x))，deg(p)≥1。因為f(x)是不可約多項式，且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，并不直接運用歐幾里得算法，而是分兩步：①先按下述快速模指數(shù)算法(即對多項式平方以使指數(shù)翻倍)求出(xqni-1-1)modf(x)的余式r(x)；②再運用歐幾里德算法求最大公因式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上乘法運算，其中l(wèi)=[log2t]。這里t=qni-1，故指數(shù)模多項式運算為O(n3)次域上乘法。由于事先把qni-1次和n次多項式的最大公因式轉換成求兩個不超過n次的多項式f(x)和r(x)的最大公因式，因此運用歐幾里德算法只需O(n2)次域上乘法，所以，完成對一個ni的判斷需O(n3)次域上乘法。而n所含素因子數(shù)不超過log2n，故判斷一個n次多項式是否為不可約多項式共需O((log2n)n3)次Fq上乘法，該算法屬于多項式時間，易于硬件實現(xiàn)。

推論1 設f(x)是Fq[x]的一個n次多項式，n為素數(shù)，則f(x)為不可約多項式的充要條件為：

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

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

證明注意到n為素數(shù)，由定理2，易見結論成立。

推論2f(x)是Fq[x]上的一個n次多項式，n=n1·n2(n1，n2均為素數(shù))，則f(x)為不可約多項式的充要條件為：

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

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

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

證明當n1=n2，易見結論成立。當n1≠n2，由定理2得出的f(x)為不可約多項式的充要條件為：(1′)對任意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)等價。 (必要性) 注意到ni(i=1, 2)為素數(shù)即得。(充分性) 由(1)，(2)，(3)知f(x)沒有一次因式，只能有n1、n2或n次不可約因式。而事實上f(x)并不含有n1(或n2)次的不可約多項式。否則，設f(x)是由k個n1次和l個n2次不可約多項式構成，則有二元一次不定方程：n=kn1+ln2，解出其所有正整數(shù)解為：k=n2,l=0和k=0,l=n1，均與條件(3)矛盾，因此f(x)不含n1(或n2)次的不可約多項式，從而gcd(f(x),xqni-1-1)=1(i=1,2)。

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

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

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

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

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

(3) 對任意ni∈M，均有gcd(xqni-1-1,f(x))=1；

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

2 結 語

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

參考文獻：

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

[2] 萬哲先. 代數(shù)和編碼 [M]. 北京: 科學出版社, 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]. 北京: 科學出版社, 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] 郭寶安，蔡長年. 有限域上的不可約多項式 [J]. 北京郵電大學學報，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] 曹涵, 陳恭亮. 基于素性檢驗思想的不可約多項式判斷[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上不可約與本原多項式的高效確定算法[J]. 中山大學學報:自然科學版, 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.