国产日韩欧美一区二区三区三州_亚洲少妇熟女av_久久久久亚洲av国产精品_波多野结衣网站一区二区_亚洲欧美色片在线91_国产亚洲精品精品国产优播av_日本一区二区三区波多野结衣 _久久国产av不卡

?

二元周期序列的5錯線性復雜度

2013-08-15 00:55:26周建欽王傳銀
關鍵詞:倍數(shù)復雜度個數(shù)

周建欽,王傳銀

(杭州電子科技大學通信工程學院,浙江杭州310018)

0 引言

線性復雜度是衡量密鑰流序列隨機性的一個重要指標,但高線性復雜度并不能保證序列是安全的。如果改變序列的一個周期段中一個或幾個元素,其線性復雜度發(fā)生很大的變化,則該序列仍然是密碼學意義上的弱序列。為了解決這個問題,文獻1引入了線性復雜度穩(wěn)定性度量指標:k-錯線性復雜度。文獻2給出了2n-周期二元序列s的k-錯線性復雜度嚴格小于線性復雜度L(s)的最小值:kmin=2WH(2n-L(s)),其中WH(b)表示整數(shù)b在二進制表示下的Hamming重量。文獻3給出了線性復雜度為L的2n-周期二元序列的具體個數(shù)。文獻4給出了當k=1,2時,線性復雜度為2n的2n周期二元序列的k-錯線性復雜度分布情況。文獻5給出了2n周期二元序列的3錯線性復雜度分布的完整計數(shù)公式。本文通過將5錯線性復雜度的計算轉化為求Hamming重量最小的錯誤序列,討論了線性復雜度為2n,周期為2n二元序列的5錯線性復雜度分布情況,給出了5錯線性復雜度為2n-3,2n-3+1和2n-3+2n-4的二元序列計數(shù)公式。

1 線性復雜度為2n二元序列的5錯線性復雜度

定義1 設s(n)={s0,s1,s2,…,s2n-1}是二元序列s的第一周期,n≥1,根據(jù)Games-Chan算法,定義映射φn從到

引理1 定義1的映射φn滿足下面的性質(zhì)[4]:

(1)W(φn(s(n)))≤W(s(n));

(2)W(φn(s(n))),W(s(n))奇偶性相同;

引理 2 設 N(L)表示周期為 2n,線性復雜度為 L的二元序列個數(shù)[3],則 N(L)

引理3 設s(n),t(n)是2個不同的二元序列但線性復雜度均為c,1≤c〈2n-3,n〉3,u(n),v(n)是2個不同的二元序列但線性復雜度均為2n,且u(n),v(n)的非零元素個數(shù)分別為1,3或5,則u(n)+s(n)與t(n)+v(n)不同。

證明 欲證明u(n)+s(n)與t(n)+v(n)不同,即證明s(n)+u(n)+v(n)與t(n)不同,即證明u(n)+v(n)與s(n)+t(n)不同。

因為s(n),t(n)是2個不同的二元序列但線性復雜度均為c,1≤c〈2n-3,n〉3,所以s(n)+t(n)的線性復雜度小于2n-3,且s(n)+t(n)的2n個元素可以分成8個相同的部分。

假設u(n)+v(n)和s(n)+t(n)相同,則u(n)+v(n)的2n個元素可以分成8個相同的部分,故u(n)+v(n)的非零元素個數(shù)只能為8,u(n)+v(n)的線性復雜度為2n-3,與s(n)+t(n)的線性復雜度小于2n-3矛盾。

給出具有給定5錯線性復雜度的2n周期二元序列個數(shù)的具體表達式:

定理1 設N5(2n-3)表示周期為2n,線性復雜度為L(s)=2n,5錯線性復雜度為2n-3的二元序列s的個數(shù),n〉3,則 N5(2n-3

證明 設序列s(n)是線性復雜度為2n-3的二元序列,則由引理2知s(n)的個數(shù)為n=5。

設二元序列u(n)的線性復雜度為2n且W(u(n))=1,可知u(n)+v(n)的5錯線性復雜度為2n-3。

設序列u(n)的線性復雜度為2n且W(u(n))=3,且u(n)中任意兩個非零元素距離為2n-3的倍數(shù),易知恰好存在一個序列v(n)且W(v(n))=5,使得u(n)+v(n)的線性復雜度為2n-3,即u(n)+s(n)的5錯線性復雜度小于2n-3。

設序列u(n)的線性復雜度為2n且W(u(n))=5,且u(n)中至少4個非零元素距離為2n-3的倍數(shù),易知恰好存在一個序列 v(n),使得 u(n)+v(n)的線性復雜度為2n-3,即u(n)+s(n)的5錯線性復雜度小于2n-3。

設序列u(n)的線性復雜度為2n且W(u(n))=3,則u(n)的個數(shù)為

設序列u(n)的線性復雜度為2n,W(u(n))=3,且u(n)中任意兩個非零元素距離為2n-3的倍數(shù),則u(n)的個數(shù)為

設序列u(n)的線性復雜度為2n且W(u(n))=5,則u(n)的個數(shù)為

設序列u(n)的線性復雜度為2n,W(u(n))=5,且u(n)中恰好4個非零元素距離為2n-3的倍數(shù),則u(n)的個數(shù)為

設序列u(n)的線性復雜度為2n,W(u(n))=5,且u(n)中任意5個非零元素距離為2n-3的倍數(shù),則u(n)的個數(shù)為

故5錯線性復雜度為2n-3的二元序列s的個數(shù)為

例如,當n=4時,N5(24-3)=7 200,即線性復雜度L(s)=24,5錯線性復雜度為2的二元序列s的個數(shù)為7 200,通過計算機驗證可得同樣的結果。

定理2 設N5(2 +1)表示周期為2,線性復雜度為L(s)=2,5錯線性復雜度為2 +1的二元序列s的個數(shù),n〉4,則

與定理1證明方法類似,只需考慮更復雜的重復情況即可。

定理3 設N5(2n-2-2n-4)表示周期為2n,線性復雜度為L(s)=2n,5錯線性復雜度為2n-2-2n-4的二元序列s的個數(shù),n〉3,則

與定理1、2證明方法類似,只需考慮更復雜的重復情況即可。

2 結束語

通過研究周期為2n的二元序列線性復雜度,將具體5錯線性復雜度值所對應的原序列的計數(shù)轉化為求Hamming重量最小的錯誤序列的個數(shù)。基于Games-Chan算法,本文討論了線性復雜度為2n的2n周期二元序列的5錯線性復雜度分布情況,給出了若干具體5錯線性復雜度對應原序列個數(shù)的計算公式?;谏厦娴挠懻摚瑢﹄S機周期序列的線性復雜度和k錯線性復雜度的統(tǒng)計性質(zhì)[6],也可研究線性復雜度為2n的2n周期二元序列的5錯線性復雜度對應原序列個數(shù)的期望值。

[1] Stamp M,Martin C F.An algorithm for the k-error linear complexity of binary sequences with period 2n[J].IEEE Transactions on Information Theory,1993,39(4):1 398-1 401.

[2] Kurosawa K,Sato F,Sakata T,et al.A relationship between linear complexity and k-error linear complexity[J].IEEE Transactions on Information Theory,2000,46(2):694-698.

[3] Rueppel R A.Analysis and Design of Stream Ciphers[M].Berlin:Springer-Verlag,1986:20-152.

[4] MeidlW.On the stablity of 2n-periodic binary sequences[J].IEEE Transactions on Information Theory,2005,51(3):1 151-1 155.

[5] Zhou J.A counterexample concerning the 3-error linear complexity of 2n-periodic binary sequences[EB/OL].http://www.springerlink.com/content/7 562p69 561 624 154/,2011-05-02.

[6] 蘇明.周期序列復雜度的分布[D].天津:南開大學,2004.

猜你喜歡
倍數(shù)復雜度個數(shù)
說說“倍數(shù)”
巧用“倍數(shù)的和”
同樣是倍數(shù),為啥還不同
怎樣數(shù)出小正方體的個數(shù)
等腰三角形個數(shù)探索
怎樣數(shù)出小木塊的個數(shù)
一種低復雜度的慣性/GNSS矢量深組合方法
怎樣數(shù)出小正方體的個數(shù)
求圖上廣探樹的時間復雜度
如何表達常用的倍數(shù)
北辰区| 丽水市| 中卫市| 天水市| 伊吾县| 弋阳县| 新晃| 汝阳县| 宁河县| 庆元县| 邛崃市| 祁门县| 嵩明县| 峨山| 琼中| 汽车| 托克托县| 丹东市| 五台县| 大石桥市| 海伦市| 桦川县| 盐山县| 宽城| 古丈县| 新建县| 建阳市| 开鲁县| 渭南市| 阳西县| 新营市| 竹山县| 时尚| 临邑县| 大连市| 泸州市| 榆林市| 民勤县| 金秀| 伊宁市| 乐东|