完全置換多項式的研究進展*

許小芳, 曾祥勇, 徐運閣

湖北大學數(shù)學與統(tǒng)計學學院應用數(shù)學湖北省重點實驗室, 武漢430062

完全置換多項式專欄

1 引言

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

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

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

2 完全置換多項式的存在性

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

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

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

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

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

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

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

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

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

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

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

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

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

(1) 當r=0,1 時,f(x) 不是 F2n上的完全置換多項式;

(2) 當 1

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

(1) 當r=0,1 時, 必有a2d?1=0;

(2) 當 1

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

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

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

定理 7[1]設q是素數(shù)的方冪, 則

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

定理 8[28]設p是任一素數(shù), 令p(z) 為有限域 Fpm上的置換多項式.則的映射

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

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

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

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

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

當a=b=c=0 時, ?a,b,c,p就退化為定理8 中的完全置換 ?p.顯然, ?a,b,c,p仿射等價于 ?p.

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

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

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

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

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

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

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

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

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

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

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

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

定理 17[6]取有限域 Fpm上的多項式p1(z),p2(z),p3(z), 其中p2(z) 是置換多項式.若對任意的γ∈Fpm,多項式p1(z)?p3(z+γ)是 Fpm上的置換,則多項式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)所對應的映射 ?p關(guān)系密切.另外, 定理17 的第一個條件并不容易滿足.當p3(x) 為線性化多項式時, 可以找到大量滿足該條件的p1(x).當p1(x),p3(x) 都不是線性化多項式時, 文獻[6]給出了滿足該條件的單項式p1(x),p3(x).

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

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

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

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

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

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

通過選取特殊的布爾函數(shù)組(或完全置換的坐標分量函數(shù))可以有效地進行上完全置換的構(gòu)造.馮登國和劉振華在文獻[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]取上的完全置換多項式fi(xi), 則F(x1,x2,··· ,xs) = (f1(x1),f2(x2),··· ,fs(xs))是上的完全置換.

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

定理 21[54]設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]設P1=(g1,g2,··· ,gn?2),P2=(h1,h2,··· ,hn?2) 為上的完全置換, 令

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

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

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

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

本節(jié)所討論的完全置換大多數(shù)是用坐標分量形式來表示的, 主要通過證明坐標分量函數(shù)的所有非零線性組合是平衡函數(shù)來說明其置換性.它們一般都具有簡潔的分量表達式, 但在Fpn上的單變元表達式非常復雜.

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

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

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

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

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

最近, 文獻[63]利用Dickson 多項式的合成逆給出了兩個特殊完全置換多項式.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

是F2mn上的完全置換.

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

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

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

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

此外, 文獻[71]運用AGW 準則給出了由子域上置換來構(gòu)造擴域上完全置換的遞歸構(gòu)造.

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

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

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

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

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

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

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

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

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

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

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

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

另外, 文獻[8]通過AGW 準則給出了由域F2m上完全置換二項式來構(gòu)造其擴域上完全置換的遞歸構(gòu)造.

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

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

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

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

是Fpn上的完全置換多項式當且僅當L(x) 是Fpn上的完全置換多項式.

作為定理37 的應用, 給出如下推論.

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

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

是Fpn上的完全置換多項式當且僅當L(x) 是Fpn上的完全置換多項式.

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

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

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

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

3.6 完全置換多項式的合成逆

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

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

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

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

3.7 稀疏型完全置換多項式

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

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

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

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

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

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

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

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

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

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

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

命題 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上的完全置換多項式.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

6 廣義完全置換多項式

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

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

Shaheen 和 Winterhof[27]研究了形如

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

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

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

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

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

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

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

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

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

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

7 總結(jié)

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

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

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

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

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

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