矩陣環上的零差分平衡函數*

易宗向,余玉銀

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 結論

本文在矩陣環上構造了零差分平衡函數,并且介紹了零差分平衡函數的應用,給出了一些最優的常重復合碼,常重碼和集合差系統.非交換環上的零差分平衡函數目前研究得還不多,因此本文的研究對于豐富不同結構上的零差分平衡函數是有一定理論意義的.接下來,我們將進一步研究其他代數結構上采用分圓陪集的方法如何構造零差平衡函數.