4错线性复杂度的2n周期序列计数

2016-09-06 08:19毕松松戴小平
关键词:复杂度个数线性

毕松松,戴小平

(安徽工业大学 计算机科学与技术学院,安徽 马鞍山243002)

4错线性复杂度的2n周期序列计数

毕松松,戴小平

(安徽工业大学 计算机科学与技术学院,安徽 马鞍山243002)

k错线性复杂度是衡量序列密码稳定性的重要指标之一。给出求满足4错线性复杂度的2n周期序列计数的过程。把4错线性复杂度的研究分解为对关键错误线性复杂度的研究,再用方体理论和筛选法讨论关键错误线性复杂度,得到相应关键错误点(下降点)4错线性复杂度的取值形式,及此时二元序列精确计数公式。最后,归纳出4错线性复杂度所有的取值形式和计算出满足4错线性复杂度的序列计数。

关键错误线性复杂度;k错线性复杂度;方体理论;筛选法

流密码是现代密码学的一个重要分支,研究具有高强度的流密码序列一直是密码学的重要工作之一。高强度的密码序列s要求序列具有高的线性复杂度L(s)和稳定的k错线性复杂度Lk(s)。k错线性复杂度是指当改变序列一个周期中至多k比特后,得到的所有序列中最小的线性复杂度。

已知L(s)或Lk(s),求满足s的计数。文献[4]给出2n周期序列3错线性复杂度的完整序列计数公式。Meidl[5]给出2n周期二元序列1错线性复杂度和2错线性复杂度的分布情况。

给出求满足4错线性复杂度的2n周期序列计数的过程。其研究方法不同于文献[2,4-5]。通过把4错线性复杂度的研究分解为对关键错误线性复杂度的研究,再使用方体理论和筛选法讨论关键错误线性复杂度,最后得到满足4错线性复杂度的序列计数。

1 预备知识

设在有限域GF(2)域上有两序列x=(x1,x2,…,xn)和y=(y1,y2,…,yn),定义x+y=(x1+y1,x2+y2,…,xn+yn),其中“+”为异或运算或模2加法运算。

引理1[7]序列s是以N=2n为周期的二元序列,若L(s)=N,当且仅当WH(sN)为奇数。

引理2[7]序列s是以N=2n为周期的二元序列,若L(s)=0,则满足条件的s的个数为1;若L(s)=L,1≤L≤N则满足条件的s的个数为2L-1。

引理3[8]序列s1,s2是以N=2n为周期的两二元序列,如果L(s1)≠L(s2),则L(s1+s2)=max(L(s1),L(s2));否则,L(s1+s2)<L(s1)。

下面给出方体理论的基本内容,可参考文献[6,9-10]。

定义2 序列s是以N=2n为周期的二元序列,设L(s)=2n-(2i1+2i2+…+2im),0≤i1<i2<…<im<n,若m=1,s有 2个非零元素且形成一条边,边长为2i1,构成一个1方体;若m=2,s有4个非零元素且形成一个矩形,边长为2i1、2i2,构成一个2方体。一般而言,s中有2m-1个非零元素构成一个(m-1)方体,s中另外2m-1个非零元素也构成一个(m-1)方体,这2m-1对元素之间的距离均为2im,则这两个(m-1)方体构成一个m方体,2im为这两个(m-1)方体的距离。

引理4 序列s是以N=2n为周期的二元序列,L(s)=2n-(2i1+2i2+…+2im),0≤i1<i2<…<im<n,线性复杂度第一下降点K=2m。

引理5 序列s是以N=2n为周期的二元序列,若s的非零元素组成一个m方体,且其边长为2i1,2i2,…,2im,0≤i1<i2<…<im<n,则L(s)=2n-(2i1+2i2+…+2im)。

图1所示是一个边长为1,2,4的3方体,其线性复杂度为2n-(1+2+4)。这个3方体可由两个边长为1和4的2方体构成,且这两个2方体之间的距离为2。

下面为筛选法的基本内容,可参考文献[10]。

图1 引理5示意图

从TE中筛选出序列t+e,Lk(t+e)=c,需要排除的序列有两类,第一类是t+e∈TE,但Lk(t+e)<c。第二类是x+u,y+v∈TE,并且Lk(x+u)=Lk(y+v)=c,x≠y,u≠v,WH(u)=WH(v)=k,但x+u=y+v。

对Lk(t+e)<c的情况,设有序列v,WH(v)=k,使得Lk(t+u)=L(t+u+v)<c。从而,有L(u+v)=c。问题可以转化成检查是否存在v,使得L(u+v)=c。对第二类的情况,因L(u+v)=c,根据异或运算规则,有x+y=u+v。而L(x)=L(y)=c,从而L(x+y)<c,进而L(u+v)<c。问题可以转化为检查是否存在v,使得L(u+v)<c。

2 4错线性复杂度的二元序列计数

定义Nk(L)表示周期为2n二元序列s的个数,其中Lk(s)=L,0≤k≤2n。

定义Ni,k(L)表示周期为2n二元序列s的个数,其中Lk(s)=L,i(0≤i≤k)是序列s线性复杂度的第一下降点。

周期为N=2n的二元序列s,据引理1,若WH(sN)为奇数,则改变s一个周期的2个或4个元素,改变后序列的线性复杂度仍为2n;若WH(sN)为偶数,改变s一个周期的2个或4个元素后,线性复杂度可能下降。

定义Ni,k(c0,c1,L)表示周期为2n二元序列s的个数,其中s的线性复杂度为c0,2错线性复杂度为c1,4错线性复杂度为L,i(0≤i≤k)是序列s复杂度的第一下降点。

那么,满足L4(s)=L的序列s的个数为:N4(L)=N0,4(L)+N2,4(L)+N4,4(L)。若求N4(L),需分别求N0,4(L),N2,4(L)和N4,4(L)。

2.1 线性复杂度第一下降点k=0的序列计数

定理1 设s(n)是以N=2n为周期的二元序列,若L(s(n))=L2(s(n))=L4(s(n)),那么L4(s(n))=2n-(2i1+2i2+…+2im),0≤i1<i2<…<im<n,m≥3。

证明 s(n)是周期为2n的二元序列,其线性复杂度为L(s(n))=2n-(2i1+2i2+…+2im),0≤i1<i2<…<im<n,由引理4,使得Lk(s(n))<L(s(n))的kmin=2m。 若L(s(n))=L2(s(n))=L4(s(n)),那么2m>4。 从而,L4(s(n))=2n-(2i1+2i2+…+2im),0≤i1<i2<…<im<n,m≥3。

定理2 设s(n)是以2n为周期的二元序列,若L(s(n))=L2(s(n))=L4(s(n)),其中L4(s(n))=2n-(2i1+2i2+…+2im),0≤i1<i2<…<im<n,m≥3。那么满足条件的二元序列s(n)的个数为2L-1。

证明 由引理2可知,L(s(n))=L,若1≤L≤2n,周期为2n的二元序列s(n)的个数为2L-1。

2.2 线性复杂度第一下降点k=2的序列计数

线性复杂度第一下降点k=2,包含2种情况:(1)线性复杂度第一下降点k=2,第二下降点k>4;(2)线性复杂度第一下降点k=2,且第二下降点k=4。

2.2.1 线性复杂度第一下降点k=2,第二下降点k>4的序列计数

定理3 设 s(n)是以 2n为周期的二元序列,若 L(s(n))>L2(s(n))=L4(s(n)),那么,L(s(n))=2n-2i,L2(s(n))= L4(s(n))=2n-(2i1+2i2+…+2im),0≤i1<i2<…<im,m≥3。

证明 s(n)是周期为2n的二元序列,L(s(n))=2n-(2i1+2i2+…+2im),0≤i1<i2<…<im,若L(s(n))>L2(s(n)),即2错是线性复杂度第一下降点,那么L(s(n))=2n-2i;而第二下降点k>4,那么L2(s(n))=L4(s(n))=2n-(2i1+2i2+…+2im),0≤i1<i2<…<im,m≥3。

由定理3容易看出,研究线性复杂度第一下降点k=2,第二下降点k>4的二元序列,可以通过研究线性复杂度第一下降点k=2的二元序列得到,但是要排除形如 L2(s(n))=2n-2i和L2(s(n))=2n-(2i+2j)两种情况。

定理 4 设 s(n)是以 2n为周期的二元序列,若 L(s(n))>L2(s(n))=L4(s(n)),其中,L(s(n))=2n-2i,L2(s(n))= L4(s(n))=2n-(2i1+2i2+…+2im),0≤i1<i2<…<im,m≥3。

(1)满足条件的二元序列s(n)的个数为22n-i-2×2L-1/(θ×2ε×2n-im-1)。

如果存在i0(0≤i0<i),使得2n-(2i0+2i)<L,那么θ=2i-i0;否则,θ=1。当i<im时,若2n-(2i+2im)>L,ε=0;若2n-(2i+2im)<L<2n-2im,ε=1。

(2)如果L2(s(n))=0,以周期为2n的二元序列s(n)的个数为22n-i-2。

证明 设TE={t+e|t∈T,e∈E},T={t|L(t)=L},其中L(t)=2n-(2i1+2i2+…+2im),并且L(e)=2n-2i。使用筛选法,从TE中筛选出L2(t+e)=L的序列t+e。

(1)由引理2可知,L(t)=L,若1≤L≤2n,周期为2n的二元序列的t个数为2L-1;否则,t的个数为1。

(2)下面求出e的个数,WH(e)=2,L(e)=2n-2i。

设s(i)是以2i为周期的二元序列,若L(s(i))=2i且WH(s(i))=1,那么序列s(i)的个数是2i。周期翻倍,变成2i+1,若线性复杂度为2i+1-2i=2i且WH(s(i+1))=2,那么s(i+1)的个数还是2i。

所以,满足条件WH(e)=2,L(e)=2n-2i的二元序列e的个数为2i×(22)n-i-1=22n-i-2。

(3)由上述可知:当L(t)=0时,t+e的个数为22n-i-2,(2)得证;当L(t)>0时,t+e的个数小于22n-i-2×2L-1,因为此时t+e的个数中存在重复的情况,即存在s+u,t+v∈TE,L2(s+u)=L2(t+v)=L,其中s≠t,u≠v,但s+u=t+v。排除重复序列的思想源自筛选法第二类的情况,需要检查是否存在这样的v,使得L(u+v)=L(s+t)<L,以及这时v的个数。其中WH(u)=WH(v)=2,L(u)=L(v)=2n-2i。下面考虑两种情况。

①跟i0,i有关

对于∀u∈E,若2n-(2i0+2i)<L,0≤i0<i,存在2i-i0-1个v,θ=2i-i0,使得L(u+v)<L。

下面进行举例说明。

假设n=4,i=3时,存在序列u(4)={1000 0000 1000 0000};

满足2n-(22+23)=4<L的v的个数为1,v={0000 1000 0000 1000};

满足2n-(21+23)=6<L的v的个数为3,v={0000 0010 0000 0010};v={0010 0000 0010 0000};

满足2n-(20+23)=7<L的v的个数为7,v={0000 0001 0000 0001};v={0000 0100 0000 0100};v={0001 0000 0001 0000};v={0100 0000 0100 0000}。

②跟im<ω<n有关

对于im<ω<n,存在3×(22)ω-im-1个序列v,使得L(u+v)=2n-(2i+2ω)<L或L(u+v)=2n-2ω<L。

对于满足任意条件的v有2个非零元素,若将v的周期加倍,那么一个原序列将会产生22个新序列。将周期变成2n,存在3+3×22+…+3×(22)n-im-2=(22)n-im-1-1个v,使得L(u+v)<L。

下面给出例子说明。

假设 n=4,i=0时,设有序列 u(4)={1100 0000 0000 0000},只存在 v={0000 0000 1100 0000},使L(u(4)+v)=2n-(2i+2ω)=24-(20+23)=7。只存在v={0100 0000 1000 0000},v={1000 0000 0100 0000},使得L(u(4)+v)=L(u(4)+v)=2n-2ω=24-23=8。

由上可知,当im<ω<n时,在2n-(2i+2im)<L<2n-2im时,v的个数增加(22)n-im-1,ε=1。

综上所述,满足L(s(n))=2n-2i>L2(s(n))=L4(s(n))且L4(s(n))=L的2n周期二元序列s(n)的计数公式为

当i=im或2n-(2i+2im)>L时,ε=0;当2n-(2i+2im)<L<2n-2im时,ε=1。

如果存在i0,使得2n-(2i0+2i)<L,0≤i0<i,那么θ=2i-i0;否则,θ=1。

定理 4已经求得在已知 L(s(n))=c0,L(s(n))>L2(s(n))=L4(s(n))=L时二元序列 s(n)的计数公式。 当已知L4(s(n))=L,而未知L(s(n))=c0时,可以根据定理3给出的L与c0的约束关系,从L推测出c0,进而得到序列s(n)的计数。

例1 若n=4,L(s(n))>L2(s(n))=L4(s(n))=9,求满足条件的以24为周期的二元序列s(n)的个数。由定理3知,L4(s(n))的线性复杂度可以由一个m≥3方体表示,L(s(n))的线性复杂度只能由一个1方体表示。因为n=4,L4(s(n))=9,可以计算出L(s(n))的值为12,14或15。所以,当L(s(n))>L2(s(n))=L4(s(n))时,N2,4(9)=N2,4(12,9,9)+N2,4(14,9,9)+N2,4(15,9,9)=1 024+2 048+4 096=7 168。

2.2.2 线性复杂度第一下降点k=2,第二下降点k=4的序列计数

线性复杂度第一下降点k=2,第二下降点k=4的二元序列分布,文献[10]已给出了相关的结论和证明。

引理6 设s(n)是以2n为周期的二元序列,若L(s(n))>L2(s(n))>L4(s(n)),那么,L(s(n))=2n-2i0,或者L2(s(n))= 2n-(2i+2j),i0<i或者i<i0<j,但是L2(s(n))≠2n-(20+21)。

引理7 设s(n)是以2n为周期的二元序列,若L(s(n))>L2(s(n))>L4(s(n)),并且L(s(n))=2n-2i0,L2(s(n))=2n-(2i+2j),i0<i或者i<i0<j,L2(s(n))≠2n-(20+21),那么

引理8 设s(n)是以2n为周期的二元序列,若L(s(n))>L2(s(n))>L4(s(n)),并且L(s(n))=2n-2i0,L2(s(n))=2n-(2i+2j),i0<i或者i<i0<j,L2(s(n))≠2n-(20+21),并且

那么,满足条件的二元序列s(n)的个数为(24n-j-i-i0-4)×2L-1/(2δ×2ε×16n-im-1)。

如果i0>i,γ=2;或则γ=1。若2n-(2i+2i0+2j)>L,δ=0;若2n-(2i+2i0+2j)<L<2n-(2i0+2j),δ=1;若2n-(2i0+2j)<L,δ=2。当j=im或2n-(2j+2im)>L,ε=0;当2n-(2j+2im)<L<2n-(2i+2im),ε=1;当2n-(2i+2im)<L<2n-(2i0+2im),ε=2;当2n-(2i0+2im)<L<2n-2im,ε=3。

由以上知,L(s(n))>L2(s(n))>L4(s(n))时,若只给出L4(s(n))=L,可以通过相关约束关系求出L(s(n))和L2(s(n)),进而得到二元序列s(n)的计数。

例2 若n=4,L(s(n))>L2(s(n)),L4(s(n))=5,求满足条件的以24为周期的二元序列s(n)的个数。

如果L(s(n))>L2(s(n))>L4(s(n)),由引理8得到L(s(n))=15,L2(s(n))=10;L(s(n))=14,L2(s(n))=11;L(s(n))=12,L2(s(n))=7或L(s(n))=12,L2(s(n))=6。

如果L(s(n))>L2(s(n))=L4(s(n)),由定理3得到L(s(n))=15;L(s(n))=14;L(s(n))=12;L(s(n))=8。

所以,当n=4,L4(s(n))=5,而2错为线性复杂度第一下降点时,

N2,4(5)=N2,4(8,5,5)+N2,4(12,5,5)+N2,4(14,5,5)+N2,4(15,5,5)+N2,4(12,6,5)+N2,4(12,7,5)+N2,4(14,11,5)+N2,4(15,10,5)=64+128+512+1 024+128+256+2 048+4 096=8 256

2.3 线性复杂度第一下降点k=4的序列计数

定理5 设s(n)是以2n为周期的二元序列,若L(s(n))=L2(s(n))>L4(s(n)),那么L(s(n))=L2(s(n))=2n-(2i+2j)。

证明 s(n)是周期为2n的二元序列,L(s(n))=2n-(2i1+2i2+…+2im),0≤i1<i2<…<im,若4错是线性复杂度第一下降点,那么L(s(n))=L2(s(n))=2n-(2i+2j)。

定理6 设s(n)是以2n为周期的二元序列,若L(s(n))=L2(s(n))>L4(s(n))且有L(s(n))=L2(s(n))=2n-(2i+2j),那么

证明 源自筛选法中的第一类的情况,并构造如下框架:设TE={t+e|t∈T,e∈E},其中T={t|L(t)=L},E= {e|WH(e)=4},使用筛选法,从TE中筛选出满足L4(t+e)=L的序列t+e。现研究t+u∈TE,但L4(t+u)<L=L4(s(n))的情况。这种情况等价于检查是否存在v,v∈E,使得L(u+v)=L。对于∀u∈E,有L4(u)=L4(s(n))。

当L4(s(n))=2n-(2i1+2i2+2i3)<2n-(2i+2j)时,使用反证法证明{i1,i2,i3}不包含{i,j}。设n=4,i=0,j=2时,有u(4)={1100 1100 0000 0000}。存在v={0000 0000 1100 1100},使得L(u+v)=25-(20+22+23),所以有L4(t+u)<25-(20+22+23),因此,{i1,i2}≠{i,j}。

同理可得{i2,i3}≠{i,j}。进而,{i1,i2,i3}不包含{i,j}。

同理有i1≠i,j且i2>j。

定理7 设s(n)是以2n为周期的二元序列,若L(s(n))=L2(s(n))>L4(s(n))且有L(s(n))=L2(s(n))=2n-(2i+2j),其中

(1)满足条件的二元序列s(n)的个数为24n-2j-i-6×2L-1/(θ1×θ2×θ3×2ε×16n-im-1)。

如果存在k0,使得2n-(2i+2k0+2j)<L,i<k0<j,那么θ1=2j-k0;否则,θ1=1。

如果存在k1,使得2n-(2k1+2j)<L,i<k1<j,那么θ2=2j-k1;否则,θ2=1。

如果存在k2,使得2n-(2k2+2i+2j)<L,0≤k2<i,那么θ3=2i-k2;否则,θ3=1。

当j<im时,若2n-(2i+2j+2im)<L,ε=0;若2n-(2i+2j+2im)<L<2n-(2j+2im),ε=1;若2n-(2j+2im)<L<2n-(2i+2im),ε=2;若2n-(2i+2im)<L<2n-2im,ε=3。

(2)如果L4(s(n))=0,以周期为2n的二元序列s(n)的个数为24n-2j-i-6。

证明 设TE={t+e|t∈T,e∈E},T={t|L(t)=L},E={e|WH(e)=4},其中L(t)=2n-(2i1+2i2+…+2im),并且L(e)= L2(e)=2n-(2i+2j)。使用筛选法,从TE中筛选出L4(t+e)=L的序列t+e。

1)由引理2可知,L(t)=L,若1≤L≤2n,周期为2n的二元序列的t个数为2L-1;否则,t的个数为1。

2)下面求出e的个数,WH(e)=4,L(e)=L2(e)=2n-(2i+2j)。

设s(i)是以2i为周期的二元序列,若L(s(i))=2i且WH(s(i))=1,那么序列s(i)的个数是2i。周期翻倍,变成2i+1,若改变后序列线性复杂度为2i+1-2i=2i且WH(s(i+1))=2,那么s(i+1)的个数为2i。周期变为2j,(j>i),序列s(j)的个数为(22)j-i-1×2i=22j-i-2。周期翻倍,变成2j+1,若改变后序列线性复杂度为2j+1-(2j+2i)且WH(s(j+1))=4的个数也是22j-i-2。

所以,满足条件WH(e)=4,L(e)=L2(e)=2n-(2i+2j)的二元序列e的个数为22j-i-2×(24)n-j-1=24n-2j-i-6。

3)由上述可知,当L(t)=0时,t+e的个数为24n-2j-i-6,(2)得证;当L(t)>0时,t+e的个数小于24n-2j-i-6×2L-1,因为此时t+e的个数中存在重复的情况,即存在s+u,t+v∈TE,L4(s+u)=L4(t+v)=L,其中s≠t,u≠v,但s+u=t+v。排除重复序列的思想源自筛选法第二类的情况,需要检查是否存在这样的v,使得L(u+v)=L(s+t)<L,以及这时v的个数。其中WH(u)=WH(v)=4,L(u)=L(v)=2n-(2i+2j)。下面考虑两种情况。

①跟i,j,i0有关

定理6已得,L4(s(n))不存在形如,2n-2im,2n-(2j+2im),2n-(2i+2im)和部分2n-(2i1+2i2+2i3)的形式。这些值使得L4(s(n))取值不连续。

对于∀u∈E,若2n-(2i+2k0+2j)<L,i<k0<j,存在2j-k0-1个v,θ1=2j-k0;若2n-(2k1+2j)<L,i<k1<j,存在2j-k1-1 个v,θ2=2j-k1;若2n-(2k2+2i+2j)<L,0≤k2<i,存在2i-k2-1个v,θ3=2i-k2。

若L同时满足上述三种情况或其中两种情况时,v的个数为θ1×θ2×θ3-1。

下面给出例子说明。

假设n=4,i=0,j=3时,设有序列u(5)={1100 0000 1100 0000},那么 满足2n-(2i+2k0+2j)=3<L,i<k0<j,k0=2 的v的总个数有1个,v={0000 1100 0000 1100};满足2n-(2k+2j)=4<L,k=2的v的总个数有3个。其中满足2n-(2i+2k0+2j)=3<L,k0=2的v个数2个;满足2n-(2k1+2j)=4<L,k1=2的v个数2个。所以v的个数共为2×2-1=3。

满足2n-(2i+2k+2j)=5<L,k=2的v的总个数有7个。其中满足2n-(2k1+2j)=4<L,k1=2的v个数2个;满足2n-(2i+2k0+2j)=3<L,k0=2的v个数4个。所以v的个数共为2×4-1=7。

②跟im<ω<n有关

对于 im<ω<n,存在15×(24)ω-im-1个序列 v,使得L(u+v)=2n-(2i+2j+2ω)<L或 L(u+v)=2n-(2j+2ω)<L或L(u+v)=2n-(2i+2ω)<L或L(u+v)=2n-2ω<L。

对于满足任意条件的v有4个非零元素,若将v的周期加倍,那么一个原序列将会产生24个新序列。当周期变为2n时,存在15+15×24+…+15×(24)n-im-2=(24)n-im-1-1个v,使得L(u+v)<L。

下面用例子说明上面的结论。

假设n=4,i=0,j=1,设有序列u(4)={1111 0000 0000 0000}。那么只存在v={0000 0000 1111 0000},使得L(u(4)+v)=2n-(2i+2j+2ω)=24-(20+21+23)=5。只存在v={0101 0000 1010 0000},v={1010 0000 0101 0000},使得L(u(4)+v)=L(u(4)+v)=2n-(2j+2ω)=24-(21+23)=6。只存在 v={0011 0000 1100 0000},v= {0110 0000 1001 0000},v={1001 0000 0110 0000},v={1100 0000 0011 0000},使得L(u(4)+v)=…= L(u(4)+v)=2n-(2i+2ω)=24-(20+23)=7。只存在v={0001 0000 1110 0000},…,v={1110 0000 0001 0000},使得L(u(4)+v)=…=L(u(4)+v)=2n-2ω=24-23=8。

由以上可知,当j<im<n时

若2n-(2i+2j+2im)>L,ε=0;若2n-(2i+2j+2im)<L<2n-(2j+2im),v的个数增加(24)n-im-1,ε=1;若2n-(2j+2im)<L<2n-(2i+2im),v的个数增加3×(24)n-im-1,ε=2;若2n-(2i+2im)<L<2n-2im,v的个数增加7×(24)n-im-1,ε=3。

综上所述,满足L(s(n))=L2(s(n))=2n-(2i+2j)>L4(s(n))且L4(s(n))=L的2n周期二元序列s(n)的计数公式为

如果存在k0,使得2n-(2i+2k0+2j)<L,i<k0<j,那么θ1=2j-k0;否则,θ1=1。

如果存在k1,使得2n-(2k1+2j)<L,i<k1<j,那么θ2=2j-k1;否则,θ2=1。

如果存在k2,使得2n-(2k2+2i+2j)<L,0≤k2<i,那么θ3=2i-k2;否则,θ3=1。

由以上知,若L(s(n))=L2(s(n))>L4(s(n)),当已知L4(s(n))=L,而未知L(s(n))和L2(s(n))时,可以通过约束关系求得L(s(n))和L2(s(n)),进而,求出二元序列s(n)的计数。

例2 若n=4,L(s(n))=L2(s(n))>L4(s(n))=3,求满足条件的二元序列s(n)的个数。由定理5知,L(s(n))的线性复杂度只能由一个2方体表示,并且{i1,i2,i3}不包括{i,j}。可以计算出L(s(n))的值为6,10或13。所以,当L (s(n))=L2(s(n))>L4(s(n))时,N4,4(3)=N4,4(6,6,3)+N4,4(10,10,3)+N4,4(13,13,3)=16+64+1 024=1 104。

2.4 4错线性复杂度的序列计数

由2.1,2.2,2.3小节可以得到

并且给出了计算N0,4(L),N2,4(L)和N4,4(L)的过程。那么,满足L4(s(n))=L的序列s(n)的个数为

求解N4(L)过程,为算法1所示,例3为详述过程:

算法1:求满足4错线性复杂度二元序列计数

Input:4错线性复杂度L4(s),序列周期N

Output:二元序列计数N4

例3 若n=5,L4(s(n))=18,求满足条件的以25为周期的二元序列s(n)的个数。

若L(s(n))=L2(s(n))=L4(s(n)),由定理1可得L(s(n))=18。进而,N0,4(18)=N0,4(18,18,18)=131 072。

若L(s(n))>L2(s(n))=L4(s(n)),由定理4可知L(s(n))的值可为24,28,30或31。

若L(s(n))>L2(s(n))>L4(s(n)),由引理8可知L(s(n)),L2(s(n))的值可为31,26;31,22;31,20;30,27;30,23或28,23。 进而,N2,4(18)=N2,4(24,18,18)+N2,4(28,18,18)+N2,4(30,18,18)+N2,4(31,18,18)+N2,4(31,26,18)+N2,4(31,22,18)+N2,4(31,20,18)+N2,4(30,27,18)+N2,4(30,23,18)+N2,4(28,23,18)=191 889 408。

当L(s(n))=L2(s(n))>L4(s(n))时,由定理7可得L(s(n))的值为29,27,23。进而,N4,4(18)=N4,4(29,29,18)+N4,4(27,27,18)+N4,4(23,23,18)=44 040 192。

所以,N4(18)=N0,4(18)+N2,4(18)+N4,4(18)=236 060 672。

3 结语

文中给出求满足4错线性复杂度的2n周期序列计数的过程。通过将4错线性复杂度的研究分解为对关键错误线性复杂度的研究,再使用方体理论和筛选法讨论关键错误线性复杂度,最后得到满足4错线性复杂度序列的计数,并且用计算机编程得到的数据佐证了给出的求解过程的正确性。文中的研究方法可以推广到求解其他k错线性复杂度序列计数。但是,随着k值的增大,其求解过程将变得繁琐。下一步,将研究简便的方法来讨论序列k错线性复杂度,力争进一步完善k错线性复杂度的研究。

[1]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.

[2]皮飞,戚文峰.二元周期序列的4错线性复杂度[J].电子学报,2011,39(12):2914-2920.

[3]ETZION T,KOLOKOTRONIS N,LIMNIOTIS K,et al.Properties of the error linear complexity spectrum[J].IEEE Trans on Inform Theory,2009,55 (10):4681-4686.

[4]周建钦.具有2n线性复杂度的2n周期二元序列的3错线性复杂度[J].应用数学学报,2013,36(3):399-413.

[5]MEDIDL W.On the stability of 2n-periodic binary sequence[J].IEEE Trans on Information Theory,2005,51(3):1151-1155.

[6]ZHOU Jianqin.On the k-error linear complexity for 2n-periodic binary sequences via Cube Theory[J].Eprint Arxiv,2013,73(1):55-75.

[7]周建钦,戴小平.具有稳定k错线性复杂度的周期序列[J].通信学报,2011,32(11A):213-220.

[8]戴小平,毕松松,王喜凤,等.k错线性复杂度具有第二下降点的 2n周期序列[EB/OL].[2015-04-10].http://www.cnki.net/kcms/detail/ 31.1289.TP.20150410.1634.004.html.

[9]ZHOU J Q,LIU W Q.The k-error linear complexity distribution for 2n-periodic binary sequence[J].Designs Codes and Cryptography,2014,73:55-75.

[10]ZHOU J Q,LIU W Q,WANG X F.Structure Analysis on the k-error Linear Complexity of 2n-periodic Binary Sequences[EB/OL].[2014-08-09].http://arxiv.org/abs/1312.6927.

责任编辑:艾淑艳

Counting functions for 2n-periodic binary sequences with 4-error linear complexity

BI Songsong,DAI Xiaoping
(School of Computer Science&Technology,Anhui University of Technology,Ma'anshan 243002,China)

The k-error linear complexity is one of the important measures for assessing the stability of sequence cipher.First,we presented the process of counting functions of 2n-periodic binary sequences with given 4-error linear complexity.Then we studied the critical error linear complexity via cube theory and sieve method.The possible values of the 4-error linear complexity of corresponding critical error point(descent point)were obtained and the number of sequences with given 4-error linear complexity of corresponding critical error point were established.Finally,we got the all the possible value forms of the 4-error linear complexity and the counting functions of 2n-periodic binary sequences.

critical error linear complexity;k-error linear complexity;cube theory;sieve method

TP918.1

A

1672-0687(2016)02-0055-09

2015-04-16

安徽省自然科学基金资助项目(1208085MF106);安徽省教育厅自然科学基金资助项目(KY2013Z025);安徽工业大学校青年科学基金资助项目(QZ201412)

毕松松(1990-),男,安徽凤台人,硕士研究生,研究方向:信息安全与密码学。

猜你喜欢
复杂度个数线性
渐近线性Klein-Gordon-Maxwell系统正解的存在性
怎样数出小正方体的个数
线性回归方程的求解与应用
等腰三角形个数探索
怎样数出小木块的个数
一种低复杂度的惯性/GNSS矢量深组合方法
二阶线性微分方程的解法
怎样数出小正方体的个数
求图上广探树的时间复杂度
某雷达导51 头中心控制软件圈复杂度分析与改进