有限域上几类置换和完全置换*

查正邦, 胡 磊

1.洛阳师范学院数学科学学院河南省大数据处理与分析重点实验室, 洛阳471934

2.中国科学院信息工程研究所信息安全国家重点实验室, 北京100093

3.中国科学院大学网络空间安全学院, 北京100049

完全置换多项式专栏

1 引言

设p为素数,n为正整数, Fpn表示含有pn个元素的有限域.定义在有限域上的映射都可以表示成一个单变量或多变量的多项式函数.令f(x) 表示映射f: Fpn−→Fpn.若f(x) 是一个一一映射, 则称f(x) 是 Fpn上的置换多项式.置换多项式是有限域的重要理论和工具, 它在数学理论和工程应用等领域均有重要的应用.关于置换多项式的研究进展, 请参考文献 [1–10].若f(x) 和f(x)+x均为 Fpn上的置换多项式, 则称f(x) 是Fpn上的完全置换[11].完全置换的复合逆仍为完全置换, 由于它特殊的置换性质, 完全置换逐渐成为密码学、编码理论、组合设计等领域中的一个热点问题.

1942 年, Mann 首次给出了完全置换的定义并将其用于构造正交拉丁方[11].Niederreiter 和Robinson[12]进一步研究了有限域上的完全置换, 分析了它们在密码学中的应用.受此影响, 有限域上的完全置换在密码算法设计中被充分应用.由于缺乏有效的完全置换判定法则, 已知的完全置换较少.为了满足密码算法设计、编码设计和组合设计的研究需要, 国内外学者相继开展了有限域特别是偶特征有限域上的完全置换的构造和应用研究.Laigle-Chapuy 构造了新的完全置换, 并给出了他们在编码理论中的应用[13].Charpin 和 Kyureghyan 利用完全置换设计了新的 Bent 函数[14].Tu、Zeng 和 Hu 通过确定有限域上特殊方程的解给出了偶特征域上三类单项式完全置换和一类三项式完全置换[15].在此基础上, Wu、Li、Helleseth 和 Zhang 给出了偶特征域上更多的单项式完全置换[16].Wu 和 Lin 给出了特征为 2 的有限域上完全置换的一种递归构造, 通过计算已知完全置换的复合逆来构造新的完全置换[17].Xu、Feng 和Zeng 刻画了 Fpn上形如 (xpm−x+δ)s+axpm+bx的完全置换[18].关于完全置换的更多研究进展请参考论文[19–25]及文内的参考文献.

本文分别研究了有限域上两种不同类型的多项式的置换性质, 通过已知置换来证明新的置换, 进而发现和构造完全置换.第2 节介绍预备知识; 第3 节给出六类形如的置换多项式, 证实了其中三类为完全置换; 第4 节介绍了形如xh(xs) 的二项式的置换性质, 进而得到完全置换的相关构造; 第5 节总结.

2 预备知识

在本文中, 令p为素数,n,m,q,d为正整数且满足q=pm和d| (qn−1).用表示有限域 Fq的乘法群, Fqn[x]表示Fqn上的多项式环.定义有限域Fqn到Fq上的迹函数为

记有限域 Fqn上的d次单位根的集合为µd且有

对于θ∈ F∗q, 定义 Fq上的 Dickson 多项式为

若有限域Fq的特征为2, 通过简单计算可得下列Dickson 多项式

两个置换多项式之间的quasi-multiplicative (简记为QM) 等价关系定义如下:

定义 1[26]设q是素数p的方幂,f(x),g(x)∈Fq[x]是 Fq上的置换多项式.如果存在和正整数使得 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]设r和d为正整数满足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]设q为素数的方幂,i,n为正整数且有a∈Fqn.线性多项式g(x)=xpi+ax是 Fqn上的置换当且仅当a=0 或者 −a不是中的pi−1 次方幂.

受文献 [31,32]的启发, 在本节中我们利用线性置换和 Dickson 置换构造了 Fqn上六类形如γx+的置换, 其中三类被证实为完全置换.此外, 我们分析了剩余三类置换不是完全置换的原因.首先, 我们利用迹函数构造出下列完全置换.

定理 1设q是素数的方幂且有q> 2.令n和k为正整数满足且令γ∈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上的置换.根据完全置换的定义可得出结论:f(x) 是Fqn上的完全置换.

定理 2设q是素数p的方幂且有q> 2.令n,k,l,i为正整数满足 1l

证明:与定理1 的证明类似, 我们需证方程

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

于是可得

不难发现, 上面的方程有且只有一个解.由此可推出f(x) 是Fqn上的置换.

由γ∈Fq{0,−1} 可得γ+1 ∈Fq{0}, 所以f(x)+x也是 Fqn上的置换.根据完全置换的定义可得出结论:f(x) 是Fqn上的完全置换.定理 3令n,m,q为正整数,p为素数且有q=pm.设对于令γ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 置换分别构造出三类定义在Fq3上的置换.

定理 4设m为奇数且有q=2m.令则是 Fq3上的置换.

证明:要证是 Fq3上的置换, 我们需证方程

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

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

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

已知m为奇数且有q= 2m, 则有 gcd(5,q2−1) = 1.由引理1 可知:g5(t,γ) 是 Fq上的置换.因此, 上式只有一个解t, 由此可得到一个唯一解x.故是 Fq3上的置换.

定理 5设m为正整数满足且有则是 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设m为正整数满足且有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为变量的函数.也就是说, 对于给定的值γ和b, ∆(γ,c) 为一个常量.已知m≡0 mod 5 且有q=2m,容易验证 gcd(11,q2−1)=1.根据引理1 可得:g11(t,γ)=t11+γt9+γ3t5+γ4t3+γ5t是Fq上的置换.因此, 上式只有一个解t, 由此可得到一个唯一解x.故f(x) 是Fq3上的置换.

定理4,5,6 中的置换是分别依据 Fq上的 Dickson 置换g5(t,γ),g7(t,γ) 和g11(t,γ) 构造而来.对于Fq上其它的 Dickson 置换gi(t,γ) (i>11), 我们可以用同样的方法构造 Fq3上形如γx+Trq3q(h(x)) 的置换.需要指出的是: 由于γ∈Fq上的 Dickson 置换不是完全置换, 因而利用该方法构造出的置换也不是完全置换.

4 xh(xs)型完全置换

在本节中, 我们应用引理2, 确定了有限域Fqn上形如的二项式的置换性质.根据这些置换性质, 我们得到一些xh(xs) 型完全置换.

定理 7设i,k为正整数,q为素数的方幂.令γ∈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设i,k为正整数,q> 2 为素数的方幂且满足 (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设i,j,k,m,q为正整数且满足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设n,i,k,m为正整数,p为素数且设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设n,k为正整数,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 结论

本文研究了有限域Fqn上几类多项式的置换性质.利用 Fq上的线性置换和Dickson 置换对应构造出 Fqn上六类形如的置换, 进而得到 Fqn上三类新的完全置换.给出了Fqn上二项式γx+xs+1是置换的几个充分条件, 由此得到一些形如xh(xs) 的完全置换.只要选取Fq上适当的完全置换, 根据本文的方法可有效的构造Fqn上的完全置换.