证明G-C算法的新途径
开篇：润墨网以专业的文秘视角，为您筛选了一篇证明G-C算法的新途径范文，如需获取更多写作素材，在线客服老师一对一协助。欢迎您的阅读与分享！
摘要 本文利用有限域F2中元素的运算特性，将2n周期二元序列的线性复杂度用另一种形式表现出来，进而利用这种分析方法对G-C算法进行了重新证明。
中图分类号TH2 文献标识码A 文章编号 1674-6708（2011）40-0110-02
0 引言
令Fq表示有q个元素的有限域。对于Fq上的序列，若存在正整数p>0，使得对所有的n都成立，则称序列是终归周期的，且称p是序列的一个周期。所有可能周期的最小者称为序列的最小周期。对于周期为N的序列来说，它的线性复杂度定义为生成该序列的最短的线性反馈移位寄存器（）（[4][2]）的长度，即满足存在某些，使得对所有的都成立的最小的L。多项式称为序列的生成函数。可见，，其中，称多项式为序列的极小多项式。序列的极小多项式是唯一的，且。
周期序列的线性复杂度是流密码强度的一个重要度量指标。密码学意义上强的序列应该具有足够高的线性复杂度，这是因为只要知道连续个比特，即可通过解线性方程组或者借助B-M算法[2，6]将整个序列完全确定出来。
目前关于线性复杂度的算法已经有许多研究，除了前面提到的B-M算法，还有周期为2n的二元序列的线性复杂度的算法，一般常称为G-C算法[2，3，6]。一般情况下，B-M算法确定序列的线性复杂度是很有效的，文献7、8都给出了该算法的证明，但是对于周期为2n的二元序列，G-C算法要比B-M算法快得多，但其不能用于上周期为的序列（p为素数）。我国学者丁存生于1988年将G-C算法推广到上周期为的序列上[1]。
本文想从另一个角度来描述周期为2n的二元序列的线性复杂度，得到它的另一种新的表达形式，进而重新证明G-C算法，可以看到一些新的性质可以很容易的推导出来，而且已有的结果还可以大大的化简。
如无特别说明，以下均在F2上进行。
1 序列的线性复杂度的另一种表示
定理2.1设是周期为N=2n的二元序列，其生成函数为，进行变换。令中次数最低的项的次数为t，则序列的线性复杂度，而极小多项式为。反之，如果序列的线性复杂度，则中次数最低的项的次数为t[9]。
2 对G-C算法的重新证明
文献6给出了一个可以快速计算周期为N=2n的二元序列的线性复杂度的算法，简称为G-C算法。在文献6中，证明该算法成立的过程比较繁琐。根据上面的分析方法，我们可以大大简化证明过程。
定理3.1 （G-C算法）
设周期为N=2n的二元序列的一个周期为，令，定义，其中加法是逐项模2加法。
1）若，则；
2）若，则。
证明：在序列的生成函数中，。
令，
则。
1)当时，。
。
令，。则在变换下变为。设的次数最低的项的次数为t'，则在变换下次数最低的项的次数为，根据定理2.1，线性复杂度为，这也是生成函数为
的周期为的序列即的线性复杂度。
2）当时，。对进行变换，有
由易知，
，对应的变换结果满足。
由于中项的次数最低不小于，所以的次数最低项的次数等于的次数最低项的次数，令其为t'。根据定理2.1，线性复杂度应为。对于周期为的二元序列，容易求得它的线性复杂度应为。所以。证毕。
G-C算法就是重复利用上面结果进行迭代运算：
令为周期为2n的二元序列，LC表示序列的线性复杂度，初值为0；
当时，，把分成两部分和。如果，则，
；如果，则。
重复上面过程，直到n=0。这时如果a0=0，则，否则。
最终的LC的值就是序列的线性复杂度。
可以看出，G-C算法得到的线性复杂度LC，等于算法中时对应的2n的积累和。当序列不是全零序列时，，容易推断出算法最后一步n=0时a0一定为1，肯定使得LC加1。所以当对非全零序列使用G-C算法求线性复杂度时，上面算法最后一步可以省略，直接对LC加1即可。这时LC可写成类似于二进制展开的形式：
其中表示比大的最小的整数。注意这个形式与二进制展开是有区别的，一定是这种形式。当LC是奇数时，这个形式就是二进制展开，而偶数时就不同。我们称这种表示形式为“复杂度展开”。复杂度展开可以清晰的说明在G-C算法中在哪一步中，即哪一步“产生”了线性复杂度。例如当时，G-C算法中只有最后连续的k步“产生”了线性复杂度。
由上面的结果和分析可见，在引入一个简单变换之后，周期为2n的二元序列的线性复杂度的表示和分析变得十分直观和简单。这主要是因为本来在求线性复杂度时需要计算最大公因式，而在变换之后，不必求最大公因式，只需要求多项式的次数最低项的次数即可。这样就使得序列的理论分析非常简单。
参考文献
[1]丁存生，肖国镇.流密码学及其应用[M].国防工业出版社，1994.
[2]孙淑玲.应用密码学[M].北京：清华大学出版社，2004.
[3]沈世镒，陈鲁生.信息论与编码理论[M].北京：北京邮电大学出版社，2004.
[4]章照止.现代密码学基础[M].北京：北京邮电大学出版社，2004.
[5]胡予濮，张玉清，肖国镇.对称密码学[M].北京：机械工业出版社，2002.
[6]R.A.Games, A.H.Chan.“A fast algorithm for determing the complexity of a pseudorandom sequence with period 2n”.IEEE Transactions on Information Theory,Vol.29,No.1,1993：144-146.
[7]Imamura K and Yoshida W,“A simple derivation of the Berlekamp-Massey algorithm and some applications”. IEEE Transactions on Information Theory, Jan.1987，IT-33(1)：146-150.
[8]万哲先.代数和编码[M].北京：科学出版社，1985.
[9]姜凌.“关于周期为2n的二元序列的一点研究”[J].科技信息，2010，15：148.