有限域上完全置换多项式的构造*

李丽莎, 曾祥勇, 曹喜望

1.湖北大学数学与统计学学院应用数学湖北省重点实验室, 武汉430062

2.南京航空航天大学理学院, 南京211106

3.信息安全国家重点实验室, 北京100039

完全置换多项式专栏

1 引言

设q是素数的方幂, Fq表示包含q个元素的有限域, 并且 Fq[x]是 Fq上的多项式环.如果映射f是从 Fq到其自身的双射, 那么称f(x) 是 Fq上的置换多项式[1].若f(x) 和f(x)+x均为 Fq上的置换多项式, 则称f(x) 是Fq上的完全置换多项式[2].近年来, 完全置换多项式在密码学、编码学和组合数学中得到了广泛应用[3].例如 bent 函数的构造[4–6], Hash 函数的设计[7,8], 分组密码中SMS4 密码算法的设计[9]等.因此对其构造的研究成为一个热门问题.

完全置换多项式的研究可以追溯到20 世纪中期.1942 年, Mann 构造正交拉丁方时提出了完全置换多项式的概念[2].在此基础上, Niederreiter 和Robinson 具体研究了有限域上的完全置换多项式[10].由于判断一个多项式的完全置换性质十分困难, 所以到目前为止, 已知的完全置换多项式类依然很有限, 尤其是具有显式表达的完全置换多项式.其早期结果很少, 只有两类 Dickson 多项式[11], 有限域 F16上所有完全置换二项式和三项式[12], 以及形如的完全置换单项式[13–15], 其中并且k|q− 1.2014 年, Tu、Zeng 和Hu 提出了用加法特征和极坐标表示的方法来将完全置换多项式的问题转化成有限域上特殊方程解的问题[16].受到其启发, 完全置换多项式的构造得到了进一步发展[17–23].近些年, 形如(xpm−x+δ)s+L(x) 的置换多项式吸引了人们的注意, 其中L(x) 是线性化多项式.文献[24,25]研究了这类多项式的完全置换性质, 并通过AGW 准则, 将有限域上多项式的完全置换问题转化为特殊方程在其子集上解的问题, 或是项数较少多项式的完全置换问题, 得到了大量完全置换多项式.除上述构造方法外,完全置换多项式的构造还包括基于特殊密码结构和函数的多变元完全置换多项式的构造[26–37], 已知完全置换多项式的合成逆[38–40]以及已知完全置换多项式的递归构造[6,26,41].

有限域Fq2上形如f(x)=xrh(xq−1) 的置换多项式已有丰富的结论[42], 其中r是正整数, 而其完全置换性质却很少被关注.本文构造了两类特征 2 有限域 Fq2上形如xh(xq−1)q+1的完全置换多项式.第一类通过选取h(x) =ax+b, 得到了 Fq2上完全置换三项式, 推广了文献 [24]中定理 4.此外, 通过文献 [43]构造形如xg(xq−1) 置换多项式的方法, 我们令h(x) =h1(x)+h2(x)y, 其中y=x+xq, 得到了第二类完全置换多项式, 丰富了已有完全置换多项式的构造.文中主要利用AGW 准则, 将证明多项式是完全置换多项式的问题转化为证明特殊方程在单位圈U上无解的问题, 进而转化成其在有限域 Fq子集上无解的问题.最终通过低次方程在有限域上无解的条件以及迹函数的性质, 给出了这些多项式是完全置换多项式的充要条件或者充分条件.

2 预备知识

在本文中, 我们用F2n表示有 2n个元素的有限域, 其中n是正整数.令k是正整数且k|n.定义从有限域F2n到其子域F2k上的迹函数为

3 完全置换多项式的构造

4 结论

本文构造了两类特征2 有限域上形如xh(xq−1)q+1的完全置换多项式.第一类推广了文献 [24]定理4 中部分结论.第二类通过构造h(x)=h1(x)+h2(x)y, 其中y=x+xq, 并选取特殊的h1(x),h2(x), 得到了完全置换三项式, 完全置换七项式和其它完全置换多项式, 丰富了已有完全置换多项式的构造.