有限域上幾類置換和完全置換*

查正邦, 胡 磊

1.洛陽(yáng)師范學(xué)院數(shù)學(xué)科學(xué)學(xué)院河南省大數(shù)據(jù)處理與分析重點(diǎn)實(shí)驗(yàn)室, 洛陽(yáng)471934

2.中國(guó)科學(xué)院信息工程研究所信息安全國(guó)家重點(diǎn)實(shí)驗(yàn)室, 北京100093

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

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

1 引言

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

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

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

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

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

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

對(duì)于θ∈ F?q, 定義 Fq上的 Dickson 多項(xiàng)式為

若有限域Fq的特征為2, 通過簡(jiǎn)單計(jì)算可得下列Dickson 多項(xiàng)式

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

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

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

引理 1[27]令Dickson 多項(xiàng)式gi(x,θ) 是 Fq上的置換當(dāng)且僅當(dāng) 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上的置換當(dāng)且僅當(dāng)下列條件成立: (i) gcd(r,(qn?1)/d) = 1; (ii)xrh(x)(qn?1)/d是μd上的置換.

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

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

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

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

的解.將方程(1)的兩邊同時(shí)取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, 進(jìn)而遞推得到xqk=x+cqk?c.將其代入(1)并利用作適當(dāng)替換可得

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

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

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

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

于是可得

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

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

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

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

于是, 方程(2)可化為

若g(x) 是 Fq上的置換, 上式只有一個(gè)解t, 對(duì)應(yīng)得到x的一個(gè)解.因此,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上兩個(gè)線性置換g1(x) 和g2(x) 是 QM 等價(jià)的, 則在 Fqn中對(duì)應(yīng)生成的線性置換f1(x) 和f2(x) 也是 QM 等價(jià)的.下面我們利用 Fq上不同的 Dickson 置換分別構(gòu)造出三類定義在Fq3上的置換.

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

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

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

和xq2=x+cq2+c.計(jì)算可得

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

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

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

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

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

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

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

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

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

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

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

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

4 xh(xs)型完全置換

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

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

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

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

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

證明:已知γ∈ Fq{?1,?2} 且μq+1∩Fq= {1}, 對(duì)于任意的x∈μq+1可以驗(yàn)證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}.對(duì)于任意的x∈μq+1有xi+γ= 0 和xi+γ+1 =0, 且有xq2=x.與推論1 的證明類似, 我們只需證x(xi+γ)k(q?1)是μq+1上的置換.

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

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

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

證明:已知?jiǎng)t對(duì)于任意的x∈ Fq恒有由引理 2 容易推出:是 Fqn上的置換當(dāng)且僅當(dāng)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中不是一個(gè)i次冪.也就是說, ?γpk在 Fq中不是一個(gè)pk?1 次冪.由引理3 可推出,xpk+γpkx是Fq上的一個(gè)線性置換.

推論 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, 不難驗(yàn)證ω和ω2均不是 Fq中的三次方冪.運(yùn)用定理8 可得:和都是 Fqn上的置換, 即:f(x) 是 Fq2k上的完全置換.

5 結(jié)論

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