許小芳, 曾祥勇, 徐運(yùn)閣

湖北大學(xué)數(shù)學(xué)與統(tǒng)計(jì)學(xué)學(xué)院應(yīng)用數(shù)學(xué)湖北省重點(diǎn)實(shí)驗(yàn)室, 武漢430062

完全置換多項(xiàng)式專欄

1 引言

有限域 Fq上多項(xiàng)式f(x) 誘導(dǎo)的從 Fq到 Fq的函數(shù)f:c→f(c) 是雙射, 則稱f(x) 為 Fq上的置換多項(xiàng)式.若f(x) 和f(x)+x都是 Fq上的置換多項(xiàng)式, 則稱f(x) 為 Fq上的完全置換多項(xiàng)式[1].若f(x) 和f(x)?x都是 Fq上的置換多項(xiàng)式, 則稱f(x) 為 Fq上的正形置換多項(xiàng)式[2].注意,f(x) 是完全置換多項(xiàng)式當(dāng)且僅當(dāng) ?f(x) 是正形置換多項(xiàng)式, 并且這兩個(gè)術(shù)語(yǔ)在偶特征有限域上是一致的.對(duì)于偶特征有限域, 早期的一些文獻(xiàn)采用“正形置換多項(xiàng)式” 這個(gè)名稱[3–5], 近年來(lái)主要使用術(shù)語(yǔ)“完全置換多項(xiàng)式”[6–8], 所以本文采用名稱“完全置換多項(xiàng)式”.本文主要關(guān)注有限域Fpm或向量空間Fmp上完全置換多項(xiàng)式(或稱為完全置換)的相關(guān)理論研究.

完全置換多項(xiàng)式的研究由來(lái)已久, 其概念是Mann 在1942 年構(gòu)造正交拉丁方時(shí)提出的[9].有限域上完全置換多項(xiàng)式的詳細(xì)研究始于Niederreiter 和Robinson[1], 其應(yīng)用非常廣泛, 特別是在密碼學(xué)領(lǐng)域.1995 年, 美國(guó)Teledyne 電子技術(shù)公司Mittenthal 首次利用偶特征域上完全置換多項(xiàng)式來(lái)設(shè)計(jì)非線性動(dòng)力替換裝置并構(gòu)造密碼算法[3,10].隨后, Vaudenay 證明了添加完全置換的Lai-Massey 結(jié)構(gòu)具有更好的偽隨機(jī)性[11].人們還利用完全置換多項(xiàng)式來(lái)設(shè)計(jì)對(duì)稱密碼中的S 盒[12]、流密碼Loiss[13]、Hash 函數(shù)[14,15]、擬群[16–18]以及構(gòu)造具有良好密碼學(xué)性質(zhì)的密碼函數(shù)[19–22].此外, 基于完全置換所構(gòu)造的分組密碼算法SMS4 是我國(guó)第一個(gè)商用分組密碼標(biāo)準(zhǔn), 且被推薦用于無(wú)線局域網(wǎng)WAPI 中[23,24].在組合數(shù)學(xué)領(lǐng)域,完全置換多項(xiàng)式與正交拉丁方聯(lián)系緊密[9,25,26].另外, 完全置換多項(xiàng)式還被用于設(shè)計(jì)校驗(yàn)位系統(tǒng)[27].由于有限域上完全置換多項(xiàng)式的廣泛應(yīng)用, 近年來(lái)完全置換多項(xiàng)式的研究已成為一個(gè)熱點(diǎn)問(wèn)題.到目前為止,完全置換多項(xiàng)式的研究已取得了較大進(jìn)展, 大多集中在完全置換多項(xiàng)式的構(gòu)造.然而, 具有顯式表示的完全置換多項(xiàng)式類非常少, 主要是稀疏型完全置換多項(xiàng)式和形如axpm+bx+h(xpm±x) 的完全置換多項(xiàng)式類.除此之外, 構(gòu)造的方法也不多, 主要是基于經(jīng)典密碼結(jié)構(gòu)、布爾函數(shù)組以及已有完全置換的遞歸構(gòu)造.與完全置換的構(gòu)造相比, 完全置換多項(xiàng)式的代數(shù)次數(shù)、圈結(jié)構(gòu)等相關(guān)密碼學(xué)性質(zhì)的研究結(jié)果更少.因此, 加強(qiáng)完全置換多項(xiàng)式的構(gòu)造以及相關(guān)密碼學(xué)性質(zhì)研究具有重要的理論和實(shí)際意義.

本文對(duì)近二十多年來(lái)有限域 Fpm或向量空間 Fmp上完全置換多項(xiàng)式的相關(guān)理論研究進(jìn)行了總結(jié).第2 節(jié)介紹有限域上完全置換多項(xiàng)式存在性的相關(guān)結(jié)論.第3 節(jié)總結(jié)完全置換多項(xiàng)式構(gòu)造方面的主要研究進(jìn)展, 第4 節(jié)和第5 節(jié)分別給出完全置換多項(xiàng)式的圈結(jié)構(gòu)以及代數(shù)次數(shù)的相關(guān)研究成果.第6 節(jié)簡(jiǎn)要介紹廣義完全置換多項(xiàng)式的相關(guān)研究.最后是本文的小結(jié).

2 完全置換多項(xiàng)式的存在性

由于判斷一個(gè)多項(xiàng)式的完全置換性是非常困難的, 完全置換多項(xiàng)式存在性相關(guān)結(jié)論在實(shí)際應(yīng)用中可以有效地縮小搜索范圍.呂述望等對(duì)有限群上完全置換多項(xiàng)式的存在性進(jìn)行了綜述和討論, 詳情見文獻(xiàn)[28].本節(jié)僅介紹文獻(xiàn) [28]中沒(méi)有收錄的域Fpn上完全置換多項(xiàng)式存在性的相關(guān)結(jié)論.在已有文獻(xiàn)中, 主要考慮特定次數(shù)或特定形式完全置換多項(xiàng)式的存在性.

早在1968 年,文獻(xiàn)[29]提出了一個(gè)與次數(shù)有關(guān)的完全置換多項(xiàng)式不存在性猜想,Cohen[30]在1990 年證明了該猜想, 具體結(jié)論如下.

定理 1[30]若n?2 且素?cái)?shù)p滿足p>(n2?3n+4)2, 則 Fp上不存在次數(shù)為n的完全置換多項(xiàng)式.

Niederreiter 和Robinson[1]討論了完全置換多項(xiàng)式的約化次數(shù), 給出了如下存在性結(jié)論.

定理 2[1]當(dāng)q>5 時(shí), 有限域 Fq上存在約化次數(shù)大于1 的完全置換多項(xiàng)式.

隨后, 人們開始關(guān)注 F2n上完全置換多項(xiàng)式的存在性問(wèn)題.文獻(xiàn) [31]和 [32]通過(guò)Hermite 準(zhǔn)則給出了F2n上完全置換多項(xiàng)式的如下不存在性結(jié)論.

定理 3n為正整數(shù),d為大于1 的正整數(shù), 有下面結(jié)論成立:

(1) 若d>1 且d|2n?1, 則 F2n上不存在d次完全置換多項(xiàng)式[31];

(2) F2n上不存在2 次完全置換多項(xiàng)式[31];

(3) 若n?3, 則 F2n上不存在 2n?1?1 次完全置換多項(xiàng)式[31];

(4) 當(dāng)n≡0,1(modd) 時(shí), F2n上不存在 2d?1 次完全置換多項(xiàng)式[32].

在文獻(xiàn) [32]的基礎(chǔ)上, 文獻(xiàn) [33]給出了n模d的各種情況下 F2n上不存在 2d?1 次完全置換多項(xiàng)式的充分條件, 其中隨后, 文獻(xiàn) [34]指出文獻(xiàn) [33]中結(jié)論的不足之處, 得到了 F2n上不存在2d?1 次完全置換多項(xiàng)式的充分條件以及存在2d次完全置換多項(xiàng)式的必要條件, 具體結(jié)論如下:

定理 4[34]設(shè)f(x) =αu(x2d?1+a2d?2x2d?2+ ···+a1x) 是 F2n上的多項(xiàng)式, 其中α為 F2n的本原元,u∈Z2n?1.設(shè)n=kd+r,e=d?r, 則:

(1) 當(dāng)r=0,1 時(shí),f(x) 不是 F2n上的完全置換多項(xiàng)式;

(2) 當(dāng) 1

定理 5[34]設(shè)f(x) =αu(x2d+a2d?1x2d?1+ ···+a1x) 是 F2n上的多項(xiàng)式, 其中α為 F2n的本原元,u∈Z2n?1.設(shè)n=kd+r,e=d?r, 若f(x) 是 F2n上的完全置換多項(xiàng)式, 則:

(1) 當(dāng)r=0,1 時(shí), 必有a2d?1=0;

(2) 當(dāng) 1

另外, 文獻(xiàn) [35]證明了有限域 F16上不存在9 次完全置換多項(xiàng)式.文獻(xiàn) [36]給出了與次數(shù)有關(guān)的正形置換不存在性結(jié)論, 根據(jù)正形置換與完全置換的關(guān)系, 下面定理說(shuō)明了6 次完全置換的不存在性.

定理 6[36]偶特征有限域上不存在6 次完全置換.另外,m>2 時(shí), F3m上不存在6 次完全置換.

此外, 文獻(xiàn)[1]通過(guò)討論二項(xiàng)式axk+bx的完全置換性給出了一些存在性相關(guān)結(jié)論.

定理 7[1]設(shè)q是素?cái)?shù)的方冪, 則

(1) 當(dāng)奇數(shù)q?13 或q=7 時(shí), 有限域 Fq上一定存在形如的完全置換多項(xiàng)式;

(2) 令k>2, 若k不是素?cái)?shù)的方冪, 當(dāng)q?(k2?4k+6)2時(shí), Fq上不存在形如axk+bx的完全置換多項(xiàng)式, 其中

(3) 令k> 2, 若k是素?cái)?shù)p的方冪且p不等于 Fq的特征, 當(dāng)q? (k2?4k+6)2時(shí), Fq上不存在形如axk+bx的完全置換多項(xiàng)式, 其中

(4) 令k>2, 若k和q都是素?cái)?shù)p的方冪, 則存在形如axk∈Fq[x]的完全置換多項(xiàng)式.

文獻(xiàn)[1,37]還給出了二項(xiàng)式axk+bxj∈Fq[x]不構(gòu)成置換的一些充分條件, 進(jìn)而在相同的條件下可知axk+bxj不構(gòu)成完全置換多項(xiàng)式.另外, 當(dāng)q=pm且p3 時(shí), 文獻(xiàn) [38]指出對(duì)任意的v∈Fq3,v?1xq2+q+2不是 Fq3上的完全置換.

除上述研究之外, 文獻(xiàn)[39]和[40]還給出了與置換多項(xiàng)式的Carlitz 秩 (Carlitz rank) 相關(guān)的完全置換不存在性結(jié)論.由于很難確定一個(gè)置換多項(xiàng)式的Carlitz 秩, 與Carlitz 秩相關(guān)的完全置換多項(xiàng)式不存在性結(jié)論的應(yīng)用受到限制.

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

完全置換多項(xiàng)式的構(gòu)造是密碼學(xué)中的熱點(diǎn)問(wèn)題, 目前已有一些成熟的構(gòu)造方法以及完全置換多項(xiàng)式類.本節(jié)從構(gòu)造方法以及多項(xiàng)式的形式來(lái)給出已有完全置換的分類, 包括基于線性完全置換的非線性完全置換、基于密碼結(jié)構(gòu)、布爾函數(shù)組、特殊函數(shù)的完全置換多項(xiàng)式、完全置換多項(xiàng)式的遞歸構(gòu)造、完全置換的合成逆以及稀疏型完全置換多項(xiàng)式和形如axpm+bx+h(xpm±x) 的完全置換多項(xiàng)式.

3.1 基于線性完全置換的上非線性完全置換

1995 年, Mittenthal[3]指出通過(guò)有限個(gè)方程利用組合的方法可以構(gòu)造上的線性完全置換.隨后,Dai、Golomb 和Gong[5]利用正形矩陣介紹了一種非冗余構(gòu)造算法生成上所有線性完全置換, 解決了上線性完全置換的構(gòu)造問(wèn)題.線性完全置換的其它相關(guān)問(wèn)題參考文獻(xiàn)[41–45].用于分組密碼體制的完全置換需要滿足的一個(gè)基本要求是非線性性, 所以研究非線性完全置換的構(gòu)造具有重要的意義.

Mittenthal[10]指出上線性完全置換可以用 2n個(gè)等式表示, 在保證等式成立的前提下通過(guò)改變等式左端兩列中元素的順序, 能夠得到非線性完全置換的過(guò)程稱為構(gòu)造性腐化(constructive corruption).專利[10]從最大線性完全置換 (詳見定理45) 出發(fā)在陪集分解的基礎(chǔ)上通過(guò)構(gòu)造性腐化來(lái)生成非線性完全置換.由于可腐化陪集的選擇方法有很多, 所以基于陪集分解的構(gòu)造方法具有較大的靈活性.

隨后, 谷大武和肖國(guó)鎮(zhèn)[46]指出專利 [10]中最大線性完全置換選取不當(dāng)時(shí)基于陪集分解的構(gòu)造方法有可能失效, 并對(duì)該構(gòu)造進(jìn)行了適當(dāng)?shù)母倪M(jìn), 新的方法可以構(gòu)造更多的非線性完全置換.

另外,Golomb、Gong 和Mittenthal[4]從最大線性完全置換出發(fā)構(gòu)造移位拉丁方,在移位拉丁方的每一行和每一列中選擇沒(méi)有重復(fù)的元素來(lái)構(gòu)造了一個(gè)截集(transversal)進(jìn)而生成非線性完全置換.文獻(xiàn)[4]中基于移位拉丁方截集的非線性完全置換構(gòu)造算法并不是最優(yōu)的, 但當(dāng)n較大時(shí)比窮舉搜索法有效.

專利 [10]和文獻(xiàn) [4]的發(fā)表吸引了很多國(guó)內(nèi)學(xué)者關(guān)注基于拉丁方的完全置換構(gòu)造問(wèn)題[47–51]以及相關(guān)引文.令人遺憾的是, 這些構(gòu)造所得非線性完全置換的代數(shù)表達(dá)式很難確定, 并且當(dāng)n較大時(shí)所需內(nèi)存較大, 在工程上難以實(shí)現(xiàn).

3.2 基于密碼結(jié)構(gòu)的完全置換

流密碼中的移位寄存器、分組密碼中的Feistel 結(jié)構(gòu)、MISTY 結(jié)構(gòu)以及它們的組合常被用于構(gòu)造完全置換多項(xiàng)式.

1995 年, Mittenthal[3]率先將極大長(zhǎng)度的線性反饋移位寄存器與最大線性完全置換聯(lián)系起來(lái).隨后,馮登國(guó)和劉振華[52]從不可約多項(xiàng)式出發(fā)利用線性反饋移位寄存器來(lái)構(gòu)造線性完全置換.

使用任意輪函數(shù)的Feistel 結(jié)構(gòu)可構(gòu)造雙射, 因此, Feistel 結(jié)構(gòu)及其推廣是創(chuàng)建非線性密碼函數(shù)(特別是完全置換多項(xiàng)式)的常用技術(shù).呂述望等[28]對(duì)完全置換的構(gòu)造以及應(yīng)用進(jìn)行了研究, 給出了省略輪密鑰的1 輪和2 輪Feistel 結(jié)構(gòu)所對(duì)應(yīng)的完全置換.

定理 8[28]設(shè)p是任一素?cái)?shù), 令p(z) 為有限域 Fpm上的置換多項(xiàng)式.則的映射

定理 9[28]令p1(z),p2(z) 為 F2m上的兩個(gè)置換多項(xiàng)式.則

下面的結(jié)論是1 輪Feistel 結(jié)構(gòu)的推廣形式.

定理 10[28]令pi(z)(i=1,2,··· ,k? 1) 為 F2m上的多項(xiàng)式.若上的置換多項(xiàng)式, 則

隨后, 文獻(xiàn)[16,17]在討論基于Feistel 結(jié)構(gòu)分組密碼的擬群表示以及擬群構(gòu)造時(shí), 利用交換群 (G,+)上雙射構(gòu)造了幾類群 (Gn,+) 上的完全置換, 其中n?2.當(dāng)G=Fpm時(shí), 可得到上的完全置換, 以如下結(jié)論為例, 其余見文獻(xiàn)[16,17].

定理 11[16]取常數(shù)a,b,c∈ Fpm.若p(x) 是 Fpm上的雙射, 則

當(dāng)a=b=c=0 時(shí), ?a,b,c,p就退化為定理8 中的完全置換 ?p.顯然, ?a,b,c,p仿射等價(jià)于 ?p.

另外, 文獻(xiàn) [18,53]在討論基于Feistel 結(jié)構(gòu)的Camellia、Four-Cell、GOST、MIBS、Skipjack 等分組密碼的擬群表示時(shí)得到了五類上的完全置換和兩類上的完全置換, 希望能夠通過(guò)對(duì)應(yīng)的代數(shù)結(jié)構(gòu)來(lái)分析相應(yīng)的分組密碼.

最近, 受Feistel 結(jié)構(gòu)和MISTY 結(jié)構(gòu)的啟發(fā), 文獻(xiàn) [6]運(yùn)用省略輪密鑰的Feistel 結(jié)構(gòu), L-MISTY 結(jié)構(gòu)以及R-MISTY 結(jié)構(gòu)的1, 2, 3 輪組合, 得到了很多上完全置換多項(xiàng)式的構(gòu)造.先給出這三種結(jié)構(gòu)對(duì)應(yīng)的三個(gè)映射 ?p, Φp和 Ψp, 其中 ?p與定理8 中表述一致.

定義 1[6]令p(z) 為 Fpm到其自身的多項(xiàng)式.的映射 ?p, Φp和 Ψp定義為

定理 12[6]當(dāng)p(z) 是 Fpm上的置換時(shí), 定義1 中映射 ?p, Φp和 Ψp是上的完全置換多項(xiàng)式.

2 輪構(gòu)造可看作是映射 ?pi, Φpi和 Ψpi(其中i= 1,2)的合成, 文獻(xiàn) [6]給出了九個(gè)合成映射構(gòu)成完全置換的充分條件, 下面僅列出其中易于實(shí)現(xiàn)的七個(gè)完全置換.

定理 13[6]令p1(z),p2(z) 為 F2m上的兩個(gè)置換多項(xiàng)式.則 {Ψp2??p1,?p2?Φp1,Ψp2?Φp1,?p2??p1,Φp2??p1,?p2?Ψp1,Φp2?Ψp1} 中任一映射是上的完全置換.

通過(guò)Feistel 結(jié)構(gòu)和MISTY 結(jié)構(gòu)的3 輪復(fù)合, 總共得到完全置換多項(xiàng)式的14 種構(gòu)造, 這些構(gòu)造所需要滿足的條件大多比較類似, 在此僅列出以下兩類, 其余見文獻(xiàn)[6].

定理 14[6]取F2m上的兩個(gè)置換多項(xiàng)式p1(z)+z,p3(z) 以及多項(xiàng)式p2(z).若多項(xiàng)式p2(z)+p3(z)是置換, 則 Φp3??p2??p1是上的完全置換.

定理 15[6]取有限域 F2m上的置換多項(xiàng)式p2(z) 和完全置換多項(xiàng)式p3(z).若p1(z) 是F2m上的完全置換多項(xiàng)式, 則映射 Φp3?Ψp2?Φp1是上的完全置換多項(xiàng)式.

相對(duì)而言, 定理15 的條件更容易實(shí)現(xiàn), 而定理14 中需要找到兩個(gè) F2m上的 (置換) 多項(xiàng)式使得它們的和仍然是置換.如下定理表明MISTY 結(jié)構(gòu)可以有效構(gòu)造此類置換.

定理 16[6]令g1(z) 和g2(z) 是 Fq上的多項(xiàng)式, 其中q是 2 的方冪.取定義1 中映射 Φg1和 Ψg2.若g1(z) 和g2(z) 是 Fq上的完全置換多項(xiàng)式, 則多項(xiàng)式 Φg1, Ψg2和 Φg1+Ψg2是上的置換.

此外, 對(duì)任意的素?cái)?shù)冪q, 文獻(xiàn)[6]利用Feistel 結(jié)構(gòu)的推廣形式構(gòu)造了一類上的完全置換多項(xiàng)式.

定理 17[6]取有限域 Fpm上的多項(xiàng)式p1(z),p2(z),p3(z), 其中p2(z) 是置換多項(xiàng)式.若對(duì)任意的γ∈Fpm,多項(xiàng)式p1(z)?p3(z+γ)是 Fpm上的置換,則多項(xiàng)式F(x1,x2)=(p1(?x2)?x1?p3(p2(p1(?x2)?x1)?x2),p2(p1(?x2)?x1)?x2) 是上的完全置換.

注意, 函數(shù)F(x1,x2) 與1 輪Feistel 結(jié)構(gòu)所對(duì)應(yīng)的映射 ?p關(guān)系密切.另外, 定理17 的第一個(gè)條件并不容易滿足.當(dāng)p3(x) 為線性化多項(xiàng)式時(shí), 可以找到大量滿足該條件的p1(x).當(dāng)p1(x),p3(x) 都不是線性化多項(xiàng)式時(shí), 文獻(xiàn)[6]給出了滿足該條件的單項(xiàng)式p1(x),p3(x).

對(duì)任意的素?cái)?shù)冪q以及不小于2 的整數(shù)n, 文章討論的2 輪構(gòu)造通過(guò)適當(dāng)?shù)卣{(diào)整可以得到很多 Fnq上的完全置換多項(xiàng)式, 由于這些結(jié)論的證明具有相似性, 這里僅給出如下結(jié)論.

定理 18[6]取 Fq上的置換多項(xiàng)式p1(z),p2(z), ··· ,pn(z), 其中q=pm, 則滿足條件

的多項(xiàng)式G(x)=(G1(x),G2(x),··· ,Gn(x)) 是上的完全置換.特別地, 當(dāng)p=n=2 時(shí), 函數(shù)G(x)是2 輪Feistel 結(jié)構(gòu)所對(duì)應(yīng)的映射 ?p2??p1.

與文獻(xiàn)[16–18,28,53]中基于密碼結(jié)構(gòu)的完全置換相比, 文獻(xiàn)[6]中除了對(duì)應(yīng)于1 輪、2 輪Feistel 結(jié)構(gòu)的 ?p和 ?p2??p1以外其余的構(gòu)造均是新的.文獻(xiàn) [6]不僅得到了大量的完全置換多項(xiàng)式類, 還研究了所構(gòu)造完全置換多項(xiàng)式的代數(shù)次數(shù)(詳見第5 節(jié)).

本節(jié)所介紹的完全置換建立在經(jīng)典密碼結(jié)構(gòu)基礎(chǔ)上, 具有易于軟硬件實(shí)現(xiàn)的特點(diǎn), 值得進(jìn)一步研究.

3.3 基于布爾函數(shù)組的完全置換

通過(guò)選取特殊的布爾函數(shù)組(或完全置換的坐標(biāo)分量函數(shù))可以有效地進(jìn)行上完全置換的構(gòu)造.馮登國(guó)和劉振華在文獻(xiàn)[52]中提出了基于布爾函數(shù)組的構(gòu)造方法.

定理 19[52]任取n?2 元布爾函數(shù)h2(x3,x4,··· ,xn),n?3 元布爾函數(shù)h3(x4,x5,··· ,xn),···, 1 元布爾函數(shù)hn?1(xn).令

則P(x)=(f1,f2,··· ,fn) 是上的完全置換.

另外他們還給出了由低階完全置換拼接構(gòu)造高階完全置換的方法.

定理 20[52]取上的完全置換多項(xiàng)式fi(xi), 則F(x1,x2,··· ,xs) = (f1(x1),f2(x2),··· ,fs(xs))是上的完全置換.

定理20 所得到的完全置換有明顯的缺點(diǎn), 即F(x1,x2,··· ,xs) 可以分解為變量間沒(méi)有關(guān)系的幾個(gè)部分, 因而容易遭受攻擊.為了提高其安全性, 文獻(xiàn)[54–56]在定理20 的基礎(chǔ)上增加元素之間的交叉, 給出了幾種推廣形式, 以如下定理來(lái)說(shuō)明.

定理 21[54]設(shè)F(x1,x2,··· ,xn) 為上的完全置換,G(y1,y2,··· ,ym) 為上的完全置換, 取的函數(shù)H1(y1,y2,··· ,ym) 以及的函數(shù)H2(x1,x2,··· ,xn), 則 (F+H1,G) 和(F,G+H2) 是上的完全置換.

定理 22[59]設(shè)P1=(g1,g2,··· ,gn?2),P2=(h1,h2,··· ,hn?2) 為上的完全置換, 令

則P=(f1,f2,··· ,fn) 是上的完全置換.

定理 23[60]設(shè)P1(x1,x2,··· ,xn?2)=(f1,f2,··· ,fn?2) 為上的完全置換, 令

則P=(f1,f2,··· ,fn) 是上的完全置換.

另外, 文獻(xiàn)[61]在研究M-M 型函數(shù)(Maiorana-McFarland 型布爾函數(shù))與高原函數(shù)(plateaued function)關(guān)系的基礎(chǔ)上, 使用上三組具體的基, 給出了一類上所有坐標(biāo)分量為M-M 型函數(shù)的完全置換多項(xiàng)式.通過(guò)計(jì)算機(jī)模擬發(fā)現(xiàn)文獻(xiàn)[61]所構(gòu)造的完全置換在n較小時(shí)存在線性結(jié)構(gòu), 易受到攻擊.隨后, 采用文獻(xiàn) [61]的思想, 文獻(xiàn) [7]利用向量空間的任意一組基以及高原函數(shù), 給出了完全置換多項(xiàng)式的一般構(gòu)造.與文獻(xiàn)[61]中的構(gòu)造相比, 文獻(xiàn) [7]中的構(gòu)造是基于任意一組基給出的, 且僅有部分坐標(biāo)分量為M-M 型函數(shù)而另一部分坐標(biāo)分量為布爾函數(shù)與高原函數(shù)的組合, 可以得到更多的完全置換多項(xiàng)式.此外, 通過(guò)計(jì)算機(jī)模擬發(fā)現(xiàn)文獻(xiàn)[7]的構(gòu)造中存在不包含線性結(jié)構(gòu)的完全置換, 因而有望從該構(gòu)造中找到安全性較高的完全置換多項(xiàng)式類.

本節(jié)所討論的完全置換大多數(shù)是用坐標(biāo)分量形式來(lái)表示的, 主要通過(guò)證明坐標(biāo)分量函數(shù)的所有非零線性組合是平衡函數(shù)來(lái)說(shuō)明其置換性.它們一般都具有簡(jiǎn)潔的分量表達(dá)式, 但在Fpn上的單變?cè)磉_(dá)式非常復(fù)雜.

3.4 基于特殊函數(shù)的完全置換多項(xiàng)式

本節(jié)主要介紹與Dikson 多項(xiàng)式、平面函數(shù)(planar mapping)、線性變換算子(linear translator)以及冪零線性化多項(xiàng)式(nilpotent linearized polynomial)相關(guān)的完全置換多項(xiàng)式.

1987 年, Mullen 和Niederreiter[62]討論了Dikson 多項(xiàng)式Dk(x,a) 的完全置換性質(zhì).

定理 24[62]令且a,b,c∈ Fq, 其中若滿足下面任一條件:

則bDk(x,a)+cx是Fq上的完全置換多項(xiàng)式.

最近, 文獻(xiàn)[63]利用Dickson 多項(xiàng)式的合成逆給出了兩個(gè)特殊完全置換多項(xiàng)式.

定理 25[63]取正整數(shù)m,k滿足m=6k±1, 令da(x) 表示 F5m上Dickson 多項(xiàng)式D7(x,a) 的合成逆, 則對(duì)任意的δ∈ F5m,d1(?x5?x+δ) 和d?1(x5+x+δ) 都是 F5m上的完全置換多項(xiàng)式.

Muratovi?-Ribi? 和Pasalic 發(fā)現(xiàn)平面函數(shù)的導(dǎo)函數(shù)與完全置換多項(xiàng)式之間存在密切的關(guān)系, 可以利用平面函數(shù)的導(dǎo)函數(shù)來(lái)構(gòu)造完全置換多項(xiàng)式[64].

定理 26[64]設(shè)h是 Fpn上的平面函數(shù)且它在處的導(dǎo)函數(shù)為fa(x) =h(x+a)?h(x).令則對(duì)任意的有:

(1)g1,a(x) 和gp?1,a(x) 是 Fpn上的完全置換多項(xiàng)式;

(2)gt,a(x)+ ···+gp?1,a(x) 是 Fpn上的完全置換多項(xiàng)式, 其中 1tp? 2;

(3)g1,a(x)+ ···+gt,a(x) 是 Fpn上的完全置換多項(xiàng)式, 其中 1tp? 2;

另外, 文獻(xiàn)[64]還提出了幾乎平面函數(shù)(almost planar mapping)的概念并利用該函數(shù)來(lái)構(gòu)造完全置換多項(xiàng)式.

定理 27[64]設(shè)f1(x),··· ,fn(x) 是 Fq上的平面函數(shù).取任意函數(shù)構(gòu)造的映射

其中xi∈ Fq.則F是幾乎平面函數(shù).特別地, 令fa(x) =F(x+a)?F(x), 則對(duì)任意的是上的完全置換多項(xiàng)式.

文獻(xiàn)[64]中給出的基于平面函數(shù)和幾乎平面函數(shù)所構(gòu)造的完全置換多項(xiàng)式依賴于某個(gè)置換的合成逆,但是計(jì)算置換合成逆的困難性可能導(dǎo)致其應(yīng)用受限.

下面先給出Fpm到其子域上線性變換算子的定義.

定義 2[65]取正整數(shù)m,n, 令f(x) 是的函數(shù).取以及若對(duì)任意的x∈ Fpmn以及u∈ Fpm, 有f(x+uγ)?f(x)=ub, 則稱γ為f(x) 在 Fpmn上相對(duì)于 Fpm的b-線性變換算子.

文獻(xiàn)[65]得到了線性變換算子與完全置換多項(xiàng)式的如下聯(lián)系.

定理 28[65]取奇素?cái)?shù)p, 令f(x) 是 Fpmn到 Fpm的函數(shù).若γ為f(x) 在 Fpmn上相對(duì)于 Fpm的b-線性變換算子, 則x+γf(x) 是Fpmn上的完全置換多項(xiàng)式當(dāng)且僅當(dāng)b/∈{?1,?2}.

隨后, Akbary、Ghioca 和Wang[66]將線性變換算子的定義推廣為 Fpm到其子集上.利用推廣的線性變換算子, 定理28 中的條件可以進(jìn)一步擴(kuò)展, 得到了如下包含定理28 中結(jié)論的一類完全置換多項(xiàng)式.

定理 29[66]取奇素?cái)?shù)p以及 Fpm的子集S且滿足 2S=S, 令f(x) 是 Fpm到S的滿射.若γ為f(x) 在 Fpm上相對(duì)于S的b-線性變換算子, 則x+γf(x) 是 Fpm上的完全置換多項(xiàng)式當(dāng)且僅當(dāng)

另外, 文獻(xiàn)[67]在研究包含跡函數(shù)的置換多項(xiàng)式時(shí)提出了一類屬于定理28 和定理29 特例的完全置換多項(xiàng)式.

定理 30[67]取奇素?cái)?shù)p,令γ∈Fpm且滿足中任意的h(x),有是Fpm上的完全置換多項(xiàng)式.

3.5 完全置換多項(xiàng)式的遞歸構(gòu)造

本節(jié)主要介紹完全置換多項(xiàng)式的遞歸構(gòu)造, 即通過(guò)已有置換或完全置換來(lái)構(gòu)造新的完全置換多項(xiàng)式.

文獻(xiàn)[1]中給出了由已知完全置換得到更多完全置換的基本方法.

定理 31[1]設(shè)f(x) 是Fpm上的完全置換多項(xiàng)式, 則:

(1)f(x+a)+b是 Fpm上的完全置換, 其中a,b∈Fpm;

(2)af(a?1x) 是 Fpm上的完全置換, 其中

(3)f?1(x) 是 Fpm上的完全置換.

由定理31 中(1)和(2)所構(gòu)造的完全置換與原完全置換是仿射等價(jià)的, 利用(3)中合成逆來(lái)構(gòu)造新的完全置換詳見3.6 節(jié).

下面介紹的遞歸構(gòu)造是文獻(xiàn)[69]和文獻(xiàn)[25]在研究置換以及完全置換多項(xiàng)式時(shí)分別獨(dú)立給出的.

定理32[25,69]取正整數(shù)m和正奇數(shù)n.假設(shè)L(x)是F2m上的線性化多項(xiàng)式.若對(duì)某些v∈F2mF2有xL(x)+vx是 F2m上的完全置換多項(xiàng)式, 則對(duì)任意的u∈F2m, 多項(xiàng)式

是F2mn上的完全置換.

在定理32 中取L(x)=0, 可構(gòu)造如下完全置換多項(xiàng)式, 該構(gòu)造是文獻(xiàn)[70]中完全置換三項(xiàng)式的推廣.

推論 1[25,69]取正整數(shù)m和正奇數(shù)n.對(duì)任意元素多項(xiàng)式ux)+vx是 F2mn上的完全置換.

多次使用定理32 和推論1, 可得如下包含多個(gè)跡函數(shù)的完全置換多項(xiàng)式.

推論 2[69]取正整數(shù)m, 正奇數(shù)n.假設(shè)d1,··· ,ds是互不相同的正整數(shù)且滿足d1|d2|··· |ds|n, 令則對(duì)任意的v∈ F2mF2, 多項(xiàng)式是 F2mn上的完全置換, 其中且d0=1.

此外, 文獻(xiàn)[71]運(yùn)用AGW 準(zhǔn)則給出了由子域上置換來(lái)構(gòu)造擴(kuò)域上完全置換的遞歸構(gòu)造.

定理 33[71]對(duì)任意素?cái)?shù)p, 取正整數(shù)r,k且n=rk.取 Fpk上的函數(shù)g(x), 若xg(x)+vx對(duì)某些構(gòu)成 Fpk上的置換多項(xiàng)式，則當(dāng) gcd(p?1,r) = gcd(r,p) = 1 且a∈ Fpk{0,?1} 時(shí), 多項(xiàng)式是 Fpn上的完全置換.

通過(guò)選取適當(dāng)?shù)膅(x), 根據(jù)定理33 能構(gòu)造很多完全置換多項(xiàng)式.例如, 當(dāng)g(x) = 0 時(shí), 可得如下推論.

推論 3[71]對(duì)任意素?cái)?shù)p, 令n=rk, 其中r,k為正整數(shù).若 gcd(p?1,r) = gcd(r,p) = 1 且a∈ Fpk{0,?1}, 則是 Fpn上的完全置換多項(xiàng)式.

在推論3 中取p=2 以及奇數(shù)r, 所得完全置換是推論1 的特殊情況.

在文獻(xiàn)[25,69,71]的基礎(chǔ)上, Tuxanidy 和Wang[26]使用AGW 準(zhǔn)則來(lái)研究完全置換的遞歸構(gòu)造.

定理 34[26]p為任意素?cái)?shù), 正整數(shù)r,m,n滿足gcd(m,r)=gcd(mn,r),p?n以及 gcd(n,pgcd(m,r)?1)=1.取 Fpm上的函數(shù)G(x), 則對(duì)任意的多項(xiàng)式

是Fpmn上的完全置換當(dāng)且僅當(dāng)xG(x) 是Fpm上的完全置換多項(xiàng)式.

定理34 推廣了定理32.在定理34 中取G(x)=b∈Fpm{0,?1}, 可構(gòu)造如下完全置換多項(xiàng)式.

推論 4[26]對(duì)任意素?cái)?shù)p, 正整數(shù)r,m,n滿足 gcd(m,r)=gcd(mn,r),p?n以及 gcd(n,pgcd(m,r)?1) = 1.則對(duì)任意的多項(xiàng)式是 Fpmn上的完全置換.

多次運(yùn)用定理34, 可以構(gòu)造如下包含多個(gè)跡函數(shù)的完全置換多項(xiàng)式.

定理 35[26]取正整數(shù)m,n,r.假設(shè)d0,d1,··· ,dt是互不相同的正整數(shù)且滿足 1=d0|d1|··· |dt=n.素?cái)?shù)p滿足以及取ak∈Fpmdk且令f0∈ Fpm[x], 則

是Fpmn上的完全置換多項(xiàng)式當(dāng)且僅當(dāng)f0(x) 是Fpm上的完全置換且滿足f0(0)=0.

另外, 文獻(xiàn)[8]通過(guò)AGW 準(zhǔn)則給出了由域F2m上完全置換二項(xiàng)式來(lái)構(gòu)造其擴(kuò)域上完全置換的遞歸構(gòu)造.

定理 36[8]取正整數(shù)n=mr且r為奇數(shù).對(duì)正整數(shù)k, 若其中b=1, 則多項(xiàng)式

是F2n上的完全置換當(dāng)且僅當(dāng)g(x)=axk+bx是 F2m上的完全置換.特別地, 取k=2i, 其中i為非負(fù)整數(shù),f(x) 是完全置換多項(xiàng)式當(dāng)且僅當(dāng)都不是 F2m中的 (k?1) 次冪元.

下面介紹Zha、Hu 和Cao 在文獻(xiàn)[72]中提出的Fpn上完全置換多項(xiàng)式的遞歸構(gòu)造, 這些構(gòu)造所依賴多項(xiàng)式的值域?yàn)镕pn的子域.

定理 37[72]令n1|n2|···|nh|n, 當(dāng)i= 1,2,··· ,h時(shí), 取 Fpn[x]上值域在 Fpni中的多項(xiàng)式gi(x).令L(x) ∈ Fpn1 為線性化多項(xiàng)式.取滿足且滿足Fpni+1(i=1,2,··· ,h? 1).取滿足則

是Fpn上的完全置換多項(xiàng)式當(dāng)且僅當(dāng)L(x) 是Fpn上的完全置換多項(xiàng)式.

作為定理37 的應(yīng)用, 給出如下推論.

推論 5[72]取任意素?cái)?shù)p, 令正整數(shù)n,l,k,s滿足且l為偶數(shù).

令θ,β,γ,δ∈ Fpn滿足取 Fpk[x]中的線性化多項(xiàng)式L(x), 則

是Fpn上的完全置換多項(xiàng)式當(dāng)且僅當(dāng)L(x) 是Fpn上的完全置換多項(xiàng)式.

由于Fpn上跡函數(shù)的值域?yàn)镕pk, 文獻(xiàn)[72]進(jìn)一步利用跡函數(shù)給出了幾個(gè)置換多項(xiàng)式的遞歸構(gòu)造, 并指出其構(gòu)成完全置換需滿足的相應(yīng)條件.

此外, 文獻(xiàn)[19]還給出了一種類似于分量表示的遞歸構(gòu)造法.

定理 38[19]對(duì)任意素?cái)?shù)p以及正整數(shù)n, 令 {α1,α2,··· ,αn} 是 Fpmn關(guān)于 Fpm的一組基.對(duì)任意的i= 1,2,··· ,n, 令θi(xi) 為 Fpm上的完全置換多項(xiàng)式.當(dāng)i= 2,3,··· ,n時(shí), 函數(shù)將 (x1,x2,··· ,xi?1) 映射為ψi(x1,x2,··· ,xi?1).則

是 Fpmn上的完全置換多項(xiàng)式, 其中x=x1α1+x2α2+ ···+xnαn∈ Fpmn.

3.6 完全置換多項(xiàng)式的合成逆

Niederreiter 和Robinson[1]指出完全置換多項(xiàng)式的合成逆(簡(jiǎn)稱為逆) 仍然是完全置換多項(xiàng)式, 故可以通過(guò)計(jì)算已有完全置換的逆來(lái)構(gòu)造新的完全置換.一般情況下, 很難確定完全置換多項(xiàng)式合成逆的顯式表示, 且相關(guān)研究成果較少.

在某些特殊情況下合成逆的計(jì)算難度相對(duì)較小, 比如計(jì)算完全置換單項(xiàng)式的合成逆.若存在v使得v?1xk構(gòu)成 Fpm上的完全置換單項(xiàng)式, 則稱k為 Fpm上的CPP 指數(shù).假設(shè)k是 Fpm上的CPP 指數(shù), 則k?1(modpm?1) 也是 Fpm上的CPP 指數(shù).計(jì)算完全置換單項(xiàng)式的合成逆等價(jià)于給出k?1的明確表達(dá)式.利用歐幾里德算法和中國(guó)剩余定理, 文獻(xiàn) [69]和 [73]分別獨(dú)立給出了文獻(xiàn) [70]中三類完全置換單項(xiàng)式的合成逆.另外, 文獻(xiàn)[73]和[74]構(gòu)造完全置換單項(xiàng)式的同時(shí)還考慮了它們的逆.部分結(jié)論見表1.

除了單項(xiàng)式的合成逆以外, 文獻(xiàn) [69]通過(guò)有限域的直和分解將單變?cè)囗?xiàng)式轉(zhuǎn)化為雙變?cè)囗?xiàng)式來(lái)計(jì)算定理32 中完全置換多項(xiàng)式的逆, 得到了完全置換多項(xiàng)式新的遞歸構(gòu)造, 該構(gòu)造依賴于完全置換xL(x) +vx的合成逆.當(dāng)L(x) = 0 時(shí), 很容易可得推論1 中完全置換多項(xiàng)式逆置換的顯式表示[69].隨后, Tuxanidy 和 Wang[26]通過(guò)計(jì)算特殊集合上線性化二項(xiàng)式的逆給出了定理34 中完全置換多項(xiàng)式f(x) 的逆, 所得完全置換多項(xiàng)式的形式十分復(fù)雜且依賴于完全置換多項(xiàng)式xG(x) 的逆.此處所介紹的完全置換依賴于特殊完全置換的逆, 并不能直接給出顯式表示.

若在分組密碼的加密過(guò)程中應(yīng)用完全置換多項(xiàng)式來(lái)構(gòu)建混淆層, 在解密過(guò)程中將需要用到完全置換多項(xiàng)式的逆.因此, 確定易于實(shí)現(xiàn)完全置換多項(xiàng)式的合成逆是非常有意義的.

3.7 稀疏型完全置換多項(xiàng)式

有限域上稀疏型完全置換多項(xiàng)式, 即項(xiàng)數(shù)較少的完全置換, 由于其具有簡(jiǎn)潔的代數(shù)形式且在工程上易于實(shí)現(xiàn)而受到人們的廣泛關(guān)注.本節(jié)重點(diǎn)介紹單項(xiàng)、二項(xiàng)以及三項(xiàng)的完全置換多項(xiàng)式.

稀疏型完全置換的研究熱點(diǎn)是完全置換單項(xiàng)式.表1 中列出了 Fpm上的部分完全置換單項(xiàng)式.2013 年之前完全置換單項(xiàng)式的研究結(jié)果十分少, 主要是線性化完全置換單項(xiàng)式[1,75]和分式型指數(shù)完全置換單項(xiàng)式[75–77].2014 年, Tu、Zeng 和Hu[70]利用加法特征和極坐標(biāo)表示法給出了有限域 F2n上的三類完全置換單項(xiàng)式, 在此將該文獻(xiàn)所使用的方法簡(jiǎn)記為Tu-Zeng-Hu 方法.受該文獻(xiàn)的啟發(fā), 通過(guò)類似方法可以得到一系列稀疏型完全置換多項(xiàng)式[71,73,74,78].從指數(shù)形式以及理論基礎(chǔ)來(lái)看, 完全置換單項(xiàng)式的研究大致分為三類: (1) 基于Tu-Zeng-Hu 方法的完全置換單項(xiàng)式; (2) 分式型指數(shù)完全置換單項(xiàng)式; (3) 已有完全置換單項(xiàng)式的合成逆(見3.6 節(jié)).

隨著文獻(xiàn) [70]的發(fā)表, 人們開始考慮利用Tu-Zeng-Hu 方法來(lái)證明多項(xiàng)式的置換性以及完全置換性.例如, Xu 和Cao[74]利用該方法研究了奇特征域 Fp2m上單項(xiàng)式v?1xk的完全置換性質(zhì), 其中p= 3 時(shí)指數(shù)k取 3m+2 或 2·3m+3.另外, 文獻(xiàn) [73,79]采用類似的方法給出了 F23k, F24k, F26k以及 Fp4k上的四類完全置換單項(xiàng)式.

表1 Fpm 上的完全置換單項(xiàng)式v?1xkTable 1 Complete permutation monomials v?1xk over Fpm

表2 Fpm 上的完全置換二項(xiàng)式αx+βxkTable 2 Complete permutation binomials αx+βxk over Fpm

完全置換三項(xiàng)式的已有結(jié)論格外少, 主要有四類, 具體結(jié)果見表3.第1 類給出了域F16上完全置換三項(xiàng)式的所有可能形式[35].第2 類是由Tu、Zeng 和Hu[70]利用AGW 準(zhǔn)則得到的F23r上的完全置換三項(xiàng)式, 由它推廣的遞歸構(gòu)造詳見文獻(xiàn) [69].第3 類是文獻(xiàn) [79]通過(guò)確定方程解的個(gè)數(shù)給出的奇特征域 Fp3r上的完全置換三項(xiàng)式.第4 類討論的是Niho 型指數(shù)完全置換三項(xiàng)式, 文章不僅給出了這類三項(xiàng)式構(gòu)成完全置換的充要條件, 還確定了所構(gòu)造完全置換的個(gè)數(shù), 相對(duì)其它完全置換三項(xiàng)式而言, 此類構(gòu)造可以得到更多的完全置換[8].

表3 Fpm 上的完全置換三項(xiàng)式αx+β1xk1 +β2xk2Table 3 Complete permutation trinomials αx+β1xk1 + β2xk2 over Fpm

表3 中的完全置換三項(xiàng)式都包含1 次項(xiàng), 文獻(xiàn) [63]從Dickson 多項(xiàng)式出發(fā)給出了一類特殊的不含1 次項(xiàng)的完全置換三項(xiàng)式.

定理 39[63]正整數(shù)m,k滿足設(shè)a是 F5m上的非平方元.若正整數(shù)t滿足 7t≡1(mod 5m?1), 則 3axt(x2t?a)2=3ax5t?6a2x3t+3a3xt是 F5m上的完全置換.

此外, 文獻(xiàn)[1,36,81]還討論了具體域上次數(shù)較低的稀疏型完全置換多項(xiàng)式.

3.8 形如axpm+bx+h(xpm±x)的完全置換多項(xiàng)式

命題 3[8]令f(x)=axpm+bx+h(xpm+x) 且 (a,b)∈Λ, 其中 Λ 見命題2.若滿足下面任一條件:

(1)h(x)=u(x)pms?u(x)s, 其中u(x) ∈ Fp2m[x];

則f(x) 是Fp2m上的完全置換多項(xiàng)式.

在命題3 的條件(3)中取c= 1,p= 2, 所構(gòu)造完全置換多項(xiàng)式與定理40 的結(jié)論有交叉.若在定理40 中添加條件a=0,b=0, 則命題3 包含了定理40 中的完全置換, 故命題3 部分推廣了定理40.

最近, 文獻(xiàn) [89]研究了形如 (xpm?x+δ)s+axpm+bx的完全置換多項(xiàng)式.與文獻(xiàn) [8]中類似形式完全置換多項(xiàng)式不同的是此處不需要a,b同時(shí)不等于0.文獻(xiàn)[89]通過(guò)確定一些相關(guān)方程解的個(gè)數(shù), 給出了有限域Fpn上8 類形如 (xpm?x+δ)s+bx的完全置換多項(xiàng)式.對(duì)于指數(shù)s=i(pm±1)+pj, 給出了Fp2m上幾類形如(xpm?x+δ)s+axpm+bx的完全置換多項(xiàng)式.當(dāng)指數(shù)滿足條件s=i(2m?1)+1 時(shí),所用的主要證明方法是將F22m上方程解的判斷轉(zhuǎn)化為單位圈上方程解的個(gè)數(shù)判斷問(wèn)題, 此處的證明思想來(lái)源于文獻(xiàn)[90].當(dāng)指數(shù)為s=i(2m+1)+2j或s=i(3m?1)+3j時(shí), 采用的證明方法是通過(guò)AGW 準(zhǔn)則將 Fp2m上方程解的判斷轉(zhuǎn)化為子域或子集上線性化方程解的判斷.文獻(xiàn) [89]不僅得到了大量完全置換多項(xiàng)式, 還推廣了類似形式置換多項(xiàng)式的已有結(jié)論, 部分結(jié)果見表4.

表4 有限域Fpn 上形如(xpm ?x+δ)s +axpm +bx 的一些完全置換多項(xiàng)式Table 4 Some CPPs (xpm ? x+ δ)s +axpm +bx over Fpn

4 完全置換多項(xiàng)式的圈結(jié)構(gòu)

與完全置換相關(guān)的一個(gè)問(wèn)題是確定其圈結(jié)構(gòu).但由于缺乏有效的研究工具, 完全置換圈結(jié)構(gòu)的研究進(jìn)展十分緩慢, 人們主要考慮上最大線性完全置換的構(gòu)造以及刻畫.

首先給出圈結(jié)構(gòu)的定義.

定義 3[28]一個(gè)置換的輪換表示中各輪換長(zhǎng)度及其個(gè)數(shù)稱為置換的圈結(jié)構(gòu), 記為 {ki× 1,k2×2,··· ,ki×i,···}, 其中ki×i說(shuō)明該置換的輪換表示中有ki個(gè)長(zhǎng)度為i的輪換.

定理 44[28]上完全置換的圈結(jié)構(gòu)為 {1 × 1,0 × 2,··· ,0 × (2n? 3),0 × (2n? 2),···}, 即有且僅有一個(gè)不動(dòng)點(diǎn)并且不存在長(zhǎng)度為2, 2n?3, 2n?2 以及2n的輪換.

若Fn2上完全置換的圈結(jié)構(gòu)為 {1×1,1×(2n?1)} 則稱其為上的最大完全置換.完全置換圈結(jié)構(gòu)的一個(gè)重要問(wèn)題是最大完全置換的構(gòu)造.Mittenthal[3]最早給出了最大線性完全置換與線性反饋移位寄存器之間的關(guān)系.

定理 45[3]F2n中最大線性完全置換的生成函數(shù)對(duì)應(yīng)于n級(jí)極大長(zhǎng)度線性反饋移位寄存器的生成函數(shù).

另外, Golomb、Gong 和Mittenthal[4]根據(jù)向量空間與有限域 F2n的對(duì)應(yīng)關(guān)系, 給出了 F2n上最大線性完全置換的代數(shù)構(gòu)造法.

定理 46[4]取F2n的本原元α,令正整數(shù)s滿足且gcd(s, 2n?1)=1.若f(x)=αsx,則f(x) 是F2n上的最大線性完全置換多項(xiàng)式.

據(jù)此定理, 文獻(xiàn)[4]從矩陣變換和m序列出發(fā)給出了上最大線性完全置換的兩種實(shí)現(xiàn)算法.

在尋找最大非線性完全置換構(gòu)造方法的過(guò)程中, Mittenthal[10]指出最大非線性完全置換與線性完全置換之間存在如下關(guān)系.

定理 47[10]任一最大非線性完全置換可以通過(guò)構(gòu)造性腐化由線性完全置換導(dǎo)出.

非常遺憾的是我們僅能從例子上看出從最大線性完全置換出發(fā)通過(guò)構(gòu)造性腐化可以得到最大非線性完全置換, 但是專利[10]并沒(méi)有給出通用的具體算法.如果能構(gòu)造出無(wú)限類最大非線性完全置換將是完全置換圈結(jié)構(gòu)研究的突破性進(jìn)展.

此外, 文獻(xiàn) [19]在定理38 的基礎(chǔ)上構(gòu)造了一類 Fpn上不含不動(dòng)點(diǎn)的完全置換多項(xiàng)式, 并指出其圈結(jié)構(gòu)中包含短圈但并沒(méi)有完全確定其圈結(jié)構(gòu).根據(jù)共軛的置換具有相同的圈結(jié)構(gòu), 文獻(xiàn) [64]指出定理26 所構(gòu)造完全置換多項(xiàng)式g1,a(x) 的圈結(jié)構(gòu)為pn?1?p, 即有pn?1個(gè)長(zhǎng)度為p的圈.

5 完全置換多項(xiàng)式的代數(shù)次數(shù)

在密碼應(yīng)用中, 通常希望使用的完全置換多項(xiàng)式具有高的代數(shù)次數(shù)從而能夠抵抗已有的一些攻擊.但是完全置換的相關(guān)文獻(xiàn)重點(diǎn)考慮其構(gòu)造與計(jì)數(shù), 代數(shù)次數(shù)等密碼學(xué)性質(zhì)討論得很少.

Niederreiter、Robinson 和Wan 在文獻(xiàn) [1,93]中討論了 Fpn上完全置換多項(xiàng)式的約化次數(shù).

定理 48[1,93]當(dāng)pn>3 時(shí), Fpn上任一完全置換多項(xiàng)式的約化次數(shù)不超過(guò)pn?3.

當(dāng)pn>3 時(shí), 由代數(shù)次數(shù)的定義以及定理48 知Fpn上任一完全置換多項(xiàng)式的代數(shù)次數(shù)最多為n(p?1)?1.

另外, 文獻(xiàn) [6]討論了由Feistel 和MISTY 結(jié)構(gòu)所構(gòu)造完全置換的代數(shù)次數(shù).很容易看出定理12 給出的上完全置換多項(xiàng)式 ?p, Φp和Ψp的代數(shù)次數(shù)不超過(guò)m(p?1)?1.文獻(xiàn)[6]中其余完全置換多項(xiàng)式的代數(shù)次數(shù)主要取決于函數(shù)F(x)=p2(p1(x1)+x2), 下面給出F(x) 的代數(shù)次數(shù)與p1,p2的關(guān)系.

命題 4[6]令q=pm其中p是素?cái)?shù)且m是正整數(shù).取 Fq[z]/(zq?z) 上的多項(xiàng)式p1(z),p2(z) 和笛卡爾積到有限域 Fq的函數(shù)F(x)=p2(p1(x1)+x2), 其中則特別地, 若p1(z),p2(z) 是 Fq上的置換多項(xiàng)式, 則F(x) 的代數(shù)次數(shù)不超過(guò) 2m(p?1)?3.

根據(jù)命題4, 文獻(xiàn) [6]中2 輪構(gòu)造和大部分3 輪構(gòu)造所得上完全置換多項(xiàng)式的代數(shù)次數(shù)都小于等于 2m?3.并且, 當(dāng)n=2 時(shí), 定理18 中完全置換多項(xiàng)式G(x) 的代數(shù)次數(shù)不超過(guò) 2m(p?1)?3[6].此外, 文獻(xiàn)[6]還給出了如下具有幾乎最優(yōu)代數(shù)次數(shù)的完全置多項(xiàng)式.

定理 49[6]令q=pm, 取 Fq[z]中多項(xiàng)式p1(z)=p2(z)=zq?2.若p=2, 則下列完全置換多項(xiàng)式

的代數(shù)次數(shù)都是2m?3;若p是奇素?cái)?shù),當(dāng)n=2 時(shí),定理18 中完全置換G(x)的代數(shù)次數(shù)為2m(p?1)?3.

值得注意的是, 通過(guò)選取合適的多項(xiàng)式pi(z)(i= 1,2,3), 3 輪構(gòu)造中有四個(gè)上完全置換多項(xiàng)式的代數(shù)次數(shù)可以達(dá)到2m?2[6].

此外, 文獻(xiàn)[60]討論了偶特征有限域上一些完全置換多項(xiàng)式的代數(shù)次數(shù), 部分結(jié)論列舉如下:

(1) 定理20 中取s=2,p=2,得到的F2n1+n2上完全置換多項(xiàng)式的代數(shù)次數(shù)不超過(guò)max{n1,n2}?1;

(2) 定理21 給出的F2m+n上完全置換多項(xiàng)式的代數(shù)次數(shù)不超過(guò)max{m,n};

(3) 定理19 和定理22 所構(gòu)造的F2n上完全置換多項(xiàng)式的代數(shù)次數(shù)不超過(guò)n?2;

(4) 定理23 中F2n上完全置換多項(xiàng)式的代數(shù)次數(shù)達(dá)到最大值n?1.

據(jù)我們所知, 目前僅有文獻(xiàn)[60]中給出的無(wú)限類完全置換多項(xiàng)式具有最優(yōu)的代數(shù)次數(shù), 因而需要探索出新的方法來(lái)構(gòu)造更多易于實(shí)現(xiàn)且代數(shù)次數(shù)達(dá)到最優(yōu)的完全置換多項(xiàng)式.

6 廣義完全置換多項(xiàng)式

本節(jié)介紹幾類與完全置換多項(xiàng)式相關(guān)的特殊置換多項(xiàng)式, 包含強(qiáng)完全置換多項(xiàng)式、K-完全置換多項(xiàng)式以及b-完全置換多項(xiàng)式, 這幾類置換多項(xiàng)式統(tǒng)稱為廣義完全置換多項(xiàng)式.

令f(x) ∈ Fpm[x], 若f(x),f(x)+x和f(x)?x均是 Fpm上的置換多項(xiàng)式, 則稱f(x) 為 Fpm上的強(qiáng)完全置換多項(xiàng)式[94].Evans[94]對(duì)有限群上強(qiáng)完全置換的存在性進(jìn)行了綜述.

Shaheen 和 Winterhof[27]研究了形如

隨后, Winterhof[84]將幾類特殊置換進(jìn)行統(tǒng)一, 提出了K-完全置換的定義.

定義 4[84]令f(x) 是Fpm上的置換, 符號(hào)f(k)(x) 表示f(x) 的k次合成.取若干正整數(shù)所構(gòu)成的集合K={k1,k2,··· ,ks}, 若FK(x)=x+ ∑k∈Kf(k)(x) 是 Fpm上的置換多項(xiàng)式, 則稱f(x) 為 Fpm上的K-完全置換多項(xiàng)式.當(dāng)K={1,2,··· ,k?1}(k?2)時(shí), 稱K-完全置換多項(xiàng)式為k-強(qiáng)完全置換多項(xiàng)式.

K-正形置換的定義可以類似給出.顯然, {1}-完全置換就是通常意義下的完全置換多項(xiàng)式.文獻(xiàn)[27]中的置換既是{2}-完全置換又是{2}-正形置換.

Winterhof[84]給出了類似于定理31 的K-完全置換多項(xiàng)式的基本構(gòu)造方法, 研究了某些線性化多項(xiàng)式和2 階分圓多項(xiàng)式的K-完全置換性質(zhì).K-正形置換的相關(guān)內(nèi)容可參閱文獻(xiàn)[30,84,95–97].

此外, 文獻(xiàn)[38]和文獻(xiàn)[98]分別提出了b-完全置換多項(xiàng)式(b-complete permutation polynomial)和b-完全(b-complete)的概念.

定義 5取 Fpm上的多項(xiàng)式f(x), 令

(1) 若f(x) 和f(x)+bx都是 Fpm上的置換多項(xiàng)式, 則稱f(x) 為 Fpm上的b-完全置換多項(xiàng)式[38].

(2) 若f(x) 和bf(x)+x都是 Fpm上的置換多項(xiàng)式, 則稱f(x) 為b-完全的[98].

根據(jù)定義5, 完全置換多項(xiàng)式即為 1-完全置換多項(xiàng)式, 亦可稱相應(yīng)的置換多項(xiàng)式是 1-完全的.顯然,f(x) 是 Fpm上的b-完全置換多項(xiàng)式當(dāng)且僅當(dāng)b?1f(x) 是 Fpm上的完全置換多項(xiàng)式[38].另外, Fpm上多項(xiàng)式f(x) 是b-完全的等價(jià)于bf(x) 是Fpm上的完全置換多項(xiàng)式[98].

除了b-完全置換多項(xiàng)式, 廣義完全置換多項(xiàng)式的研究主要集中在分圓多項(xiàng)式和線性化多項(xiàng)式, 且已知結(jié)論不多.鑒于廣義完全置換多項(xiàng)式在校驗(yàn)位系統(tǒng)中的應(yīng)用, 其構(gòu)造研究尚需深入.

7 總結(jié)

本文對(duì)完全置換多項(xiàng)式的相關(guān)理論進(jìn)行了綜述, 包含完全置換的存在性、完全置換多項(xiàng)式的構(gòu)造、代數(shù)次數(shù)、圈結(jié)構(gòu)以及廣義完全置換多項(xiàng)式.雖然近二十多年來(lái)人們?cè)谕耆脫Q多項(xiàng)式的構(gòu)造方面進(jìn)行了深入地研究, 已取得了豐富的成果, 但僅有少數(shù)的完全置換多項(xiàng)式具有最優(yōu)或幾乎最優(yōu)的代數(shù)次數(shù), 且它們的圈結(jié)構(gòu)等其它密碼學(xué)性質(zhì)鮮有人研究.另外, 完全置換的存在性和廣義完全置換多項(xiàng)式這兩方面的研究成果較少, 還沒(méi)有引起足夠地關(guān)注.總而言之, 完全置換多項(xiàng)式在分組密碼、校驗(yàn)位系統(tǒng)以及組合設(shè)計(jì)等方面的理論和應(yīng)用研究還需深入, 尚存在大量值得繼續(xù)研究的問(wèn)題, 比如:

研究問(wèn)題1: 構(gòu)造易于實(shí)現(xiàn)且具有最優(yōu)代數(shù)次數(shù)的完全置換多項(xiàng)式.

研究問(wèn)題2: 構(gòu)造最大非線性完全置換多項(xiàng)式.

研究問(wèn)題3: 分析并確定某些完全置換多項(xiàng)式的圈結(jié)構(gòu).

研究問(wèn)題4: 分析并構(gòu)造具有高非線性度、低差分等良好密碼學(xué)性質(zhì)的完全置換多項(xiàng)式.

研究問(wèn)題5: 選取合適的完全置換多項(xiàng)式并將其用于密碼系統(tǒng)的設(shè)計(jì).