查正邦, 胡 磊

1.洛陽師范學院數(shù)學科學學院河南省大數(shù)據(jù)處理與分析重點實驗室, 洛陽471934

2.中國科學院信息工程研究所信息安全國家重點實驗室, 北京100093

3.中國科學院大學網(wǎng)絡(luò)空間安全學院, 北京100049

完全置換多項式專欄

1 引言

設(shè)p為素數(shù),n為正整數(shù), Fpn表示含有pn個元素的有限域.定義在有限域上的映射都可以表示成一個單變量或多變量的多項式函數(shù).令f(x) 表示映射f: Fpn?→Fpn.若f(x) 是一個一一映射, 則稱f(x) 是 Fpn上的置換多項式.置換多項式是有限域的重要理論和工具, 它在數(shù)學理論和工程應用等領(lǐng)域均有重要的應用.關(guān)于置換多項式的研究進展, 請參考文獻 [1–10].若f(x) 和f(x)+x均為 Fpn上的置換多項式, 則稱f(x) 是Fpn上的完全置換[11].完全置換的復合逆仍為完全置換, 由于它特殊的置換性質(zhì), 完全置換逐漸成為密碼學、編碼理論、組合設(shè)計等領(lǐng)域中的一個熱點問題.

1942 年, Mann 首次給出了完全置換的定義并將其用于構(gòu)造正交拉丁方[11].Niederreiter 和Robinson[12]進一步研究了有限域上的完全置換, 分析了它們在密碼學中的應用.受此影響, 有限域上的完全置換在密碼算法設(shè)計中被充分應用.由于缺乏有效的完全置換判定法則, 已知的完全置換較少.為了滿足密碼算法設(shè)計、編碼設(shè)計和組合設(shè)計的研究需要, 國內(nèi)外學者相繼開展了有限域特別是偶特征有限域上的完全置換的構(gòu)造和應用研究.Laigle-Chapuy 構(gòu)造了新的完全置換, 并給出了他們在編碼理論中的應用[13].Charpin 和 Kyureghyan 利用完全置換設(shè)計了新的 Bent 函數(shù)[14].Tu、Zeng 和 Hu 通過確定有限域上特殊方程的解給出了偶特征域上三類單項式完全置換和一類三項式完全置換[15].在此基礎(chǔ)上, Wu、Li、Helleseth 和 Zhang 給出了偶特征域上更多的單項式完全置換[16].Wu 和 Lin 給出了特征為 2 的有限域上完全置換的一種遞歸構(gòu)造, 通過計算已知完全置換的復合逆來構(gòu)造新的完全置換[17].Xu、Feng 和Zeng 刻畫了 Fpn上形如 (xpm?x+δ)s+axpm+bx的完全置換[18].關(guān)于完全置換的更多研究進展請參考論文[19–25]及文內(nèi)的參考文獻.

本文分別研究了有限域上兩種不同類型的多項式的置換性質(zhì), 通過已知置換來證明新的置換, 進而發(fā)現(xiàn)和構(gòu)造完全置換.第2 節(jié)介紹預備知識; 第3 節(jié)給出六類形如的置換多項式, 證實了其中三類為完全置換; 第4 節(jié)介紹了形如xh(xs) 的二項式的置換性質(zhì), 進而得到完全置換的相關(guān)構(gòu)造; 第5 節(jié)總結(jié).

2 預備知識

在本文中, 令p為素數(shù),n,m,q,d為正整數(shù)且滿足q=pm和d| (qn?1).用表示有限域 Fq的乘法群, Fqn[x]表示Fqn上的多項式環(huán).定義有限域Fqn到Fq上的跡函數(shù)為

記有限域 Fqn上的d次單位根的集合為μd且有

對于θ∈ F?q, 定義 Fq上的 Dickson 多項式為

若有限域Fq的特征為2, 通過簡單計算可得下列Dickson 多項式

兩個置換多項式之間的quasi-multiplicative (簡記為QM) 等價關(guān)系定義如下:

定義 1[26]設(shè)q是素數(shù)p的方冪,f(x),g(x)∈Fq[x]是 Fq上的置換多項式.如果存在和正整數(shù)使得 gcd(d,q?1) = 1 和f(x) =ag(cxd), 則稱多項式f(x) 和g(x) 是 QM 等價的.

下面我們給出三個已知的置換判定法則, 它們將在后面的證明中用到.

引理 1[27]令Dickson 多項式gi(x,θ) 是 Fq上的置換當且僅當 gcd(i,q2? 1)=1.

引理 2[28,29]設(shè)r和d為正整數(shù)滿足d| (qn?1).令h(x) ∈ Fq[x], 則f(x) =xrh(x(qn?1)/d) 是有限域 Fqn上的置換當且僅當下列條件成立: (i) gcd(r,(qn?1)/d) = 1; (ii)xrh(x)(qn?1)/d是μd上的置換.

引理 3[30]設(shè)q為素數(shù)的方冪,i,n為正整數(shù)且有a∈Fqn.線性多項式g(x)=xpi+ax是 Fqn上的置換當且僅當a=0 或者 ?a不是中的pi?1 次方冪.

受文獻 [31,32]的啟發(fā), 在本節(jié)中我們利用線性置換和 Dickson 置換構(gòu)造了 Fqn上六類形如γx+的置換, 其中三類被證實為完全置換.此外, 我們分析了剩余三類置換不是完全置換的原因.首先, 我們利用跡函數(shù)構(gòu)造出下列完全置換.

定理 1設(shè)q是素數(shù)的方冪且有q> 2.令n和k為正整數(shù)滿足且令γ∈Fq{0,?1},則是 Fqn上的完全置換.

證明:對于任意的b∈Fqn, 我們考慮方程

的解.將方程(1)的兩邊同時取q次冪, 再與原方程相減可得γqxq?γx=bq?b.已知γ∈Fq{0,?1},可以推出xq=x+cq?c, 這里c=γ?1b.由xq=x+cq?c可得xq2=xq+cq2?cq=x+cq2?c, 進而遞推得到xqk=x+cqk?c.將其代入(1)并利用作適當替換可得

由γ∈Fq{0,?1} 可得γ+1 ∈Fq{0}, 所以f(x)+x也是 Fqn上的置換.根據(jù)完全置換的定義可得出結(jié)論:f(x) 是Fqn上的完全置換.

定理 2設(shè)q是素數(shù)p的方冪且有q> 2.令n,k,l,i為正整數(shù)滿足 1l

證明:與定理1 的證明類似, 我們需證方程

對于任意的b∈Fqn均只有一個解.令c=γ?1b, 由上面的方程可得xq=x+cq?c, 進而可推出

于是可得

不難發(fā)現(xiàn), 上面的方程有且只有一個解.由此可推出f(x) 是Fqn上的置換.

由γ∈Fq{0,?1} 可得γ+1 ∈Fq{0}, 所以f(x)+x也是 Fqn上的置換.根據(jù)完全置換的定義可得出結(jié)論:f(x) 是Fqn上的完全置換.定理 3令n,m,q為正整數(shù),p為素數(shù)且有q=pm.設(shè)對于令γi∈ Fqn使得若g(x) 是Fq上的置換, 則f(x) 是 Fqn上的置換.特別地, 若g(x) 是 Fq上的完全置換且則f(x) 是 Fqn上的完全置換.

證明:對于任意的b∈Fqn, 我們考慮方程

的解.已知a0∈ Fq且有由方程(2)可得xq=x+cq?c, 其中令t=x?c, 不難驗證tq=t.不失一般性, 對于任一個有

于是, 方程(2)可化為

若g(x) 是 Fq上的置換, 上式只有一個解t, 對應得到x的一個解.因此,f(x) 是 Fqn上的置換.

若g(x)是 Fq上的完全置換且則g(x)和g(x)+x均為 Fq上的置換且滿足a0,a0+1 =0.同上我們可以得出:f(x) 和f(x)+x都是Fqn上的置換.也就是說,f(x) 是Fqn上的完全置換.

需要指出的是: 在定理3 中, 若 Fq上兩個線性置換g1(x) 和g2(x) 是 QM 等價的, 則在 Fqn中對應生成的線性置換f1(x) 和f2(x) 也是 QM 等價的.下面我們利用 Fq上不同的 Dickson 置換分別構(gòu)造出三類定義在Fq3上的置換.

定理 4設(shè)m為奇數(shù)且有q=2m.令則是 Fq3上的置換.

證明:要證是 Fq3上的置換, 我們需證方程

對于任意的b∈Fqn均只有一個解.令c=γ?2b.已知由上面的方程可得

和xq2=x+cq2+c.計算可得

令t=x+cq2+cq.由(3)可得tq=t, 則有

已知m為奇數(shù)且有q= 2m, 則有 gcd(5,q2?1) = 1.由引理1 可知:g5(t,γ) 是 Fq上的置換.因此, 上式只有一個解t, 由此可得到一個唯一解x.故是 Fq3上的置換.

定理 5設(shè)m為正整數(shù)滿足且有則是 Fq3上的置換.

證明:與定理4 的證明類似, 我們需證方程

對于任意的b∈ Fqn均只有一個解.令c=γ?3b.已知由上面的方程可得xq=x+cq+c和xq2=x+cq2+c.計算可得

令t=x+cq2+cq.由xq=x+cq+c可得tq=t, 則有

定理 6設(shè)m為正整數(shù)滿足且有q= 2m.令則是 Fq3上的置換.

證明:要證f(x) 是Fq3上的置換, 只需證明方程

對于任意的b∈ Fqn均只有一個解.令c=γ?5b.已知γ∈ F?q, 由上面的方程可得xq=x+cq+c和xq2=x+cq2+c.計算可得

令t=x+cq2+cq.由xq=x+cq+c可得tq=t, 則有

其中 ?(γ,c) 是以γ,c為變量的函數(shù).也就是說, 對于給定的值γ和b, ?(γ,c) 為一個常量.已知m≡0 mod 5 且有q=2m,容易驗證 gcd(11,q2?1)=1.根據(jù)引理1 可得:g11(t,γ)=t11+γt9+γ3t5+γ4t3+γ5t是Fq上的置換.因此, 上式只有一個解t, 由此可得到一個唯一解x.故f(x) 是Fq3上的置換.

定理4,5,6 中的置換是分別依據(jù) Fq上的 Dickson 置換g5(t,γ),g7(t,γ) 和g11(t,γ) 構(gòu)造而來.對于Fq上其它的 Dickson 置換gi(t,γ) (i>11), 我們可以用同樣的方法構(gòu)造 Fq3上形如γx+Trq3q(h(x)) 的置換.需要指出的是: 由于γ∈Fq上的 Dickson 置換不是完全置換, 因而利用該方法構(gòu)造出的置換也不是完全置換.

4 xh(xs)型完全置換

在本節(jié)中, 我們應用引理2, 確定了有限域Fqn上形如的二項式的置換性質(zhì).根據(jù)這些置換性質(zhì), 我們得到一些xh(xs) 型完全置換.

定理 7設(shè)i,k為正整數(shù),q為素數(shù)的方冪.令γ∈Fq2, 則是 Fq2k上的置換當且僅當x(xi+γ)k(q?1)是μq+1上的置換.

證明:容易驗證記h(x) =xi+γ, 由引理2 可得:f(x) 是Fq2k上的置換當且僅當是μq+1上的置換.已知γ∈ Fq2且μq+1?Fq2, 對于任意的x∈μq+1有xi+γ∈ Fq2.由此可推出

故,f(x) 是 Fq2k上的置換當且僅當x(xi+γ)k(q?1)是μq+1上的置換.

推論 1設(shè)i,k為正整數(shù),q> 2 為素數(shù)的方冪且滿足 (q+ 1) |k.令γ∈ Fq{?1,?2}, 則是 Fq2k上的完全置換.

證明:已知γ∈ Fq{?1,?2} 且μq+1∩Fq= {1}, 對于任意的x∈μq+1可以驗證xi+γ= 0 和xi+γ+10.由于xi+γ∈ Fq2而 (q+1)|k, 所以x(xi+γ)k(q?1)=x.x顯然是μq+1上的置換, 于是由定理7 可得是 Fq2k上的置換.同理可證也是Fq2k上的置換.因此,f(x) 是Fq2k上的完全置換.

推論 2設(shè)i,j,k,m,q為正整數(shù)且滿足i= 22m?j,k= 2j,q= 2m和q> 2.令γ∈ Fq{0,1}, 則是 Fq2k上的完全置換.

證明:已知γ∈ Fq{0,1}, 則γ+ 1 ∈ Fq{0,1}.對于任意的x∈μq+1有xi+γ= 0 和xi+γ+1 =0, 且有xq2=x.與推論1 的證明類似, 我們只需證x(xi+γ)k(q?1)是μq+1上的置換.

由已知條件i=22m?j和k=2j可得

對于任意的b∈μq+1, 方程可化為

定理 8設(shè)n,i,k,m為正整數(shù),p為素數(shù)且設(shè)q=pm.令若滿足 (i)n|(q? 1); 或 (ii)n=pk且i=q?pm?k, 則是 Fqn上的置換.

證明:已知則對于任意的x∈ Fq恒有由引理 2 容易推出:是 Fqn上的置換當且僅當x(xi+γ)n是 Fq上的置換.下面我們將分別證明x(xi+γ)n恰為 Fq上的置換.

(1) 若n|(q? 1), 由可得x(xi+γ)n=x, 它顯然是 Fq上的置換.

(2) 若n=pk且i=q?pm?k, 則x(xi+γ)n=xpk+γpkx.由可推出 ?γ在 Fq中不是一個i次冪.也就是說, ?γpk在 Fq中不是一個pk?1 次冪.由引理3 可推出,xpk+γpkx是Fq上的一個線性置換.

推論 3設(shè)n,k為正整數(shù),q=22k且滿足和n|(q?1).令ω∈ Fq{1} 使得ω3=1,則是 Fqn上的完全置換.

證明:已知q=22k且有則q? 1≡0 mod 3 但由ω3=1 和可得ω+1=ω2, 不難驗證ω和ω2均不是 Fq中的三次方冪.運用定理8 可得:和都是 Fqn上的置換, 即:f(x) 是 Fq2k上的完全置換.

5 結(jié)論

本文研究了有限域Fqn上幾類多項式的置換性質(zhì).利用 Fq上的線性置換和Dickson 置換對應構(gòu)造出 Fqn上六類形如的置換, 進而得到 Fqn上三類新的完全置換.給出了Fqn上二項式γx+xs+1是置換的幾個充分條件, 由此得到一些形如xh(xs) 的完全置換.只要選取Fq上適當?shù)耐耆脫Q, 根據(jù)本文的方法可有效的構(gòu)造Fqn上的完全置換.