两类面向算术化幂函数的差分性质

Differential properties of two classes of arithmetization-oriented power mappings

摘要

设p为素数，n为正整数. 主要研究有限域{\mathbb{F}}_{p^n}上低阶非线性幂函数x^{\mathrm{5}}以及x^{\mathrm{7}}的差分性质. 通过研究函数x^{\mathrm{5}}和x^{\mathrm{7}}的差分方程，刻画了差分方程有特定解数的条件，利用二次特征和确定了这两类幂函数差分谱. 在面向算术的密码原语中，这两类低阶非线性幂函数可用于构造S盒或轮函数，其差分性质可为评估他们抗差分攻击的性能提供参考.

Abstract

Let p be a prime number and n be a positive integer. The differential properties of two classes of low-degree nonlinear power mappings x^{\mathrm{5}} and x^{\mathrm{7}} over finite field {\mathbb{F}}_{p^n} are investigated. By investigating the derivative equations of the functions x^{\mathrm{5}} and x^{\mathrm{7}}， the conditions under which the differential equations have a specific number of solutions are characterized. Utilizing quadratic character sums， the differential spectrum of these two classes of power mappings are determined. These two classes of low-degree nonlinear power mappings can be used to design S-boxes or round functions in arithmetization-oriented cryptographic primitives， and their differential properties can provide a reference for evaluating their performance against differential attack.

关键词

有限域 / 幂函数 / 差分方程 / 差分谱 / 特征和

Key words

finite field / power mapping / derivative equation / differential spectrum / character sums

密码Hash函数对于实际的零知识证明应用至关重要，有时直接作为零知识证明（Zero-Knowledge， ZK）协议的一部分使用. 现代密码Hash函数，如SHA-2、SHA-3和p是一个较大的素数. 为了在{\mathbb{F}}_p上实现高效的Hash运算，需要开发新的Hash函数，这类函数称为面向算术的（Arithmetization-Oriented， AO）Hash函数. 研究人员和工程师们已经提出了多种AO Hash函数的设计，如MiMCHash^［1］，Rescue-Prime^［2-3］，Reinforced Concrete^［4］BLAKE，通常设计在偶特征的有限域上^［5］. 然而，ZK协议往往在大素数域{\mathbb{F}}_p上操作，其中Anemoi^［6］，Poseidon^［7］和Grende^［8］等这些新的Hash函数旨在提供{\mathbb{F}}_p上高效的算术运算，同时保持必要的安全性和实用性，以支持大规模的加密货币和其他需要高效ZK证明的应用.

由于面向算术Hash函数的概念相对较新，对这些函数的严格密码分析尚未完成. 除了Anemoi^［6］和Grende^［8］之外，这些面向算术的Hash函数都使用低阶非线性函数作为轮函数，例如幂映射. MiMCHash^［2］和Poseidon^［7］两类AO Hash函数使用幂映射x^d，d\in\{\mathrm{3,5}\}作为轮函数. 当x^d的次数较低时，其抵抗代数攻击的能力较弱，因此必须使用大量的轮数. 为了克服这一问题，对于满足\mathrm{g}\mathrm{c}\mathrm{d}(d,p-\mathrm{1})=\mathrm{1}的低阶幂映射x^d，人们常选择x^d的复合逆x^{d^{-\mathrm{1}}}来构造轮函数，x^{d^{-\mathrm{1}}}具有较高的阶，其抵抗代数攻击的能力较强，同时保持了与x^d相同的差分均匀度和非线性度. 本文主要分析两类低阶幂函数x^{\mathrm{5}}和x^{\mathrm{7}}的差分性质^［9］，为抗差分攻击的轮函数设计和选择提供理论依据.

1 基础知识

设p为素数，n为正整数，{\mathbb{F}}_{p^n}是含有p^n个元素的有限域，{\mathbb{F}}_{p^n}^{\mathrm{*}}={\mathbb{F}}_{p^n}\backslash \{\mathrm{0}\}. 下面给出差分均匀度和差分谱的概念.

定义1^［10］ 设f为有限域{\mathbb{F}}_{p^n}上的函数，对任意的a\in {\mathbb{F}}_{p^n}^{\mathrm{*}}，b\in {\mathbb{F}}_{p^n}，令{\delta }_f(a,b)表示差分方程f(x+a)-f(x)=b在有限域{\mathbb{F}}_{p^n}中解的个数. 定义：

\delta (f)=\underset{a\in {\mathbb{F}}_{p^n}^{\mathrm{*}},b\in {\mathbb{F}}_{p^n}}{\mathrm{m}\mathrm{a}\mathrm{x}}{\delta }_f(a,b)

为函数f(x)的差分均匀度，特别当\delta (f)=\delta时，f(x)也被称作\delta-差分一致性函数.

若函数f(x)是有限域{\mathbb{F}}_{p^n}上的幂函数，即f(x)=x^d，当a\in {\mathbb{F}}_{p^n}^{\mathrm{*}}时，根据：

f(x+a)-f(x)={(x+a)}^d-x^d=a^d\left({\left(\frac{x}{a}+\mathrm{1}\right)}^d-{\left(\frac{x}{a}\right)}^d\right),

故{\delta }_f(a,b)={\delta }_f(\mathrm{1},b/a^d)，从而幂函数f(x)=x^d的差分性质由{\delta }_f(\mathrm{1},b)的取值完全确定，其中b遍历{\mathbb{F}}_{p^n}. 幂函数f(x)=x^d的差分谱即为b遍历{\mathbb{F}}_{p^n}时{\delta }_f(\mathrm{1},b)的取值分布. 下面给出其精确描述.

定义2^［11］ 设f(x)=x^d为定义在有限域{\mathbb{F}}_{p^n}上的幂函数，其差分均匀度为\delta，则其差分谱定义为序列[{\omega }_{\mathrm{0}},{\omega }_{\mathrm{1}},\dots ,{\omega }_{\delta }]，其中：

{\omega }_i=\left|\left\{b\in {\mathbb{F}}_{p^n}|{\delta }_f(\mathrm{1},b)=i\right\}\right|,\mathrm{0}\le i\le \delta .

根据{\omega }_i的定义，可以得到幂函数差分谱的两个基本性质：

{\displaystyle \sum _{i=\mathrm{0}}^{\delta }}{\omega }_i=p^n和{\displaystyle \sum _{i=\mathrm{0}}^k}i{\omega }_i=p^n.

定义3 定义\chi (\cdot )为有限域{\mathbb{F}}_{p^n}上二次特征，即对任意的x\in {\mathbb{F}}_{p^n}，有：

\chi (x)=x^{\frac{p^n-\mathrm{1}}{\mathrm{2}}}=\left\{\begin{array}{ll}\mathrm{1},& \mathrm{如果}x\mathrm{是}{\mathbb{F}}_{p^n}\mathrm{中的}\mathrm{平方}\mathrm{元},\\ -\mathrm{1},& \mathrm{如果}x\mathrm{是}{\mathbb{F}}_{p^n}\mathrm{中的}\mathrm{非平}\mathrm{方元},\\ \mathrm{0},& x=\mathrm{0}.\end{array}\right.

对于f(x)\in {\mathbb{F}}_{p^n}[x]，\sum _{x\in {\mathit{𝔽}}_{p^n}}\chi (f(x))表示f(x)的二次特征和.

引理1^［12］ 设f(x)=a_{\mathrm{2}}{x}^{\mathrm{2}}+a_{\mathrm{1}}x+a_{\mathrm{0}}\in {\mathbb{F}}_{p^n}[x]，且a_{\mathrm{2}}\ne \mathrm{0}. 令d={a_{\mathrm{1}}}^{\mathrm{2}}-\mathrm{4}{a}_{\mathrm{0}}{a}_{\mathrm{2}}，\chi (\cdot )是有限域{\mathbb{F}}_{p^n}上的二次特征，那么有：

\sum _{x\in F_{p^n}}\chi (f(x))=\left\{\begin{array}{ll}-\chi (a_{\mathrm{2}}),& \mathrm{若}d\ne \mathrm{0},\\ (p^n-\mathrm{1})\chi (a_{\mathrm{2}}),& \mathrm{若}d=\mathrm{0}.\end{array}\right.

引理2^［13］ 设{\mathbb{F}}_{{\mathrm{3}}^n}上的方程

x^{\mathrm{3}}+a{x}^{\mathrm{2}}+bx+c=\mathrm{0}（1）

在{\mathbb{F}}_{{\mathrm{3}}^n}中有一根x_{\mathrm{0}}，则有：

（1）当方程

y^{\mathrm{2}}+ay+(\mathrm{2}ad+b)=\mathrm{0}（2）

在{\mathbb{F}}_{{\mathrm{3}}^n}中有根y_{\mathrm{0}}时，方程（1）在{\mathbb{F}}_{{\mathrm{3}}^n}中有根y_{\mathrm{0}}+x_{\mathrm{0}}；

（2）对于方程（1）的根r，r\cancel{=}{x}_{\mathrm{0}}，则r-x_{\mathrm{0}}为方程（2）的根.

2 主要结果及证明

为方便表示，令\delta (\mathrm{1},b)表示差分方程{(x+a)}^d-x^d=b的解数. 本节主要研究幂函数x^{\mathrm{5}}，x^{\mathrm{7}}在有限域{\mathbb{F}}_{p^n}上的差分性质，对d=\mathrm{5,7}，在一定条件下将给出\delta (\mathrm{1},b)的取值及其分布，即确定幂函数x^{\mathrm{5}}，x^{\mathrm{7}}的差分谱.

首先考虑{\mathbb{F}}_{p^n}上的幂函数x^{\mathrm{5}}（p为奇素数且p\ne \mathrm{5}）的差分均匀度和差分谱. 当p=\mathrm{2}时，f(x)=x^{\mathrm{5}}是{\mathbb{F}}_{{\mathrm{2}}^n}上的Gold函数，其差分谱BLONDEAU等人在文献［9］已给出结果.

命题1f(x)=x^{{\mathrm{2}}^t+\mathrm{1}}是定义在{\mathbb{F}}_{{\mathrm{2}}^n}上的幂函数，其中\mathrm{g}\mathrm{c}\mathrm{d}(t,n)=s，s\ge \mathrm{1}，对任意(a,b)\in ({\mathbb{F}}_{{\mathrm{2}}^n}{)}^{\mathrm{2}}，函数差分谱为：

[{\omega }_{\mathrm{0}},{\omega }_{{\mathrm{2}}^s},{\omega }_{{\mathrm{2}}^n}]=\left[\left({\mathrm{2}}^n-\mathrm{1}\right)\left({\mathrm{2}}^n-{\mathrm{2}}^{n-s}+\mathrm{1}\right),{\mathrm{2}}^{n-s}({\mathrm{2}}^n-\mathrm{1}),\mathrm{1}\right]；

当k为奇数时，{\omega }_k=\mathrm{0}.

特别t=\mathrm{2}时，可由命题1得到{\mathbb{F}}_{{\mathrm{2}}^n}上幂函数f(x)=x^{\mathrm{5}}的差分谱：

\left\{\begin{array}{l}[{\omega }_{\mathrm{0}},{\omega }_{\mathrm{2}},{\omega }_{{\mathrm{2}}^n}]=[({\mathrm{2}}^n-\mathrm{1})({\mathrm{2}}^n-{\mathrm{2}}^{n-\mathrm{1}}+\mathrm{1}),{\mathrm{2}}^{n-\mathrm{1}}({\mathrm{2}}^n-\mathrm{1}),\mathrm{1}]n\mathrm{为奇}\mathrm{数},\\ [{\omega }_{\mathrm{0}},{\omega }_{\mathrm{4}},{\omega }_{{\mathrm{2}}^n}]=[({\mathrm{2}}^n-\mathrm{1})({\mathrm{2}}^n-{\mathrm{2}}^{n-\mathrm{2}}+\mathrm{1}),{\mathrm{2}}^{n-\mathrm{2}}({\mathrm{2}}^n-\mathrm{1}),\mathrm{1}]n\mathrm{为偶}\mathrm{数},\end{array}\right.

且k为奇数时，{\omega }_k=\mathrm{0}.

下面定理1考虑p>\mathrm{2}，p\ne \mathrm{5}时的情况（当p=\mathrm{5}时差分方程为线性方程，结论是平凡的）.

定理1 设f(x)=x^{\mathrm{5}}是定义在有限域{\mathbb{F}}_{p^n}上的幂函数，其中p为奇素数且p\ne \mathrm{5}，此时函数f(x)为4-差分一致性函数，差分谱情况如下：

（1）当\chi (-\mathrm{2})=\mathrm{1}时，函数f(x)的差分谱为：

\begin{array}{l}[{\omega }_{\mathrm{0}},{\omega }_{\mathrm{1}},{\omega }_{\mathrm{2}},{\omega }_{\mathrm{3}},{\omega }_{\mathrm{4}}]=\left[\frac{\mathrm{5}{p}^n-\mathrm{3}\chi (-\mathrm{1})-\mathrm{2}}{\mathrm{8}},\mathrm{0},\frac{p^n+\chi (-\mathrm{1})+(\mathrm{1}+\chi {(-\mathrm{1}))}^{\mathrm{2}}-\mathrm{2}}{\mathrm{4}},\mathrm{1},\right.\\ \left.\frac{p^n-\chi (-\mathrm{1})-(\mathrm{1}+\chi {(-\mathrm{1}))}^{\mathrm{2}}-\mathrm{4}}{\mathrm{8}}\right],\end{array}

（2）当\chi (-\mathrm{2})=-\mathrm{1}时， 函数f(x)的差分谱为：

\begin{array}{l}[{\omega }_{\mathrm{0}},{\omega }_{\mathrm{1}},{\omega }_{\mathrm{2}},{\omega }_{\mathrm{3}},{\omega }_{\mathrm{4}}]=\left[\frac{\mathrm{5}{p}^n-\chi (-\mathrm{1})-(\mathrm{1}+\chi {(-\mathrm{1}))}^{\mathrm{2}}-\mathrm{4}}{\mathrm{8}},\mathrm{1},\frac{p^n+\chi (-\mathrm{1})+(\mathrm{1}+\chi {(-\mathrm{1}))}^{\mathrm{2}}-\mathrm{2}}{\mathrm{4}},\right.\mathrm{0},\\ \left.\frac{p^n-\chi (-\mathrm{1})-(\mathrm{1}+\chi {(-\mathrm{1}))}^{\mathrm{2}}}{\mathrm{8}}\right].\end{array}

证明 对任意b\in {\mathbb{F}}_{p^n}，考虑差分方程

{(x+\mathrm{1})}^{\mathrm{5}}-x^{\mathrm{5}}=b（3）

在{\mathbb{F}}_{p^n}中解的个数. 将（3）展开，得到如下方程

\mathrm{5}{x}^{\mathrm{4}}+\mathrm{10}{x}^{\mathrm{3}}+\mathrm{10}{x}^{\mathrm{2}}+\mathrm{5}x+\mathrm{1}=b.（4）

令x=y-\frac{\mathrm{1}}{\mathrm{2}}，则方程（4）等价于

y^{\mathrm{4}}+\frac{\mathrm{1}}{\mathrm{2}}{y}^{\mathrm{2}}+\frac{\mathrm{1}-\mathrm{16}b}{\mathrm{80}}=\mathrm{0}.（5）

当b=\frac{\mathrm{1}}{\mathrm{16}}时，方程（5）为y^{\mathrm{2}}\left(y^{\mathrm{2}}+\frac{\mathrm{1}}{\mathrm{2}}\right)=\mathrm{0}，此时若\chi \left(-\frac{\mathrm{1}}{\mathrm{2}}\right)=\chi (-\mathrm{2})=\mathrm{1}，方程的解为y=\mathrm{0}，\pm \sqrt[]{-\frac{\mathrm{1}}{\mathrm{2}}}，即差分方程（3）有三个解；若\chi \left(-\frac{\mathrm{1}}{\mathrm{2}}\right)=\chi (-\mathrm{2})=-\mathrm{1}，差分方程（3）仅有一个零解.

接下来考虑b\cancel{=}\frac{\mathrm{1}}{\mathrm{16}}时方程（5）解的情况. 当b\ne \frac{\mathrm{1}}{\mathrm{16}}时，显然方程（5）的解都是成对出现的（y和-y都是方程（5）的解）. 设y^{\mathrm{2}}=u，\frac{\mathrm{1}-\mathrm{16}b}{\mathrm{80}}=c， 此时方程（5）化简为：

u^{\mathrm{2}}+\frac{\mathrm{1}}{\mathrm{2}}u+c=\mathrm{0}.（6）

方程（6）的判别式\mathrm{\Delta }=\frac{\mathrm{1}}{\mathrm{4}}-\mathrm{4}c，解的情况如下：

（1）当\chi (\mathrm{\Delta })=-\mathrm{1}时，（6）无解；

（2）当\chi (\mathrm{\Delta })=\mathrm{0}时，（6）的解为u=-\frac{\mathrm{1}}{\mathrm{4}}，此时若\chi (-\mathrm{1})=\mathrm{1}，方程（5）有两个解；若\chi (-\mathrm{1})=-\mathrm{1}，方程（5）无解；

（3）当\chi (\mathrm{\Delta })=\mathrm{1}时，（6）有两解，不妨设为u_{\mathrm{1}}，u_{\mathrm{2}}，则u_{\mathrm{1}}=-\frac{\mathrm{1}}{\mathrm{4}}+\frac{\sqrt[]{\mathrm{1}-\mathrm{16}c}}{\mathrm{4}}，u_{\mathrm{2}}=-\frac{\mathrm{1}}{\mathrm{4}}-\frac{\sqrt[]{\mathrm{1}-\mathrm{16}c}}{\mathrm{4}}此时方程（5）最多有4解，有四解时当且仅当\chi (u_{\mathrm{1}})=\chi (u_{\mathrm{2}})=\mathrm{1}.

设u_{\mathrm{1}}=-\frac{\mathrm{1}}{\mathrm{4}}+\frac{\sqrt[]{\mathrm{1}-\mathrm{16}c}}{\mathrm{4}}=t，则u_{\mathrm{2}}=-\frac{\mathrm{1}}{\mathrm{2}}-t. 当c遍历{\mathbb{F}}_{p^n}^{\mathrm{*}}时，\mathrm{1}-\mathrm{16}c遍历{\mathbb{F}}_{p^n}\backslash \left\{\mathrm{1},\frac{\mathrm{1}}{\mathrm{16}}\right\}，此时t遍历{\mathbb{F}}_{p^n}\backslash \left\{\mathrm{0},-\frac{\mathrm{1}}{\mathrm{4}},-\frac{\mathrm{1}}{\mathrm{2}}\right\}. 令T=\left\{t|\chi (t)=\mathrm{1},\chi \left(-\frac{\mathrm{1}}{\mathrm{2}}-t\right)=\right.\mathrm{1},t\in{\mathbb{F}}_{{\mathrm{3}}^n}\backslash\left.\left\{\mathrm{0},-\frac{\mathrm{1}}{\mathrm{4}},-\frac{\mathrm{1}}{\mathrm{2}}\right\}\right\}，N=|T|. 利用二次特征和可得：

\begin{array}{l}\mathrm{4}N=\sum _{{}_{t\in {\mathit{𝔽}}_{p^n}\backslash \{\mathrm{0},-\frac{\mathrm{1}}{\mathrm{2}},-\frac{\mathrm{1}}{\mathrm{4}}\}}}(\mathrm{1}+\chi (t))\left(\mathrm{1}+\chi \left(-\frac{\mathrm{1}}{\mathrm{2}}-t\right)\right)\\ =\sum _{t\in {\mathbb{F}}_{p^n}}(\mathrm{1}+\chi (t))\left(\mathrm{1}+\chi \left(-\frac{\mathrm{1}}{\mathrm{2}}-t\right)\right)-\left(\mathrm{1}+\chi \left(-\frac{\mathrm{1}}{\mathrm{2}}\right)\right)-\left(\mathrm{1}+\chi \left(-\frac{\mathrm{1}}{\mathrm{2}}\right)\right)-{\left(\mathrm{1}+\chi \left(-\frac{\mathrm{1}}{\mathrm{4}}\right)\right)}^{\mathrm{2}}\\ =\sum _{t\in {\mathit{𝔽}}_{p^n}}\mathrm{1}+\sum _{t\in {\mathbb{F}}_{p^n}}\chi (t)+\sum _{t\in {\mathbb{F}}_{p^n}}\chi \left(-t-\frac{\mathrm{1}}{\mathrm{2}}\right)+\sum _{t\in {\mathbb{F}}_{p^n}}\chi \left(-t^{\mathrm{2}}-\frac{\mathrm{1}}{\mathrm{2}}t\right)-\mathrm{2}\left(\mathrm{1}+\chi \left(-\frac{\mathrm{1}}{\mathrm{2}}\right)\right)-{\left(\mathrm{1}+\chi \left(-\mathrm{1}\right)\right)}^{\mathrm{2}}\\ =p^n-\chi (-\mathrm{1})-\mathrm{2}\left(\mathrm{1}+\chi \left(-\frac{\mathrm{1}}{\mathrm{2}}\right)\right)-{\left(\mathrm{1}+\chi \left(-\mathrm{1}\right)\right)}^{\mathrm{2}}.\end{array}

由等式-\frac{\mathrm{1}}{\mathrm{4}}+\frac{\sqrt[]{\mathrm{1}-\mathrm{16}c}}{\mathrm{4}}=t可知1-\mathrm{16}c={(\mathrm{4}t+\mathrm{1})}^{\mathrm{2}}，易验证t与-\frac{\mathrm{1}}{\mathrm{2}}-t对应同一个c，即当t\cancel{=}-\frac{\mathrm{1}}{\mathrm{2}}-t时\mathrm{1}-\mathrm{16}c={(\mathrm{4}t+\mathrm{1})}^{\mathrm{2}}是t是与c之间的二对一映射. 当t\in T时\chi (u_{\mathrm{1}})=\chi (u_{\mathrm{2}})=\mathrm{1}，方程（5）有4解；此外当t\in T时，有-\frac{\mathrm{1}}{\mathrm{2}}-t\in T且t\cancel{=}-\frac{\mathrm{1}}{\mathrm{2}}-t. 所以使得方程（5）有4解的c的个数是|T|的二分之一，又因为c与b是一一对应，所以使得差分方程（3）有四个解的b的个数等于\frac{N}{\mathrm{2}}，当p^n足够大时\frac{N}{\mathrm{2}}>\mathrm{0}.

综上，幂函数x^{\mathrm{5}}在{\mathbb{F}}_{p^n}（p>\mathrm{2}，且p\cancel{=}\mathrm{5}）上是4-差分一致性函数，设其差分谱为[{\omega }_{\mathrm{0}},{\omega }_{\mathrm{1}},{\omega }_{\mathrm{2}},{\omega }_{\mathrm{3}},{\omega }_{\mathrm{4}}]，前述讨论知：{\omega }_{\mathrm{4}}=\frac{N}{\mathrm{2}}；当\chi (-\mathrm{2})=\mathrm{1}时，{\omega }_{\mathrm{3}}=\mathrm{1}，{\omega }_{\mathrm{1}}=\mathrm{0}；当\chi (-\mathrm{2})=-\mathrm{1}时，{\omega }_{\mathrm{3}}=\mathrm{0},{\omega }_{\mathrm{1}}=\mathrm{1}. 再由定义2的性质计算出差分谱.

定理1证毕.

接下来分析{\mathbb{F}}_{p^n}上的幂函数x^{\mathrm{7}}的差分均匀度和差分谱. 当p=\mathrm{2}时，f(x)=x^{\mathrm{7}}在{\mathbb{F}}_{{\mathrm{2}}^n}上的差分谱BLONDEAU等人在文献［14］已给出.

命题2f(x)=x^{\mathrm{7}}是有限域{\mathbb{F}}_{{\mathrm{2}}^n}上的幂函数，f(x)的差分均匀度等于6. 令i=\sqrt[]{-\mathrm{1}}，f(x)的差分谱可表示如下：

（1） n是奇数时

[{\omega }_{\mathrm{0}},{\omega }_{\mathrm{2}},{\omega }_{\mathrm{4}},{\omega }_{\mathrm{6}}]=\left[{\mathrm{2}}^{n-\mathrm{1}}+\mathrm{2}{\omega }_{\mathrm{6}},{\mathrm{2}}^{n-\mathrm{1}}-\mathrm{3}{\omega }_{\mathrm{6}},\mathrm{0},\frac{{\mathrm{2}}^n+\mathrm{1}}{\mathrm{24}}-\frac{\mathrm{1}}{\mathrm{8}}{\left(\frac{\mathrm{1}-i\sqrt[]{\mathrm{7}}}{\mathrm{2}}\right)}^n-\frac{\mathrm{1}}{\mathrm{8}}{\left(\frac{\mathrm{1}+i\sqrt[]{\mathrm{7}}}{\mathrm{2}}\right)}^n\right]；

当k\notin \{\mathrm{0,2},\mathrm{4,6}\}，{\omega }_k=\mathrm{0}.

（2） n是偶数时

[{\omega }_{\mathrm{0}},{\omega }_{\mathrm{2}},{\omega }_{\mathrm{4}},{\omega }_{\mathrm{6}}]=\left[{\mathrm{2}}^{n-\mathrm{1}}+\mathrm{2}{\omega }_{\mathrm{6}}+\mathrm{1},{\mathrm{2}}^{n-\mathrm{1}}-\mathrm{3}{\omega }_{\mathrm{6}}-\mathrm{2},\mathrm{1},\frac{{\mathrm{2}}^n-\mathrm{13}}{\mathrm{24}}-\frac{\mathrm{1}}{\mathrm{8}}{\left(\frac{\mathrm{1}-i\sqrt[]{\mathrm{7}}}{\mathrm{2}}\right)}^n-\frac{\mathrm{1}}{\mathrm{8}}{\left(\frac{\mathrm{1}+i\sqrt[]{\mathrm{7}}}{\mathrm{2}}\right)}^n\right]；

当k\notin \{\mathrm{0,2},\mathrm{4,6}\}，{\omega }_k=\mathrm{0}.

定理2 设f(x)=x^{\mathrm{7}}是定义在{\mathbb{F}}_{p^n}上的幂函数，其中p>\mathrm{2}，p\cancel{=}\mathrm{7}，其差分均匀度小于等于6，且：

（1）当p=\mathrm{3}时，

1） 若n>\mathrm{1}为奇数时，f(x)为4-差分一致性函数且差分谱为

\begin{array}{c}[{\omega }_{\mathrm{0}},{\omega }_{\mathrm{1}},{\omega }_{\mathrm{2}},{\omega }_{\mathrm{3}},{\omega }_{\mathrm{4}}]=\\ \left[\frac{\mathrm{5}\cdot {\mathrm{3}}^n+\mathrm{1}}{\mathrm{8}},\mathrm{0},\frac{{\mathrm{3}}^n-\mathrm{3}}{\mathrm{4}},\mathrm{1},\frac{{\mathrm{3}}^n-\mathrm{3}}{\mathrm{8}}\right]\end{array}；

2）若n>\mathrm{2}为偶数时，函数f(x)为6-差分一致性函数且差分谱为：

[{\omega }_{\mathrm{0}},{\omega }_{\mathrm{1}},{\omega }_{\mathrm{2}},{\omega }_{\mathrm{3}},{\omega }_{\mathrm{4}},{\omega }_{\mathrm{5}},{\omega }_{\mathrm{6}}]=\left[\frac{\mathrm{7}\cdot {\mathrm{3}}^{n-\mathrm{1}}-\mathrm{1}}{\mathrm{4}},\mathrm{0},\frac{{\mathrm{3}}^{n+\mathrm{1}}-\mathrm{3}}{\mathrm{8}},\mathrm{1},\mathrm{0},\mathrm{0},\frac{{\mathrm{3}}^{n-\mathrm{1}}-\mathrm{3}}{\mathrm{8}}\right].

（2） 当p=\mathrm{5}，n>\mathrm{2}时，设函数f(x)=x^{\mathrm{7}}的差分谱分布为[{\omega }_{\mathrm{0}},{\omega }_{\mathrm{1}},{\omega }_{\mathrm{2}},{\omega }_{\mathrm{3}},{\omega }_{\mathrm{4}},{\omega }_{\mathrm{5}},{\omega }_{\mathrm{6}}]，若n是4的倍数，则有{\omega }_{\mathrm{1}}=\mathrm{0},{\omega }_{\mathrm{3}}=\mathrm{0},{\omega }_{\mathrm{5}}=\mathrm{1}；若n不是4的倍数，则有{\omega }_{\mathrm{1}}=\mathrm{1},{\omega }_{\mathrm{3}}=\mathrm{0},{\omega }_{\mathrm{5}}=\mathrm{0}.

证明 对任意b\in {\mathbb{F}}_{p^n}，下面讨论差分方程

{(x+\mathrm{1})}^{\mathrm{7}}-x^{\mathrm{7}}=b（7）

在域中解的个数.

方程（7）展开为：

x^{\mathrm{6}}+\mathrm{3}{x}^{\mathrm{5}}+\mathrm{5}{x}^{\mathrm{4}}+\mathrm{3}{x}^{\mathrm{2}}+x+\frac{\mathrm{1}-b}{\mathrm{7}}=\mathrm{0},（8）

令x=y+\mathrm{1}，（8）等价于：

y^{\mathrm{6}}+\frac{\mathrm{5}}{\mathrm{4}}{y}^{\mathrm{4}}+\frac{\mathrm{3}}{\mathrm{16}}{y}^{\mathrm{2}}+\frac{\mathrm{1}-\mathrm{64}b}{\mathrm{448}}=\mathrm{0},（9）

设y^{\mathrm{2}}=z，\frac{\mathrm{1}-\mathrm{64}b}{\mathrm{448}}=c此时（9）化简为：

z^{\mathrm{3}}+\frac{\mathrm{5}}{\mathrm{4}}{z}^{\mathrm{2}}+\frac{\mathrm{3}}{\mathrm{16}}z+c=\mathrm{0}.（10）

当p>\mathrm{7}时，考虑方程（9）. 首先当b=\frac{\mathrm{1}}{\mathrm{64}}，即c=\mathrm{0}时，此时方程（10）的解就转化为考虑方程z^{\mathrm{2}}+\frac{\mathrm{5}}{\mathrm{4}}z+\frac{\mathrm{3}}{\mathrm{16}}=\mathrm{0}的解，方程z^{\mathrm{2}}+\frac{\mathrm{5}}{\mathrm{4}}z+\frac{\mathrm{3}}{\mathrm{16}}=\mathrm{0}的判别式\mathrm{\Delta }=\frac{\mathrm{13}}{\mathrm{16}}.

（1）当\chi (\mathrm{13})=\mathrm{1}时，方程（10）的解为z=\mathrm{0}，\frac{\pm \sqrt[]{\mathrm{13}}-\mathrm{5}}{\mathrm{8}}. 当\chi (\frac{\pm \sqrt[]{\mathrm{13}}-\mathrm{5}}{\mathrm{8}})只有一个等于1时，方程（9）有三个解；当都等于1时方程（9）有五个解；当都不等于1时，方程（9）只有零解.

（2）当\chi (\mathrm{13})=-\mathrm{1}时，方程（9）只有零解.

（3）当\chi (\mathrm{13})=\mathrm{0}时，方程（10）的解为z=\mathrm{0}，1，此时方程（9）有三个解.

当b\ne \frac{\mathrm{1}}{\mathrm{64}}时，方程（9）的解成对出现. 又因为方程（9）最高次数为6，因此差分方程（7）在{\mathbb{F}}_{p^n}（p>\mathrm{7}）上最多有6个解. 由此我们可知幂函数x^{\mathrm{7}}在{\mathbb{F}}_{p^n}（p>\mathrm{3}，p\ne \mathrm{7}）上的差分均匀度小于等于6.

下面考虑两种特殊情况：p=\mathrm{3}和p=\mathrm{5}.

情况1 当p=\mathrm{3}时方程（9）等价为：

y^{\mathrm{6}}-y^{\mathrm{4}}+\mathrm{1}-b=\mathrm{0},（11）

方程（10）等价为：

z^{\mathrm{3}}-z^{\mathrm{2}}+c=\mathrm{0}.（12）

当b=\mathrm{1}时即c=\mathrm{0}时，方程（11）变为y^{\mathrm{4}}(y^{\mathrm{2}}-\mathrm{1})=\mathrm{0}，则方程的解为y=\mathrm{0},\pm \mathrm{1}.

当b\ne \mathrm{1}（c\ne \mathrm{0}）时，方程（11）的解是成对出现的. 假设方程（12）在{\mathbb{F}}_{{\mathrm{3}}^n}中有一根为z_{\mathrm{0}}，由引理2可知：当方程

u^{\mathrm{2}}-u-\mathrm{2}{z}_{\mathrm{0}}=\mathrm{0}（13）

在{\mathbb{F}}_{{\mathrm{3}}^n}中有一根u_{\mathrm{0}}时，方程（12）在{\mathbb{F}}_{{\mathrm{3}}^n}中有根r=u_{\mathrm{0}}+z_{\mathrm{0}}. 方程（13）的判别式\mathrm{\Delta }=\mathrm{1}+\mathrm{2}{z}_{\mathrm{0}}，根据\chi (\mathrm{\Delta })的取值情况也即z_{\mathrm{0}}的取值情况，可以得到方程（12）在{\mathbb{F}}_{{\mathrm{3}}^n}中根的情况：

（1）当\mathrm{\Delta }=\mathrm{0}时z_{\mathrm{0}}=\mathrm{1}，则c=\mathrm{0}，矛盾；

（2）当\chi (\mathrm{\Delta })=-\mathrm{1}时方程（12）只有一根z_{\mathrm{0}}，当\chi (z_{\mathrm{0}})=\mathrm{1}时方程（11）有两个解，当\chi (z_{\mathrm{0}})=-\mathrm{1}时，方程（11）无解；

（3）当\chi (\mathrm{\Delta })=\mathrm{1}时，设u_{\mathrm{1}},u_{\mathrm{2}}是方程（13）的两个互异根，此时方程（12）有三个根z_{\mathrm{0}}，z_{\mathrm{0}}+u_{\mathrm{1}}，z_{\mathrm{0}}+u_{\mathrm{2}}. 假设有二重根，不妨设u_{\mathrm{1}}+z_{\mathrm{0}}=z_{\mathrm{0}}，那么u_{\mathrm{1}}=\mathrm{0}，则z_{\mathrm{0}}=\mathrm{0}，从而c=\mathrm{0}， 矛盾. 所以，当\chi (\mathrm{\Delta })=\mathrm{1}时，方程（12）有三个互异的根z_{\mathrm{0}}，z_{\mathrm{0}}+u_{\mathrm{1}}，z_{\mathrm{0}}+u_{\mathrm{2}}.

下面讨论方程（12）有三个互异根时的情况. 此时\chi (\mathrm{\Delta })=\chi (\mathrm{1}+\mathrm{2}{z}_{\mathrm{0}})=\mathrm{1}，且方程（12）的三个互异的根为z_{\mathrm{0}}，z_{\mathrm{1}}=z_{\mathrm{0}}+u_{\mathrm{1}}，z_{\mathrm{2}}=z_{\mathrm{0}}+u_{\mathrm{2}}. 由方程（13）可知u_{\mathrm{1}}=\frac{\mathrm{1}+\sqrt[]{\mathrm{1}+\mathrm{2}{z}_{\mathrm{0}}}}{\mathrm{2}}，u_{\mathrm{2}}=\frac{\mathrm{1}-\sqrt[]{\mathrm{1}+\mathrm{2}{z}_{\mathrm{0}}}}{\mathrm{2}}，则z_{\mathrm{1}}=\frac{\mathrm{1}+\mathrm{2}{z}_{\mathrm{0}}+\sqrt[]{\mathrm{1}+\mathrm{2}{z}_{\mathrm{0}}}}{\mathrm{2}}，z_{\mathrm{2}}=\frac{\mathrm{1}+\mathrm{2}{z}_{\mathrm{0}}-\sqrt[]{\mathrm{1}+\mathrm{2}{z}_{\mathrm{0}}}}{\mathrm{2}}. 令\sqrt[]{\mathrm{1}+\mathrm{2}{z}_{\mathrm{0}}}=t，那么z_{\mathrm{0}}=\frac{(t+\mathrm{1})(t-\mathrm{1})}{\mathrm{2}}，z_{\mathrm{1}}=\frac{t(t+\mathrm{1})}{\mathrm{2}}，z_{\mathrm{2}}=\frac{t(t-\mathrm{1})}{\mathrm{2}}.

（1）当n为大于1的奇数时，有\chi (\mathrm{2})=-\mathrm{1}. 此时当z_{\mathrm{0}}遍历{\mathbb{F}}_{p^n}\backslash \left\{\mathrm{0,1}\right\}时，t遍历{\mathbb{F}}_{p^n}\backslash \left\{\mathrm{0},\pm \mathrm{1}\right\}. z_{\mathrm{0}},z_{\mathrm{1}},z_{\mathrm{2}}这三个根是否为平方元由\chi (t)，\chi (t+\mathrm{1})，\chi (t-\mathrm{1})的取值决定，当t\in {\mathbb{F}}_{p^n}\backslash \left\{\mathrm{0},\pm \mathrm{1}\right\}时，它们所有的情况由表1给出：

如表所示，z_{\mathrm{0}},z_{\mathrm{1}},z_{\mathrm{2}}分为两种情况：（i）z_{\mathrm{0}},z_{\mathrm{1}},z_{\mathrm{2}}仅有两个为平方元；（ii）z_{\mathrm{0}},z_{\mathrm{1}},z_{\mathrm{2}}全为非平方元. 情况（i）出现时方程（11）有4个解，情况（ii）出现时方程（11）无解.

令T为表1中满足前6行条件的t构成的集合，N表示该集合包含的元素数目. 当t\in T时前述情况（i）出现，方程（11）有四个解. 利用二次特征和有：

\begin{array}{l}\mathrm{8}N=\sum _{t\in {\mathit{𝔽}}_{{\mathrm{3}}^n}\backslash \{\mathrm{0},\pm \mathrm{1}\}}(\mathrm{1}+\chi (t))(\mathrm{1}-\chi (t+\mathrm{1}))(\mathrm{1}+\chi (t-\mathrm{1}))+\sum _{t\in {\mathit{𝔽}}_{{\mathrm{3}}^n}\backslash \{\mathrm{0},\pm \mathrm{1}\}}(\mathrm{1}-\chi (t))(\mathrm{1}+\chi (t+\mathrm{1}))(\mathrm{1}-\chi (t-\mathrm{1}))\\ +\sum _{t\in {\mathit{𝔽}}_{{\mathrm{3}}^n}\backslash \{\mathrm{0},\pm \mathrm{1}\}}(\mathrm{1}+\chi (t))(\mathrm{1}+\chi (t+\mathrm{1}))(\mathrm{1}-\chi (t-\mathrm{1}))+\sum _{t\in {\mathit{𝔽}}_{{\mathrm{3}}^n}\backslash \{\mathrm{0},\pm \mathrm{1}\}}(\mathrm{1}-\chi (t))(\mathrm{1}-\chi (t+\mathrm{1}))(\mathrm{1}+\chi (t-\mathrm{1}))\\ +\sum _{t\in {\mathit{𝔽}}_{{\mathrm{3}}^n}\backslash \{\mathrm{0},\pm \mathrm{1}\}}(\mathrm{1}+\chi (t))(\mathrm{1}-\chi (t+\mathrm{1}))(\mathrm{1}-\chi (t-\mathrm{1}))+\sum _{t\in {\mathit{𝔽}}_{{\mathrm{3}}^n}\backslash \{\mathrm{0},\pm \mathrm{1}\}}(\mathrm{1}-\chi (t))(\mathrm{1}+\chi (t+\mathrm{1}))(\mathrm{1}+\chi (t-\mathrm{1}))\\ =\mathrm{2}\sum _{t\in {\mathit{𝔽}}_{{\mathrm{3}}^n}}\mathrm{1}-\mathrm{2}\sum _{t\in {\mathbb{F}}_{{\mathrm{3}}^n}}\chi (t^{\mathrm{2}}+t)-\mathrm{2}\sum _{t\in {\mathbb{F}}_{{\mathrm{3}}^n}}\chi (t^{\mathrm{2}}-\mathrm{1})+\mathrm{2}\sum _{t\in {\mathbb{F}}_{{\mathrm{3}}^n}}\chi (t^{\mathrm{2}}-t)-\mathrm{8}\\ +\mathrm{2}\sum _{t\in {\mathit{𝔽}}_{{\mathrm{3}}^n}}\mathrm{1}+\mathrm{2}\sum _{t\in {\mathbb{F}}_{{\mathrm{3}}^n}}\chi (t^{\mathrm{2}}+t)-\mathrm{2}\sum _{t\in {\mathbb{F}}_{{\mathrm{3}}^n}}\chi (t^{\mathrm{2}}-\mathrm{1})-\mathrm{2}\sum _{t\in {\mathbb{F}}_{{\mathrm{3}}^n}}\chi (t^{\mathrm{2}}-t)-\mathrm{8}\\ +\mathrm{2}\sum _{t\in {\mathit{𝔽}}_{{\mathrm{3}}^n}}\mathrm{1}-\mathrm{2}\sum _{t\in {\mathbb{F}}_{{\mathrm{3}}^n}}\chi (t^{\mathrm{2}}+t)+\mathrm{2}\sum _{t\in {\mathbb{F}}_{{\mathrm{3}}^n}}\chi (t^{\mathrm{2}}-\mathrm{1})-\mathrm{2}\sum _{t\in {\mathbb{F}}_{{\mathrm{3}}^n}}\chi (t^{\mathrm{2}}-t)-\mathrm{8},\end{array}

由引理1可得\mathrm{8}N=\mathrm{6}\times {\mathrm{3}}^n-\mathrm{18}，即N=\frac{\mathrm{3}\times {\mathrm{3}}^n-\mathrm{9}}{\mathrm{4}}.

因为\sqrt[]{\mathrm{1}+\mathrm{2}{z}_{\mathrm{0}}}=t即\mathrm{1}+\mathrm{2}{z}_{\mathrm{0}}=t^{\mathrm{2}}，可知\pm t对应同一个z_{\mathrm{0}}，且t\in T时有-t\in T及t\ne \mathrm{0}. 所以使得\chi (\mathrm{1}+\mathrm{2}{z}_{\mathrm{0}})=\mathrm{1}且情况（i）出现的z_{\mathrm{0}}个数是N的二分之一. 根据z_{\mathrm{0}}的任意性及关系式（12）知：（12）的三个互异的根z_{\mathrm{0}}，z_{\mathrm{0}}+u_{\mathrm{1}}，z_{\mathrm{0}}+u_{\mathrm{2}}对应同一个c，所以使得方程（11）有4个解的c的个数是前述z_{\mathrm{0}}数目的三分之一，即使得方程（11）有四个解的b的个数为\frac{N}{\mathrm{6}}=\frac{{\mathrm{3}}^n-\mathrm{3}}{\mathrm{8}}. 当n为大于1的奇数时，\frac{N}{\mathrm{6}}>\mathrm{0}.

故当n为大于1的奇数时幂函数x^{\mathrm{7}}在{\mathbb{F}}_{{\mathrm{3}}^n}上是4-差分一致性函数函数，设其差分谱为[{\omega }_{\mathrm{0}},{\omega }_{\mathrm{1}},{\omega }_{\mathrm{2}},{\omega }_{\mathrm{3}},{\omega }_{\mathrm{4}}]，前述讨论知：{\omega }_{\mathrm{4}}=\frac{{\mathrm{3}}^n-\mathrm{3}}{\mathrm{8}}，{\omega }_{\mathrm{3}}=\mathrm{1}（b=\mathrm{1}时）；当b\cancel{=}\mathrm{1}，此时方程（11）的解成对出现，所以{\omega }_{\mathrm{1}}=\mathrm{0}. 再由定义2的性质可计算出差分谱.

（2）当n为大于2的偶数时，有\chi (\mathrm{2})=\mathrm{1}，同理，根据\chi (t)，\chi (t+\mathrm{1})，\chi (t-\mathrm{1})的取值，z_{\mathrm{0}},z_{\mathrm{1}},z_{\mathrm{2}}的平方元分布情况如表2所示.

所以此时z_{\mathrm{0}},z_{\mathrm{1}},z_{\mathrm{2}}也只存在两种情况：（i）z_{\mathrm{0}},z_{\mathrm{1}},z_{\mathrm{2}}全为平方元；（ii）z_{\mathrm{0}},z_{\mathrm{1}},z_{\mathrm{2}}中仅有一个为平方元. 当出现情况（i）时方程（11）有六个解，当出现情况（ii）时方程（11）有两个解. 由此可知，当b\cancel{=}\mathrm{1}（c\cancel{=}\mathrm{0}）时，方程（11）可能的解数为2，6.

类似地，令T为表2中满足前2行条件的t构成的集合，N表示该集合包含的元素数目. 当t\in T时前述情况（i）出现，方程（11）有6个解. 令N=|T|，利用二次特征和有：

\begin{array}{l}\mathrm{8}N={\sum }_{t\in {\mathit{𝔽}}_{{\mathrm{3}}^n}\backslash \{\mathrm{0},\pm \mathrm{1}\}}(\mathrm{1}+\chi (t))(\mathrm{1}+\chi (t+\mathrm{1}))(\mathrm{1}+\chi (t-\mathrm{1}))+{\sum }_{t\in {\mathit{𝔽}}_{{\mathrm{3}}^n}\backslash \{\mathrm{0},\pm \mathrm{1}\}}(\mathrm{1}-\chi (t))(\mathrm{1}-\chi (t+\mathrm{1}))(\mathrm{1}-\chi (t-\mathrm{1}))\\ =\mathrm{2}\sum _{t\in {\mathit{𝔽}}_{{\mathrm{3}}^n}}\mathrm{1}+\mathrm{2}\sum _{t\in {\mathbb{F}}_{{\mathrm{3}}^n}}\chi (t^{\mathrm{2}}+t)+\mathrm{2}\sum _{t\in {\mathbb{F}}_{{\mathrm{3}}^n}}\chi (t^{\mathrm{2}}-\mathrm{1})+\mathrm{2}\sum _{t\in {\mathbb{F}}_{{\mathrm{3}}^n}}\chi (t^{\mathrm{2}}-t)-\mathrm{12},\end{array}

由引理1可得\mathrm{8}N=\mathrm{2}\times {\mathrm{3}}^n-\mathrm{18}，即N=\frac{{\mathrm{3}}^n-\mathrm{9}}{\mathrm{4}}.

同情况（1）的讨论类似，可知使得方程（12）有6个解的b的个数为\frac{N}{\mathrm{6}}=\frac{{\mathrm{3}}^{n-\mathrm{1}}-\mathrm{3}}{\mathrm{8}}. 当n为大于2的偶数时，\frac{N}{\mathrm{6}}>\mathrm{0}.

故当n为大于2的偶数时，函数f(x)为6-差分一致性函数且{\omega }_{\mathrm{6}}=\frac{{\mathrm{3}}^{n-\mathrm{1}}-\mathrm{3}}{\mathrm{8}}. 设其差分谱为[{\omega }_{\mathrm{0}},{\omega }_{\mathrm{1}}，{\omega }_{\mathrm{2}},{\omega }_{\mathrm{3}},{\omega }_{\mathrm{4}},{\omega }_{\mathrm{5}},{\omega }_{\mathrm{6}}]，前述讨论知：{\omega }_{\mathrm{6}}=\frac{{\mathrm{3}}^{n-\mathrm{1}}-\mathrm{3}}{\mathrm{8}}，{\omega }_{\mathrm{4}}=\mathrm{0}，{\omega }_{\mathrm{3}}=\mathrm{1}（b=\mathrm{1}时），{\omega }_{\mathrm{1}}=\mathrm{0}，{\omega }_{\mathrm{5}}=\mathrm{0}. 再由定义2的性质即可计算出差分谱.

情况2 当p=\mathrm{5}时，方程（9）可化简为：

y^{\mathrm{6}}+\mathrm{3}{y}^{\mathrm{2}}+\frac{\mathrm{1}+b}{\mathrm{3}}=\mathrm{0}.（14）

显然n>\mathrm{2}时，方程（14）的解至多为6，且当b\ne -\mathrm{1}时方程（14）的解成对出现. 当b=-\mathrm{1}时，方程（14）转化为y^{\mathrm{2}}(y^{\mathrm{4}}-\mathrm{2})=\mathrm{0}，下面讨论y^{\mathrm{4}}=\mathrm{2}的解.

设{\mathbb{F}}_{{\mathrm{5}}^n}的本原元为\alpha，则{\mathbb{F}}_{\mathrm{5}}的本原元可表示为{\alpha }^{\frac{{\mathrm{5}}^n-\mathrm{1}}{\mathrm{5}-\mathrm{1}}}，注意到2为{\mathbb{F}}_{\mathrm{5}}的本原元，不妨设{\alpha }^{\frac{{\mathrm{5}}^n-\mathrm{1}}{\mathrm{5}-\mathrm{1}}}=\mathrm{2}. 设y={\alpha }^i（i为任意整数），则方程y^{\mathrm{4}}=\mathrm{2}变形为({\alpha }^i{)}^{\mathrm{4}}={\alpha }^{\frac{{\mathrm{5}}^n-\mathrm{1}}{\mathrm{5}-\mathrm{1}}}，该方程等价于\mathrm{4}i\equiv \frac{{\mathrm{5}}^n-\mathrm{1}}{\mathrm{4}}\hspace{1em}\left(\mathrm{m}\mathrm{o}\mathrm{d}{\mathrm{5}}^n-\mathrm{1}\right). 所以当n为4的倍数时同余方程有四个解，进而方程（14）有5个解；当n不为4的倍数时同余方程无解. 因此，方程（14）有5个解时当且仅当4整除n，方程（14）有1个解时当且仅当4不整除n. 综上所述，当n>\mathrm{2}时，方程（14）在{\mathbb{F}}_{{\mathrm{5}}^n}上可能的解数为\{\mathrm{0,1},\mathrm{2,4},\mathrm{5,6}\}，其中解数1和5不同时出现，且仅在b=-\mathrm{1}时出现1次. 基于前述讨论可得：当n为4的倍数时，{\omega }_{\mathrm{1}}=\mathrm{0}，{\omega }_{\mathrm{5}}=\mathrm{1}；当n不为4的倍数时，{\omega }_{\mathrm{1}}=\mathrm{1},{\omega }_{\mathrm{5}}=\mathrm{0}. 当b\ne -\mathrm{1}时方程（14）的解成对出现，恒有{\omega }_{\mathrm{3}}=\mathrm{0}.

定理2证毕.

注^［14］：设F(x)=x^d和G(x)=x^e是{\mathbb{F}}_{p^n}上的幂函数，如果\mathrm{g}\mathrm{c}\mathrm{d}(d,p^n-\mathrm{1})=\mathrm{1}且e\equiv d^{-\mathrm{1}}(\mathrm{m}\mathrm{o}\mathrm{d}{p}^n-\mathrm{1})，即G(x)是F(x)的复合逆，则F(x)与G(x)有相同的差分谱. 原因如下所述：由F(x)的差分方程{(x+a)}^d-x^d=b可得x+a=(x^d{+b)}^{\mathrm{1}/d}. 令y=x^d，代入得a={(y+b)}^{\mathrm{1}/d}-y^{\mathrm{1}/d}，该方程即为G(x)的差分方程（输入差分为b，输出差分为a），故F(x)与G(x)差分方程解数的分布相同，从而具有相同的差分谱.

下面提供一些数值实验的结果来说明定理1和定理2的正确性.

例1 取p=\mathrm{7}，n=\mathrm{4}，利用Magma计算，{\mathbb{F}}_{{\mathrm{7}}^{\mathrm{4}}}上幂函数f(x)=x^{\mathrm{5}}的差分谱为：

[{\omega }_{\mathrm{0}},{\omega }_{\mathrm{1}},{\omega }_{\mathrm{2}},{\omega }_{\mathrm{3}},{\omega }_{\mathrm{4}}]=[\mathrm{1500},\mathrm{0},\mathrm{601},\mathrm{1},\mathrm{299}].

再取p=\mathrm{7}，n=\mathrm{3}，利用Magma计算{\mathbb{F}}_{{\mathrm{7}}^{\mathrm{3}}}上幂函数f(x)=x^{\mathrm{5}}差分谱为：

[{\omega }_{\mathrm{0}},{\omega }_{\mathrm{1}},{\omega }_{\mathrm{2}},{\omega }_{\mathrm{3}},{\omega }_{\mathrm{4}}]=[\mathrm{214},\mathrm{1},\mathrm{85},\mathrm{0},\mathrm{43}].

以上结果与利用定理1中的公式进行计算所得的结果是一致的.

例2 令p=\mathrm{3}，n=\mathrm{5}，利用Magma计算，{\mathbb{F}}_{{\mathrm{3}}^{\mathrm{5}}}上幂函数f(x)=x^{\mathrm{7}}的差分谱为：

[{\omega }_{\mathrm{0}},{\omega }_{\mathrm{1}},{\omega }_{\mathrm{2}},{\omega }_{\mathrm{3}},{\omega }_{\mathrm{4}}]=[\mathrm{152},\mathrm{0},\mathrm{60},\mathrm{1},\mathrm{30}].

再令p=\mathrm{3}，n=\mathrm{6}，利用Magma计算{\mathbb{F}}_{{\mathrm{3}}^{\mathrm{6}}}上幂函数f(x)=x^{\mathrm{7}}的差分谱为：

[{\omega }_{\mathrm{0}},{\omega }_{\mathrm{1}},{\omega }_{\mathrm{2}},{\omega }_{\mathrm{3}},{\omega }_{\mathrm{4}},{\omega }_{\mathrm{5}},{\omega }_{\mathrm{6}}]=[\mathrm{425},\mathrm{0},\mathrm{273},\mathrm{1},\mathrm{0},\mathrm{0},\mathrm{30}].

上述数值结果与定理2是相符的.

3 结论

对于有限域{\mathbb{F}}_{p^n}上两类低阶非线性幂函数x^{\mathrm{5}}和x^{\mathrm{7}}，本文通过研究差分方程{(x+\mathrm{1})}^d-x^d=b，在一定条件下刻画了差分方程具有特定解数时元素b满足的条件，再利用二次特征和求出满足条件的b的个数，从而确定了{\mathbb{F}}_{p^n}上幂函数x^{\mathrm{5}}（其中p>\mathrm{2},p\ne \mathrm{5}）和{\mathbb{F}}_{{\mathrm{3}}^n}上幂函数x^{\mathrm{7}}的差分谱. 当\mathrm{g}\mathrm{c}\mathrm{d}(d,p^n-\mathrm{1})=\mathrm{1}，幂函数x^d和其复合逆x^{\mathrm{1}/d}具有相同的差分均匀度和差分谱，所以本文所得结果也相应地给出了幂函数x^{\mathrm{1}/\mathrm{5}}和x^{\mathrm{1}/\mathrm{7}}的差分性质. 以上两类低阶非线性幂函数作为轮函数或S盒用于构造面向算术的Hash函数时，本文所得结果可以很好地评估他们抵抗差分攻击的性能. 本文的方法未能解决p>\mathrm{3}时{\mathbb{F}}_{p^n}上幂函数x^{\mathrm{7}}的差分谱，欢迎感兴趣的读者解决这一遗留问题.

参考文献

[1] ALBRECHT M， GRASSI L， RECHBERGER C， et al. MiMC： Efficient encryption and cryptographic hashing with minimal multiplicative complexity［M］Berlin： Springer， 2016.

[2] ALY A， ASHUR T， BEN-SASSON E， et al. Design of symmetric-key primitives for advanced cryptographic protocols［J］. IACR Transactions on Symmetric Cryptology， 2020：1-45.

[3] SZEPIENIEC A， ASHUR T， DHOOGHE S. Rescue-prime： A standard specification （SoK）［J］. IACR Cryptol EPrint Arch， 2020：1143.

[4] BARBARA M， GRASSI L， KHOVRATOVICH D， et al. Reinforced concrete： Fast hash function for zero knowledge proofs and verifiable computation［J］. IACR Cryptol EPrint Arch， 2021：1038.

[5] AUMASSON J P， NEVES S， WILCOX-O’HEARN Z， et al. BLAKE2： simpler， smaller， fast as MD5［M］Berlin： Springer， 2013.

[6] BOUVIER C， BRIAUD P， CHAIDOS P， et al. New design techniques for efficient arithmetization-oriented hash functions［C］//Annual International Cryptology Conference. Cham： Springer， 2023： 507-539.

[7] GRASSI L， KHOVRATOVICH D， RECHBERGER C， et al. Poseidon： A new hash function for Zero-Knowledge proof systems［C］//30th USENIX Security Symposium.Vancouver：ACM： 2021： 519-535.

[8] GOLDWASSER S， MIT， MICALI S， et al. The knowledge complexity of interactive proof-systems［M］Micali： Association for Computing Machinery， 2019.

[9] BLONDEAU C， CANTEAUT A， CHARPIN P. Differential properties of power functions［C］//2010 IEEE International Symposium on Information Theory. Austin：IEEE， 2010： 2478-2482.

[10] NYBERG K. Differentially uniform mappings for cryptography［C］//Workshop on the Theory and Application of Cryptographic Techniques. Berlin： Springer， 1993： 55-64.

[11] XIA Y， ZHANG X， LI C， et al. The differential spectrum of a ternary power mapping［J］. Finite Fields and Their Applications， 2020， 64：101660.

[12] LIDL R， NIEDERREITER H. Finite fields［M］. Cambridge： Cambridge university press， 1997.

[13] 孙宗明， 牟兴祥， 李振国. 3 k 元域上的三次方程根的简况［J］. 广西师院学报（自然科学版）， 1995（2）： 32-34.

[14] BLONDEAU C， CANTEAUT A， CHARPIN P. Differential properties of power functions［C］//2010 IEEE International Symposium on Information Theory. Austin： IEEE， 2010： 2478-2482.

基金资助

国家自然科学基金资助项目(62171479)

中央高校基本科研业务费专项资金资助项目(CZZ23004)