矩陣環(huán)上的零差分平衡函數(shù)*

易宗向,余玉銀

1.廣州大學(xué) 數(shù)學(xué)與信息科學(xué)學(xué)院,廣州 510006

2.廣東科技學(xué)院,東莞 523083

1 引言

設(shè)(A,+)和(B,+)是兩個(gè)有限的阿貝爾群,一個(gè)從A到B的函數(shù)f稱(chēng)為是一個(gè)(n,m,λ)零差分平衡(zero-difference balanced,ZDB)函數(shù),如果對(duì)任意的a∈A{0} 都有

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

其中n=|A|,m=|Im(f)|,λ為常數(shù).

Ding[1]在2008年首先提出了ZDB 函數(shù)的概念,并利用ZDB 函數(shù)構(gòu)造了最優(yōu)的常重復(fù)合碼(constant composition code,CCC),也就是如果存在(n,m,λ)ZDB 函數(shù),就一定可以構(gòu)造最優(yōu)的(n,n,n?λ)CCCs[1].緊接著在2009年,Ding 利用ZDB 函數(shù)構(gòu)造了最優(yōu)的完美的集合差系統(tǒng)(difference systems of sets,DSS),也就是如果存在(n,m,λ)ZDB 函數(shù),就可能構(gòu)造(n,{rb|b∈B},n?λ)最優(yōu)的完美的DSSs,其中rb={x∈A|f(x)=b}[2].在2012年,Zhou 等人利用ZDB 函數(shù)構(gòu)造最優(yōu)的等重碼(constant weight code,CWC),也就是如果存在(n,m,λ)ZDB 函數(shù),就可能構(gòu)造最優(yōu)的(n,n,n?λ)CWCs[3].在2014年,Wang 等人利用ZDB 函數(shù),構(gòu)造了最優(yōu)的跳頻序列(frequency-hopping sequence,FHS),也就是如何存在(n,m,λ)ZDB 函數(shù),就可能構(gòu)造最優(yōu)的(n,m,λ)FHSs[4].CCC、CWC、DSS 以及FHS 在通信和組合等領(lǐng)域都有重要應(yīng)用,因此隨后有很多學(xué)者一直在研究如何構(gòu)造更多的ZDB 函數(shù)[2–12].表1 給出了一些已知的ZDB 函數(shù)的參數(shù).

最早Carlet 等人在2004年[13]通過(guò)完全非線(xiàn)性(perfect nonlinear,PN)函數(shù)構(gòu)造了一類(lèi)ZDB 函數(shù),同時(shí)指出了劃分差族(partition difference family,PDF)和ZDB 函數(shù)的等價(jià)性.接著Ding 在2009年[2]分別采用有限域上的特征和以及GMW 序列構(gòu)造了三類(lèi)ZDB 函數(shù),并在2012年[5]以群的特征、差集、置換、跡函數(shù)、有限域上的冪函數(shù)等構(gòu)造了一些參數(shù)簡(jiǎn)單的ZDB 函數(shù),同時(shí)給出了從Zn到自身的多項(xiàng)式為ZDB 函數(shù)的充要條件,更重要的是還給出了ZDB 函數(shù)在差族(difference family,DF)和集合差系統(tǒng)(difference system of sets,DSS)的應(yīng)用.同在2012年,Zhou 等人[3]使用線(xiàn)性方程組,基于差分平衡函數(shù)和d-form 函數(shù)構(gòu)造了兩類(lèi)ZDB 函數(shù),同時(shí)將ZDB 函數(shù)用于構(gòu)造等重碼(constant weight code,CWC).他們所構(gòu)造的ZDB 函數(shù)大部分利用了具有差分平衡性質(zhì)的函數(shù),而這樣的有用函數(shù)是比較少的.2014年Wang 等[4]給出了ZDB 函數(shù)的兩個(gè)界,并使用參數(shù)化的方法給出了一類(lèi)ZDB 函數(shù).在此基礎(chǔ)上,他們還給出了利用ZDB 函數(shù)構(gòu)造最優(yōu)跳頻序列上的方法.早期構(gòu)造ZDB 函數(shù)的方法比較繁雜,有些構(gòu)造方法還需要依賴(lài)其他對(duì)象,比如PN 函數(shù)、差族、差分平衡函數(shù)和d-form 函數(shù)等.

最近用得比較多的構(gòu)造方法是采用分圓陪集.2013年Cai 等人[6]采用廣義分圓類(lèi)的方法在Zn上構(gòu)造了一類(lèi)ZDB 函數(shù).隨后在2014年Ding 等人[7]在有限域直積環(huán)上也構(gòu)造了一類(lèi)ZDB 函數(shù).同時(shí)對(duì)n=2m?1,在Zn上構(gòu)造了一類(lèi)ZDB 函數(shù).緊接著在2015年Zha 等人[8]使用簡(jiǎn)潔的方法對(duì)Cai 等人[6]在Zn上的結(jié)果進(jìn)行了解釋,并對(duì)n=構(gòu)造了一類(lèi)ZDB 函數(shù).特別地,Zha 等人在Zp×Zp上采用相同的思想構(gòu)造了另一類(lèi)ZDB 函數(shù).使用分圓陪集在Zn上構(gòu)造ZDB 函數(shù)要求n為奇數(shù).在2018年,Yi 等人[12]將前面兩類(lèi)ZDB 函數(shù)推廣到抽象的代數(shù)環(huán)上,并給出了在環(huán)上利用分圓陪集構(gòu)造ZDB 函數(shù)的條件,并對(duì)兩個(gè)代數(shù)整數(shù)環(huán)給出了具體的構(gòu)造方法.本文以Yi 等人的方法為基礎(chǔ),在有限域的矩陣環(huán)上,討論滿(mǎn)足文獻(xiàn)[12]中條件的循環(huán)群的生成元的情況.這種構(gòu)造是具有理論意義的,因?yàn)橹暗腪DB 函數(shù)都是在交換環(huán)上的構(gòu)造.

本文組織如下:第2 節(jié)介紹需要用到的基本知識(shí);第3 節(jié)首先給出給出Yi 等人[12]的方法,然后在矩陣環(huán)上構(gòu)造ZDB 函數(shù);第4 節(jié)展示如何使用ZDB 函數(shù)來(lái)構(gòu)造其他對(duì)象;第5 節(jié)是本文的總結(jié).

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

2 預(yù)備知識(shí)

2.1 符號(hào)說(shuō)明

除非特別說(shuō)明,本文中的所有環(huán)(R,+,×)都是含有乘法單位元1 的.(R,×)中的所有可逆元記為R×,R中的所有非零元記為R?.對(duì)任意的a∈R×,滿(mǎn)足ak=1 的最小正整數(shù)k記為OrdR(a),或者Ord(a).對(duì)于R的任意一個(gè)子集A和R的任意一個(gè)元素a,定義

以及

所有的整數(shù)集合記為Z,所有的自然數(shù)集合記為N,所有的正整數(shù)集合記為Z+.含有q=ps個(gè)元素的有限域記為Fq.

關(guān)于矩陣,有限域Fq上的所有n階方陣的集合記為Mn(Fq).顯然Mn(Fq)帶上普通的矩陣加法和矩陣乘法,可以構(gòu)成一個(gè)非交換環(huán),稱(chēng)為矩陣環(huán).在不引起歧義的情況下,Mn(Fq)也記為Mn(q),或者M(jìn)n.Mn(Fq)中所有的可逆矩陣在矩陣乘法下構(gòu)成一個(gè)群,記為GLn(q).

2.2 矩陣環(huán)的基本知識(shí)

注意到行列式的定義中只涉及到了元素的加法和乘法,因此對(duì)于任意的矩陣A∈Mn,可以類(lèi)似地定義A的行列式Det(A),并且大部分關(guān)于實(shí)矩陣的結(jié)論對(duì)于有限域上的矩陣都是成立的.

引理1任意的矩陣A∈Mn,A可逆當(dāng)且僅當(dāng)Det(A)0.

定義1矩陣A∈Mn稱(chēng)為可對(duì)角化的,如果存在可逆矩陣P∈GLn(q),使得

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

定義2設(shè)f(x)=xn+an?1xn?1+···+a1x+a0是Fq上的多項(xiàng)式,則矩陣

稱(chēng)為f(x)的友矩陣.

3 矩陣環(huán)上的構(gòu)造

3.1 環(huán)上的構(gòu)造方法

本節(jié),我們簡(jiǎn)單介紹一下Yi 等人構(gòu)造ZDB 函數(shù)的方法.

命題1[12]設(shè)(R,+,×)是一個(gè)n階環(huán),G是(R,×)的一個(gè)e階子群.定義

如果G滿(mǎn)足

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

(1)S 是R的一個(gè)劃分;

(2)對(duì)任意的α∈R?,都有|αG|=e;

(3)|S|=+1;

(4)f=f2(f1(x))是從(R,+)到(,+)的(n,+1,e?1)ZDB 函數(shù),其中f1(x)是從R到S 的函數(shù),將x映射為S 中包含x的那個(gè)元素αG,f2(x)是從S 到的任意一個(gè)雙射;

(5)對(duì)任意的a∈R?,都有

3.2 矩陣環(huán)上的構(gòu)造方法

在給出構(gòu)造方法之前,我們先考慮一種特殊情況.

引理2設(shè)A∈GLn(q),記r=Ord(A).假設(shè)A可對(duì)角化,也就是存在P∈GLn(q)使得

其中λi∈,i=1,2,···,n.如果滿(mǎn)足命題1 中的條件(2),那么Ord(λi)=r,i=1,2,···,n,并且r|q?1.

證明:記B=,以及={Aj|j=0,1,···,r?1}.

一方面,對(duì)于j=1,···,r?1,考慮行列式Det(Aj?I)=Det(P?1(Bj?I)P)=.因?yàn)锳滿(mǎn)足命題1 中的條件(2),因此Det(Aj?I)0,也就是,于是有≠1,對(duì)于i=1,···,n以及j=1,···,r?1.

另一方面,因?yàn)锳r=I,即P?1BrP=P?1.所以=1,i=1,···,n.

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

盡管并不是所有的矩陣都是可對(duì)角化的,但Kaylor 等人[16]證明了,對(duì)于n階方陣來(lái)說(shuō)，當(dāng)q足夠大時(shí),大概是的矩陣是可對(duì)角化的.特別地,當(dāng)n=2 時(shí),可對(duì)角化方陣就幾乎占據(jù)了一半.

使用可對(duì)角化方陣,結(jié)合命題1,我們可以得到如下定理.

定理1設(shè)λ1,λ2,···,λn是Fq上的n個(gè)r階元素.定義對(duì)于任意的P∈GLn(q),記A=P?1BP.則在Mn(q)上滿(mǎn)足命題1 的條件(2),因此存在(qn2,+1,r?1)ZDB 函數(shù),其中r|q?1.

證明:令R=Mn(q),G=A.因?yàn)橐? 表明G滿(mǎn)足命題1 中的條件(2),因此應(yīng)用命題1 即可得到(qn2,+1,r?1)ZDB 函數(shù),其中|R|=|Mn(q)|=qn2,|G|=Ord(A)=r.

如果A∈GLn(q)不可以對(duì)角化,則考慮其特征多項(xiàng)式Det(A?λI)=0,存在Fq的分裂域Fqm,使得A在擴(kuò)域上恰好有n個(gè)特征值(重根按重?cái)?shù)算).此時(shí)A有若爾當(dāng)標(biāo)準(zhǔn)型,即存在P∈GLn(qm)使得A=P?1BP,其中

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

關(guān)于若爾當(dāng)標(biāo)準(zhǔn)型,有如下引理.

引理3[17]符號(hào)同上,設(shè)f∈Fq[x],則

其中k為J(λ)的大小,f(i)為f的i階形式導(dǎo)數(shù)[18],i=1,2,···,k?1.

現(xiàn)在令r=Ord(A).一方面,我們有Ar=I,也就是說(shuō)

對(duì)于每個(gè)J(λi)r,i=1,2,···,t,由引理3 得:

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

綜合以上,有Ord(λi)=Ord(A)=r.到這里我們先介紹一個(gè)結(jié)論.

引理4設(shè)α是Fq上d次不可約多項(xiàng)式f(x)的一個(gè)根,并且f(0)0.α在f(x)分裂域上乘法階Ord(α)記為r.m是最小的正整數(shù)使得r|qm?1.則m=d.

證明:因?yàn)閞|qm?1,以及r是α的階,所以αqm?1=1,也就是αqm=α.于是,α∈Fqm.又由于不可約多項(xiàng)式f(x)的分裂域?yàn)镕qd,故Fqd為Fqm的一個(gè)子域.于是有d|m.最后由m的最小性可知m=d.

設(shè)A的特征多項(xiàng)式為

其中,fk為Fq上的不可約多項(xiàng)式.因?yàn)锳有n個(gè)不同的特征根λi,所以A的特征多項(xiàng)式無(wú)平方因子.由引理4 和Ord(λi)=r,可知fk的次數(shù)相等,不妨記為d.于是有deg(fk)=dt=n,也就是,d|n.此時(shí),我們有如下命題.

命題2任意的A∈GLn(q),如果滿(mǎn)足命題1 中的條件(2),那么Ord(A)|qn?1.

證明:記A的特征多項(xiàng)式的分裂域次數(shù)為d,則Ord(A)|qd?1.由上述的討論可知,d|n,所以O(shè)rd(A)|qn?1.

注1由文獻(xiàn)[19]可知,對(duì)任意的A∈GLn(q),都有Ord(A)qn?1.另外,在文獻(xiàn)[20]中指出,存在A∈GLn(q),使得p| Ord(A).如果同時(shí)要求滿(mǎn)足條件(2),之前并不清楚是否存在A∈GLn(q),使得p|Ord(A).現(xiàn)在我們證明了這樣的A是不存在的,并且如果A滿(mǎn)足條件(2),那么我們將文獻(xiàn)[19]的結(jié)果加強(qiáng)為Ord(A)|qn?1.

通過(guò)Magma 程序[21]搜索,統(tǒng)計(jì)了GL2(q)中滿(mǎn)足條件(2)的元素個(gè)數(shù),如表2 所示.

表2 GL2(q)中滿(mǎn)足條件(2)的元素個(gè)數(shù)Table 2 Number of elements in GL2(q)meeting condition(2)

例1 令n=2,q=3.取A=生成陪集,并對(duì)M2(F3)進(jìn)行劃分.

其中

在M2(F3)上定義函數(shù)f(x)=i,如果x∈Ci.容易驗(yàn)證滿(mǎn)足條件(2),并且Ord(A)=8.因此f是一個(gè)(81,11,7)的零差分平衡函數(shù).

4 應(yīng)用

ZDB 函數(shù)可以用來(lái)構(gòu)造各種密碼學(xué)對(duì)象,例如常重復(fù)合碼(constant composition code,CCC)、等重碼(constant weight code,CWC)、集合差系統(tǒng)(difference systems of sets,DSS)以及跳頻序列(frequencyhopping sequence,FHS)等.

4.1 最優(yōu)的常重復(fù)合碼

(n,M,d,[w0,w1,···,wq?1])q常重復(fù)合碼是指定義阿貝爾群{b0,b1,···,bq?1} 上的碼長(zhǎng)為n、大小為M、最小漢明距離為d的碼,并且使得每個(gè)碼字中bi都出現(xiàn)wi次(0iq?1).令A(yù)q(n,d,[w0,w1,···,wq?1])表示所有的(n,M,d,[w0,w1,···,wq?1])q常重復(fù)合碼中最大的那個(gè)碼的大小.Luo 等人[22]給出了關(guān)于Aq(n,d,[w0,w1,···,wq?1])的一個(gè)界.

引理5[22]如果

那么

在2008年,Ding 給出了構(gòu)造常重復(fù)合碼的方法[1].

命題3[1]設(shè)

如果f是一個(gè)從A到B的(n,q,λ)ZDB 函數(shù),那么

是一個(gè)定義在B上的(n,n,n?λ,[w0,w1,···,wq?1])q常重復(fù)合碼,其中wi=|{x∈A|f(x)=bi}|(0iq?1).同時(shí)相對(duì)引理5 中的界來(lái)說(shuō),Cf是最優(yōu)的.

我們有如下定理.

定理2如果f是一個(gè)通過(guò)定理1 構(gòu)造的ZDB 函數(shù),那么公式(3)所定義的Cf,相對(duì)引理5 的界來(lái)說(shuō),是一個(gè)最優(yōu)的常重復(fù)合碼.

4.2 最優(yōu)的等重碼

(n,M,d,w)q等重碼是指定義在阿貝爾群{b0,b1,···,bq?1} 上、碼長(zhǎng)為n、大小為M、最小漢明距離為d的碼,并且使得每個(gè)碼字的漢明重量都是w.令A(yù)q(n,d,w)表示所有的(n,M,d,w)q等重碼中最大的那個(gè)碼的大小.Fu 等人[23]給出了關(guān)于Aq(n,d,w)的一個(gè)界.

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

Zhou 等人[3]給出了達(dá)到這個(gè)界的最優(yōu)等重碼的方法.他們構(gòu)造的等重碼是通過(guò)一簇ZDB 函數(shù)來(lái)生成一些碼,然后將這些碼并起來(lái)得到的.我們可以只通過(guò)一個(gè)ZDB 函數(shù)來(lái)生成最優(yōu)的等重碼.這里所說(shuō)的“生成”,是指命題3 中的方法.

定理3設(shè)f(x)=f2(f1(x))是一個(gè)通過(guò)定理1 構(gòu)造的(qn2,+1,r?1)ZDB 函數(shù),并且使得f2將0A映射為0.那么公式(3)所定義的Cf,相對(duì)引理6 中的界來(lái)說(shuō),是一個(gè)最優(yōu)的等重碼.

證明:顯然Cf是一個(gè)等重碼,因?yàn)閒只將0 映射為0,因此每個(gè)碼字的漢明重量為n?1.最后通過(guò)簡(jiǎn)單的計(jì)算,我們有

所以達(dá)到了引理6 中的界.

注2注意到f2(x)是從S 到任意一個(gè)雙射,其中S 由式(1)定義.存在很多這樣的雙射,將0A映射為0.

4.3 最優(yōu)的完美的集合差系統(tǒng)

集合差系統(tǒng)與逗號(hào)自由碼[24]和認(rèn)證碼有關(guān)[25].設(shè){D0,D1,···,Dq?1} 是交換群(G,+)的一些非空子集.記|Di| =wi,0iq?1.{D0,D1,···,Dq?1} 稱(chēng)為一個(gè)(n,{w0,w1,···,wq?1},λ)集合差系統(tǒng),如果這個(gè)多重集

中包含G中每個(gè)非零元至少λ次.一個(gè)集合差系統(tǒng)是完美的,如果每個(gè)非零元恰好出現(xiàn)λ次.一個(gè)集合差系統(tǒng)是循環(huán)的如果G是循環(huán)的.通常,我們要求

越小越好.WANG[26]給出了τq(n,λ)的一個(gè)下界.

引理7[26]對(duì)于一個(gè)(n,[w0,w1,···,wq?1],λ)集合差系統(tǒng),我們有

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

一個(gè)集合差系統(tǒng)稱(chēng)為最優(yōu)的,如果它可以達(dá)到引理7 中的界.Ding[2]給出了利用ZDB 函數(shù)來(lái)構(gòu)造循環(huán)的集合差系統(tǒng)的方法.

引理8[2]設(shè)f是一個(gè)從(Zn,+)到(B,+)的(n,m,λ)ZDB 函數(shù).對(duì)每一個(gè)b∈B,定義

以及

那么集合S是一個(gè)完美的循環(huán)的(n,{τb|b∈B},n?λ)集合差系統(tǒng),其中τb=|Db|.進(jìn)一步地,S是最優(yōu)的,如果mλn.

和引理8 相比,我們可以使用定義在非循環(huán)群上的ZDB 函數(shù)構(gòu)造完美的集合差系統(tǒng).利用我們的ZDB 函數(shù)構(gòu)造集合差系統(tǒng)的方法如下.

定理4設(shè)f:是一個(gè)由定理1 構(gòu)造的ZDB 函數(shù).那么通過(guò)引理8 構(gòu)造的集合S是一個(gè)完美的(qn2,{1,r,···,r},qn2?r+1)集合差系統(tǒng).進(jìn)一步地,S是最優(yōu)的,如果n2.

證明:因?yàn)閞|q?1,因此n2 意味著qn2(r?1)2.于是有

也就是

因此滿(mǎn)足引理8 的條件,所以S是最優(yōu)的.

4.4 最優(yōu)的跳頻序列

對(duì)于任意兩個(gè)字母表B上的兩個(gè)長(zhǎng)度為n的序列X,Y,它們的漢明相關(guān)HX,Y,定義為

其中h[a,b]等于1,如果a=b,否則等于0.跳頻序列要求它的漢明自相關(guān)越小越好.Lempel 等人[27]給出了一個(gè)序列的漢明自相關(guān)的下界.

引理9[27]對(duì)于任意一個(gè)長(zhǎng)度為n,在長(zhǎng)度為l的字母表上的跳頻序列,定義

那么

其中b是n模l的最小非負(fù)剩余,?x?表示不小于x的最小整數(shù).

令(n,l,λ)表示一個(gè)長(zhǎng)度為n,在長(zhǎng)度為l的字母表上的,漢明自相關(guān)H(X)為λ的跳頻序列.一個(gè)跳頻序列是最優(yōu)的,如果它滿(mǎn)足引理9 的界.

Zha 等人[8]在Zn上給出的零差分平衡函數(shù)可以用于構(gòu)造跳頻序列.遺憾的是,由于矩陣環(huán)的加法群為非循環(huán)群,因此本文構(gòu)造的零差分平衡函數(shù)無(wú)法用于構(gòu)造最優(yōu)的跳頻序列．

5 結(jié)論

本文在矩陣環(huán)上構(gòu)造了零差分平衡函數(shù),并且介紹了零差分平衡函數(shù)的應(yīng)用,給出了一些最優(yōu)的常重復(fù)合碼,常重碼和集合差系統(tǒng).非交換環(huán)上的零差分平衡函數(shù)目前研究得還不多,因此本文的研究對(duì)于豐富不同結(jié)構(gòu)上的零差分平衡函數(shù)是有一定理論意義的.接下來(lái),我們將進(jìn)一步研究其他代數(shù)結(jié)構(gòu)上采用分圓陪集的方法如何構(gòu)造零差平衡函數(shù).