李麗莎, 曾祥勇, 曹喜望

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

2.南京航空航天大學(xué)理學(xué)院, 南京211106

3.信息安全國(guó)家重點(diǎn)實(shí)驗(yàn)室, 北京100039

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

1 引言

設(shè)q是素?cái)?shù)的方冪, Fq表示包含q個(gè)元素的有限域, 并且 Fq[x]是 Fq上的多項(xiàng)式環(huán).如果映射f是從 Fq到其自身的雙射, 那么稱f(x) 是 Fq上的置換多項(xiàng)式[1].若f(x) 和f(x)+x均為 Fq上的置換多項(xiàng)式, 則稱f(x) 是Fq上的完全置換多項(xiàng)式[2].近年來(lái), 完全置換多項(xiàng)式在密碼學(xué)、編碼學(xué)和組合數(shù)學(xué)中得到了廣泛應(yīng)用[3].例如 bent 函數(shù)的構(gòu)造[4–6], Hash 函數(shù)的設(shè)計(jì)[7,8], 分組密碼中SMS4 密碼算法的設(shè)計(jì)[9]等.因此對(duì)其構(gòu)造的研究成為一個(gè)熱門問(wèn)題.

完全置換多項(xiàng)式的研究可以追溯到20 世紀(jì)中期.1942 年, Mann 構(gòu)造正交拉丁方時(shí)提出了完全置換多項(xiàng)式的概念[2].在此基礎(chǔ)上, Niederreiter 和Robinson 具體研究了有限域上的完全置換多項(xiàng)式[10].由于判斷一個(gè)多項(xiàng)式的完全置換性質(zhì)十分困難, 所以到目前為止, 已知的完全置換多項(xiàng)式類依然很有限, 尤其是具有顯式表達(dá)的完全置換多項(xiàng)式.其早期結(jié)果很少, 只有兩類 Dickson 多項(xiàng)式[11], 有限域 F16上所有完全置換二項(xiàng)式和三項(xiàng)式[12], 以及形如的完全置換單項(xiàng)式[13–15], 其中并且k|q? 1.2014 年, Tu、Zeng 和Hu 提出了用加法特征和極坐標(biāo)表示的方法來(lái)將完全置換多項(xiàng)式的問(wèn)題轉(zhuǎn)化成有限域上特殊方程解的問(wèn)題[16].受到其啟發(fā), 完全置換多項(xiàng)式的構(gòu)造得到了進(jìn)一步發(fā)展[17–23].近些年, 形如(xpm?x+δ)s+L(x) 的置換多項(xiàng)式吸引了人們的注意, 其中L(x) 是線性化多項(xiàng)式.文獻(xiàn)[24,25]研究了這類多項(xiàng)式的完全置換性質(zhì), 并通過(guò)AGW 準(zhǔn)則, 將有限域上多項(xiàng)式的完全置換問(wèn)題轉(zhuǎn)化為特殊方程在其子集上解的問(wèn)題, 或是項(xiàng)數(shù)較少多項(xiàng)式的完全置換問(wèn)題, 得到了大量完全置換多項(xiàng)式.除上述構(gòu)造方法外,完全置換多項(xiàng)式的構(gòu)造還包括基于特殊密碼結(jié)構(gòu)和函數(shù)的多變?cè)耆脫Q多項(xiàng)式的構(gòu)造[26–37], 已知完全置換多項(xiàng)式的合成逆[38–40]以及已知完全置換多項(xiàng)式的遞歸構(gòu)造[6,26,41].

有限域Fq2上形如f(x)=xrh(xq?1) 的置換多項(xiàng)式已有豐富的結(jié)論[42], 其中r是正整數(shù), 而其完全置換性質(zhì)卻很少被關(guān)注.本文構(gòu)造了兩類特征 2 有限域 Fq2上形如xh(xq?1)q+1的完全置換多項(xiàng)式.第一類通過(guò)選取h(x) =ax+b, 得到了 Fq2上完全置換三項(xiàng)式, 推廣了文獻(xiàn) [24]中定理 4.此外, 通過(guò)文獻(xiàn) [43]構(gòu)造形如xg(xq?1) 置換多項(xiàng)式的方法, 我們令h(x) =h1(x)+h2(x)y, 其中y=x+xq, 得到了第二類完全置換多項(xiàng)式, 豐富了已有完全置換多項(xiàng)式的構(gòu)造.文中主要利用AGW 準(zhǔn)則, 將證明多項(xiàng)式是完全置換多項(xiàng)式的問(wèn)題轉(zhuǎn)化為證明特殊方程在單位圈U上無(wú)解的問(wèn)題, 進(jìn)而轉(zhuǎn)化成其在有限域 Fq子集上無(wú)解的問(wèn)題.最終通過(guò)低次方程在有限域上無(wú)解的條件以及跡函數(shù)的性質(zhì), 給出了這些多項(xiàng)式是完全置換多項(xiàng)式的充要條件或者充分條件.

2 預(yù)備知識(shí)

在本文中, 我們用F2n表示有 2n個(gè)元素的有限域, 其中n是正整數(shù).令k是正整數(shù)且k|n.定義從有限域F2n到其子域F2k上的跡函數(shù)為

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

4 結(jié)論

本文構(gòu)造了兩類特征2 有限域上形如xh(xq?1)q+1的完全置換多項(xiàng)式.第一類推廣了文獻(xiàn) [24]定理4 中部分結(jié)論.第二類通過(guò)構(gòu)造h(x)=h1(x)+h2(x)y, 其中y=x+xq, 并選取特殊的h1(x),h2(x), 得到了完全置換三項(xiàng)式, 完全置換七項(xiàng)式和其它完全置換多項(xiàng)式, 豐富了已有完全置換多項(xiàng)式的構(gòu)造.