流密码学是一个古典的课题.近十年来，对序列密码的研究一直比较热门.自90年代以来，国内的学者如丁存生，肖国镇，魏仕民，戴宗铎开展了这方面的研究工作，丁存生的主要工作包括对特定周期序列的模式分布的研究，肖国镇老师的工作主要是针对特定周期序列如N=2pv周期的周期序列的线性复杂度快速算法的研究，魏仕民的工作包括对特定周期的周期序列的k错线性复杂度快速算法的研究；戴宗铎老师的工作包括对周期序列的扰动(如添加，删除)后序列线性复杂度的变化情况，以及一般情形下的随机周期序列的线性复杂度的期望，方差. 国外学者Niederreiter很早就开始了有关序列复杂度的研究工作，对于特定长度的，特定周期的序列的线性复杂度有很多的估计结果，尤其是给出了周期序列的线性复杂度的分布，线性复杂度与k错线性复杂度之间的关系；Meidl对于随机周期序列的k错线性复杂度的统计性质，包括期望的界有了很多的研究结果.在研究周期序列线性复杂度，k错线性复杂度快速算法方面，早期的工作包括Games和Chsq，1983)的工作，对于N=2v的周期序列给出了一种快速算法，大大优于原先的Berlekamp-Massey算法.接着M.StampandC.F.Martin提出了N=2v的周期序列k错线性复杂度的算法，于是后面引发了一系列的研究，通过探询内在的代数结构，找到递归算法的依据，现在对于N=2n，N=pb，N=2pv的周期序列都有了类似的快速计算的方法.此外，还有一些其他的工作，比如K.Kurosawa,F.Sato，T.Sakata,和W.Kishimoto的工作，得到了在特定周期N=2v，pv的周期序列的线性复杂度发生最小跳变的错误值.比如Alan.G.B.LauderandKenneth.G.Paterson的工作，给出一种高效算法得到二元周期序列线性复杂度的错误谱并用于Reed-Muller码的译码中. 说到这里，要谈一谈对研究序列的性质的原始动机.笔者对序列的兴趣并不是从密码学意义角度来的.当时笔者2002年在微软亚洲研究院实习的时候，碰到了一个问题：有一个研究小组用极长序列(MaximalLengthSequence)折叠后来进行定位，直观的说，因为极长序列的冗余很大，这样做可以用比较少的比特来实现定位.但是有这么一个问题，如果出错了怎样解决?笔者试图从编码理论的角度解决这样的问题，但是没有想到这个问题的难度会很大，这涉及到序列的稳定性的问题.国外曾经有这样的工作，试图从线性复杂度的图象变化来进行判断，这种线性复杂度的跃迁或者是幅度的变化可以给错误提供一定的判断信息，从而进行纠错.这样的问题引发了笔者的思考，究竟序列的稳定性是怎么进行度量和判断的?兴趣引起了对序列复杂度性质的研究.于是发现国内国外有一些这方面的研究工作，特别是对序列线性复杂度和k错线性复杂度的研究. 笔者博士论文中主要的研究工作是对周期序列线性复杂度和k错线性复杂度按照不同的周期类别进行了近一步的细划，对随机周期序列的线性复杂度和k错线性复杂度的统计性质，包括期望，方差的界的一些估计有一些更紧的结果.另外还有一些多重序列方面的研究工作.此外，对于周期为2n的二元随机周期序列的k=1，2-错线性复杂度进行了深入的研究，给出了精确的数学公式描述分布的规律；并给出了周期为2n的二元周期序列的1-错线性复杂度的新算法，另外还在得到了二元随机周期序列的线性复杂度为固定值时，内在结构的一些性质基础之上，提出了新算法去定位这些可能发生错误的位置. 事实上这样的研究是还是非常的理论的，试图从序列本身固有的定量的东西(如周期，长度，错误值，有限域的元素数目，分圆陪集的结构)来揭示序列的线性复杂度和k错线性复杂度的统计性质，这样的研究结果会很定量而且很深刻；但是这样的结果毕竟是太理论了一些；如果能够参与到一些与数字版权相关的，与安全工程相关的实际项目中，会对实际的应用背景和要求会有更深的理解.笔者有幸能够到微软亚洲研究院，IBM中国研究中心参与这样的一些项目，包括数字版权管理，安全存储，数字水印的应用项目.从中收获也非常大. 这篇博士论文的结构是这样的：第一章主要是介绍序列各种复杂度的基本概念和近几年国内外对序列复杂度研究的方法和进展；第二章主要是介绍自己在周期序列线性复杂度和k错线性复杂度方面所做的一些研究工作和结果，以及未来工作的展望；第三章主要是介绍自己在周期为2n的随机周期序列1-错线性复杂度和2-错线性复杂度分布及算法方面所做的最新的研究工作；第四章主要是介绍自己在微软亚洲研究院，IBM中国研究中心所参与的一些与数字版权管理(DRM)相关的项目和所做的研究工作.最后是附录，介绍自己独立设计的周期为2n的周期序列1-错线性复杂度的新算法(用C语言实现).