几类伪随机序列的研究_图文

1、分类号口翌密级编号中国科学院研究生院博士学位论文且耋鱼瞳扭压到鲍婴窒塑堑塑指导教师墨登国熬援虫国科堂睦班嚣生睫值星塞全垦塞重盛塞坠窒申请学位级别煎±学科专业名称通篮生信息丕缠论文提交日期§玺旦论文答辩日期蝼生旦旦培养单位虫国整堂瞳婴筮生睦生垦揖堂隧垒王堂硒冠压学位授予单位史国抖堂隧亚塑生医答辩委员会主席墓盍厶瞳圭摘要伪随机序列在密码学、扩频通信、计算、控制等领域都有广泛的应用。伪随机序列的设计和分析一直是国际上的研究热点，寻找新的方法来设计更多性质良好的序列，以及寻找更有力的工具来分析清楚已有序列的性质，都是非常有价值的工作。在本文中，我们对伪随机序列中的几个问题进行了深入

2、的研究，这些问题是：带进位的反馈移位寄存器（）、二元序列的复杂度、周期序列的广义离散傅立叶变换和周期序列的一线性复杂度、两类邑导出序列的独立一样式分布和部分周期性质、利用函数域设计序列等等。具体地说主要贡献如下：）给出了序列分布的明显公式，利用这个公式讨论了序列的游程分布等分布性质。讨论了序列的通常自相关和算术自相关。证明了二元序列在某些条件下具有大的和线性复杂度。）指出了二元周期序列线性复杂度和复杂度的一个显著的差别，讨论了这个差别对序列综合的影响。基于这一观察，给出了更加合理的二元周期序列对称复杂度的概念。计算了二元周期序列复杂度和对称复杂度的期望值。给出了二元周期序列复杂度和对称复杂度的

3、非平凡下界。）指出上年和年的两篇论文的结果本质上是一祥的。）将周期序列的广义离散傅立叶变换应用到周期序列的线性复杂度的研究中去，构造了许多具有大的线性复杂度的序列，改进了的结果。）利用环上的指数和估计分析了两类磊导出序列的独立一样式分布，证明了它们都是渐进均匀的，所得结果改进了以前的公开结果。）利用环上的混合指数和估计与离散傅立叶变换，给出了环上的部分指数和估计。）利用环上的部分指数和估计，分析了两类邑导出序列的部分周期分布和部分周期独立一样式分布，证明了它们也都是渐进均匀的。摘要）利用函数域的扩张构造了一类新的具有低相关和高线性复杂度的二元周期序列，并且使用椭圆函数域的理论给出了一些具体例子

4、。在某些情况下，我们的构造方法比等学者的构造方法更好，关键词线性复杂度，线性复杂度，复杂度，复杂度，环上的指数和，环上的部分指数和，周期序列的一样式，函数域，函数域的扩张。（），：（），一，扬，：），），），邑），¨），：，研究成果声明本人郑重声明：所提交的学位论文是我本人在指导教师的指导下进行的研究工作获得的研究成果。尽我所知，文中除特别标注和致谢的地方外，学位论文中不包含其他人已经发表或撰写过的研究成果，也不包含为获得中国科学院电子学研究所或其它教育机构的学位或证书所使用过的材料。与我一同工作的合作者对此研究工作所做的任何贡献均已在学位论文中作了明确的说明并表示了谢意。特此申明。

5、签名：锅幼习日期：神关于学位论文使用权的说明本人完全了解中国科学院电子学研究所有关保留、使用学位论文的规定，其中包括：电子所有权保管、并向有关部门送交学位论文的原件与复印件；电子所可以采用影印、缩印或其它复制手段复制并保存学位论文；电子所可允许学位论文被查阅或借阅；电子所可以学术交流为目的，复制赠送和交换学位论文；电子所可以公布学位论文的全部或部分内容（保密学位论文在解密后遵守此规定）。签名：钥譬）羽日期：矽日期：矿导师签名：。，设曩第一章绪论§研究背景和意义随着计算机和通信网络的广泛应用，信息安全越来越受到人们的重视，在年发表了著名论文“保密通信的信息理论”，这是密码年，、和提出了

6、著名的算法。同当今的密码体制根据密钥的特点可以分为对称密码体制和非对称密码，小是明文比特流，觑，是密钥比特流，：，是密文比特流，。鬼序列密码加解密实现方式简单，速度快，而且理论相对比较成熟（一个而密码技术是保证信息的安全性的关键技术。随着社会的进一步发展，密码技术将得到更加广泛的应用，这将为密码学的发展提供更加广阔的舞台。学由一门艺术成为一门科学的标志。到了上个世纪年代，人类开始进入信息时代，密码学也进入了快速发展的时期。年，和发表了“密码学的新方向”，提出了公钥密码体制，使密码学经历了一场变革。年，美国公布了由公司研制的数据加密标准（）。从此以后，密码学不再局限于政治和军事，其商用价值和社会

7、价值得到充分肯定。大量的密码学论文开始出现，许多有关信息安全的工业标准被公布，进入这一领域的公司和大学也越来越多体制。在对称密码体制中，加密密钥和解密密钥相同，或者从一个容易得到另一个。然而在非对称密码体制中，加密密钥和解密密钥不同，从一个很难得到另一个，加密和解密是可分离的按照具体实现方式对称密码体制又可分为序列密码和分组密码两种基本方式。在序列密码体制中，加密时将明文消息字符流逐位地加密成密文消息字符流，解密时则将密文消息字符流逐位地解密成明文消息字符流。下面用二元时的例子来说明。设那么相应的加解密变换是重要原因是数学这一工具可以有效地用来研究它），因而受到广泛重视。序第一章绪论列密码算法

8、的安全强度取决于相应的密钥流的质量，因而产生好的密钥流是序列密码体制的关键问题。：证明了如果密钥流序列是真随机的，那么相应的序列密码体制将是完善保密的。通常有下面几种方式来产生真随机序列：使用随机噪声、使用计算机时钟、测量键盘反应时间等等。真正随机的序列是不能重复产生的，即使你用相同的输入对序列发生器操作两次，你将得到两条完全不同的序列。在一般的应用环境中生成和使用真随机序列是不现实的，因此人们便退而使用伪随机序列做为密钥流，于是如何产生和评价伪随机序列便成为序列密码的一个非常重要的问题。在密码学的其它领域，伪随机序列也被广泛使用，比如著名的和数字签名算法这两个数字签名算法分别基于有限域上的离

9、散对数和椭圆曲线上的离散对数这两个困难问题，在签名过程中需要使用伪随机数。虽然求解有限域和椭圆曲线上的离散对数都是困难的，但是如果签名过程中使用的伪随机数不安全，这两个签名算法将很容易被攻击。伪随机序列在扩频通信中也有重要应用。从上个世纪年代开始，数字无线通信开始成为主流，实际的系统有等。由于无线信道是开放的，通信环境很容易受到各种干扰，使得信号传输的可靠性降低。另一方面，无线业务的快速增长要求无线网络具有高度的灵活性，以逶应业务的发展变化。这些都是传统的无线通信系统无法解决的。扩频通信将待传输的信号用伪随机序列调制，实现频谱扩展后再传输，很好地解决了上面的可题。扩频时使用的伪随机序列，要求具

10、有低的非平凡自相关和互相关，这保证了同步相关的输出远远大于非同步相关的输出，大大降低了信号之间的干扰。在扩频通信中，所有用户可以共用同一频带，简化了系统的设计，提高了灵活性。而们已经知道了它们的许多性质，但仍然有更多的秘密不为人知，这需要更加此外，伪随机序列在编码、计算、控制等领域中也有广泛的应用。从上面的讨论可以看出，伪随机序列不是一个孤立的问题，它与数学、且扩频通信还具有保密、高精度测量等优点。寻找扩频时所需要的伪随机序列是国际上众多学者长期以来一直进行的工作。另一方面，对于现在已经找到的那些伪随机序列，分析清楚它们的各种性质也是非常有意义的。虽然人有力的数学工具。通信、计算机等等许多领域

11、都有联系，它既有很强的理论背景，也有很强的应用背景，因此从事这方面的研究是有意义的。而且这方面的问题将一直被第一章绪论人们讨论下去。一条周期序列应该尽可能满足以下几个随机性准则（我们用上的序列做为例子）：）大的周期：任意确定性算法生成的序列都是周期的，要想获得好的随机性，周期应该尽量大；）平衡性：比如在二元序列的一个周期段中，与的个数相羞要尽量小。一条不平衡的伪随机序列在实际应用中无疑会带来安全隐患；）高的线性复杂度；一条序列的线性复杂度定义为生成该序列的最短线性反馈移位寄存器的长度。如果用表示所考虑序列的线性复杂度，使用算法，只需连续的比特就可以恢复整条序列，因此低线性复杂度的序列做为密钥流

12、是很不安全的。）良好的统计特性：在文献中，认为对于一条伪随机序列，在每个周期内，它的一游程和一游程的数目基本相等。）二值自相关函数：同样地，在文献中，认为对于一条伪随机序列，它的周期自相关函数应该是二值的。但是，在一般情况下这个要求难以达到，人们退而要求伪随机序列的自相关函数应该是低值的。对于有限序列，人们也提出了许多衡量其随机性的指标。比如：频数、块内频数、跟随性、重叠子序列、游程变化、游程分布等等。下面我们给出两个例子。】和用能生成这条序列的最短图灵机程序的长度描述这条序列的随机性。另一种度量有穷序列的随机性的方法是由和提出的所谓“线性复杂度“的方法，规定用产生该序列的最短线性反馈移位寄存

13、器的长度来度量随机性计算能产生给定序列的最短非线性反馈移位寄存器是很困难的，但是算法能够有效地计算出产生给定序列的最短线性反馈移位寄存器。因此，这是一个非常实用的参数。年，和提出了一种新的产生伪随机序列的移位寄存器结构一带进位的反馈移位寄存器（），并提出了二元序列复杂度的新的度量指标一一复杂度。在此后的这些年中，、以及其他许多学者做了很多有关的有价值的工作。题值得我们进一步考虑。和既有许多相似之处，也有许多不同之处。有关和复杂度的问第一章绪论如果一条序列虽然具有大的线性复杂度，但是改变少量元素后会引起线性复杂度的显著降低，那么这条序列序列用到密码学中也是不安全的。基于这一想法，和独立提出了线性

14、复杂度的概念。由于这一想法的重要性，此后这个领域一直受到广泛关注。直到现在，仍然有许多问题没有解决。从上个世纪中叶以来，人们研究最多的是有限域上的序列。到了上个世纪年代末，环上的序列开始成为人们关注的热点。由于环的结构比域的结构更复杂，因此环上的序列不但数目更多，而且密码学性质更好，更难于攻击。研究环上的序列需要更深入的数学工具，而且人们研究的时间也还很短，这方面还有许多问题没有搞清楚。寻找更多更好的扩频序列一直是人们最求的目标。到目前为止，人们已经找到了许多这样的序列，比如：序列、序列、序列、级联序列、序列等等。等学者首次使用函数域来构造伪随机序列，他们使用函数域的扩张构造了一类具有低相关和

15、高线性复杂度的二元周期序列。由于这一思想提出还不久，是否能构造出更多的性质好的伪随机序列值得进一步考虑。§国内外研究现状首先我们介绍和复杂度方面的研究进展情况在文献中，和提出了带进位的反馈移位寄存器（）。这种移位寄存器的结构与线性反馈移位寄存器（）的结构很相似，主要区另是引入了记忆，分析的数学理论是数理论。的输出序列我们称为序列，当序列的周期达到最大时，和将其称为一序列。一序列是序列的算术版本。在文献中，和将原始的推广到了数的分歧扩张的情况，并分析了在这种情况下输出序列的性质。基于这种新的，他们找到了求和发生器的明显弱点【。在文献】中，和系统地研究了一序列的性质，比如它们的构造和统计

16、性质等等。和利用指数和估计证明了一序列在部分周期内和的分布是渐进均匀的。和在文献】中讨论了序列的综合问题，给第一章绪论出了有理逼近算法，该算法可以有效地找出生成给定序列的最短。后来，他们在文献中又给出了一种的移位寄存器结构，并在文献中详细分析了序列的分布特点。关于序列的线性复杂度，文献中给出了它们的下界。关于和的具体实现方式，文献中讨论了两种结构：结构和结构在文献中，和给出了周期序列算术相关的概念，并且构造了具有理想算术互相关的大的序列簇。受到定理的启发，、和在文献中研究了二元周期序列的傅立叶变换和它的复杂度的关系，给出了带进位版本的定理。竹卜序列和它们的采样序列之间的移位等价关系是容易确定的

17、，但一序列却要复杂很多。在文献中，作者利用指数和估计证明了在某些情况下一序列和它的采样序列不是移位等价的，而且作者猜想一序列和它所有的采样序列都不是移位等价的。在文献中，和设计了完备环上的反馈移位寄存器，这是和的共同推广。下面我们介绍序列的线性复杂度方面的研究进展情况和独立地提出了线性复杂度的概念。在文献中，作者初步分析了二元序列的线性复杂度的一些性质，并且提出了一个猜想：周期序列的线性复杂度和线性复杂度存在制约关系，它们不可能同时取得很大的值。在文献中构造了许多同时具有大的线性复杂度和大的线性复杂度的周期序列，从而否定了的这个猜想。文献给出了周期为“的二元序列的线性复杂度的快速计算方法。、盯

18、和在文献中将该算法推广到了上周期为矿的序列的情况。文献】讨论了周期序列在一个符号替换下的线性复杂度，证明了周期序列的线性复杂度可以由该序列的极小多项式计算出来。关于一般情况下周期序列线性复杂度，文献】给出了它们的非平凡下界对于某些特殊周期序列，几位日本学者在文献】中确定了最小的使得这些序列的线性复杂度严格小于它们的线性复杂度。对于线性复杂度这种特殊情况，文献给出了个陕速算法计算周期为”一的二元序列的线性复杂度，并给出了几条设计具有大的线性第一章绪论复杂度的二元周期序列的准则。在文献中，作者设计了一个快速算法计算周期序列的线性复杂度谱。该算法在文献中被改进。和在文献中研究了周期序列的离散傅立叶变

19、换和线性复杂度之间的关系。接着我们介绍一下环上序列的研究进展情况近多年来，环上的序列设计和分析一直是国内外的热点。文献研究了邑上本原序列的最高权位序列的最小周期和极小多项式。在文献中，作者给出了上本原序列的最高权位序列的线性复杂度的下界。在文献中证明了具有重要密码学价值的保墒定理。等著名学者在文献【中给出了环版本的指数和估计，这个指数和估计对于设计和分析环上序列具有基础性的作用。后来在文献中，和在特征为的情况下改进了这类指数和。在文献中，和他的合作者又给出了一类上的混合指数和（）估计，并利用这样的指数和估计分析了一些环导出序列的非周期自相关。受到文献】和的启发，此后人们又给出了一些类似的环上的

20、指数和估计。在文献【中，和利用文献中的指数和估计分析了邑上本原序列的最高权位序列的、分布，改进了文献中的结果。一样式分布是有限域上周期序列的重要性质文献【和讨论了一般环上的极大长序列的最高权位序列的独立一样式分布，证明了它们是渐进均匀的。在文献】中，几位作者研究了磊上的码导出的二元序列，证明它们具有大的线性复杂度、高的非线性度和低的互相关和非平凡自相关。在文献】中，两位作者利用】中的方法，分析了最高权位序列的、分布，进一步改进了文献中的结果最后我们介绍一下函数域在序列设计中的应用情况，有限域和有限环一直是序列设计的常用方法，等学者首次将函数域引入到序列设计中来，找到了一系列性质良好的序列。在文

21、献】中，和设计了许多具有几乎完美线性复杂度轮廓的序列（）。在文献（嘲中，和他的合作者又改进了文献】中的方法在文献，中，进一步将这一套方法推广到多序列的情况。等几位学者在文献阳中利用函数域的扩张构第一章绪论造了一类具有低相关和高线性复杂度的二元周期序列，并且分别就有理函数域和椭圆函数域两种情况给出了具体例子。姐本文的主要结果和章节安排在本文中，我们对伪随机序列的设计和分析中的几个问题进行了深入研究，主要有：带进位的反馈移位寄存器（）和二元序列的复杂度、周期序列的广义离散傅立叶变换和周期序列的线性复杂度、环邑导出序列的独立样式分布和部分周期性质、函数域与序列设计等等。具体地说主要贡献如下：）给出了

22、序列分布的明显公式，利用这个公式讨论了序列的游程分布等分布性质。利用一般情况下序列的指数表示分析了一个周期内元素之间的关系。讨论了序列的通常自相关和算术自相关。证明了二元序列在某些条件下具有大的和线性复杂度。）指出了二元周期序列线性复杂度和复杂度的个显著的差别，讨论了这个差别对序列综合的影响。基于这一观察，给出了更加合理的二元周期序列非对称复杂度的概念。计算了二元周期序列复杂度和非对称复杂度的期望值。给出了二元周期序列复杂度和非对称一复杂度的非平凡下界）指出上年和年的两篇论文的结果本质上是一样的。）将周期序列的广义离散傅立叶变换应用到周期序列的线性复杂度的研究中去，构造了许多具有大的线性复杂度

23、的序列，改进了的结果。）利用环上的指数和估计分析了两类邑导出序列的独立。样式分布，证明了它们都是渐进均匀的，所得结果改进了以前的公开结果。）利用环上的混合指数和估计和离散傅立叶变换，给出了环上的部分指数和估计。）利用环上的部分指数和，分析了两类邑导出序列的部分周期分布和部分周期独立一样式分布，证明了它们也都是渐进均匀的。第一章绪论）利用函数域的扩张构造了一类新的具有低相关和高线性复杂度的二元周期序列，并且使用椭圆函数域的理论给出了一些具体例子。在某些情况下，我们的结果比以前的公开结果更好。本文的章节安排如下：第一章（本章）介绍了研究伪随机序列的背景和意义，以及国内外的研究进展。第二章给出了以后

24、各章会共同用到的一些基本概念，并简单讨论了它们的性质。第三章分析序列的统计性质和线性复杂度，对二元周期序列的复杂度进行深入研究。第四章利用周期序列的广义离散傅立叶变换研究周期序列的线性复杂度，改进了的结果。第五章对邑导出序列进行了深入分析。第六章利用函数域的扩张构造一类新的具有低相关和高线性复杂度的二元周期序列，并给出了具体例子。第二章基本概念和性质为了方便以后四章的工作，我们在这一章中给出它们会共同用到的一些基本概念，并简要讨论这些概念的一些性质。对于以后各章单独需要的那些概念和预备知识，我们则在各章中分别给出。§序列的周期和线性复杂度日是有个元素的有限域，其中是某个素数的方幂。本

25、章考虑的序列都是只上的。定义设（）是上一条半无限序列，如果存在正整数丁和非负整数”使得。对任意都成立，我们称序列是终归周期的，称为的一个周期。序列的所有周期的最小值称为它的最小周期，记为（）。如果他，我们称序列是周期的。如果（）是最小周期为于的周期序列，我们也把它记为（￥）。定义（）是日上一条半无限序列，它的线性复杂度定义为满足如下条件的最小的：是一个非负整数，存在，日，使得下面的关系成立；¨，任意的线性复杂度记为（）。需要指出的是，如果（。）是最小周期为的周期序列，那么（）。线性反馈移位寄存器（）是产生伪随机序列的非常有用的装置之一，它的一般形式如图所示（本图来自文献）。记号和条件

26、同定义，多项式（）。一陋称为序列的零化多项式。当时，首一的零化多项式称为特征多项式。此时多项式（），（一）第二章基本概念和性质图：线性反馈移位寄存器称为序列的联结多项式。次数最小的特征多项式称为序列的极小多项式。因此极小多项式的次数就是生成序列的最短的线性反馈移位寄存器的长度，即序列的线性复杂度。年，给出了一个迭代算法来译码。两年后，将其成功用于线性移位寄存器的综合问题。算法可以有效地计算序列的线性复杂度，它的时间复杂度为（），空间复杂度为（）。因此，如果一条序列的线性复杂度太低，它在密码学上是不安全的。下面介绍塌上的形式幂级数环玛】。任意日盼中的元素（）可以表示成未定元。的形式幂级数。以扛）

27、。（。其中称为（）的系数。日】中的两个元素（）茎。和（）墨相等，当且仅当它们的所有系数相等，即，任意任意吲中的多项式尸（）十“可以看成形式幂级数（）扩”十计，于是成为【旧的子集。日中的加法和乘法定义为：！在这种规定下，：蚴枷。脚啪石玛】形成一个整环。如果（）（。），我们称（）和（）互为乘法逆元。第二章基本概念和性质定理玛盼】中的元素（）；。是乘法可逆的当且仅当，如果它的乘法逆元存在那么必定唯一。序列的周期与多项式的周期或阶有密切的联系，下面介绍多项式的周期及其性质。定义设（）是日中一个次数不小于的多项式，而且（），使得厂（）（一护）成立的最小的称为，（）的阶，记为（）。如果（），那么存在整数和

28、（）矧，使得（）。夕（），我们规定（）为（）。引理，如果（）的次数，；（），那么（）（”一）。引理，设是上的一条周期序列，它的极小多项式为（），那么的最小周期等于（）。本原多项式是一类特殊的多项式，下面给出它们的定义。定义如果（）蜀的次数礼，（），如果（）旷一，那么，（）称为本原多项式。联结多项式为本原多项式的非零周期序列称为一序列。一序列具有许多良好的统计性质，它在密码学和通信中有着广泛的用途。但它也有一个明显的缺点，那就是线性复杂度太低。对于半无限序列（），它的生成函数定义为）十铷对于有限序列，可以在它的后面添加无数个，从而将其看做无限序列。下面这个定理常常用来计算周期序列的线性复杂度和极

29、小多项式。对于某些特殊情况，可以据此设计出一蝗快速算法，。定理归玎设（）是日上一条周期为的周期序列不必为的最小周期，它的生成函数是（），令）一那么（）表示为）辫墨！型（鱼！二望（一）（岛（），一丁）第二章基本概念和性质其中（一）（曲（），一丁）是序列的极小多项式，它的线性复杂度为（）（一）（），一）一（。），一，）和独立地提出了线性复杂度的概念，这是线性复杂度概念的自然推广。一个密码学强的序列不仅要有大的线性复杂度，而且改变少量位置的元素不能引起线性复杂度的显著降低。这个领域的问题一直受到国际上许多学者的关注。下面给出线性复杂度的正式定义。定义副设（，）。是有限域上的一条周期为的序列，对于任意

30、，的线性复杂度，（）定义为工（），这里取遍所有周期为的序列（，）。，其中向量（，一）和（，？一）的距离不超过七，二（尸）表示的线性复杂度。在文献】中，和给出了一个有效的算法计算周期为“的二元序列的线性复杂度后来，、和将这个算法推广到有限域上周期为“的序列的情况。当多大时，条序列的线性复杂度会严格小于它的线性复杂度，文献在某些特殊情况下回答了这个问题。定理庳设是一条周期为“的二元序列，那么最小的使得，（）（）是（”（跏，其中（“一（）表示整数“一（）的二进制表示的重量。在文献中作者研究了日上周期序列的线性复杂度，证明了周期序列的线性复杂度在一般情况下都能计算出来。在文献中，作者研究了蜀上周期序列

31、在个符号替换下的线性复杂度，并给出了一般的下界，结果如下：定理设是上的一条周期为，的序列，那么一（）三（）墨第二章基本概念和性质§序列的周期相关和非周期相关设（，）”是昂上的一条周期为的序列，它的周期自相关定义为一（）沪”，其中冬一，等，是实数域上求和。设（，）。和岛（，¨，）。是上的两条周期为的序列，它们的周期互相关定义为，。（）其中墨一，：等，是实数域上求和。设是昂上周期为的序列，它具有如下的值自相关嘶，怪葚。在通信中，我们经常面对的其实是序列的非周期相关，因为在一般情况下，确定序列的非周期相关是一件很困难的事，所以人们转而研究序列的周期相关，设（，）。是弓上的一条周期

32、为的序列。的非周期自相关定义为嘶）手酸墨沪一“（鬻一，鲫。其中警，是实数域上求和。容易看出（）。对任意，墨（）盯一一丁）”。，这正好是在移位处的周期自相关。关于序列的非周期自相关，有如下结果。第二章基本概念和性质定理删设是一条二元一序列，它的周期是，它的非周期自相关有如下的上界（）（）（）归（），第三章序列的统计性质及二元周期序列的一复杂度和在年提出了一种新的生成伪随机序列的移位寄存器结构，他们将其称为带进位的反馈移位寄存器（），并提出了二元序列复杂度的一种新的度量指标：复杂度。在此后的一系列论文中，他们又做了许多与有关的工作。本章内容安排如下；在第节中，介绍的概念和与之相关的基本知识；在第节

33、中，详细分析序列的各种统计性质；在第节中，分析二元序列的线性复杂度；在第节中，指出复杂度和线性复杂度的一个大的差别，基于这一差别，提出二元周期序列的对称复杂度的概念；在第节中，计算二元周期序列的复杂度和对称复杂度的期望值；在第节中，给出二元周期序列的复杂度和对称复杂度的非平凡的下界；最后，在第节中，指出上最近两篇论文的结果本质上是一样的。本章内容来自作者论文，。§是一个奇数，它可以表示为，一，吼，。这些系数，够可以看做图，中反馈寄存器的抽头（本图来自文献【）。下面给出的正式定义。定义跗一个由个系数，妇，这里岱，），和一个初姑记忆整数，一决定。如果在当前时刻寄存器的内容是（。一，。一，

34、。一，。一，），记忆整数的值是竹一，那么移位寄存器的操作规定为：求出整数和；。一一；将寄存器的内容右移一位，输出最右比特一，；将。别输入最左边的寄存器；第三章序列的统计性质及二元周期序列的复杂度将记忆整数的值更新为。（盯一。）。整数一称为的联结整数（）。图：带进位的反馈移位寄存器（）定义对于二元终归周期序列（，），它的定义为所有输出序列为（，）的中最小的。如果。（，）是周期为丁的严格周期序列，令茎。吼。，那么一哿（一）。在集合；，）和集合旧（，。，）是二元终归周期序列）之间存在一一对应关系。我们也将集合，）中的元素称为序列的有理表示。如果读者想更多地了解有关数的知识，请看文献】。如果（，），是

35、奇数，那么与一对应的二元序列的最小周期为。（），这里。（）表示模口的阶。注上面的整数可以替换成任意素数，相应的联结整数）改变为十辨扩，这里啦，。一果读者想知道为什么一骱矿，请看文献跗的第节。同样地，改变为（），改变为血一”。舻（护一），一。下面我们给出复杂度的定义。定义（，）一条二元终归周期序列，假设它的有理表示为一，（，），那么的复杂度蕾（）定义为实数（，）。注如果是全序列，规定圣（）。注如果。是周期为的周期序列，那么垂（）。第三章序列的统计性质及二元周期序列的复杂度注一般情况下似时的复杂度定义是类似的，但在本文中我们只讨论复杂度。下面给出一序列的定义，一序列是一序列的算术版本。定义对于一个纰，如果是它的联结整数的本原根，我们称这个嫱的输出序列为一序列。由定义，一序列的周期为（），这里是欧拉函数。定义是一个正整数，如果是模的本原根，我们称为的。如果口存在本原根，一定形为，。，或印，这里是一个奇素数，三。在第节和第节中我们仅考虑口。的情况，的情况是类似的。下面讨论序列的综合问题。与情况下的算法类似，和给出