一類長度為2p2 的二元序列的2-Adic 復(fù)雜度研究*

柯品惠, 盧櫟羽, 陳智雄

1. 福建師范大學(xué) 數(shù)學(xué)與統(tǒng)計學(xué)院, 福州350117

2. 福建省應(yīng)用數(shù)學(xué)中心(福建師范大學(xué)), 福州350117

3. 莆田學(xué)院 應(yīng)用數(shù)學(xué)福建省高校重點(diǎn)實驗室, 莆田351100

1 引言

偽隨機(jī)序列在通信和密碼學(xué)等領(lǐng)域具有廣泛的應(yīng)用[1]. 理論上, 每個二元序列都可以由線性反饋移位寄存器(LFSR) 或帶進(jìn)位反饋移位寄存器(FSCR) 產(chǎn)生. Berlekam-Massey 算法(BMA)[2]和有理逼近算法(RAA)[3]是目前較為有效的兩種攻擊算法, 如果已知一定長度的二元序列, 那么可利用上述兩種算法來恢復(fù)完整的二元序列. 線性復(fù)雜度和2-adic 復(fù)雜度是抵御BMA 和RAA 攻擊的兩個重要安全準(zhǔn)則. 由BMA 和RAA 攻擊方式可知, 序列的線性復(fù)雜度和2-adic 復(fù)雜度都不應(yīng)小于該序列周期的一半.目前, 許多分圓序列和廣義分圓序列已被證明具有較高的線性復(fù)雜度[4–7]. 然而, 對于序列的2-adic 復(fù)雜度, 僅有少數(shù)幾類序列的2-adic 復(fù)雜度是已知的. 因此, 分析已有序列的2-adic 復(fù)雜度以及設(shè)計具有高2-adic 復(fù)雜度的偽隨機(jī)序列成為近年研究的熱點(diǎn).

迄今為止, 計算二元序列的2-adic 復(fù)雜度主要有三種方法. 第一種方法是Xiong 等[8]提出的計算序列的循環(huán)矩陣的行列式和兩個整數(shù)的最大公約數(shù). 在文獻(xiàn)[8] 中, Xiong 等證明了所有具有理想自相關(guān)值的序列都具有最大的2-adic 復(fù)雜度. 之后, Xiao 等[9]利用相同的方法證明了兩類廣義分圓二元序列的2-adic 復(fù)雜度可達(dá)到最大值. 第二種方法是Hu[10]提出的利用序列的自相關(guān)分布來分析二元序列的2-adic 復(fù)雜度. 基于文獻(xiàn)[10] 的研究方法, Sun 等分別給出了文獻(xiàn)[11] 和文獻(xiàn)[12] 中兩類二元序列的2-adic 復(fù)雜度的下界, 并且得到了文獻(xiàn)[13] 中Ding-Helleseth-Lam 序列的2-adic 復(fù)雜度的上下界. 最近,Hofer 和Winterhof[14]用文獻(xiàn)[10] 的方法證明了二素數(shù)生成器(two-prime generater) 的2-adic 復(fù)雜度接近于它的周期. 最后一種方法是直接計算序列的2-adic 復(fù)雜度. 例如, Zhang 等[15]利用有限域Fq和Z2N ?1上的“高斯周期”和“二次高斯和”確定了Ding-Helleseth-Martinsen 序列的2-adic 復(fù)雜度. Yang等[16]推廣了文獻(xiàn)[13] 中給出的結(jié)果, 并確定了一類二元序列的2-adic 復(fù)雜度的精確值.

最近, Zhang 等[17]構(gòu)造了一類長度為2p2的二元廣義分圓序列, 證明了此類二元序列具有較大的線性復(fù)雜度. 基于文獻(xiàn)[8] 給出的方法, 本文研究了此類二元廣義分圓序列的2-adic 復(fù)雜度. 我們證明了此類序列的2-adic 復(fù)雜度不小于其周期的一半, 并且該序列的2-adic 復(fù)雜度在一些情形下也可以達(dá)到最大值.

本文其余部分組織如下. 第2 節(jié), 給出本文所需要的相關(guān)概念與知識, 以及一些必要的結(jié)果. 第3 節(jié),首先, 利用中國剩余定理和Zp上的“高斯周期” 得到了Z2p2上的“高斯周期”; 然后, 證明了一類長度為2p2的二元序列的2-adic 復(fù)雜度在一些情形下可以達(dá)到最大值. 第4 節(jié)對本文工作進(jìn)行總結(jié).

2 基礎(chǔ)知識

令p為奇素數(shù). 設(shè)2 為模p2的本原根, 當(dāng)k ≥1 時, 則2 也是模pk的本原根[18]. 由于2+pk為奇數(shù), 則2+pk為模2pk的本原根[19]. 設(shè)g=2+p2, 則g是模p,2p,p2和2p2的公共本原根.

定義

上述引理1—4的證明, 請參見文獻(xiàn)[20].

引理5 令p為奇素數(shù), 則有g(shù)cd(p,2p2?1)=1.

證明: 由費(fèi)馬小定理, 可得2p ≡2 modp. 于是, 有2p2≡(2p)p ≡2p ≡2 modp, 即2p2?1≡1 modp. 所以gcd(p,2p2?1)=1.

引理6 (i) 令p為奇素數(shù), 則有g(shù)cd(p ?1,2p2?1) = 1; (ii) 令p為奇素數(shù)且p ?≡1 mod 3, 則有g(shù)cd(p ?1,2p2+1)=1.

證明: (i) 設(shè)r為2p2?1 的素因子, ordr2 為2 模r的乘法階, 則有2p2≡1 modr和ordr2|p2. 又p為奇素數(shù)且ordr2?= 1. 因此, ordr2 =p或ordr2 =p2. 此外, 因為r為素數(shù), 故ordr2|(r ?1). 于是,r ?1 是p的偶數(shù)倍, 2p2?1 的每個因子必須具有2kp+1 的形式. 因此, gcd(p ?1,2p2?1)=1.

(ii) 設(shè)r為2p2+1 的素因子, 有2p2≡?1 modr, 則22p2≡1 modr. 令ordr2 為2 模r的乘法階,由于2p2≡?1 modr, 則ordr2 = 2,2p或ordr2 = 2p2. 若ordr2 = 2, 則r= 3. 由假設(shè)可知,r= 3 不可能為p ?1 的一個因子. 對于剩余的ordr2=2p或2p2的情形, 正如我們在(i) 中所述, 可以類似證明r不可能是p ?1 的因子.

引理7 設(shè)p>3 為奇素數(shù),

(i) 若p ≡?3 mod 8 且p ?≡5 mod 24, 或者p ≡3 mod 8, 則gcd(p2+p+1,2p2?1)=1;

(ii) 若p ≡±3 mod 8, 則gcd(p2+p+1,2p2+1)=1 or 3.

注1 借助計算機(jī),可以驗證對不超過105的所有素數(shù)p,引理7 都是成立的. 具體地,對于所有素數(shù)p,1

3 主要結(jié)果

本節(jié)我們將首先回顧二元序列的2-adic 復(fù)雜度的有關(guān)概念. 然后, 利用中國剩余定理(Chinese Reminder Theorem, CRT) 和Zp上的“高斯周期” 得到了Z2p2上的“高斯周期”. 作為本文的主要結(jié)果, 我們將基于文獻(xiàn)[8] 提出的計算方法分析式(1)中定義的序列的2-adic 復(fù)雜度.

由2-adic 復(fù)雜度的定義可知, 確定gcd(2N ?1,S(2)) 是得到序列2-adic 復(fù)雜度的關(guān)鍵步驟. 在給定的條件下, Xiong 等[8]證明了該問題可以轉(zhuǎn)化為計算給定序列相關(guān)的循環(huán)矩陣A的行列式, 并確定gcd(det(A),2N ?1).

引理8[8]設(shè)s是周期為N的二元序列,A=(ak,j)N×N是Z 上的矩陣, 其中ak,j=s(k?j)modN.若det(A)?=0, 則存在u(x),v(x)∈Z[x] 使得

由引理8,gcd(S(2),2N ?1)是gcd(det(A),2N ?1)的一個因子. 特別地,若gcd(det(A),2N ?1)=1,則gcd(S(2),2N ?1)=1. 此時序列s的2-adic 復(fù)雜度達(dá)到最大值log2(2N ?1).

引理9[8]設(shè)s是周期為N的二元序列,A=(ak,j)N×N是Z 上的矩陣, 其中ak,j=s(k?j)modN,則

引理11[9]令符號定義如上, 則

當(dāng)i=0,1 時, 我們需要確定ηi和βi的值. 由于p為奇素數(shù), 由中國剩余定理可知, Z2p與Z?2×Z?p是同構(gòu)的. 于是, 定義同構(gòu)映射如下

因此,

進(jìn)而,

因此,

進(jìn)而,

類似地, 若p ≡±3 mod 8, 則β1=?γ0. 綜上所述, 我們有以下引理.

引理12 令符號定義如上, 則有

這里S(·) 為式(1)定義的序列所對應(yīng)的序列多項式.

證明: 我們將引理13 的證明分為以下幾種情形.

綜合上述情形, 得證.

引理14 沿用與前面相同的符號, 若p ≡±3 mod 8, 則有

證明: 由于該證明與引理13 的證明類似, 故省略.

定理1 設(shè)s是定義在式(1)中的周期為N=2p2(p>3) 的廣義分圓二元序列. 若p ≡±1 mod 8, 則序列s的2-adic 復(fù)雜度為

若p ≡±3 mod 8 以及p ?≡5 mod 24, 則序列s的2-adic 復(fù)雜度下界為

若p ≡5 mod 24, 則序列s的2-adic 復(fù)雜度下界為

此外, 若p ≡11 mod 24, 則序列s的2-adic 復(fù)雜度可以達(dá)到最大值.

證明: 根據(jù)p的取值, 下面分兩種情況進(jìn)行討論.

情形1: 若p ≡±1 mod 8, 由引理8 和引理13, 可得

進(jìn)而,

情形2: 若p ≡±3 mod 8, 由引理8 和引理14, 可得

由于p為素數(shù)且p>3, 可得2p2≡2 modp, 所以2p2+1≡3 modp. 于是gcd(p,2p2+1)=1.

若p ≡±3 mod 8 以及p ?≡5 mod 24, 由引理5, 引理6 和引理7, 可知gcd(det(A),2p2?1) = 1. 因此,

若p ≡11 mod 24, 則由中國剩余定理可知,p ≡3 mod 8 和p ≡2 mod 3. 再由引理7(ii) 中的證明可知, 3 不可能是p2+p+1 的因子. 于是, 由引理6 和引理7, 可得gcd(det(A),2p2±1)=1. 因此,

4 結(jié)論

本文研究了一類具有高線性復(fù)雜度的二元廣義分圓序列的2-adic 復(fù)雜度. 利用Xiong 等[8]給出的計算方法以及數(shù)論相關(guān)知識, 證明了在一些條件下, 此類序列的2-adic 復(fù)雜度可以達(dá)到最大. 我們的結(jié)果表明了此類序列的2-adic 復(fù)雜度不小于其周期的一半, 即此類序列同時具有高的2-adic 復(fù)雜度. 因此, 可以有效抵抗有理逼近算法的攻擊.