一些二進(jìn)制數(shù)列的族復(fù)雜度和互相關(guān)測(cè)度

梁嘉怡, 薛 盼

(西安歐亞學(xué)院 通識(shí)教育學(xué)院, 陜西 西安 710065)

隨著計(jì)算機(jī)和互聯(lián)網(wǎng)的普及, 傳統(tǒng)的業(yè)務(wù)處理與服務(wù)等日?；顒?dòng)已經(jīng)不能滿足日益發(fā)展的新時(shí)代了. 目前人類已經(jīng)進(jìn)入了信息時(shí)代, 許多問(wèn)題都可以通過(guò)計(jì)算機(jī)和網(wǎng)絡(luò)等工具來(lái)實(shí)現(xiàn). 此時(shí), 偽隨機(jī)二進(jìn)制數(shù)列成為了密碼系統(tǒng)中的一個(gè)常用工具, 并有著廣泛的應(yīng)用, 比如密碼學(xué)、光譜學(xué)等[1-2].

為衡量二進(jìn)制數(shù)列的偽隨機(jī)性，引入了多種偽隨機(jī)測(cè)度，比如f-復(fù)雜度[3]，互相關(guān)測(cè)度[4]，一致分布測(cè)度[5]等等. 本文將采用f-復(fù)雜度和互相關(guān)測(cè)度來(lái)衡量二進(jìn)制數(shù)列的偽隨機(jī)性.Mauduit和Sárk?zy[5]于1997年開始對(duì)偽隨機(jī)二進(jìn)制數(shù)列進(jìn)行研究,構(gòu)造出了一些“好”的數(shù)列，并分析討論了其數(shù)列的偽隨機(jī)性. Ahlswede等[3]給出了f-復(fù)雜度(f-complexity )的定義.

定義1長(zhǎng)度為N的二進(jìn)制數(shù)列EN∈{-1,+1}N的族F的f-復(fù)雜度C(F) 是指對(duì)于任意的1≤i1

ei1=ε1,ei2=ε2, …,eij=εj

成立的最大整數(shù)j≥0.

由定義1有2C(F)≤|F|，其中|F|表示族F的長(zhǎng)度.Gyarmati等[4]給出了互相關(guān)測(cè)度(cross-correlation measure ) 的定義.

定義2長(zhǎng)度為N的二進(jìn)制數(shù)Ei,N=(ei,1,ei,2,…,ei,N)∈{-1,+1}N,i=1,2,…,F族F的l階互相關(guān)測(cè)度Φl(F)為

其中:I=(i1,i2,…,il)∈{1,2,…,|F|}l,D=(d1,d2,…,dl)∈Zl滿足0≤d1≤d2≤…≤dl

如果二進(jìn)制數(shù)列族F具有“大”的f-復(fù)雜度和“小”的互相關(guān)測(cè)度，那么稱其為“好”的二進(jìn)制數(shù)列族. 然而構(gòu)造具有這樣性質(zhì)的二進(jìn)制數(shù)列，是信息安全領(lǐng)域中非常困難的問(wèn)題.Gyarmati[6-7]給出了一些具有較“大”的f-復(fù)雜度的數(shù)列族，然而其互相關(guān)測(cè)度也很大，沒(méi)有得到一個(gè)較好的結(jié)果.而文獻(xiàn)[4]中的二進(jìn)制數(shù)列族具有較小的互相關(guān)測(cè)度，但是其f-復(fù)雜度卻很難衡量.

Winterhof 等[8]證明了f-復(fù)雜度和互相關(guān)測(cè)度之間的關(guān)系.

其中l(wèi)og2表示二進(jìn)制對(duì)數(shù).

1 主要結(jié)論

本文基于數(shù)論方法構(gòu)造出更多具有“大”的f-復(fù)雜度和“小”的互相關(guān)測(cè)度的二進(jìn)制數(shù)列族，用偽隨機(jī)二進(jìn)制數(shù)列來(lái)模擬真正的隨機(jī)數(shù)列. 以下兩個(gè)定理中給出了兩個(gè)族均具有上述“好”的性質(zhì).

則有

且

則有

且

2 特征和的估計(jì)與定理1的證明

有關(guān)特征和估計(jì)的相關(guān)引理如下.

證明參見(jiàn)文獻(xiàn)[10]中第三章.

f(x)=c(x-x1)d1(x-x2)d2…(x-xs)ds

當(dāng)i≠j時(shí)，xi≠xj，其中(d1,d2,…,ds)=1.設(shè)X,Y∈R滿足0

證明參見(jiàn)文獻(xiàn)[5]中定理2.

顯然方程

1≤x≤M, 1≤i≤l

最多有2l個(gè)解. 則有

其中:M∈N,滿足0≤d1≤…

其中

而

因此h(x)無(wú)平方因子.注意到h(x)是不可約的且無(wú)平方因子,而Legendre符號(hào)是二次特征,根據(jù)引理2有

從而

2l≤18lp1/2logp+2l≤20lp1/2logp

因此

Φl(F1)?lp1/2logp,l=1,2,…

類似可證

(1)

需要證明

(2)

此外由引理1可得

由式(1)和式(2)以及命題1可得

那么

3 指數(shù)和的估計(jì)與定理2的證明

有關(guān)指數(shù)和估計(jì)的相關(guān)引理如下.

引理3[11]設(shè)g(x),h(x)∈Fp[x],f(x)=g(x)/h(x)在Fp上不為常值函數(shù).設(shè)s表示g(x)的不同根的數(shù)目，則有

證明參見(jiàn)文獻(xiàn)[11]中定理2.

引理4[12]設(shè)整數(shù)s1,…,sk,d1,…,dk滿足(s1…sk,p)=1和d1<…

在Fp上不是零多項(xiàng)式.

證明參見(jiàn)文獻(xiàn)[12]中引理7.1.

引理5設(shè)整數(shù)u,x,d1,…,dl,r1,…,rl,s1,…,sl滿足d1

H1(x)=(x+d1)…(x+dl)y1…yl

G1(x)=r1(x+d2)…(x+dl)y1…yl+…+

rl(x+d1)…(x+dl-1)y1…yl+

s1(x+d1)…(x+dl)y2…yl+…+

sl(x+d1)…(x+dl)y1…yl-1+

ux(x+d1)…(x+dl)y1…yl

顯然函數(shù)G1(x)在Fp上不為常數(shù)，則由引理3可得

如果p|u,則有

定義

x+dl+1=y1，…，x+d2l=yl

rl+1=s1，…，r2l=sl

可得

如果存在n,m使得n

若p|rn+rm,定義

對(duì)于F′1(x)，若仍然存在n′,m′滿足n′

其中(t1…tk,p)=1,c1<…

因此

現(xiàn)在定義

有

綜上可得，引理5證畢.

引理6[13]設(shè)χ是模q的非主特征，則對(duì)任意的整數(shù)M及正整數(shù)N有

證明參見(jiàn)文獻(xiàn)[13]中第十三章.

證明定理2.首先考慮F2.設(shè)(i1,…,il)∈{1,2,…,|F2|}l,0≤d1≤…≤dl

有

(3)

同理

(4)

又有

(5)

由式(3～5)和引理5可得

因此

Φl(F2)?lp1/2(logp)2l+1l=1,2,…

(6)

需要證明

(7)

由引理6可得

那么

(8)

由式(6,7)和命題1可得

因此

致謝：本文得到西安歐亞學(xué)院校級(jí)科研基金(2022XJZK03,2020XJZK10)的資助，在此表示感謝.