谢 茜, 王丽莎, 李 念

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

1 引言

设p 是素数, n 为正整数, Fpn 表示含有pn个元素的有限域. 若有限域Fpn 上的多项式F(x) 是从Fpn 到自身的一个一一映射, 则称F(x) 是Fpn 上的置换多项式. 平衡性是密码函数一项重要的安全性指标, 而有限域上的置换多项式能够有效地保证平衡性. 在密码算法设计中, 密码函数常由有限域上具有优良密码性质(如低差分均匀度、高非线性度、高代数次数等) 的置换构成. 基于置换多项式在密码学、编码理论和序列设计等领域的广泛应用, 构造新的置换多项式是一个值得深入研究的问题.

人们对置换多项式的研究已有150 多年的历史. 1863 年, Hermite[1]首先开创了对模素数p 的置换多项式的研究, 并提出了有限域Fp上置换多项式的一经典判别方法: Hermite 准则. 之后, Dickson[2]于1896–1897 年将置换多项式的概念推广到任意有限域Fpn上, 并对置换多项式作了深入探讨. 随后,越来越多的学者对置换多项式进行了研究. 目前, 已有利用迹函数和线性化多项式[3]、分段函数[4,5]、AGW 准则[6]等多种不同方法构造置换多项式. 2009 年, Coulter, Henderson 和Matthews[3]利用迹函数和线性化多项式构造有限域Fpn上的置换多项式. 同年, Charpin 和Kyureghyan[7]构造有限域Fpn上形式为G(x)+γ Tr(H(x)) 的置换多项式, 其中G(x) ∈Fpn[x], H(x) ∈Fpn[x], γ ∈Fpn, Tr(·) 表示Fpn上的绝对迹函数. 随后, Marcos 在文献[8] 中讨论形式为L(x)+γh(Tr(x)) 的置换多项式, L 为定义在Fpn上的Fp-线性置换, h(x) ∈Fp[x], γ ∈Fpn. 基于对以上形如G(x)+γh(f(x)) 的置换多项式的研究, Kyureghyan[9]提出由线性转换构造形式为L(x)+L(γ)h(f(x)) 的置换多项式F(x), 其中L 为定义在Fpn上的Fpm-线性置……