0 概述

有限域上置换多项式被广泛应用于密码学、编码理论、组合设计等领域。在密码学中, 高级加密标准(Advanced Encryption Standard, AES)的S盒利用有限域上的置换x^－1进行设计^[1], 置换多项式及其逆置换多项式可用来构造密钥交换协议^[2]及差分均匀度较低的密码函数^[3-4]。在编码理论和组合设计中, 特殊Dickson置换多项式可用来构造新类型的skew Hadamard差集^[5], 有限域上置换多项式还可构造循环码^[6]、正交拉丁方^[7-8]等。

关于有限域上置换多项式的研究较多^[9-10], 但仍有问题尚未解决^[9-10]。例如, 置换二项式的完全刻画问题未得到解决, 寻找有效算法计算已知置换多项式的逆置换多项式依然是一个开放性问题。因此, 构造新类型的置换多项式具有重要的研究价值。

本文阐述利用AGW(Akbary-Ghioca-Wang)准则和分段方法构造置换多项式的研究现状, 介绍有限域上置换多项式的逆置换多项式, 并展望下一步研究工作。

1 置换多项式的定义

从有限域到自身的每个函数都可用多项式表示, 因此在有限域上只考虑多项式函数。设f(x)是系数在有限域GF(q)上的多项式, 若其导出的映射$f:c \mapsto f\left(c \right)$是GF(q)的置换, 则称f(x)为GF(q)的置换多项式。

国内外学者对有限域上置换多项式进行了较多研究。文献[11]总结了1983年之前有限域上置换多项式的主要成果。文献[12-13]介绍了有限域上置换多项式的Hermite准则、计数与分布、群结构及其构造方法。

2 AGW准则

文献[14]推导出$f\left(x \right) = {x^r}h\left({{x^{\left({q - 1} \right)/d}}} \right)$是GF(q)的置换多项式的充要条件。文献[15]用群置换的方法将f(x)是否置换GF(q)的问题转化为$\mathit{g}\left(x \right) = {x^r}h{\left(x \right)^{\left({q - 1} \right)/d}}$是否置换GF(q)中所有d次单位根组成的群U(d)问题。

定理1    设d、s、r均是正整数且ds=q－1。对任意h(x)∈GF(q)[x], $f\left(x \right) = {x^r}h\left({{x^s}} \right)$是GF(q)的置换多项式当且仅当(r, s)=1, ${x^r}h{\left(x \right)^s}$置换U(d)^[15-16]。

定理2 (AGW准则^[17])   设R、S、S是有限集合且S和S中元素个数相等, f、θ、θ、g是图 1中相应集合之间的映射。若$\bar \theta \circ f = g \circ \theta $, 则f置换R当且仅当g是从S到S的双射, 且对任意s∈S, 映射f在θ^－1(s)上均是单射。其中, $ \circ $表示函数复合运算。

上述定理将f是否置换R的问题转化为g是否是从S到S的双射的问题。文献[12]称上述思想为AGW准则。该准则为构造置换多项式提供了一个非常重要的方法。该准则可应用到剩余类环和有限域等集合。在定理2中取θ(x)=θ(x)=x^s即可得到定理1。

文献[18-19]利用AGW准则重点研究了形如f(x)=g(B(x))+∑(L_i(x)+δ_i)h_i(B(x))和f(x)=g(x)h(λ(x))的置换多项式。文献[20]利用AGW准则构造形如θx+βg(x^pk－β^pk－1x)Tr_n^k(x)的置换多项式。文献[21]运用AGW准则构造了GF(q²)上形如(x^q－bx+c)^(q2－1)/d+1+bx的置换多项式, 其中d∈{2, 3, 4, 6}且d整除q²－1。文献[22]推导出(ax^q+bx+c)^rφ((ax^q+bx+c)^(q2－1)/d)+ux^q+vx是GF(q²)上置换多项式的充要条件, 其中a、b、c、u、v∈GF(q²), r是任意正整数, d是q²－1的任意正因子, φ(x)是系数在GF(q²)上的任意多项式。文献[23]构造了特殊的交换图, 进而利用AGW准则得到GF(q²)上形如x^rh(x^q－1)的置换多项式, 将其结果统一并应用到已知的置换三项式。

综上, AGW准则是构造置换多项式的重要方法, 但是该准则也有一定的局限。如图 1所示, 给定一般的R和f, 如何构造θ、θ、g使图 1可交换是一个非常困难的问题, 目前还没有构造交换图的通用方法。

3 分段方法

分段构造置换多项式思想是将有限域GF(q)划分成互不相交的三段:GF(q)={0}∪D₁∪D₂, 其中D₁是GF(q)中非零平方元的集合, D₂是非平方元的集合。当x∈D₁时, x^(q－1)/2=1;当x∈D₂时, x^(q－1)/2=－1。因此f(x)=x^(q+1)/2+ax可写成:

$ f(x) = \left\{ {\begin{array}{*{20}{l}} {0, x = 0}\\ {{f_1}(x) = (a + 1)x, x \in {D_1}}\\ {{f_2}(x) = (a - 1)x, x \in {D_2}} \end{array}} \right. $

显然, f₁(x)在D₁是单射, f₂(x)在D₂也是单射。若a+1和a－1同时属于D₁或D₂, 则集合f₁(D₁)和f₂(D₂)的交集为空集。此时{0}、f₁(D₁)、f₂(D₂)构成GF(q)的一个划分, 因此可得到如下定理:

定理3    设q是奇素数的方幂, a∈GF(q), 则多项式f(x)=x^(q+1)/2+ax是GF(q)的置换多项式当且仅当(a²－1)^(q－1)/2=1。

文献[7]推导出多项式x^(q+1)/d+ax置换GF(q)的充要条件, 其中d是q－1的任意正因子。文献[24]用分段方法证明了reversed Dickson多项式D_3²ⁿ+5(1, x)是GF(3²ⁿ)上的置换多项式。文献[25]研究GF(pⁿ)上形如(x^pk－x+c)^(pn－1)/2+1+x^pk+x的置换多项式。当n=2k时, 文献[26]将(p^2k－1)/2推广到(p^2k－1)/3。文献[19]将上述结果进行改进, 并用分段方法证明了定理4。

定理4    设p是奇素数, a, b, c∈GF(pⁿ), 1≤k＜n, 则f(x)=(ax^pk－bx+c)^(pn+1)/2+ax^pk+bx是GF(pⁿ)的置换多项式当且仅当ab是非零的平方元。

文献[27]在研究广义割圆映射置换时证明了定理5。

定理5    设d, s, r₀, r₁, …, r_d－1是正整数且ds=q－1, β是GF(q)的本原元, ω=β^s, a₀, a₁, …, a_d－1∈GF(q)^*。则$f\left(x \right) = \left({1/d} \right)\sum\limits_{i = 0}^{d - 1} {{a_i}{x^{{r_i}}}} \sum\limits_{j = 0}^{d - 1} {{{\left({{x^s}/{\omega ^i}} \right)}^j}} $是GF(q)的置换多项式当且仅当(r_i, s)=1(0≤i≤d－1)且{log_βa_i+ir_i:i=0, 1, …, d－1}是模d的完全剩余系。

文献[28-29]总结了分段构造置换多项式的思想。下文定理用有限域的语言描述该思想。

定理6    设D₁, D₂, …, D_m是GF(q)的一个划分, f₁(x), f₂(x), …, f_m(x)∈GF(q)[x], f(x)=∑f_i(x)I_Di(x), 其中, I_Di(x)是D_i的特征函数, 即当x∈D_i时, I_Di(x)=1;当x∉D_i时, I_Di(x)=0, 则f(x)是GF(q)的置换多项式, 当且仅当每个f_i(x)在D_i上都是单射, 且f₁(D₁), f₂(D₂), …, f_m(D_m)互不相交。

在定理6中, 当x∈D_i时, f(x)=f_i(x), 说明f(x)是由片函数f_i(x)构成的分段多项式函数。根据上述定理, 分段构造置换多项式可分为如下4步:

1) 把GF(q)分成若干互不相交的子集D₁, D₂, …, D_m。

2) 系数在GF(q)上的任意多项式f(x)都可写成分段的形式, 即:

$ f(x)=\left\{\begin{array}{c}{f_{1}(x), x \in D_{1}} \\ {f_{2}(x), x \in D_{2}} \\ {\vdots} \\ {f_{m}(x), x \in D_{m}}\end{array}\right. $

3) 研究f_i(x)在对应子集D_i上的置换性质。

4) f(x)是GF(q)的置换多项式当且仅当f₁(D₁), f₂(D₂), …, f_m(D_m)是GF(q)的一个划分。

虽然分段构造置换多项式的思想比较简单, 但是对于一些特殊情况确实非常有效。

4 逆置换多项式

设f(x)是GF(q)的置换多项式, 则存在一个系数在GF(q)的多项式f^－1(x)使得f^－1(f(e))=e对任意e∈GF(q)均成立, 称f^－1(x)是f(x)在GF(q)上的逆置换多项式, 简称逆置换。给定f(x), 当q较小时, 可用如下拉格朗日插值公式计算其逆置换:

$ {f^{ - 1}}(x) = \sum\limits_{c \in GF(q)} c \left( {1 - {{(x - f(c))}^{q - 1}}} \right) $

这是一个逐点求逆的方法。当q较大时, 该方法不可行, 因为计算量大。事实上, 求有限域上的置换多项式的逆置换非常困难^[15]。因此相关研究较少, 关于多项式的递置换描述如下:

1) 线性多项式。设a, b∈GF(q)且a≠0, 则ax+b是GF(q)的置换多项式, 其逆置换为(x－b)/a。

2) 单项式。x^m是GF(q)的置换多项式当且仅当(m, q－1)=1, 逆置换为xⁿ, 其中, mn≡1(modq－1)。

3) Dickson多项式。设a=±1且mn≡1(modq²－1), 则第一类Dickson多项式D_m(x, a)是GF(q)的置换多项式, 其逆置换为D_n(x, a)。

4) 形如x^rh(x^(q－1)/d)的多项式。文献[30]给出x^rh(x^(q－1)/d)在GF(q)上的逆置换的系数表达式。

5) 线性化多项式。文献[31]利用Dickson矩阵第一列元素的代数余子式构造了有限域上线性化置换多项式的逆置换。

6) 双线性多项式。两个线性化多项式的乘积是双线性多项式。文献[32]构造了双线性置换多项式x(Tr_qⁿ/q(x)+ax)在GF(qⁿ)上的逆置换。在此基础上, 文献[33]将GF(qⁿ)分解成两个子空间的直和GF(q)⊕ker(Tr), 然后计算两个相关函数在这两个子空间上的逆, 利用这两个逆推导出原置换在GF(qⁿ)上的逆置换。文献[34]构造了置换f(x)=h(ψ(x))φ(x)+g(ψ(x))在GF(qⁿ)上的逆置换。文献[35-36]将分段方法和求逆置换结合起来, 提出用分段方法构造逆置换的思想。

定理7    设D₁, D₂, …, D_m是GF(q)的一个划分, f₁(x), f₂(x), …, f_m(x)∈GF(q)[x], f(x)=∑f_i(x)I_Di(x)。若f(x)是GF(q)的置换多项式, 则其逆置换多项式为:

$ {f^{ - 1}}(x) = \sum {f_i^{ - 1}} (x){I_{{f_i}\left( {{D_i}} \right)}}(x) $

其中, f_i^－1(x)是f_i(x)在D_i的逆函数, I_fi(Di)(x)是f_i(D_i)的特征函数。

定理7描述了定理6中置换多项式的逆置换多项式的抽象表达式。定理7将计算逆置换多项式f^－1(x)的问题转化为另一个问题:求若干个片函数f_i(x)的逆函数f_i^－1(x)和若干个像集合f_i(D_i)的特征函数I_fi(Di)(x)。一般情况下, 该问题也是一个困难问题。但是, 当片函数比较简单时, 第2个问题通常容易解决。根据上述思路, 文献[35-36]构造了已知置换的逆置换多项式, 下文列出主要定理。

定理8    设d、s、q、r_i、a_i、β、ω、f(x)如定理5所定义。若f(x)是GF(q)的置换多项式, 则有:

$ {f^{ - 1}}(x) = (1/d)\sum\limits_{i = 0}^{d - 1} {{\omega ^{i{t_i}}}} {\left( {x/{a_i}} \right)^{{{\tilde r}_i}}}\sum\limits_{j = 0}^{d - 1} {{{\left( {{x^s}/a_i^s{\omega ^{i{r_i}}}} \right)}^j}} $

其中, ${{\tilde r}_i}$、t_i∈Z满足$1 \le {{\tilde r}_i} < s$且${r_i}{{\tilde r}_i} + s{t_i} = 1$。

定理8给出定理5中置换多项式的逆置换多项式的简明表达式。在定理8中取a_i=h(ωⁱ)且r_i=r, 可得到定理1中f(x)的逆置换多项式。

定理9    设d、s、r均是正整数且ds=q－1。对任意h(x)∈GF(q)[x], 设f(x)=x^rh(x^s)是GF(q)的置换多项式, 则f(x)在GF(q)上的逆置换多项式为:

$ {f^{ - 1}}(x) = (1/d)\sum\limits_{i = 0}^{d - 1} {\sum\limits_{j = 0}^{d - 1} {{\omega ^{i(t - jr)}}} } {\left( {x/h\left( {{\omega ^i}} \right)} \right)^{\tilde r + js}} $

其中, $\tilde r, t \in Z$满足$1 \le \tilde r < s$且$r\tilde r + st = 1$。

在定理9中取d=2, r=1, q是奇数, h(x)=x+a, 可得到定理3中f(x)的逆置换多项式。

定理10    设q是奇数, f(x)=x^(q+1)/2+ax是GF(q)的置换多项式。若(a+1)^(q－1)/2=(a－1)^(q－1)/2=－1, 则有:

$ {f^{ - 1}}(x) = {\left( {{a^2} - 1} \right)^{ - 1}}\left( {ax + {x^{(q + 1)/2}}} \right) $

若(a+1)^(q－1)/2=(a－1)^(q－1)/2=1, 则:

$ {f^{ - 1}}(x) = {\left( {{a^2} - 1} \right)^{ - 1}}\left( {ax - {x^{(q + 1)/2}}} \right) $

文献[35]给出定理4中f(x)的逆置换多项式。

定理11    设a、b、c、p、k、n、f(x)如定理4所定义。若f(x)是GF(q)的置换多项式, 则:

$ \begin{aligned} f^{-1}(x)=& \frac{1}{2}(u(x)+v(x))-\\ & \frac{1}{2} a^{\left(p^{n}-1\right) / 2}(u(x)-v(x))^{\left(p^{n}+1\right) / 2} \end{aligned} $

其中, u(x)=(x+c)/2b, v(x)=((x－c)/2a)^pn－k。

5 结束语

本文研究了有限域上置换多项式的进展, 并阐述了构造有限域上置换多项式的AGW准则和分段方法, 对置换多项式的逆置换进行分析与总结。目前, 该领域的研究已经取得一定的成果, 但仍存在一些问题, 如AGW准则中交换图的构造、寻找计算已知置换的逆置换的有效算法, 以及低次数置换多项式的分类、Reverse Dickson置换多项式的完全刻画等。下一步将对以上问题进行深入研究与分析。