完全置換多項(xiàng)式的研究進(jìn)展*

許小芳, 曾祥勇, 徐運(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ù)語在偶特征有限域上是一致的.對(duì)于偶特征有限域, 早期的一些文獻(xiàn)采用“正形置換多項(xiàng)式” 這個(gè)名稱[3–5], 近年來主要使用術(shù)語“完全置換多項(xiàng)式”[6–8], 所以本文采用名稱“完全置換多項(xiàng)式”.本文主要關(guān)注有限域Fpm或向量空間Fmp上完全置換多項(xiàng)式(或稱為完全置換)的相關(guān)理論研究.

完全置換多項(xiàng)式的研究由來已久, 其概念是Mann 在1942 年構(gòu)造正交拉丁方時(shí)提出的[9].有限域上完全置換多項(xiàng)式的詳細(xì)研究始于Niederreiter 和Robinson[1], 其應(yīng)用非常廣泛, 特別是在密碼學(xué)領(lǐng)域.1995 年, 美國Teledyne 電子技術(shù)公司Mittenthal 首次利用偶特征域上完全置換多項(xiàng)式來設(shè)計(jì)非線性動(dòng)力替換裝置并構(gòu)造密碼算法[3,10].隨后, Vaudenay 證明了添加完全置換的Lai-Massey 結(jié)構(gòu)具有更好的偽隨機(jī)性[11].人們還利用完全置換多項(xiàng)式來設(shè)計(jì)對(duì)稱密碼中的S 盒[12]、流密碼Loiss[13]、Hash 函數(shù)[14,15]、擬群[16–18]以及構(gòu)造具有良好密碼學(xué)性質(zhì)的密碼函數(shù)[19–22].此外, 基于完全置換所構(gòu)造的分組密碼算法SMS4 是我國第一個(gè)商用分組密碼標(biāo)準(zhǔn), 且被推薦用于無線局域網(wǎng)WAPI 中[23,24].在組合數(shù)學(xué)領(lǐng)域,完全置換多項(xiàng)式與正交拉丁方……