用离散傅立叶变换(DFT)和广义离散傅里叶变换(GDFT)作为主要的研究工具，给出了任意有限域GF(q)上周期序列线性复杂度的数学期望的值和k-错线性复杂度的数学期望的一些有用的下界。证实了Rueppel的猜测。丁-肖-单在提出线性复杂度的稳定性的同时猜测序列的线性复杂度及球体复杂度之间存在相互制约关系[6],随之，Niederreiter进一步研究并提出同时使得线性复杂度和k-错线性复杂度都达到最大值的序列是存在的[20，21，22，27]。
1.2 论文研究的内容及主要结果
论文总共分为六章。第一章介绍本文研究工作的背景及意义，以及论文的内容安排和作者研究的主要结果；第二章介绍本文的密码学基础知识和数学基础知识；第三章介绍周期单序列及其对偶序列的线性复杂度；第四章介绍2n?周期二元序列的4-错线性复杂度；第五章介绍周期多序列及其广义对偶多序列的联合线性复杂度；第六章介绍本论文的工作总结及结束寄语。
第一章 介绍本文研究工作的背景及意义，以及论文的内容安排和作者研究生阶段所作出的主要结果。
第二章
介绍了本文研究所需要的密码学基础知识和数学基础知
识。密码学基础知识主要介绍了密码学的基本概念，密码实现机制，线性反馈移位寄存器序列，密码强度的稳定性指标和线性复杂度。
第三章
介绍了周期单序列线性复杂度基础知识，利用二元周期序
列及其对偶序列的极小多项式之间关系的已有结论，在提出p元周期序列的对偶序列的基础上，讨论了p元周期序列及其对偶序列的极小多项式之间的关系，并计算出p元周期序列及其对偶序列的线性复杂度之间的关系。
第四章
介绍了周期单序列k-错线性复杂度的基础知识利用线性复杂度
为2n?1的2n?周期二元序列的2-错（或3-错）线性复杂度的已有结论，讨论了线性复杂度为2n?1的2n?周期二元序列的4-错（或5-错）线性复杂度的，并计算出相应的期望值。
第五章
介绍了周期多序列联合线性复杂度的基础知识，在此基础
上提出了周期多序列的广义对偶序列的定义，在此基础上，首先讨论了二元周期多序列及其对偶序列的极小多项式之间关系，并计算出它们之间线性复杂度的关系；接下来进一步讨论了p元周期多序列及其广义对偶序列的极小多项式之间的关系，并计算出它们之间线性复杂度的关系。
第六章 介绍本论文的工作总结，本研究工作的具体意义，研究中遇到的问题，以及下一步研究的计划和进一步探讨的方向。
主要研究结果如下：
(1)提出了Fp上周期序列对偶序列的定义，并在此基础上分别讨论了Fp上周期序列及其对偶序列之间的极小多项式，生成函数的关系，最后进一步计算出
3
Fp上周期序列及其对偶序列的线性复杂度之间的关系。
(2)给出了F2上线性复杂度为2n?1的2n?周期序列的k-错线性复杂度（k=4,5），并计算出相关的期望值。
(3)提出了F2上周期多序列的广义对偶多序列的定义，在此基础上进一步得出了F2上周期多序列及其对偶多序列的极小多项式之间的关系，并计算出它们之间线性复杂度的关系；提出了F2上周期多序列的广义重量复杂度的定义, 并讨论了周期多序列及其广义对偶多序列的广义重量复杂度之间的关系。
(4)提出了Fp上周期多序列的广义对偶多序列定义，在此基础上得出了Fp上周期多序列及其对偶多序列的极小多项式之间的关系，并计算出它们之间线性复杂度的关系。
4
第二章 基础知识
本章首先给出了密码学一些必备的基础知识。密码学基础知识主要介绍了密码学的基本概念，密码实现机制，线性反馈移位寄存器序列，密码强度的稳定性指标和线性复杂度。 2.1 密码学基础知识
本节给出了密码学一些必备的基础知识。密码学基础知识主要介绍了密码学的基本概念，密码实现机制，线性反馈移位寄存器序列，密码强度的稳定性指标和线性复杂度。
密码学(Cryptography)是一门研究通信安全和保护信息资源的科学和技术。密码学的基本通信模式为：
加密密钥 解密密钥 明文 Mary 加密 密文 解密 Bob Eve 图2-1密码学的基本通信模式
密码学包括密码编码学和密码分析学。密码编码学是对信息编码以隐蔽信息的一门学问。密码分析学是研究分析破译密码的学问。密码体制设计是密码编码学的主要内容，密码体制的破译是密码分析学的主要内容，密码编码技术和密码分析技术是相互对立又相互依存的辨证统一的两个方面，共同促进密码学的发展。密码体制有对称密钥密码体制（又称单钥密码体制）和非对称密钥密码体制（又称公钥密码体制）。对称密钥密码体制要求加密解密双方拥有相同的密钥，或者从一个容易得到另一个；而非对称密钥密码体制是加密解密双方拥有不相同的密钥，或者从一个很难得到另一个，在不知道陷门信息的情况下，加密密钥和解密密钥是不能相互算出的。 （1）对称密钥密码体制
对称密码体制是从传统的简单换位发展而来的其主要特点是:加解密双方在加
5
解密过程中要使用完全相同的一个密钥。使用最广泛的是DES密码算法。从1977年美国颁布DES密码算法作为美国数据加密标准以来，对称密钥密码体制得到了广泛的应用。对称密钥密码体制从加密模式上可分为序列密码和分组密码两大类。
①序列密码，又称为流密码，它是一个伪随机序列发生器。流密码是保密通信中的一个重要的密码体制。它是私钥密码体制的一类，其加密过程是先把报文、语音、图象等原始明文转换成数据，然后将它同密钥序列逐位加密生成密文序列发送给接收者，接收者用相同的密钥序列对密文进行逐位解密来恢复明文。现代数字电子技术的发展已使密钥序列可以方便地利用以移位寄存器为基础的电路来产生，加上有效的数学工具，使得流密码迅速发展并走向较成熟阶段。同时，由于流密码不存在数据扩展和错误传播，其硬件加、解密速度快，且实现容易，因此流密码在实际中得到广泛的应用。序列密码方面有三本影响最大的著作：Siegenthaler的博士论文《流密码系统的设计方案》；Rueppel的研究专著《流密码的分析与设计》；丁存生等人的《流密码学及其应用》。序列密码体制以简捷，快速的生成算法，使其成为新一代移动通信的主流加密算法。 ②分组密码的工作方式是将明文分成固定长度的组，如64比特一组，用同一密钥和算法对每一块加密，输出也是固定长度的密文。 分组密码体制也具有简捷快速的特点，并且容易标准化，使其成为软硬件加密标准的主流。分组密码方面有四个著名的算法标准：美国IBM公司研制的“DES”；来学嘉博士设计的“IDEA”；密码学专家James.L.Massey设计的“SAFER”
；Joan Daemen和 Vincent Rijmen共同提交的“RIJNDAEL”。分组密码的密码分析方面有两个著名的方法：E.Biham和 A.Shamir的“差分密码分析”;Matsui等人的“线性密码分析”。
对称密钥密码体制存在的最主要问题是:由于加解密双方都要使用相同的密钥，因此在发送、接收数据之前，必须完成密钥的分发。所以密钥的分发便成了该加密体系中的最薄弱，也是风险最大的环节，所使用的手段均很难保障安全地完成此项工作这样，密钥更新的周期加长，给他人破译密钥提供了机会在历史上，破获他国情报不外乎两种方式:一种是在敌方更换“密码本”的过程中截获对方密码本;另一种是敌人密钥变动周期太长，被长期跟踪，找出规律从而被破解在对称算法中，尽管由于密钥强度增强跟踪找出规律破解密钥的机会大大减小了，但密钥分发的困难问题几乎无法解决。例如，设有n方参与通信，若n方都采用同一个对称密钥，一旦密钥被破解，整个体系就会崩溃;若采用不同的对称密钥则需n(n-1)个密钥，密钥数与参与通信人数的平方数成正比，可见，大系统密钥的管理几乎成为不可能。然而,由于对称密钥密码系统具有加解密速度快和安全强度高的优点，目前被越来越多地应用在军事、外交以及商业等领域。
6
（2）非对称密钥密码体制
非对称密钥密码体制，即公开密钥密码体制，是现代密码学最重要的发明和进展。1976年，Dif fie和Hellman为解决密钥的分发与管理问题，在他们奠基性的工作<<密码学的新方向>>[2]一文中，提出一种密钥交换协议，允许在不安全的媒体上通过通讯双方交换信息，安全地传送秘密密钥。在此新思想的基础上，很快出现了公开密钥密码体制。公钥密钥技术解决了密钥的发布和管理问题，任何一方可以公开其公开密钥，而保留私有密钥。发送方可以用人人皆知的接收方公开密钥对发送的信息进行加密，安全的传送给接收方，然后由接收方用自己的私有密钥进行解密。
公开密钥密码体制较秘密密钥密码体制处理速度慢。因此，通常把这两种技术结合起来能实现最佳性能。即用公开密钥密码技术在通信双方之间传送秘密密钥，而用秘密密钥来对实际传输的数据加密解密。
2.2 线性反馈移位寄存器序列
线性反馈移位寄存器（简记LFSR）由于它实现简单，速度快，有比较成熟的理论基础，所以LFSR成为构造密钥流生成器的最重要的部件之一。设GF(p)表示p元有限域（p为素数）。 GF(p)上一个n级LFSR由n个p元存储器与若干个
GF(p)上的乘法器和加法器联结而成(当p=2时，不需要乘法器)，每一个存储器
称为LFSR的一级。初始状态由用户确定，当第i个移位时钟脉冲到来之时，LFSR的状态由(Si,Si?1,?,Si?n?1)变为(Si?1,Si?2,?,Si?n)，并输出Si作为序列S的一位。补入LFSR的最右边一级的Si?n的值由下列的线性递归关系式（也称反馈函数）决定
Si?n???cjSn?i?j,i?0
j?1n以反馈系数决定的多项式
f(x)?c0?c1x?c2x??cn?1x2n?1?cnx??cjxj
nj?0n称为该LFSR（Linear Feedback Shift Register）的联结多项式，或反馈多项式，式中c0?cn?1。
7