有限域上高次方程的解在编码、序列和密码函数等多个方向的研究中发挥着重要的作用, 近年来得到了学者们的广泛关注和研究. 设$ k $为奇素数, $ n=2k $, 文献[1]利用Dickson多项式发明了一种新方法, 结合Niho的相关定理, 分析了方程
在有限域$ \mathbb{F}_{2^{n}} $上的解, 研究了长度为$ 2^{n}-1 $的二进制$ m $序列之间的互相关函数$ C_{d}(\tau) $, 其中抽选指数$ d $为Niho型. 针对一类特定的$ d $ (即$ s=3 $, $ d=3\cdot2^{k}-2 $) 计算了函数$ f^{\ast}_{d}(y) $的六值互相关分布. 文献[2]对方程$ A_{a}(v)=a^{2}v^{2^{l}}+v^{2}+av+1=0 $在有限域$ \mathbb{F}_{2^{k}} $中解的分布以及方程$ L_{a}(z)=z^{2^{k+l}}+r^{2^{l}}a^{2^{l}}z^{2^{2^{l}}}+raz=0 $在有限域$ \mathbb{F}_{2^{m}} $中解的个数进行分析, 研究了长度为$ 2^{m}-1 $的二进制$ m $序列与长度为$ 2^{k}-1 $的二进制$ m $序列之间的互相关函数, 其中$ m=2k $, $ k,\; l $均为奇数, $ \gcd(l,k)=1 $, $ r $是$ \mathbb{F}_{2^{m}} $中的非立方元, 且$ r^{2^{k}+1}=1 $. 证明了当$ d(2^{l}+1)\equiv2^{l}(\text{mod} 2^{k}-1) $时, 互相关函数为三值. 文献[3]通过对方程
以及方程
解的情况进行分析, 提出了一个新的三重纠错码三元组, 并为已知的Kasami三元组提供了新的、更简洁的证明. 文献[4]分析了方程
和方程
对Dillon提出的差分一致性$ \leq4 $的六项式形式的二次函数的构造进行推广, 提出了更一般的二次多项式形式, 并提出了新的三项式APN函数族和六项式APN函数族. 文献[5]刻画了方程
在有限域$ \mathbb{F}_{2^{n}} $上无解的充要条件, 其中$ a\in\mathbb{F}^{\ast}_{2^{n}} $, $ n=2k $, $ \gcd(n,i)=1 $. 运用该结论构造了一类新的无限族APN函数, 证明了文献[4]提出的六项式APN函数族的存在性.
有限域上一般高次方程解的研究是困难的, 但学者们在此方向仍取得了很多重要成果. 文献[6]刻画出了奇特征有限域$ \mathbb{F}_{p^n} $上变元$ x,y,z $的方程
和变元$ x,y,z,t $的方程
的解数公式. 在上文的基础上, Baoulina对奇特征有限域$ \mathbb{F}_{p^{n}} $上方程
进行了分析. 令$ d=\gcd(r-2,\frac{p^{n}-1}{2}) $. Baoulina在文献[7]给出了方程(1.1) 在$ d=1 $时和$ d=2 $时的解数公式. 在文献[8]中他又确定了方程(1.1) 在正整数$ l $满足$ 2d\mid(p^{l}+1) $时的解数公式, 还给出了$ d=4 $且$ p\not\equiv 7\pmod8 $时方程的解数公式. 在文献[9]中他又以高次对角方程$ a_{1}x_{1}^{m_{1}}+\cdot\cdot\cdot+a_{n}x_{r}^{m_{r}}=0 $的解数和一些特征和为基础, 给出了$ \mathbb{F}_{q} $上的方程
在指数$ m_1,m_2,\cdots, m_r $满足特定条件时的解数公式. Bluher在文献[10]中系统地研究了有限域$ \mathbb{F} $上形如$ f(x)=x^{q+1}+ax+b $的多项式, 完整刻画了其在$ \mathbb{F} $中有理根个数的可能取值, 并给出每种情况的等价算数条件和计数公式, 其中$ ab\neq0 $, 有限域$ \mathbb{F} $特征为$ p $, $ q $是$ p $的方幂. 文献[11]通过巧妙分拆问题、深入利用MCM与Dickson多项式的性质, 并结合有限域中的显式求解技巧, 彻底解决了$ P_{a}(x)=x^{2^{k}+1}+x+a $在$ \gcd(n,k)=1 $条件下的求根问题. 该文献不仅给出了所有根的显式表达式, 还完成了零点个数的完整分类, 统一并推广了前人结果. 直到现在, 有限域上高次方程解的问题仍有很多学者进行研究并得到了很多优秀的结果, 如胡双年[12], 王文松和孙琦[13]等学者也给出了有限域上一些高次方程在特定条件下的解数公式.
本文研究了有限域$ \mathbb{F}_{2^{3m}} $上的方程
分析了方程的根的个数的可能取值, 并给出每种情况下系数$ a $, $ b $所要满足的条件, 其中$ a,b\in\mathbb{F}^{\ast}_{2^{3m}} $. 文章的结构如下: 第二节介绍本文所涉及的概念、符号及相关定理, 并证明后文所需要的引理. 第三节对方程进行分析, 证明方程的可能解数, 并给出每种情况下系数$ a $, $ b $的对应条件. 最后对文章进行总结.
设$ p $为素数, $ n $为正整数, $ \mathbb{F}_{p^{n}} $表示具有$ p^{n} $个元素的有限域, 后文中也用符号$ GF(p^{n}) $表示具有$ p^{n} $个元素的有限域. $ \mathbb{F}^{\ast}_{p^{n}}=\mathbb{F}_{p^{n}}\setminus\{0\} $表示由有限域$ \mathbb{F}_{p^{n}} $的非零元素构成的乘法群.
定义2.1[14, Definition 2.22] 对$ \alpha\in F=\mathbb{F}_{p^{n}} $, $ K=\mathbb{F}_{p} $, 定义$ \alpha $的迹$ Tr_{F/K}(\alpha) $为
定义2.2[14, Definition 2.27] 设$ \alpha\in F=\mathbb{F}_{p^{n}} $, $ K=\mathbb{F}_{p} $. 定义$ K $上$ \alpha $的范数$ N_{F/K}(\alpha) $为
定理2.1[10, Theorem 5.6, Table 2] 设$ F $是特征为$ p $的有限域, $ q $是$ p $的幂方, $ F\cap GF(q)=GF(Q) $. 令$ N_{i} $为满足$ f_{b}(x)=x^{q+1}-bx+b $在$ F $上有$ i $个解的$ b $的个数, 其中$ i\in\{0,1,2,Q+1\} $, $ b\in F^{\ast} $. 定义$ m=[F:GF(Q)] $, 若$ q $为偶数且$ m $为奇数, 则
且当$ f_{b}(x) $有$ Q+1 $个解时, $ f_{b}(x) $的根$ x $均满足$ N_{F/GF(Q)}(x-1)=1 $.
引理2.1 设$ F=\mathbb{F}_{2^{3m}} $, $ q=2^{m} $, $ F\cap GF(q)=GF(Q)=GF(2^{m}) $. 令$ g_{b}(x)=x^{2^{m}+1}+bx+b\in\mathbb{F}_{2^{3m}}[x] $, 其中$ b\in F^{\ast} $. 则$ g_{b}(x) $有$ 2^{m}+1 $个解当且仅当$ b=1 $, 此时$ g_{b}(x) $的根均可开$ 2^{m}-1 $次幂.
证 设$ a\in\mathbb{F}^{\ast}_{2^{3m}} $是方程$ x^{2^{2m}}+x^{2^{m}}+x=0 $的一个非零根, 则$ a $满足
故该非零根$ a $所对应的$ a^{2^{m}-1} $满足方程$ y^{2^{m}+1}+y+1=0 $. 当方程$ x^{2^{2m}}+x^{2^{m}}+x=0 $有$ 2^{2m}-1 $个不同的非零根时, 若非零$ b,d $均满足方程$ x^{2^{2m}}+x^{2^{m}}+x=0 $且$ b^{2^{m}-1}=d^{2^{m}-1} $, 则$ (\frac{b}{d})^{2^{m}-1}=1 $, $ b=k\cdot d $, $ k\in\mathbb{F}^{\ast}_{2^{m}} $, 即满足$ x^{2^{2m}}+x^{2^{m}}+x=0 $的非零根$ a $, 每$ 2^{m}-1 $个不同的非零$ a $, 对应同一个$ a^{2^{m}-1} $. 有$ 2^{2m}-1 $个不同的非零根$ a $满足$ x^{2^{2m}}+x^{2^{m}}+x=0 $, 所以有$ \frac{2^{2m}-1}{2^{m}-1}=2^{m}+1 $个不同的$ a^{2^{m}-1} $满足方程$ y^{2^{m}+1}+y+1=0 $. 因此, 方程$ y^{2^{m}+1}+y+1=0 $有$ 2^{m}+1 $个不同根, 且每个根均可表示为$ a^{2^{m}-1} $的形式, 即每个根均可开$ 2^{m}-1 $次幂.
由定理2.1, $ q=2^{m} $为偶数, $ [F:GF(Q)]=[\mathbb{F}_{2^{3m}}:\mathbb{F}_{2^{m}}]=3 $为奇数, 当$ g_{b}(x) $有$ 2^{m}+1 $个解时, 满足条件的$ b $的个数$ N_{2^{m}+1}=\frac{(2^{m})^{3-1}-1}{(2^{m})^{2}-1}=1 $, 即仅有1个$ b\in F^{\ast} $使得$ g_{b}(x)=x^{2^{m}+1}+bx+b $有$ 2^{m}+1 $个解. 又由上述证明知, 方程$ y^{2^{m}+1}+y+1=0 $有$ 2^{m}+1 $个解. 故$ g_{b}(x) $有$ 2^{m}+1 $个解当且仅当$ b=1 $, 此时$ g_{b}(x) $的根均可开$ 2^{m}-1 $次幂.
定理2.2[14, pp. 361] 设$ \mathbb{F}_{p} $和$ \mathbb{F}_{p^{n}} $是分别有$ p $和$ p^{n} $个元素的有限域. 令$ f(x)=a_{0}x+a_{1}x^{p}+\cdot\cdot\cdot+a_{n-1}x^{p^{n-1}} $是从$ \mathbb{F}_{p^{n}} $到$ \mathbb{F}_{p^{n}} $的一个线性化多项式. 定义
则$ f:\; \mathbb{F}_{p^{n}}\rightarrow \mathbb{F}_{p^{n}} $是一个置换多项式当且仅当$ detA(f)\neq0 $.
基于上述预备知识, 本节将对方程$ x^{2^{2m}}+ax^{2^{m}}+bx=0 $在有限域$ \mathbb{F}_{2^{3m}} $上解的情况进行分析.
定理3.1 设$ m $为正整数, 令方程$ x^{2^{2m}}+ax^{2^{m}}+bx=0 $在有限域$ \mathbb{F}_{2^{3m}} $上解的个数为$ N(a,b) $, 则
其中$ a,b\in\mathbb{F}^{\ast}_{2^{3m}} $, $ E=\mathbb{F}_{2^{3m}} $, $ H=\mathbb{F}_{2^{m}} $.
证 $ f(x)=x^{2^{2m}}+ax^{2^{m}}+bx $是有限域$ \mathbb{F}_{2^{3m}} $上的线性化多项式, 设方程$ x^{2^{2m}}+ax^{2^{m}}+bx=0 $解的个数$ N(a,b)=2^{i} $, $ 0\leq i\leq2m $, $ i $为整数.
显然$ x=0 $是方程$ x^{2^{2m}}+ax^{2^{m}}+bx=0 $的解. 当$ x\neq0 $时, 原方程化为
此时方程(2.1) 解的个数为$ 2^{i}-1 $, $ 0\leq i\leq2m $, $ i $为整数.
令$ z=x^{2^{m}-1} $, 方程(2.1) 转化为
由$ z=x^{2^{m}-1} $, 若方程(2.2) 的解$ z_{0} $可开$ 2^{m}-1 $次方, 则$ x_{0}=\sqrt[2^{m}-1]{z_{0}} $是方程(2.1) 的解. 且由$ \gcd(2^{m}-1,2^{3m}-1)=2^{m}-1 $知, 一个$ z_{0} $对应$ 2^{m}-1 $个不同的$ x_{0} $是方程(2.1) 的解.
不妨设方程(2.2) 有$ k $个不同的解$ z_{0} $可开$ 2^{m}-1 $次方, 则方程(2.1) 对应有$ (2^{m}-1)k $个不同的解$ x_{0} $. 前面已知方程(2.1) 解的个数为$ 2^{i}-1 $, 则$ 2^{i}-1=(2^{m}-1)k $, 可知$ i $必须满足$ 2^{m}-1\mid2^{i}-1 $. 又因为$ 0\leq i\leq2m $, 且$ i $为整数, 所以$ i $的可能取值只有$ 0,m,2m $. 因此方程$ x^{2^{2m}}+ax^{2^{m}}+bx=0 $解的个数$ N(a,b)=2^{i} $, $ i\in\{0,m,2m\} $.
下面证明方程$ x^{2^{2m}}+ax^{2^{m}}+bx=0 $分别有$ 2^{2m} $个, $ 1 $个以及$ 2^{m} $个解时系数$ a,b $满足的条件.
$ N(a,b)=2^{2m} $时, 方程(2.1) 有$ 2^{2m}-1 $个解. 由$ z $与$ x $的对应关系知, 此时方程(2.2) 有$ \frac{2^{2m}-1}{2^{m}-1}=2^{m}+1 $个不同的解$ z $. 令$ z=\frac{b}{a}y $, 方程(2.2) 化为$ \frac{b^{2^{m}+1}}{a^{2^{m}+1}}y^{2^{m}+1}+by+b=0 $. 方程两边同乘$ \frac{a^{2^{m}+1}}{b^{2^{m}+1}} $得
由$ z=\frac{b}{a}y $知, 方程(2.3) 此时也有$ 2^{m}+1 $个不同的解$ y_{0} $. 由引理2.1知, 方程(2.3) 有$ 2^{m}+1 $个解当且仅当$ \frac{a^{2^{m}+1}}{b^{2^{m}}}=1 $, 则$ a^{2^{m}+1}=b^{2^{m}} $, 两边同时$ 2^{2m} $次幂得$ b^{2^{3m}}=a^{2^{3m}+2^{2m}} $. 又因为$ a,b\in\mathbb{F}^{\ast}_{2^{3m}} $, 所以$ b=a^{2^{2m}+1} $. 由两次变量替换$ x^{2^{m}-1}=z=\frac{b}{a}y $知, 只有$ \frac{b}{a}y_{0} $可开$ 2^{m}-1 $次幂时, 对应的$ x_{0}=\sqrt[2^{m}-1]{\frac{b}{a}y_{0}} $为方程(2.1) 的解. 由引理2.1知, 此时方程(2.3) 的解$ y_{0} $均可开$ 2^{m}-1 $次幂, 因此$ \frac{b}{a} $也要满足可开$ 2^{m}-1 $次幂, 即$ (\frac{b}{a})^{\frac{2^{3m}-1}{2^{m}-1}}=1 $. 将上面$ b=a^{2^{2m}+1} $代入得$ (a^{2^{2m}})^{\frac{2^{3m}-1}{2^{m}-1}}=(a^{\frac{2^{3m}-1}{2^{m}-1}})^{2^{2m}}=1 $, 两边同时$ 2^{m} $次幂得$ (a^{\frac{2^{3m}-1}{2^{m}-1}})^{2^{3m}}=a^{\frac{2^{3m}-1}{2^{m}-1}}=1 $, 此时$ \frac{b}{a}y_{0} $可开$ 2^{m}-1 $次幂. 因此$ a,b $满足$ a^{\frac{2^{3m}-1}{2^{m}-1}}=N_{E/H}(a)=1 $及$ b=a^{2^{2m}+1} $时, $ N(a,b)=2^{2m} $, 其中$ E=\mathbb{F}_{2^{3m}} $, $ H=\mathbb{F}_{2^{m}} $.
$ N(a,b)=1 $时, 方程$ x^{2^{2m}}+ax^{2^{m}}+bx=0 $仅有一个解$ x=0 $. 方程$ x^{2^{2m}}+ax^{2^{m}}+bx=0 $两边同时$ 2^{m} $次幂得$ x+a^{2^{m}}x^{2^{2m}}+b^{2^{m}}x^{2^{m}}=0 $, 对此式两边再同时$ 2^{m} $次幂得$ x^{2^{m}}+a^{2^{2m}}x+b^{2^{2m}}x^{2^{2m}}=0 $. 将三个方程联立后可表示为如下矩阵乘法形式:
令
由定理2.2知, 方程仅有零解当且仅当$ det(A)\neq0 $, 即$ det(A)=(a^{2^{2m}}b^{2^{m}}+1)+a(a^{2^{m}}\cdot a^{2^{2m}}+b^{2^{2m}})+b(a^{2^{m}}+b^{2^{m}}\cdot b^{2^{2m}})=1+ab^{2^{2m}}+a^{2^{m}}b+a^{2^{2m}}b^{2^{m}}+a^{2^{2m}+2^{m}+1}+b^{2^{2m}+2^{m}+1}\neq0 $. 由定义2.1及定义2.2, $ Tr_{E/H}(ab^{2^{2m}})=ab^{2^{2m}}+(ab^{2^{2m}})^{2^{m}}+(ab^{2^{2m}})^{2^{2m}}=ab^{2^{2m}}+a^{2^{m}}b+a^{2^{2m}}b^{2^{m}} $, $ N_{E/H}(a)=a^{\frac{(2^{m})^{3}-1}{2^{m}-1}}=a^{2^{2m}+2^{m}+1} $, $ N_{E/H}(b)=b^{2^{2m}+2^{m}+1} $, 所以$ det(A)=Tr_{E/H}(ab^{2^{2m}})+N_{E/H}(a)+N_{E/H}(b)+1 $, 其中$ E=\mathbb{F}_{2^{3m}} $, $ H=\mathbb{F}_{2^{m}} $. 因此$ a,b $满足$ Tr_{E/H}(ab^{2^{2m}})+N_{E/H}(a)+N_{E/H}(b)+1\neq0 $时, $ N(a,b)=1 $.
由于方程$ x^{2^{2m}}+ax^{2^{m}}+bx=0 $解的个数的可能取值只有$ 2^{2m} $, $ 1 $及$ 2^{m} $. 因此当$ a,b $不满足$ N_{E/H}(a)=1 $, $ b=a^{2^{2m}+1} $及$ Tr_{E/H}(ab^{2^{2m}})+N_{E/H}(a)+N_{E/H}(b)+1\neq0 $时, $ N(a,b)=2^{m} $.
注: 当$ a,b $满足$ N_{E/H}(a)=a^{\frac{2^{3m}-1}{2^{m}-1}}=1, b=a^{2^{2m}+1} $时, $ N_{E/H}(b)=N_{E/H}(a^{2^{2m}+1})=(a^{2^{2m}+1})^{\frac{2^{3m}-1}{2^{m}-1}}=(a^{\frac{2^{3m}-1}{2^{m}-1}})^{2^{2m}+1}=1^{\frac{2^{3m}-1}{2^{m}-1}}=1 $, $ Tr_{E/H}(ab^{2^{2m}})=Tr_{E/H}(a^{2^{4m}+2^{2m}+1})=Tr_{E/H}(a^{2^{2m}+2^{m}+1})=Tr_{E/H}(a^{\frac{2^{3m}-1}{2^{m}-1}})=Tr_{E/H}(1)=1 $, 则$ Tr_{E/H}(ab^{2^{2m}})+N_{E/H}(a)+N_{E/H}(b)+1=0 $.
例1: 令$ m=1 $, $ z $为有限域$ \mathbb{F}_{2^{3}} $的本原元. 取$ a=z^{2},\; b=z^{4} $时, 通过Magma计算方程$ x^{4}+z^{2}x^{2}+z^{4}x=0 $在有限域$ \mathbb{F}_{2^{3}} $上仅有1个解$ x=0 $. 此时$ Tr_{E/H}(ab^{4})+N_{E/H}(a)+N_{E/H}(b)+1=1 $符合条件$ Tr_{E/H}(ab^{2^{2m}})+N_{E/H}(a)+N_{E/H}(b)+1\neq0 $. 取$ a=1,\; b=1 $时, 通过Magma计算方程$ x^{4}+x^{2}+x=0 $在有限域$ \mathbb{F}_{2^{3}} $上有4个解. 此时$ N_{E/H}(a)=N_{E/H}(1)=1,\; a^{2^{2}+1}=1=b $符合条件$ N_{E/H}(a)=1,\; b=a^{2^{2m}+1} $. 取$ a=z^{2},\; b=z $时, 通过Magma计算方程$ x^{4}+z^{2}x^{2}+zx=0 $在有限域$ \mathbb{F}_{2^{3}} $上有2个解. 此时$ N_{E/H}(a)=N_{E/H}(b)=Tr_{E/H}(ab^{4})=1,\; a^{2^{2}+1}=z^{3}\neq b,\; Tr_{E/H}(ab^{4})+N_{E/H}(a)+N_{E/H}(b)+1=0 $不满足$ b=a^{2^{2m}+1} $以及$ Tr_{E/H}(ab^{2^{2m}})+N_{E/H}(a)+N_{E/H}(b)+1\neq0 $. 实验所得结果与论文结论一致.
例2: 令$ m=3 $, $ z $为有限域$ \mathbb{F}_{2^{9}} $的本原元. 取$ a=z^{31},\; b=z^{32} $时, 通过Magma计算方程$ x^{64}+z^{31}x^{8}+z^{32}x=0 $在有限域$ \mathbb{F}_{2^{9}} $上仅有1个解$ x=0 $. 此时$ Tr_{E/H}(ab^{4})+N_{E/H}(a)+N_{E/H}(b)+1=z^{3} $符合条件$ Tr_{E/H}(ab^{2^{2m}})+N_{E/H}(a)+N_{E/H}(b)+1\neq0 $. 取$ a=z^{126},\; b=z^{14} $时, 通过Magma计算方程$ x^{64}+z^{126}x^{8}+z^{14}x=0 $在有限域$ \mathbb{F}_{2^{9}} $上有64个解. 此时$ N_{E/H}(a)=1,\; a^{2^{6}+1}=z^{14}=b $符合条件$ N_{E/H}(a)=1,\; b=a^{2^{2m}+1} $. 取$ a=z^{64},\; b=z^{12} $时, 通过Magma计算方程$ x^{64}+z^{64}x^{8}+z^{12}x=0 $在有限域$ \mathbb{F}_{2^{9}} $上有8个解. 此时$ N_{E/H}(a)=z,\; a^{2^{6}+1}=z^{72}\neq b,\; Tr_{E/H}(ab^{4})+N_{E/H}(a)+N_{E/H}(b)+1=0 $不满足$ N_{E/H}(a)=1,\; b=a^{2^{2m}+1} $以及$ Tr_{E/H}(ab^{2^{2m}})+N_{E/H}(a)+N_{E/H}(b)+1\neq0 $. 实验所得结果与论文结论一致.
本文分析了有限域上一类高次方程解的个数, 并刻画了方程有相应解数时系数$ a,b $所要满足的条件. 本文利用变量代换对方程形式进行转化, 通过不同形式方程解的个数之间的关系确定原方程解的个数, 再通过Bluher论文相关结论刻画了$ a,b $需要满足的条件. 本文所得结论可推广到一般的奇特征有限域上, 证明过程类似因此未重复证明. 遗憾的是本文未能根据系数$ a,b $对所要满足的条件求解出相应$ a,b $对的个数, 后续我们也将继续深入研究, 旨在完整刻画出满足相应解数时对应$ a,b $对的个数.