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

柯品惠, 盧櫟羽, 陳智雄

1. 福建師范大學 數學與統計學院, 福州350117

2. 福建省應用數學中心(福建師范大學), 福州350117

3. 莆田學院 應用數學福建省高校重點實驗室, 莆田351100

1 引言

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

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

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

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

2 基礎知識

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

定義

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

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

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

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

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

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

引理7 設p>3 為奇素數,

(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 借助計算機,可以驗證對不超過105的所有素數p,引理7 都是成立的. 具體地,對于所有素數p,1

3 主要結果

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

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

引理8[8]設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 復雜度達到最大值log2(2N ?1).

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

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

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

因此,

進而,

因此,

進而,

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

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

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

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

綜合上述情形, 得證.

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

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

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

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

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

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

證明: 根據p的取值, 下面分兩種情況進行討論.

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

進而,

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

由于p為素數且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 結論

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