有限域上一類完全置換單項(xiàng)式的構(gòu)造

黃萌濛，伍高飛

(西安電子科技大學(xué) 網(wǎng)絡(luò)與信息安全學(xué)院，陜西 西安 710071)

設(shè)有限域Fq有q=pn個(gè)元素，其中，p是素?cái)?shù)，n是正整數(shù)。若f(x)為FqFq上的一一映射，則稱多項(xiàng)式f(x)∈Fq[x]為域Fq上的置換多項(xiàng)式(Permutation Polynomials，PPs)。有限域上的置換多項(xiàng)式在編碼理論以及代數(shù)組合論中有著非常重要的應(yīng)用。在編碼理論中，置換多項(xiàng)式可以用來構(gòu)造最優(yōu)線性碼[1-2]。在代數(shù)組合論中，置換多項(xiàng)式可以用來構(gòu)造具有良好性質(zhì)的差集系統(tǒng)[3]。完全置換多項(xiàng)式(Complete Permutation Polynomials，CPPs)是一類特殊的置換多項(xiàng)式，除了上述在編碼理論和代數(shù)組合論中有應(yīng)用外，完全置換多項(xiàng)式還可用來構(gòu)造正交拉丁方陣[4-6]，并和最大長度序列(maximum length sequence，m-序列)及其采樣之間的互相關(guān)值猜想具有密切聯(lián)系[7]。近年來，研究者又發(fā)現(xiàn)利用完全置換多項(xiàng)式可以構(gòu)造一類在兩種不同的廣義離散傅里葉變換下具有均勻頻譜的布爾函數(shù)——Bent-Negabent函數(shù)[8]。因此，完全置換多項(xiàng)式的研究無論是在理論上還是應(yīng)用上都十分有必要。

1 預(yù)備知識

(1)f是雙射的；

引理2設(shè)f(x)是Fq上的完全置換多項(xiàng)式[9]，則

(1)f(x+a)+b是Fq上的完全置換多項(xiàng)式，其中a，b∈Fq；

(3)f-1(x)是Fq上的完全置換多項(xiàng)式。

引理2說明，若d是Fpn上的完全置換單項(xiàng)式指數(shù)，則d-1(modpn-1)也是Fpn上的完全置換單項(xiàng)式指數(shù)。

由AGW準(zhǔn)則可以證明：

引理3設(shè)p為素?cái)?shù)，r，n和d為正整數(shù)且滿足d|(pn-1)。令h(x)∈Fpn[x]，則f(x)=xrh(x(pn-1)/d)是有限域Fpn上的置換當(dāng)且僅當(dāng)下列條件同時(shí)成立[18]：

(2)xrh(x)(pn-1)/d是μd上的置換，其中μd是Fpn中階為d的元素的集合，即

μd={x|xd=1，x∈Fpn} 。

2 完全置換單項(xiàng)式的構(gòu)造

首先，總結(jié)有限域上完全置換單項(xiàng)式指數(shù)的已有研究結(jié)果；其次，發(fā)現(xiàn)并證明一類新的完全置換單項(xiàng)式指數(shù)。

利用Magma對完全置換單項(xiàng)式指數(shù)展開搜索，總結(jié)了完全置換單項(xiàng)式的已有構(gòu)造，見表1和表2。表1中給出了F2n上完全置換單項(xiàng)式指數(shù)的研究結(jié)果，表2列出了奇特征有限域Fpn上完全置換單項(xiàng)式指數(shù)的研究結(jié)果，其中粗體表示的是未被證明的完全置換多項(xiàng)式指數(shù)。

表1 F2n上的完全置換單項(xiàng)式指數(shù)(2≤n≤12)

表2 Fpn上的完全置換單項(xiàng)式指數(shù)

續(xù)表2

筆者對近十多年來有限域Fpn完全置換單項(xiàng)式的相關(guān)理論研究進(jìn)行了總結(jié)。表3列出了有限域Fpn上完全置換單項(xiàng)式的研究結(jié)果。

表3 Fpn上已知的完全置換單項(xiàng)式v-1xd

續(xù)表3

續(xù)表3

通過觀察分析表1和表2中尚未被證明的完全置換多項(xiàng)式指數(shù)，發(fā)現(xiàn)并證明了一類新的完全置換單項(xiàng)式指數(shù)。

因此，對任意x∈μ4，η(a2-x2)=1等價(jià)于η(a2-1)=1且η(a2+1)=1。證畢。

故滿足條件的a的個(gè)數(shù)為

程序結(jié)果表明：當(dāng)p=3，3≤m≤12；p=5，2≤m≤10；p=7，2≤m≤8；p=11，2≤m≤8時(shí)，|τ|>0。

后續(xù)將考慮集合{x|x∈C0，x+1∈C0，x-1∈C0，x∈Fpm}中元素的個(gè)數(shù)。

證明 ① 若p≡±3(mod 8)且m是奇數(shù)，則p2m≡9(mod 16)。事實(shí)上，要證p2m≡9(mod 16)，若令p=8k±3，k為正整數(shù)，則只需證p2m≡(8k±3)2m≡9(mod 16)即可。而

注意到m是奇數(shù)，可令m=2l+1，l為正整數(shù)，則32m≡9m≡92l+1≡9(mod 16)。

② 若p≡±1(mod 8)或m是偶數(shù)，則p2m≡1(mod 16)。證明過程與①中類似，不再贅述。

證畢。

綜合定理1和命題1，有如下定理：

證明d1是Fp2m上的完全置換單項(xiàng)式指數(shù)，只需證下面(1)和(2)同時(shí)成立即可：

(1) gcd(d1，p2m-1)=1；

注2利用定理2，可以證明表2中p=7，n=4時(shí)，d(d-1)=601(1 801)；p=11，n=4時(shí)，d(d-1)=3 661(10 981)為完全置換單項(xiàng)式指數(shù)。程序結(jié)果表明，當(dāng)p=3，n=6；p=3，n=10；p=7，n=6；p=11，n=6時(shí)，定理1的結(jié)論依然成立。故猜測當(dāng)pm≡-1(mod 4)時(shí)，定理1仍成立。

3 結(jié)束語

由于完全置換多項(xiàng)式在密碼學(xué)中的重要應(yīng)用，構(gòu)造新的完全置換多項(xiàng)式非常重要。但現(xiàn)有的構(gòu)造以及計(jì)算機(jī)搜索驗(yàn)證表明，目前仍有很多完全置換多項(xiàng)式尤其是完全置換單項(xiàng)式指數(shù)尚未被刻畫。