矩阵环上的零差分平衡函数*

易宗向,余玉银

1.广州大学 数学与信息科学学院,广州 510006

2.广东科技学院,东莞 523083

1 引言

设(A,+)和(B,+)是两个有限的阿贝尔群,一个从A到B的函数f称为是一个(n,m,λ)零差分平衡(zero-difference balanced,ZDB)函数,如果对任意的a∈A{0} 都有

|{x∈A|f(x+a)−f(x)=0}|=λ

其中n=|A|,m=|Im(f)|,λ为常数.

Ding[1]在2008年首先提出了ZDB 函数的概念,并利用ZDB 函数构造了最优的常重复合码(constant composition code,CCC),也就是如果存在(n,m,λ)ZDB 函数,就一定可以构造最优的(n,n,n−λ)CCCs[1].紧接着在2009年,Ding 利用ZDB 函数构造了最优的完美的集合差系统(difference systems of sets,DSS),也就是如果存在(n,m,λ)ZDB 函数,就可能构造(n,{rb|b∈B},n−λ)最优的完美的DSSs,其中rb={x∈A|f(x)=b}[2].在2012年,Zhou 等人利用ZDB 函数构造最优的等重码(constant weight code,CWC),也就是如果存在(n,m,λ)ZDB 函数,就可能构造最优的(n,n,n−λ)CWCs[3].在2014年,Wang 等人利用ZDB 函数,构造了最优的跳频序列(frequency-hopping sequence,FHS),也就是如何存在(n,m,λ)ZDB 函数,就可能构造最优的(n,m,λ)FHSs[4].CCC、CWC、DSS 以及FHS 在通信和组合等领域都有重要应用,因此随后有很多学者一直在研究如何构造更多的ZDB 函数[2–12].表1 给出了一些已知的ZDB 函数的参数.

最早Carlet 等人在2004年[13]通过完全非线性(perfect nonlinear,PN)函数构造了一类ZDB 函数,同时指出了划分差族(partition difference family,PDF)和ZDB 函数的等价性.接着Ding 在2009年[2]分别采用有限域上的特征和以及GMW 序列构造了三类ZDB 函数,并在2012年[5]以群的特征、差集、置换、迹函数、有限域上的幂函数等构造了一些参数简单的ZDB 函数,同时给出了从Zn到自身的多项式为ZDB 函数的充要条件,更重要的是还给出了ZDB 函数在差族(difference family,DF)和集合差系统(difference system of sets,DSS)的应用.同在2012年,Zhou 等人[3]使用线性方程组,基于差分平衡函数和d-form 函数构造了两类ZDB 函数,同时将ZDB 函数用于构造等重码(constant weight code,CWC).他们所构造的ZDB 函数大部分利用了具有差分平衡性质的函数,而这样的有用函数是比较少的.2014年Wang 等[4]给出了ZDB 函数的两个界,并使用参数化的方法给出了一类ZDB 函数.在此基础上,他们还给出了利用ZDB 函数构造最优跳频序列上的方法.早期构造ZDB 函数的方法比较繁杂,有些构造方法还需要依赖其他对象,比如PN 函数、差族、差分平衡函数和d-form 函数等.

最近用得比较多的构造方法是采用分圆陪集.2013年Cai 等人[6]采用广义分圆类的方法在Zn上构造了一类ZDB 函数.随后在2014年Ding 等人[7]在有限域直积环上也构造了一类ZDB 函数.同时对n=2m−1,在Zn上构造了一类ZDB 函数.紧接着在2015年Zha 等人[8]使用简洁的方法对Cai 等人[6]在Zn上的结果进行了解释,并对n=构造了一类ZDB 函数.特别地,Zha 等人在Zp×Zp上采用相同的思想构造了另一类ZDB 函数.使用分圆陪集在Zn上构造ZDB 函数要求n为奇数.在2018年,Yi 等人[12]将前面两类ZDB 函数推广到抽象的代数环上,并给出了在环上利用分圆陪集构造ZDB 函数的条件,并对两个代数整数环给出了具体的构造方法.本文以Yi 等人的方法为基础,在有限域的矩阵环上,讨论满足文献[12]中条件的循环群的生成元的情况.这种构造是具有理论意义的,因为之前的ZDB 函数都是在交换环上的构造.

本文组织如下:第2 节介绍需要用到的基本知识;第3 节首先给出给出Yi 等人[12]的方法,然后在矩阵环上构造ZDB 函数;第4 节展示如何使用ZDB 函数来构造其他对象;第5 节是本文的总结.

表1 已知的(n, m, λ)ZDB 函数Table 1 Some known(n, m, λ)ZDB functions

2 预备知识

2.1 符号说明

除非特别说明,本文中的所有环(R,+,×)都是含有乘法单位元1 的.(R,×)中的所有可逆元记为R×,R中的所有非零元记为R∗.对任意的a∈R×,满足ak=1 的最小正整数k记为OrdR(a),或者Ord(a).对于R的任意一个子集A和R的任意一个元素a,定义

以及

所有的整数集合记为Z,所有的自然数集合记为N,所有的正整数集合记为Z+.含有q=ps个元素的有限域记为Fq.

关于矩阵,有限域Fq上的所有n阶方阵的集合记为Mn(Fq).显然Mn(Fq)带上普通的矩阵加法和矩阵乘法,可以构成一个非交换环,称为矩阵环.在不引起歧义的情况下,Mn(Fq)也记为Mn(q),或者Mn.Mn(Fq)中所有的可逆矩阵在矩阵乘法下构成一个群,记为GLn(q).

2.2 矩阵环的基本知识

注意到行列式的定义中只涉及到了元素的加法和乘法,因此对于任意的矩阵A∈Mn,可以类似地定义A的行列式Det(A),并且大部分关于实矩阵的结论对于有限域上的矩阵都是成立的.

引理1任意的矩阵A∈Mn,A可逆当且仅当Det(A)0.

定义1矩阵A∈Mn称为可对角化的,如果存在可逆矩阵P∈GLn(q),使得

其中λi∈Fq,i=1,2,···,n.

定义2设f(x)=xn+an−1xn−1+···+a1x+a0是Fq上的多项式,则矩阵

称为f(x)的友矩阵.

3 矩阵环上的构造

3.1 环上的构造方法

本节,我们简单介绍一下Yi 等人构造ZDB 函数的方法.

命题1[12]设(R,+,×)是一个n阶环,G是(R,×)的一个e阶子群.定义

如果G满足

其中G−1={g−1|g∈G}.那么

(1)S 是R的一个划分;

(2)对任意的α∈R∗,都有|αG|=e;

(3)|S|=+1;

(4)f=f2(f1(x))是从(R,+)到(,+)的(n,+1,e−1)ZDB 函数,其中f1(x)是从R到S 的函数,将x映射为S 中包含x的那个元素αG,f2(x)是从S 到的任意一个双射;

(5)对任意的a∈R∗,都有

3.2 矩阵环上的构造方法

在给出构造方法之前,我们先考虑一种特殊情况.

引理2设A∈GLn(q),记r=Ord(A).假设A可对角化,也就是存在P∈GLn(q)使得

其中λi∈,i=1,2,···,n.如果满足命题1 中的条件(2),那么Ord(λi)=r,i=1,2,···,n,并且r|q−1.

证明:记B=,以及={Aj|j=0,1,···,r−1}.

一方面,对于j=1,···,r−1,考虑行列式Det(Aj−I)=Det(P−1(Bj−I)P)=.因为A满足命题1 中的条件(2),因此Det(Aj−I)0,也就是,于是有≠1,对于i=1,···,n以及j=1,···,r−1.

另一方面,因为Ar=I,即P−1BrP=P−1.所以=1,i=1,···,n.

综合以上有Ord(λi)=r,i=1,···,n.由于λi∈Fq,所以有r|q−1.

尽管并不是所有的矩阵都是可对角化的,但Kaylor 等人[16]证明了,对于n阶方阵来说，当q足够大时,大概是的矩阵是可对角化的.特别地,当n=2 时,可对角化方阵就几乎占据了一半.

使用可对角化方阵,结合命题1,我们可以得到如下定理.

定理1设λ1,λ2,···,λn是Fq上的n个r阶元素.定义对于任意的P∈GLn(q),记A=P−1BP.则在Mn(q)上满足命题1 的条件(2),因此存在(qn2,+1,r−1)ZDB 函数,其中r|q−1.

证明:令R=Mn(q),G=A.因为引理2 表明G满足命题1 中的条件(2),因此应用命题1 即可得到(qn2,+1,r−1)ZDB 函数,其中|R|=|Mn(q)|=qn2,|G|=Ord(A)=r.

如果A∈GLn(q)不可以对角化,则考虑其特征多项式Det(A−λI)=0,存在Fq的分裂域Fqm,使得A在扩域上恰好有n个特征值(重根按重数算).此时A有若尔当标准型,即存在P∈GLn(qm)使得A=P−1BP,其中

以及λi∈Fqm,i=1,2,···,t.

关于若尔当标准型,有如下引理.

引理3[17]符号同上,设f∈Fq[x],则

其中k为J(λ)的大小,f(i)为f的i阶形式导数[18],i=1,2,···,k−1.

现在令r=Ord(A).一方面,我们有Ar=I,也就是说

对于每个J(λi)r,i=1,2,···,t,由引理3 得:

因此1,i=1,···,n,i=1,···,r−1,

综合以上,有Ord(λi)=Ord(A)=r.到这里我们先介绍一个结论.

引理4设α是Fq上d次不可约多项式f(x)的一个根,并且f(0)0.α在f(x)分裂域上乘法阶Ord(α)记为r.m是最小的正整数使得r|qm−1.则m=d.

证明:因为r|qm−1,以及r是α的阶,所以αqm−1=1,也就是αqm=α.于是,α∈Fqm.又由于不可约多项式f(x)的分裂域为Fqd,故Fqd为Fqm的一个子域.于是有d|m.最后由m的最小性可知m=d.

设A的特征多项式为

其中,fk为Fq上的不可约多项式.因为A有n个不同的特征根λi,所以A的特征多项式无平方因子.由引理4 和Ord(λi)=r,可知fk的次数相等,不妨记为d.于是有deg(fk)=dt=n,也就是,d|n.此时,我们有如下命题.

命题2任意的A∈GLn(q),如果满足命题1 中的条件(2),那么Ord(A)|qn−1.

证明:记A的特征多项式的分裂域次数为d,则Ord(A)|qd−1.由上述的讨论可知,d|n,所以Ord(A)|qn−1.

注1由文献[19]可知,对任意的A∈GLn(q),都有Ord(A)qn−1.另外,在文献[20]中指出,存在A∈GLn(q),使得p| Ord(A).如果同时要求满足条件(2),之前并不清楚是否存在A∈GLn(q),使得p|Ord(A).现在我们证明了这样的A是不存在的,并且如果A满足条件(2),那么我们将文献[19]的结果加强为Ord(A)|qn−1.

通过Magma 程序[21]搜索,统计了GL2(q)中满足条件(2)的元素个数,如表2 所示.

表2 GL2(q)中满足条件(2)的元素个数Table 2 Number of elements in GL2(q)meeting condition(2)

例1 令n=2,q=3.取A=生成陪集,并对M2(F3)进行划分.

其中

在M2(F3)上定义函数f(x)=i,如果x∈Ci.容易验证满足条件(2),并且Ord(A)=8.因此f是一个(81,11,7)的零差分平衡函数.

4 应用

ZDB 函数可以用来构造各种密码学对象,例如常重复合码(constant composition code,CCC)、等重码(constant weight code,CWC)、集合差系统(difference systems of sets,DSS)以及跳频序列(frequencyhopping sequence,FHS)等.

4.1 最优的常重复合码

(n,M,d,[w0,w1,···,wq−1])q常重复合码是指定义阿贝尔群{b0,b1,···,bq−1} 上的码长为n、大小为M、最小汉明距离为d的码,并且使得每个码字中bi都出现wi次(0iq−1).令Aq(n,d,[w0,w1,···,wq−1])表示所有的(n,M,d,[w0,w1,···,wq−1])q常重复合码中最大的那个码的大小.Luo 等人[22]给出了关于Aq(n,d,[w0,w1,···,wq−1])的一个界.

引理5[22]如果

那么

在2008年,Ding 给出了构造常重复合码的方法[1].

命题3[1]设

如果f是一个从A到B的(n,q,λ)ZDB 函数,那么

是一个定义在B上的(n,n,n−λ,[w0,w1,···,wq−1])q常重复合码,其中wi=|{x∈A|f(x)=bi}|(0iq−1).同时相对引理5 中的界来说,Cf是最优的.

我们有如下定理.

定理2如果f是一个通过定理1 构造的ZDB 函数,那么公式(3)所定义的Cf,相对引理5 的界来说,是一个最优的常重复合码.

4.2 最优的等重码

(n,M,d,w)q等重码是指定义在阿贝尔群{b0,b1,···,bq−1} 上、码长为n、大小为M、最小汉明距离为d的码,并且使得每个码字的汉明重量都是w.令Aq(n,d,w)表示所有的(n,M,d,w)q等重码中最大的那个码的大小.Fu 等人[23]给出了关于Aq(n,d,w)的一个界.

引理6[23]如果nd−2nw+>0,那么

Zhou 等人[3]给出了达到这个界的最优等重码的方法.他们构造的等重码是通过一簇ZDB 函数来生成一些码,然后将这些码并起来得到的.我们可以只通过一个ZDB 函数来生成最优的等重码.这里所说的“生成”,是指命题3 中的方法.

定理3设f(x)=f2(f1(x))是一个通过定理1 构造的(qn2,+1,r−1)ZDB 函数,并且使得f2将0A映射为0.那么公式(3)所定义的Cf,相对引理6 中的界来说,是一个最优的等重码.

证明:显然Cf是一个等重码,因为f只将0 映射为0,因此每个码字的汉明重量为n−1.最后通过简单的计算,我们有

所以达到了引理6 中的界.

注2注意到f2(x)是从S 到任意一个双射,其中S 由式(1)定义.存在很多这样的双射,将0A映射为0.

4.3 最优的完美的集合差系统

集合差系统与逗号自由码[24]和认证码有关[25].设{D0,D1,···,Dq−1} 是交换群(G,+)的一些非空子集.记|Di| =wi,0iq−1.{D0,D1,···,Dq−1} 称为一个(n,{w0,w1,···,wq−1},λ)集合差系统,如果这个多重集

中包含G中每个非零元至少λ次.一个集合差系统是完美的,如果每个非零元恰好出现λ次.一个集合差系统是循环的如果G是循环的.通常,我们要求

越小越好.WANG[26]给出了τq(n,λ)的一个下界.

引理7[26]对于一个(n,[w0,w1,···,wq−1],λ)集合差系统,我们有

其中SQUARE(x)表示不小于x的最小平方数,x表示不小于x的最小整数.

一个集合差系统称为最优的,如果它可以达到引理7 中的界.Ding[2]给出了利用ZDB 函数来构造循环的集合差系统的方法.

引理8[2]设f是一个从(Zn,+)到(B,+)的(n,m,λ)ZDB 函数.对每一个b∈B,定义

以及

那么集合S是一个完美的循环的(n,{τb|b∈B},n−λ)集合差系统,其中τb=|Db|.进一步地,S是最优的,如果mλn.

和引理8 相比,我们可以使用定义在非循环群上的ZDB 函数构造完美的集合差系统.利用我们的ZDB 函数构造集合差系统的方法如下.

定理4设f:是一个由定理1 构造的ZDB 函数.那么通过引理8 构造的集合S是一个完美的(qn2,{1,r,···,r},qn2−r+1)集合差系统.进一步地,S是最优的,如果n2.

证明:因为r|q−1,因此n2 意味着qn2(r−1)2.于是有

也就是

因此满足引理8 的条件,所以S是最优的.

4.4 最优的跳频序列

对于任意两个字母表B上的两个长度为n的序列X,Y,它们的汉明相关HX,Y,定义为

其中h[a,b]等于1,如果a=b,否则等于0.跳频序列要求它的汉明自相关越小越好.Lempel 等人[27]给出了一个序列的汉明自相关的下界.

引理9[27]对于任意一个长度为n,在长度为l的字母表上的跳频序列,定义

那么

其中b是n模l的最小非负剩余,⌈x⌉表示不小于x的最小整数.

令(n,l,λ)表示一个长度为n,在长度为l的字母表上的,汉明自相关H(X)为λ的跳频序列.一个跳频序列是最优的,如果它满足引理9 的界.

Zha 等人[8]在Zn上给出的零差分平衡函数可以用于构造跳频序列.遗憾的是,由于矩阵环的加法群为非循环群,因此本文构造的零差分平衡函数无法用于构造最优的跳频序列．

5 结论

本文在矩阵环上构造了零差分平衡函数,并且介绍了零差分平衡函数的应用,给出了一些最优的常重复合码,常重码和集合差系统.非交换环上的零差分平衡函数目前研究得还不多,因此本文的研究对于丰富不同结构上的零差分平衡函数是有一定理论意义的.接下来,我们将进一步研究其他代数结构上采用分圆陪集的方法如何构造零差平衡函数.