周期序列的K-错线性复杂度分析和研究

周期序列的K-错线性复杂度分析和研究

Analyse and Research of the k-error Linear Complexity

of Periodic Sequences

作 者 姓 学 位 类 学 科、专 研 究 方 导 师 及 职

名 王菊香 型 学 历 硕 士 业 应 用 数 学 向 代数编码和序列密码 称 朱士信 教授

2009年3月

目录

第一章 绪论 ........................................................ 1

1.1 研究背景 ................................................... 1 1.2 论文研究的内容及主要结果 ................................... 3 第二章 基础知识 .................................................... 5

2.1 密码学基础知识 ............................................. 5 2.2 线性反馈移位寄存器序列 ...................................... 7 第三章 周期单序列及其对偶序列的线性复杂度 ........................... 8

3.1 周期单序列线性复杂度基础知识 ............................... 8 3.2 二元周期单序列及其对偶序列线性复杂度 ....................... 9 3.3 P元周期单序列及其对偶序列线性复杂度 ...................... 10 第四章 2n?周期二元序列的4-错线性复杂度 ........................... 14

4.1 周期单序列k-错线性复杂度基础知识 ......................... 14

n4.2 线性复杂度为2n?1的2?周期二元序列的2-错（或3-错）线性复杂

度 ............................................................. 16

n4.3 线性复杂度为2n?1的2?周期二元序列的4-错（或5-错）线性复杂

度 ............................................................. 16 第五章 周期多序列及其广义对偶多序列的线性复杂度 .................... 22

5.1 周期多序列联合线性复杂度基础知识 ........................... 22 5.2 二元周期多序列及其广义对偶序列的联合线性复杂度 ............. 23 5.3 p元周期多序列及其广义对偶序列的联合线性复杂度 ............ 26 第六章 总结 ........................................................ 30

6.1 论文工作总结 .............................................. 30 6.2 结束寄语 .................................................. 30 参考文献 ........................................... 错误！未定义书签。 本文作者在攻读硕士期间的研究成果 ................... 错误！未定义书签。

第一章 绪论

1.1 研究背景

随着信息化时代的到来，信息安全越来越成为人们关注的焦点。密码技术是保障信息安全的核心技术。密码技术在古代的应用已经有四千多年的历史，但是主要应用于外交通信和军事保护，密码学还没有系统的理论基础。直到1949年Shannon（美国数学家）发表了论文《保密系统的信息理论》[1]，这为单钥密码系统奠定了理论基础，从此，密码才成为一门科学。但是从1949年到1975年这段时间，密码学理论研究工作进展不大。一直到70年代中期，在密码学的研究中出现了两件非常重要的事件:一件事是1976年Diffie和Hellman (美国学者)发表了《密码学的新方向》[2]一文，提出的公钥密码体制，引起了密码学史上的一场革命，为解决通信网络中的信息安全提供了新的理论支持和技术基础；另一事件是美国国家标准局NBS( National Bureau of Standards)公开征集，并于1977年正式公布实施的美国数据加密标准(DES)(Data Encryption Standard)。这两个事件标志着现代密码学的诞生。从此，现代密码学无论在理论上，还是在应用上都得到了空前的发展，逐渐形成了集数学、计算机科学、电子与通信等诸多学科于一身的综合学科。

自从密码理论和技术诞生以来，密码体制的强度问题就一直成为密码设计者和分析者研究的核心内容。 流密码是保密通信中的一个重要的密码体制。流密码体制的强度完全依赖于密钥流产生器所生成的伪随机序列的随机性(Randomness)和不可预测性(Unpredictability)。Shannon在1949年就从理论上严格证明了如果密钥流序列是一个真随机序列，那么相应的流密码是绝对安全的

[3]

。但是实际上，由于人们无法完全重复地产生同一个随机序列，只能用伪随

机序列代替随机序列。很多密码学研究者开始寻找评价伪随机序列随机性和不可预测性的度量指标。密钥流序列的随机性度量指标主要有：串分布、自相关值、周期和线性复杂度等。特别是六十年代末Berlekamp-Massey提出的线性反馈移位寄存器序列的B-M综合算法[4]使得线性复杂度成为一些流密码系统强度的重要指标，随之很多相关研究成果相继提出。如果序列S??(s0,s1,?,sN?1,?)的线性复杂度为LC(s?)，则只要知道该序列的任意LC(s?)个连续比特，就可通过解线性方程组或用B-M算法找到该序列所满足的齐次线性递归关系式，从而确定整个序列。因此要求密钥流序列的线性复杂度必须足够大。对于一般序列的综合，B-M算法目前仍然是最优的。1983年Games和Chan提出了周期为2n的二元序列线性复杂度的快速算法[5]，进一步推进了线性复杂度算法的研究。

但是线性复杂度高的序列并不一定是安全稳定的序列。例如一个周期为N的二元序列S?的第一个周期为SN?(0,?,0,1)，其线性复杂度LC(S?)?N达到了最大值 ，只要把最后的一位的1变为0，则该序列的线性复杂度降低为0，这样的序列的线性复杂度是不稳定的，用来作为密钥序列是不安全的，可见，序列

1

的线性复杂度的稳定性与序列的不可预测性是密切相关的。因此，密钥流序列的线性复杂度不仅要足够大而且必须有很好的稳定性。八十年代末期，中国学者丁-肖-单在此基础上首先提出了重量复杂度、球体复杂度、球面周期、球体周期、函数稳定性等流密码系统稳定性的新的度量指标，并且建立了各种指标之间的相互关系，给出了对于某些序列改变k位元素后序列线性复杂度的下界，建立了流密码稳定性的基础理论，使得流密码强度问题研究得到了重大突破[6]，引起了国际密码学界的广泛关注。1993年Stamp和Martin提出了类似‘球体复杂度’的线性复杂度稳定性度量指标‘k-错线性复杂度’，并且提出了一个计算周期为2n的二元序列k-错线性复杂度的快速算法[7，8]，使得线性复杂度的稳定性研究有了新的重要推进，很快k-错线性复杂度就被广大学者进行了大量的应用和推广。2003年Lauder和Paterson将Games-Chan算法和Stamp-Martin算法同时推广，提出了一个计算周期为2n的二元序列线性复杂度曲线的算法，该算法可以同时计算周期为2n的二元序列的线性复杂度和k-错线性复杂度，随后也得到了一些推广算法[9，10，11]。现在，周期和线性复杂度仍然是度量密钥流序列安全强度的两个最为重要的指标。

在分析密钥流序列的这两个指标的同时，必须考察它们的稳定性.对于线性复杂度及其稳定性的研究，一方面是设计线性复杂度和k-错线性复杂度的快速算法，另一个重要的热门话题是对周期序列的线性复杂度及其稳定性进行理论分析.研究线性复杂度的稳定性是因为少量比特发生变化可能会引起线性复杂度的急剧下降，那么，究竟多少比特发生变化会引起线性复杂度的下降?在文献[12]中提出了最小错误minerror(S)的概念来描述这个问题，将最小错误minerror(S)定义为使得线性复杂度下降时至少要改变的比特数.那么，具体是哪些位置发生变化会引起线性复杂度的下降?文献[12]引入错误序列来阐述这个问题.下降后的线性复杂度又会是多少呢?即当k = minerror(S)时，k-错线性复杂度的值是多少，针对这些问题，文献[12]研究了2n?周期二元序列线性复杂度与k-错线性复杂度的关系，给出了用线性复杂度的Hamming重量表示的最小错误minerror(S)的值，并给出了k = minerror(S)时k一错线性复杂度的上界.这一结果的提出引起了很多研究者的关注[9，13，14，15，16] 。随之，研究学者开始考虑线性复杂度的稳定性及线性复杂度之间可能存在的某种内在联系.找出线性复杂度及其稳定性的关系不仅有利于指导设计计算周期序列线性复杂度和k-错线性复杂度的快速算法，而且可以直接通过对线性复杂度的分析，从而进一步分析其稳定性。

对于周期序列的线性复杂度及其稳定性的理论分析的另一个重要方面是分析周期序列线性复杂度和k-错线性复杂度的统计特性，如分布、数学期望、方差等[17，18，19，20，21，22，23，24],Rueppel对二元序列线性复杂度的随机性进行了研究

[25]

，并猜测周期二元序列的线性复杂度的期望值接近它的周期N，文献[26]利

2

用离散傅立叶变换(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

第三章 周期单序列及其对偶序列的线性复杂度

本章介绍了周期单序列线性复杂度基础知识，利用F2上二元周期序列及其对偶序列的极小多项式，生成函数和线性复杂度之间关系的已有结论，在Fp（p为素数）上提出p元周期序列的对偶序列的基础上，讨论了p元周期序列及其对偶序列的极小多项式之间的关系，并计算出p元周期序列及其对偶序列的线性复杂度之间的关系。

3.1 周期单序列线性复杂度基础知识

周期序列的线性复杂度是度量流密码强度的一个重要指标,序列,S??(s,,?,的线性复杂度定义为生成它的最小线性反馈移位寄存器的长度)0,s1?Ns?1记为: LC(S?)。从线性复杂度的定义可知，如果一个序列的线性复杂度为L，则只

需知道该序列的任意2L个连续元素，即可通过解线性方程组或借助B?M算法[25，28]找到该序列所满足的齐次线性递归关系式，进而可确定整个序列。这说明密钥流序列的齐次线性复杂度必须足够大，才能保证流密码系统的安全性。因而线性复杂度是度量密钥流序列的密码强度的一个重要指标，但是线性复杂度高的序列未必是“好”的密钥流序列。

例如: SN?1111?10，LC(SN)?N?1但是只要把序列中的一个字节“0”改为“1”,则序列的线性复杂度就降为1。设fs(x)是生成SN的极小多项式,则

LC(SN)?N?deg(gcd(SN(x),1?xN))?? [29]

。由此可见讨论序列的极小多项式有十分重要

的意义。由于序列S?的对偶序列S是一类特殊的序列,且与S?有着密切的关系,则研究S的极小多项式有一定的应用价值。文[30]讨论了F2上的序列S?与其对偶序列

??本节将在此基础上讨论F上序列S与其对S的生成函数及极小多项式之间的关系。

偶序列S的生成函数及极小多项式之间的关系，并且计算出Fp上序列S与其对偶序列S之间的线性复杂度的关系。

设SN表示有限域Fp上有限序列(S0,S1,?,SN?1)，S?表示Fp上无限序列

，使SN（或S?）(S0,S1,?,SN?1,?)，设有整数L和Fp上一组数c1,c2,?,cL（p是素数）

满足：Sj?c1Sj?1?c2Sj?2???cLSj?L?0,j?L (1),则称SN（或S?）是一个L阶齐次线性递归序列，L是SN（或S?）所满足的齐次线性递归关系的最小阶数，称为SN（或

S?）的线性复杂度，记为：LC(SN)（或LC(S?)）。

??p?对于序列S?和SN,它们的生成函数定义为:

S(x)?S0?S1(x)?????SNx??????Sixi和SN(x)?S0?S1x?????SN?1xN?1。

Ni?0?如果S?是周期为

S(x)?S(x)(1?x?xNN2NN

的序列, SN是它的第一个周期,则

SN(x)??)?,则: S(x)可以表示成:

1?xN8

rs(x)SN(x)/gcd(SN(x),1?xN) S(x)?。 ?(1?xN)/gcd(SN(x),1?xN)fs(x)这里

fs(x?)?x(N1s)Nx/?gxcrsNdx(?sx(N),s1xNN然?x),。显

rs(x)fsx/是既约的, deg(rs(x))＜deg(fs(x)),fs(x)为S?的极小多项式, deg(fs(x))=LC(S?)为S?的线性复杂度

[31]

。

3.2 二元周期单序列及其对偶序列线性复杂度

引理3.2.1[29] 设S?是满足Sj?c1Sj?1?c2Sj?2?????cLSj?L?0, j?L的L阶 二元递归序列（或称伪随机序列），则生成函数S(x)可表示为s(x)?g(x)/f(x),其中f(x)?c0?c1x???cLx 为S的一个生成函数，且：g(x)??(?sj?ici)xj。

L?L?1j?0ji?0反之，若g(x)为F2上的一个次数deg(g(x))?l的多项式，且

)g(x)/的f幂x级数是一个满足f(x)?c0?c1x???cLxL，则s(x?Sj?c1Sj?1?c2Sj?2?????cLSj?L?0, j?L递归关系的齐次线性递归序列的生成函

数。

关于生成多项式与极小多项式有引理3.2.2：

引理3.2.2[29]设S?是周期为N的序列，则其生成函数可表示为:

rs(x)SN(x)/gcd(SN(x),1?xN)?NN?1S，其中，且的S(x)??s(x)?s?sx?????sx01N?1NNN(1?x)/gcd(S(x),1?x)fs(x)极小生成多项式为 fs(x)?(1?xN)/gcd(sN(x),1?xN)。

结合引理3.2.1和引理3.2 .2可知，周期序列的生成函数的既约有理表达式唯一，且既约有理形的分母一定是其极小多项式。

设 F2上二元序列S??(S0,S1,?,SN?1,?)，下面以S表示S?按位取反所得的

?)，这里Si?1?Si,i?0,1,2序列S?(S0,S1,S2,?，对于S?与S的生成多项式与

???极小多项式有下列定理：

定理3.2.1

[30]

设F2上周期序列S生成函数S(x)??Sixi ?rs(x)/fs(x)，其

??i?0中gcd(rs(x),fs(x))?1且fs(x)是S的极小多项式，记fs(x)??cjxj(c，0?cm?1) j?0?m以l记x?1为fs(x)根的次数(l?0)，即fs(x)?(1?x)lf(1x)，其中f1(1)?0，则对S?的按位取反所得的序列S的生成函数：

? 9

?(1?x)rs(x)?fs(x),?f(x)(1?x)s?(1?x)rs(x)?fs(x)?(rs(x)?f1(x))/(1?x)S(x)???,fs(x)(1?x)f1(x)??rs(x)?f1(x),?fs(x)??(1?x)fs(x),?f1(x),S?的极小多项式为: fs(x)???fs(x),?l?0l?1

l?2l?0l?1 l?2l?0l?1 l?2

?L(s)?1,?推论3.2.1[30]在上述记号下:L(s)??L(s)?1,?LC(s),?定理3.2.2 [30]F2[x]中的n次不可约多项式fs(x)生成的n阶伪随机序列

S?的对偶序列S的极小多项式为(1?x)fs(x)，且线性复杂度为n+1。

?定理3.2.3[30]F2[x]中的n次本原多项式fs(x)生成的n阶m序列S?的对偶 序列S的极小多项式为(1?x)fs(x)，且线性复杂度为n+1。

以上讨论了F2上关于周期序列S?与其对偶序列S的生成函数，极小多项式及线性复杂度之间的关系的已有结论。下面将讨论Fp上周期序列S?与其对偶序列S的生成函数及极小多项式之间的关系，并且计算出Fp上周期序列S?与其对偶序列S之间的线性复杂度的关系。

3.3 P元周期单序列及其对偶序列线性复杂度

定义3.3.1 设S?是满足式(1)的p元序列，则f(x)?c0?c1x?????cLxL 为S?的一个特征多项式或生成多项式，其中c0?0,ci?Fp,i?1,2,???L，并且其中

????cL?0。S?的生成多项式中次数最小的多项式称为S?S?的极小多项式，并记为fs(x)。S所对应的生成为S(x)??Sixi。

??i?0定义3.3.2 设Fp上p元序列S??(S0,S1,S2,?)，称S?(S0,S1,S2,?)为

S?的对偶序列，其中Si?(p?1)?Si,i?0,1,2,?。

?引理3.3.1[29]设S?是周期为N的序列，则其生成函数可表示为：

10

NNNNNN??s(x)??sixi??s(x)/gcd(s(x),1?x)/1?x/gcd(s(x),1?x)?????

i?0?其中sN(x)?s0?s1x?????sN?1xN?1，且S?的极小多项式为:

fs(x)?(1?xN)/gcd(SN(x),1?xN)。

周期序列的生成函数的既约有理表达式唯一，且既约有理形的分母一定是其极小多项式。

对于Fp上的序列S?与S的生成函数与极小多项式有：

定理3.3.1 设Fp上周期序列S?的极小多项式为fs(x)?(1?x)tg(x)，

i?0其中t为非负整数g(1)。S的生成函数S(x)??S?ix???s其r()x/sf(,x)中

i?0S?的对偶序列S的生成函数： gcdrs(x(f)s,x(?)，则)??(p?1)g(x)?rs(x)(1?x)?(1?x)g(x)?(p?1)fs(x)?rs(x)(1?x)?(p?1)(1?x)g(x)?rs(x)(1?x)??S(x)?2(1?x)g(x)(1?x)fs(x)??(p?1)(1?x)tg(x)?rs(x)(1?x)?(1?x)t?1g(x)?,t?0,t?1 ,t?2?(1?x)fS(x)?1??fS(x)?的极小多项式为: SfS(x)??1?x?fS(x)???fS(x)???ii,t?0

,g(1)?rS(1)?pt?1,g(1)?rS(1)?pt?1,?iit?2?isN(x)证明 S(x)??six??(p?1?si)x??(p?1)x??six?(p?1)?x? N1?xi?0i?0i?0i?0i?0而?xi?1?x?x2???i?0?1，则 1?xS(x)?(p?1)r(x)(p?1)fs(x)?rs(x)(1?x)1 ?s?1?xfs(x)(1?x)fs(x)??(p?1)fs?x??rs(x)(1?x)??/gcd?(p?1)fs(x)?rs(x)(1?x),(1?x)fs(x)??

?(1?x)fs(x)?/gcd?(p?1)fs(x)?rs(x)(1?x),(1?x)fs(x)?

由引理3.3.1知S的极小多项式fs(x)为:

?fs(x)?(1?x)fs(x)/gcd?(p?1)fs(x)?rs(x)(1?x),(1?x)fs(x)?

11

接下来只需证明

?1?(1?x)2?gcd?(p?1)fs(x)?rs(x)(1?x),(1?x)fs(x)????1?x??1?x(1) 当t?0时,fs(x)?g(x)

,t?0,g(1)?rs(1)?pt?1

,g(1)?rs(1)?pt?1,t?2gcd?(p?1)fs(x)?rs(x)(1?x),(1?x)fs(x)?

gcd?(p?1)g(x)?rs(x)(1?x),(1?x)g(x)?

?gcd?(1?x),(p?1)g(x)?rs(x)(1?x)??gcd?g(x),(p?1)g(x)?rs(x)(1?x)? ?gcd?(1?x),(p?1)g(x)??gcd?g(x),rs(x)(1?x)? =1

则fs(x)?(1?x)fs(x)

t(2)当t?1时，fs(x)?(1?x)g(x),g1()?0，

gcd?(p?1)fs(x)?rs(x)(1?x),(1?x)fs(x)?

tt?1?gcd?(p?1)(1?x)g(x)?r(x)(1?x),(1?x)g(x)?s?? t?1t?(1?x)gcd??(p?1)(1?x)g(x)?rs(x),(1?x)g(x)??

tt?1t?1?(1?x)gcd??(1?x),(p?1)(1?x)g(x)?rs(x)???gcd??g(x),(p?1)(1?x)g(x)?rs(x)?? i 当t=1时

tt?1 gcd?(1?x),(p?1)(1?x)gx(?)rsx(?)??

1?x), ?gcd??p?1?g(x)?sr(x??(?)

?gcd?(1?x),g(x)?rs(x)?

① 当g(1)?rs(1)?p时：

gcd?(1?x),g(x)?rs(x)??1?x

t?1gcd??g(x),(p?1)(1?x)g(x)?rs(x)??

?gcd?g(x),(p?1)g(x)?rs(x)??1

tt?1t?1gcd?(1?x),(p?1)(1?x)g(x)?r(x)?gcdg(x),(p?1)(1?x)g(x)?rs(x)???s????

?1?x

fs(x)?(1?x)fs(x)/(1?x)2?② 当g(1)?rs(1)?p时：

1fS(x) 1?xgcd?(1?x),g(x)?rs(x)??1

tt?1t?1gcd??(1?x),(p?1)(1?x)g(x)?rs(x)???gcd??g(x),(p?1)(1?x)g(x)?rs(x)???1

fs(x)?fs(x) ⅱ 当t?2时：

12

tt?1t?1gcd??(1?x),(p?1)(1?x)g(x)?rs(x)???gcd??g(x),(p?1)(1?x)g(x)?rs(x)???1

fs(x)?fs(x)

证毕.

推论3.3.1：在上述记号下

?LC(S)?1?LC(S)?1? LC(S)???LC(S)??LC(S),t?0,g(1)?rs1()?pt?1

,g(1)?rs(1)?pt?1,t?2

证明 由定理3.3.1直接可以证出。定理3.3.2 Fp?x?中的n次不可约多项式

?fs(x)生成的n阶伪随机序列S?的对偶序列S的极小多项式为(1?x)fs(x)，且线性复杂度为n+1。

证明 因为fs(x)在域FP上不可约，则 gcd((1?x),fs(x))?1,即t=0,由定理3.3 .1得：fs?(1?x)fs(x),则由推论3.3.1得证。

定理3.3.3 Fp?x?中的n次本原多项式fs(x)生成的n阶m序列S?的对偶序?

列S的极小多项式为(1?x)fs(x)，且线性复杂度为n+1。

证明 Fp?x?中的n次本原多项式fs(x)为不可约多项式，则由定理3.3.2直接可以得证。

13

第四章 2n?周期二元序列的4-错线性复杂度

本章介绍了周期单序列k-错线性复杂度的基础知识，利用F2上线性复杂度为2n?1的2n?周期二元序列的2-错（或3-错）线性复杂度的已有结论，进一步讨论了线性复杂度为2n?1的2n?周期二元序列的4-错（或5-错）线性复杂度的，并计算出相应的期望值。

4.1 周期单序列k-错线性复杂度基础知识

周期序列的线性复杂度和k-错线性复杂度是度量流密码强度的两个重要指标,序列S??(s0,s1,?,sN?1,?)的线性复杂度定义为生成它的最小线性反馈移位寄存器的长度,记为: LC(s?)。从线性复杂度的定义可知，如果一个序列的线性复杂度为L，则只需知道该序列的任意2L个连续元素，即可通过解线性方程组或借助B?M算法找到该序列所满足的齐次线性递归关系式，进而可确定整个序列。这说明密钥流序列的齐次线性复杂度必须足够大，才能保证流密码系统的安全性。因而线性复杂度是度量密钥流序列的密码强度的一个重要指标，但是线性复杂度高的序列未必是安全的密钥流序列。例如: SN?1111?10,LC(SN)?N?1,但是只要把序列中的一个字节“0”改为“1”,则序列的线性复杂度就降为1，即这个序列的稳定性较差。上世纪80年代末，丁存生和肖国镇等提出了重量复杂度，球体复杂度，函数稳定性等一系列密码稳定性的重要指标，进一步推进了序列的安全性研究。后来Stamp和Martin提出了类似球体复杂度的线性复杂度稳定性指标，即k-错线性复杂度。

设S??(s0,s1,?,sN?1,?)是N?周期序列，k是非负整数，定义N?周期序列S?的

???k?错线性复杂度LCN,K(S?)?minLC(S?T)，其中，T?(t0,t1,?,t,)，N?1??WN(T)?K[8]

显然K=0时，k-错线性复杂度就是序列的线性复杂度。WN(T?)是序列T?的汉明重量。

在文献[12]中，Kurosawa等给出2n?周期二元序列S的K-错线性复杂度严格小于线性复杂度LC(S)的最小值为：Kmin?2WH(2n?LC(S))其中WH(b)指整数b在二进制表示下的

nK?2n?汉明重量。在2002年，W. Meidl给出更低的界：EK?2?2?log2(???)，其中EKt?0?t?表示2n?周期二元序列的k?错线性复杂度的期望值[26]。在文献[32]中进一步指出了EK的范围：

?2n?n?1?2t?tK?2t?EK?2?3?2n?????2?? ?j2j?0??t?2j?0?j?2n?1?1K?2n?1n?1?2t?tK?2t?nEK?2?3?????2?? ??2n2t?22j?0?j?j?0?j?n1K当K?0时，Rueppel给出线性复杂度为L的2n?周期二元序列的具体个数

14

N(L):N(0)=1, N(L)?2L?1(1?L?2n)，且E0?2n?1?2[25]

?2n。当K?1Wilfried。,2时，

Meidl给出线性复杂度为2n的2n?周期二元序列的k?错线性复杂度的期望值[32]：

E1?2?3?2n?2n(2?1)??2?2?r。当K?2,3时，在文献[33]中讨论了线性复杂度为

nr?2n?1r2n?1的2n?周期二元序列相关结论令

Lr,c?2?2N2(0)?22n?2nr?1?c，(2?r?n?1,1?c?2?2)n?2n?2nr，

n?1N2(Lr,c)?22rn?2r?1?2r?c?1，

，并计算出：E2LC(S)?2n?1?2?7?2??2?2?2r?1。

r?3本节将在此基础上进一步讨论k?4,5时的相关结果。

设SN表示有限域F2上有限序列(S0,S1,?,SN?1)，S?表示F2上无限序列

(S0,S1,?,SN?1,?)，设有整数L和F2上一组数c1,c2,?cL，使SN（或S?）满足：

Sj?c1Sj?1?c2Sj?2???cLSj?L?0,j?L ,则称SN（或S?）是一个L阶齐次线性递归序列，L是SN（或S?）所满足的齐次线性递归关系的最小阶数，称为SN（或S?）的线性复杂度记为：LC(SN)（或LC(S?)）。对于序列S?和SN,它们的生成函数定义为:

?S(x)?S0?S1x???SNx????Sixi 和 SN(x)?S0?S1x???SN?1xN?1。

Ni?0若S?是周期为N的序列, SN是它的第一个周期,则

S(x)?S(x)(1?x?xNN2NSN(x)??)?,故S(x)可以表示成:

1?xNN(?1xrS(x)SN(x)gcd(SN(x),1?xN)这里fS(x)S(x)???(1?xN)gcd(SN(x),1?xN)fS(x)rS(x))?rS(x)?SN(x)gcd(SN(x),1?xN)，显然deg()NgScdx(?N，(x),1)是deg(fSx(r)),x(Sf)x(既)约的, SfS(x)为S?的极小多项式,LC(S?)?deg(fS(x))?N?deg(gcd(SN(x),1?xN))为S?的线性复杂度[34]。对于一个2n?周期二元序列S，它的线性复杂度LC(S)可以由Chan-Games算法确定。Chan-Games算法在文献[8]中总结出计算2n?周期二元序列的k?错线性

[5]

复杂度的方法，其中K是定值，且对于所有K都适合。本文主要利用Chan-Games算法展开讨论。

下面简要介绍一下Chan-Games算法：

令S(n)?(S0,S1,?,S2n?1)是S?的第一个周期序列，则LC(S(n))?LC(S?)，把S(n)分成左右两半部分，分别记为：

L(S(n))?(S0,S1,?,S2n?1?1)，R(S(n))?(S2n?1,S2n?1?1,?,S2n?1)。

)（1） 若L(S(n))?R(S(n))，则LC(S?)?LC(L(S(n)))，并记S(n?1)?L(S(n)；

15

（2） 若L(S(n))?R(S(n))，则LC(S?)?2n?1?LC(S(n?1))，其中

显然S(n?1)是长为2n?1的序列，其中各元素的加法运算在F2S(n?1)?L(S(n))?R(S(n))。中进行。

当n?1时，Chan-Games算法定义了从F2n到F2n?1上的映射?n：

2

2?n((S0,S1,?,S2?1))?(S0?S2,S1?S2?1,?,S2由映射?n的定义可以得到以下性质：

nn?1n?1n?1?1?S2n?1)

P

1

：W(?n(S(n)))?W(S(n))；

：W(?n(S(n)))?W(S(n))(mod2)，其中n?2；

nPP

2?1(n)(n)(n)2?(S)?{v?F|?(v)?S}S：的原象有个元素。 2n?1n?1n?1232n4.2 线性复杂度为2n?1的2?周期二元序列的2-错（或3-错）线性复杂度

引理4.2.1[35] 令S是周期N?2n的二元序列，则LC(S)?2n，当且仅当W(S)是奇数。

引理

4.2.2[35]令S(n)?(S0,S1,?,S2n?1)是周期N?2n的二元序列，

[35]

LC(S(n))?2n?2，当且仅当S0?S2???S2n?2?S1?S3???S2n?1?0。

引理4.2.3

n在F2上不存在两个2?周期二元序列a?(a0,a1,?,a2n?1)?和

b?(b0,b1,?,b2n?1)?有相同的线性复杂度C(1?C?2n?2)，且满足au?bu，av?bv，

ai?bi(u?v,0?i?2n?1,i?u,v)，其中u?v(mod2)。

n定理4.2.1[35] 设S是线性复杂度为2n?1的2?周期二元序列,记

LC4(S)?Lr,c,对于所有形如: Lr,c?2n?2r?1?c，(2?r?n?1,1?c?2r?2)的整数 有:N2(Lr,c)?22n?2r?1?2r?c?1且N2(0)?22n?2 .如果L?0,且不是Lr,c的形式,则不存在

n线性复杂度为LC(S)?2n?1,且LC4(S)?L的2?周期二元序列S。

n定理4.2.2 [35]线性复杂度为2n?1(n?3)的2?周期二元序列的2?错线性

复杂度的期望值为：

E2LC(S)?2n?1?2?7?2n?2n?2n??2?2?2r?1

r?3n?1r

n4.3 线性复杂度为2n?1的2?周期二元序列的4-错（或5-错）线性复杂度

引理4.3.1 令S是周期N?2n的二元序列，则LC(S)?2n，当且仅当W(S)是奇数。

证明 由LC(S)?deg(fS(x))?N?deg(gcd(SN(x),1?xN))得：

16

LC(S)?2n?gcd(x2?1,SN(x))?1?gcd(SN(x),1?xN))?1?SN(1)?1?W(S)是奇数。

引理

4.3.2[35]令S(n)?(S0,S1,?,S2n?1)是周期N?2n的二元序列，

nLC(S(n))?2n?2，当且仅当S0?S2???S2n?2?S1?S3???S2n?1?0。

n引理4.3.3[35]在F2上不存在两个2?周期二元序列a?(a0,a1,?,a2n?1)和

b?(b0,b1,?,b2n?1)有相同的线性复杂度C(1?C?2n?2)，且满足au?bu，av?bv，am?bm，an?bn和ai?bi(u?v?m?n,0?i?2n?1,i?u,v,m,n)，其中：u,v,m和n中有三个奇偶性相同,有一个奇偶性不同。

证明 令: a(n)(x)和b(n)(x)分别是序列a和b的生成函数，由

LC(S)?deg(fS(x))?N?deg(gcd(SN(x),1?xN))，且a与b有相同的线性复杂度C

nn得： a(n)(x)?a0?a1x???a2n?1x2?1?(1?x)2?ca?(x)

b(n)(x)?b0?b1x???b2n?1x2nn?1?(1?x)2n?cb?(x)

?x)?1其中：(a?(x),1，(b?(x),1?x)?1，由au?bu，av?bv，am?bm，an?bn得：

b(n)(x)?a(n)(x)?xu?xv?xm?xn?(1?x)2?ca?(x)?xv(1?xu?v)?xn(1?xm?n)， u,v,m和

n中有三个奇偶性相同,有一个奇偶性不同。不妨设:

u?v(mod2),m?n?v(mod2).u?v是奇数，且1?xnu?v?(1?x)?xj，则：1?x能被

j?0u?v?11?xu?v整除。但是((1故((1?x)2,b(n)(x))?1.由1?c?2n?2得：?x2),?1xu?v?).1n22?2n?c?2?1，则：(1?x)2?c能被b(n)(x)整除.这与((1?x),b(n)(x))?矛盾1.故原

命题得证。

n本部分主要讨论线性复杂度为2n?1的2?周期二元序列.由

Kmin?2WH(2n?LC(S))可知LC（S）减小，当且仅当K≥2.当K=2，3时，文献[35]已

经讨论.本文将进一步讨论K=4，5时的情况.由引理4.3.1知，W(S)为偶数.如果S中每个周期中改变五个字节，W(S)变为奇数，则LC(S)?2n。由此可见，

n对于线性复杂度为2n?1的2?周期二元序列，LC4(S)?LC5(S)。下面只需讨论

LC4(S)即可。

n定理4.3.1 设S是线性复杂度为2n?1的2?周期二元序列,记

r?2)的整数 LC4(S)?Lr,c ,对于所有形如: Lr,c?2n?2r?1?c(2?r?n?1,1?c?2nr?112n?2r?1?2r?c?1r?1?2?2r?c?1r?12(2?1)(2?2)?2有：N4(Lr,c)??2 31且N4(0)??(24n?4?22n?1)?23n?3?22n?2 。如果L≠0,且不是Lr,c的形式,则不存在

3n线性复杂度为LC(S)?2n?1,且LC4(S)?L的2?周期二元序列S。

证明 令S(n)?(S0,S1,?,S2n?1)是s的第一个周期序列，且LC(S)?2n?1。 由 Chan-Games算法知: L(S(t))?R(S(t)),LC(S(1))?1。其中

17

S(t)??t?1????n(S(n))?(S0(t),S1(t),???,S2t?1(t)),

S(t)i?2n?t?j?0?1Sj2t?i(2?t?n,0?i?2t?1)显然S(1)?(1,1),

则: S0?S2???S2n?2?1 (1)

S1?S3???S2n?1?1 (2)

令:a是s改变4个字节后得到的新的序列, a(t)的获得与S(t)一样(2?t?n). 由引理4.3.1知，W(S)是偶数，则a(t)与S(t)最多有4个字节不同. 接下来分三种情况讨论：

(ⅰ)当W(S)?W(s)?2时，显然：LC4(0)?LC2(0)是最小的。

由等式（1），（2）可知：1??S0,S2,???,S2n?2?，且集合?S0,S2,???,S2n?2?中只有一个“1”，同样，集合?S1,S3,???,S2n?1?中也只有一个“1”。故满足以上条件的序列S总共有：2n?1?2n?1?22n?2个，即：N4(0)?N2(0)?22n?2。 (ⅱ)当W(S)?W(S(n))?4时，显然：LC4(0)是最小的。 以下分两种情况讨论：

①1?{s0,s2,...,s2n?2}，且集合{s0,s2,...,s2n?2}中只有一个“1”， 1,1,1?{s1,s3,...,s2n?1}，

2且集合{s1,s3,...,s2n?1}只有3个“1”。则：满足以上条件的序列S总共有： 2n?1(3)n?1(n)个。

②1?{s1,s3,...,s2n?1}，且集合{s1,s3,...,s2n?1}中只有一个“1”， 1,1,1?{s0,s2,...,s2n?2}，且集合{s0,s2,...,s2n?2}中只有三个“1”， 则：满足以上条件的序列S总共有：

22n?1(3)个。

n?1综合①，②得：N4(0)?2(n?12n?13)?2(n?12n?131)?(24n?4?22n?1)?23n?3 31由(ⅰ)，(ⅱ)可知：N4(0)?(24n?4?22n?1)?23n?3?22n?2

3(ⅲ)当W(S)?W(S(n))?4时：

由?n的性质P2知W(S(t))(2?t?n)是偶数。令r是使得W(S(r))?4的最大整数，其中1?r?n?1，则对于所有r?j?n，W(L(S(j?1))?R(S(j?1)))?W(S(j))?4，即： 且S改变四个字节对应S(j)改变四个字L(S(j?1))和R(S(j?1))至少有四个字节不同，

节。 a(j?1)是S(j?1)最多改变四个字节所得到的序列。由L(a(j?1))?R(a(j?1))得

LC4(S)?2n?1?2n?2???2r?1。 接下来分两种情况讨论：

① 若S(n)中改变四个字节，恰好对应S(r?1)有四个字节改变使得

18

L(a(r?1))?R(a(r?1))，则a的线性复杂度满足下列形式：

(r?1)))。否则,若 Lr,c?2n?1?2n?2???2r?1?c，1?c?2r，其中C?LC(L(aL(a(r?1))?R(a(r?1))，a(r)是非零向量，则：a的线性复杂度LC?满足：

LC??2n?1?2n?2???2r?1?2r?Lr,c由LC4(S)是S(n)中改变四个字节得到的最小线性复杂度知LC4(S)?Lr,c。下面令a的线性复杂度为最小值LC4(S)?Lr,c。

(r?1)其中：C?LC(L(a))，且L(a(r?1))?R(a(r?1))。

)接下来说明C?2r?2，令：S(r)?(S0(r),S1r(,...,S2rr(?1))，且W(S(r))?4。设：

S(r)?(0,?,0,1,0,?,0,1,0,?,0,1,0,?,0,1,0,?,0) (3)

????uvmn其中，0?u?v?m?n?2r?1。由S(r)??r?1(S(r?1))得：

(r?1)(r?1)S(r?1)?(S0,S1(r?1),...,S2)，且满足： r?1?1(r?1)(r?1)(r)(r?1)(r?1)(r)(r?1)(r?1)(r),,Su?Su?1S?S?1S?S?1， r?Sur?Svr?Smvm?2v?2m?2(r?1)(r?1)(r)Sn?Sn?1 (4) r?Sn?2rr?1)(r)，0?t?2?1,2t?u,v,m,n。 St(r?1)?St(??S?0rt2(r)(r)(r)由L(a(r?1))?R(a(r?1))，且S(r)应该变为a(r)?0得Su应该变为0。由等,Sv(r),Sm,Sn(r?1)(r?1)r?1)(r?1)(r?1)(r?1)(?1)式(4)知Su，Sv(r?1)?Sv(?，Sm，和Sn应该变为0。若?Su?Sm?Snr?2r2r?2r?2r(1)?(1)r?(1)r?a(r?1)?(a0r(?1),a1r?,...,a2ra,a,r01?1((r?1)1)r?(S是由改变四个字节得到的，则可,...,a2)r?1(r?1)(r?1r)(r?1)以适当选择位置Su使得下列等式成立： ,Sv(r?1),Sm,Sn(r?1)(r?1)(r?1)a0?a2?....?a2?0 (5) r?2(r?1)(r?1)(r?1)a1?a3?....?a2?0 (6) r?1r对于长为2r的序列L(a(r?1))，由引理2知：C?LC(L(a(r?1)))?2，则二元序列?2S的4?错线性复杂度LC4(S)是形如：

Lr,c?2n?2r?1?c(2?r?n?1,1?c?2r?2)的整数，其中r=1时，C没有意义。 接下来计算满足线性复杂度为2n?1，LC4(S)?Lr,c的2n?周期二元序列S的总数。

(r))由(1)，(2)和(3)知：S0 ?S2(r)?....?S2rr(?2?S0?S2?...?S2n?2?1(r)(r)S1(r)?S3?....?S2?S1?S3?...?S2n?1?1，这里，u,v,m和n的取值情况与r?1W(S(n))?4时相似。

由以上讨论结果可知：对于固定的S(r)和线性复杂度为C的L(a(r?1))，L(a(r?1)))是由L(S(r?1)通过适当改变Su(r?1),Sv(r?1),Sm(r?1)和Sn(r?1)而得，故由L(S(r?1))变为)共有16种情况。对于定值C，1?c?2r?2，由文献[40]知，L(a(r?1))共L(a(r?1)(r?1)有2c?1种选择，可使LC(L(a))?C。由引理4。3。3知，不存在两个2r?周期

序列仅仅只有四个字节不同，却有相同的线性复杂度C (1?c?2r?2)。R(S(r?1))完全由L(S(r?1))确定。所以对于固定的S(r)和C，S(r)的原象有16?2c?1?2c?3种选择使得S(r?1)改变后的序列线性复杂度为C。

19

r?12??(r)rS当W(S)?4时，与情况1类似。 的个数为2??，则利用?n的性质P3知，

3??2r?1??12n?12n?22rc?1r?共有2?2?2?2?2??条序列S满足：且LC4(S)?Lr,c，LC(S)?2n?1，??16?3?(r)其中1?c?2r?2。 故N4(Lr,c)?22n?1?22n?2?22r?1?2r?1??2?2????16

3??c?1r?11nr?1?22?2?2r?c?1(2r?1?1)(2r?1?2)(2?r?n?1,1?c?2r?1?2) 3② 若S(n)中改变四个字节，恰好对应S(r?1)有两个字节改变使得：

L(a(r?1))?R(a(r?1))

这种情况的讨论与情况①类似，可参见文献[44]得出：

N4(Lr,c)?22?22?22?22r?2?2c?1?4?22n?1n?2r?1n?2r?1?2r?c?1

nr?11nr?1综合①，②可知：N4(Lr,c)?22?2?2r?c?1(2r?1?1)(2r?1?2)?22?2?2r?c?1

3定理4.3.2 线性复杂度为2n?1（n≥3）的2n?周期二元序列的4?错线性复杂度的期望值为：

E4|LC?s??2n?1?22?2(T1?T2?T3?T4?T5?T6)

n其中: T1?22n?n?1n?1r?23n?22r?2(22?1?2)(2r?1?1)(2r?1?2)

r?1r22?2n?13r?2r?12r?1T2?(2?2)(2r?1?1)(2r?1?2) ?23r?222?1n?12r?2r?12r?r?12r2r?1T3?2(2?2?2?2)(2r?1?1)(2r?1?2) ?3r?2nT4?2T6?22n?n?1?2r?2n?12r?2r?1(2r2r?1?2)；T5?2?23r?2(22?1?2)

r?2rr2nn?1r?1r2n?1?22r?2(22?r?1?22?22?1?2)

r?2n?1r?1证明 22n?2E4|LC?s??2n?1???N4(Lr,c)Lr,c

r?2c?1n?12r?2n?12r?21nr?1nr?1???????22?2?2r?c?1(2r?1?1)(2r?1?2)?22?2?2r?c?1??(2n?2r?1?c)r?2c?1?3?n?12r?21nr?112n?n?2r?1?2r?c?1r?1r?1????2(2?1)(2?2)????22?2?3r?c?2(2r?1?1)(2r?1?2)r?2c?13r?2c?13n?12r?2

20

n?12r?2nr?112n?2r?1?2r?c?1r?1r?1????c?2(2?1)(2?2)???22?n?2?2r?c?1r?2c?13r?2c?1n?12r?2n?12r?22n?2r?1?3r?cn?12r?2n???2r?2c?1???c?22r?2c?1?2r?1?2r?c?1

?T1?T2?T3?T4?T5?T6

其中

2r?212n?n?2r?1?2r?c?1r?112n?n?1n?12r?2r?1r?1r?1r?1T1????2(2?1)(2?2)??2(2?1)(2?2)?2c?2r?2c?13r?2c?13n?12r?2

?22n?n?1n?1r?23n?12r?2?22r?2(22?1?2)(2r?1?1)(2r?1?2)

r?1r2r?212n?2r?1?3r?c?2r?112n?2n?13r?2r?1r?1r?1r?1T2????2(2?1)(2?2)??2?2(2?1)(2?2)?2cr?2c?13r?2c?1322?2n?13r?2r?12r?1?2(2?2)(2r?1?1)(2r?1?2) ?3r?2n?12r?212r?2nr?1r?11nn?1T3????c?22?2?2r?c?1(2r?1?1)(2r?1?2)??22?1.?22r?2(2r?1?1)(2r?1?2)??c?2c

r?2c?13r?2c?13mn由?j?2?(m?1)2jj?1nm?1?2,得?c?2c?(2r?3)?22c?12r?2r?1?2

22?1n?12r?2r?1?r2r?1?(2r?1?1)(2r?1?2) 故T3?.?2(2?3)?2?2??3r?2T4???22r?2c?1nn?12r?2n?n?2r?1r22?1n?12r?2r?12r?r?12r?2r?c?1?.?2(2?2?22?1?2)(2r?1?1)(2r?1?2)3r?2n

?22?n?1?2r?2n?12r?2r?12r?2c?1?2?2c2nn?1r?22n?n?1?22r?2(22?1?2)

r?2c2nn?1r?1rn?1r?1rT5???2r?2c?1n?12r?2n?12r?22n?2r?1?3r?c?2?2?23r?2r?12r?2c?1?2?2?23r?2(22r?22r?2c?1?1?2)r?1r

T6???c?2r?2c?12n?2r?1?2r?c?12n?1?2r?2n?12r?2r?1?c?2?2c2n?1r2?1(2?3)?2?2??22r?2??? r?2n?1?22n?1?2r?2n?12r?2r?1(2n2r?r?1?2?22r2r?1?2)

故 E4|LC?s??2n?1?22?2(T1?T2?T3?T4?T5?T6)

21

第五章 周期多序列及其广义对偶多序列的线性复杂度

本章介绍了周期多序列联合线性复杂度的基础知识，在此基础上分别提出了F2和Fp上周期多序列的广义对偶序列的定义，讨论了F2上二元周期多序列及其对偶序列的极小多项式之间关系，并计算出它们之间线性复杂度的关系；提出了F2上周期多序列的广义重量复杂度的定义, 在此基础上进一步讨论了周期多序列及其广义对偶多序列的广义重量复杂度之间的关系；接下来进一步讨论了Fp上p元周期多序列及其广义对偶序列的极小多项式之间的关系，并计算出它们之间线性复杂度的关系。

5.1 周期多序列联合线性复杂度基础知识

有限域上单序列的线性复杂度分析是流密码学密钥流序列的基本内容[6],很多学者研究了单序列线性复杂度以及序列的复杂度测量[36]。随着流密码学的发展,近年来以“字”或“向量”为单位的流密码渐渐引起重视,这些流密码学的理论要求研究多序列的联合线性复杂度。对于多序列的研究主要包括两个方面:一方面是多序列的分析,文献[37]中介绍了多序列的联合线性复杂度的综述;文献[18]研究了周期多序列的联合线性复杂度的期望值;文献[38]研究了一类特殊多序列的联合线性复杂度轮廓。文献[39,40]利用代数曲线构造了具有近乎优的联合线性复杂度轮廓性质的多序列。另一方面是对多序列的综合,即求多序列的极小多项式与联合线性复杂度。这是多序列中非常重要的问题。单序列的综合有B-M算法,连分式算法和欧几里德算法[6]等。文献[41,42]]中研究了多序列的综合及其在编码解码中的应用,Feng 等在文献[43,44]提出了广义欧几里德算法和迭代算法,后来许多学者也应用Gr?bner基理论来处理这个问题[45,46]。本文将在提出周期多序列的广义对偶多序列定义的基础上,讨论了二元周期多序列及其广义对偶多序列的极小多项式之间的关系,并且将进一步计算出它们之间的联合线性复杂度的关系。

设S是一个字长为t的以“字”为单位的序列,即S?(S0,S1,?),其中

Si?(a1i,a2i,?,ati),aji?F2,1?j?t,i?0,1,?,称S为F2上t-维多序列,当t?1时,即为通常所指的单序列。多序列S可以写成矩阵的形式:

a12???a21a22??,其中第i列为Si。

?????at1at2??用Aj?(aj0,aj1,aj2,?),j?1,2,?,t,那么S可以看成由t个“平行序列”构成的新?a10?aS?(S0,S1,?)??20????at0a11序列,并记: S?(A1,A2,?,At)。

在F2上t-维多序列S?(S0,S1,?),如果满足: Si?N?Si,i?0,则称正整数N是

22

多序列S的周期,其最小周期记为per(S),显然

lcm(per(A1),per(A2),?,per(At))?per(s),其中per(Aj)是Aj,1?j?t的最小周期。周期为N的t-维多序列S?(A1,A2,?,At)的极小多项式F(x)是指序列A1,A2,?,At的次数最低的共同特征多项式,则: F(x)?lcm(f1(x),f2(x),?,ft(x)),其中fj(x)是

F(x))称为多序列S的联合线性复杂Aj,1?j?t的极小多项式。那么L(S)?deg(度。设序列Aj的周期为N,记AjN(x)为Aj,1?j?t的第一个周期所对应的多项

1?xN式。由于:fj(x)? ,1?j?t，那么F(x)?lcm(f1(x),f2(x),?,ft(x)) NNgcd(1?x,Aj(x))1?xN1?xN1?xN?lcm(,,?,)NNNNNNgcd(1?x,A1(x))gcd(1?x,A2(x))gcd(1?x,At(x))1?xN ?gcd(1?xN,A1N(x),A2N(x),?,AtN(x))

5.2 二元周期多序列及其广义对偶序列的联合线性复杂度

定义

5.2.1 周期为N的t-维多序列S?(A1,A2,?,At)，其中

如果S?(A1,A2,?,At)满足Aj?(a0j,aAj?(aa?0j,a1j,?2j,，)1j,a2j,，)其中

i?0,1,2,?，1?j?t，则称S为S的广义对偶多序列。周期为N的t-aji?1?a，ji

维多序列S?(A1,A2,?,At)的极小多项式F(x)是指序列A1,A2,?,At的次数最低的共同特征多项式，显然F(x)?lcm(f1(x),f2(x),?,ft(x)),，其中fj(x)是Aj，1?j?t的极小多项式，那么L(S)?deg(F(x))称为多序列S的联合线性复杂度。设序列Aj的周期为N，记AjN(x)为Aj，1?j?t的第一个周期所对应的多项式。

1?xN由于fj(x)? ，1?j?t，

gcd(1?xN,AjN(x))则F(x)?lcm(f1(x),f2(x),?,ft(x))

1?xN1?xN1?xN ?lcm(,,?,)

gcd(1?xN,A1N(x))gcd(1?xN,A2N(x))gcd(1?xN,AtN(x))1?xN ? NNNNgcd(1?x,A1(x),A2(x),?,At(x))引理5.2.1

[31]

设F2上周期序列S生成函数s(x)??Sixi????i?0rs(x)，其中fs(x)gcdrs(x(fs)x,?(，且))fs(x)是S的极小多项式，记fs(x)??cjxj (c0?cm?1)，

?mj?0以l记x?1为fs(x)根的次数（l?0），即：fs(x)?(1?x)lf1(x)，其中f1(1)?0，则

23

对S?的按位取反序列S?的生成函数：

?(1?x)rs(x)?fs(x)，l?0??(1?x)fs(x)(1?x)rs(x)?fs(x)?(rs(x)?f1(x))/(1?x)s(x)???,fs(x)(1?x)f1(x)??rs(x)?f1(x),l?2?fs(x)??(1?x)fs(x),l?0?,l?1 S?的极小多项式为：fs(x)??f1(x)?f(x),l?2?sl?1

推论5.2.1 设F2上周期多序列S?(A1,A2,?,At)，N-周期序列Aj，1?j?t的生成函数Aj(x)??ajixi?i?0m??rj(x)fj(x)，其中gcd(rj(x),fjx())?，且1fj(x)是Aj的极小多

项式，记fj(x)??crxr(c0?cm?1)，以lj记x?1时fj(x)根的次数(lj?0)，即：

r?0fj(x)?(1?x)jgjx(,)其中gj(1)?0，则对Aj按位取反序列Aj的生成函数：

?(1?x)rj(x)?fj(x),?(1?x)fj(x)?(1?x)rj(x)?fj(x)??(rj(x)?gj(x))/(1?x)Aj(x)???,fj(x)(1?x)g(x)j??rj(x)?gj(x)?,f(x)?j?lj?0lj?1 ； lj?2l?(1?x)fj(x),?Aj的极小多项式为： fj(x)??gj(x),?f(x),j?lj?0lj?1

lj?2定理5.2.1设周期t-维多序列S?(S0,S1,?)?(A,,A)1,A2?t的广义对偶多序列

S?(S0,S1,?)?(A1,A2,?,At)，其中Si?(a1i,a2i,?,ati)，Aj?(aj0,aj1,aj2,?)，

Aj?(aj0,aj1,aj2,?)，aji?1?aji，i?0,1,2,?，1?j?t，fj(x)和fj(x)分别表示Aj与Aj的极小多项式。如果：fj(x)?(1?x)jgj(x)，1?j?t，lj?0，其中：gj(1)?0，则：S的极小多项式F(x)与S的极小多项式F(x)存在以下关系：

?(1?x)F(x),lj?0?lj?1 ，其中：G(x)?lcm[g1(x),g2(x),?,gt(x)] F(x)??G(x),?F(x),lj?2?证明 由推论5.2.1知：若fj(x)?(1?x)jgj(，1?j?t，lj?0，gj(1)?0，x)

24

ll?(1?x)f(x),l?0jj??,lj?1 则fj(x)??gj(x)?,lj?2??fj(x)而：F(x)?lcm(f1(x),f2(x),?,ft(x))，F(x)?lcm(f1(x),f2(x),?,ft(x)),那么： (1)当lj?0时，

F(x)?lcm(f1(x),f2(x),?,ft(x))

?lcm[(1?x)f1(x),(1?x)f2(x),?,(1?x)ft(x)] ?(1?x)lcm[f1(x),f2(x),?,ft(x)]

?(1?x)F(x)

(2)当lj?1时，

F(x)?lcm(f1(x),f2(x),?,ft(x))

?lcm[g1(x),g2(x),?,gt(x)] 令：G(x)?lcm[g1(x),g2(x),?,gt(x)] 则：F(x)?G(x) (3)当lj?2时，

F(x)?lcm(f1(x),f2(x),?,ft(x))

?lcm[f1(x),f2(x),?,ft(x)]

?F(x)

从而得证。

?L(S)?1,lj?0?推论5.2.2：在上述记号下，L(S)??L(S)?t,lj?1。

?L(S),lj?2?证明 由定理5.2.1的结论及周期多序列的联合线性复杂度定义可以直接得出结果。

定义5.2.2 设F2上周期为N的t-维多序列S?(A1,A2,?,At)的广义对偶多序列S?(A1,A2,?,At)，其中Aj?(aj0,aj1,aj2,,Aj?(aj0,aj1,aj2,?)， ?)aji?1?aji，i?0,1,2,?,1?j?t,SN的广义重量复杂度定义为：

NNWcu(SN)?minL(A?M) jjNWH(Mj)?u?m10?m20?这里M?(m0,m1,...)?????mt0m11m12???m21m22??用Mj?(M1,M2,...,Mt),其中第i列为mi，

????mt1mt2?? 25

N表示上述矩阵的第j行,即：Mj?(mj0,mj1,mj2,?)，1?j?t。WH(MNj)?u表示Mj的Hamming重量，即MjN中非零分量的个数，L(SN)表示序列SN的线性复杂度。 定理5.2.2设SN是F2上N-周期多序列，SN与SN重量复杂度有下列关系：

Wcu(SN)?WcN?u(SN)。

证明 Wcu(SN)?minL(AjN?MjN)?minL(AjN?MjN?1N) NNWH(Mj)?uWH(Mj)?uNN?minL(A?M)?jjNWH(Mj)?uWH(Rj)?N?uminNL(AjN?RjN)?WcN?u(SN)

5.3 p元周期多序列及其广义对偶序列的联合线性复杂度

设S是一个字长为t的以“字”为单位的序列,即S?(S0,S1,?),其中

Si?(a1i,a2i,?,ati),aji?Fp,1?j?t,i?0,1,?,称S为Fp上t?维多序列,当t?1时,即为通常所指的单序列。多序列S可以写成矩阵的形式:

a12???a21a22??,其中第i列为Si。

?????at1at2??用Aj?(aj0,aj1,aj2,?),j?1,2,?,t,那么S可以看成由t个“平行序列”构成的新?a10?aS?(S0,S1,?)??20????at0a11序列,并记: S?(A1,A2,?,At)。

在Fp上t?维多序列S?(S0,S1,?),如果满足: Si?N?Si,i?0,则称正整数N是多序列S的周期,其最小周期记为per(s),显然

per(s)?lcm(per(A1),per(A2),?,per(At)),其中per(Aj)是Aj,1?j?t的最小周期。周期为N的t?维多序列S?(A1,A2,?,At)的极小多项式F(x)是指序列A1,A2,?,At的次数最低的共同特征多项式,则:

F(x)?lcm(f1(x),f2(x),?,ft(x))其中fj(x)是Aj,1?j?t的极小多项式。那么

L(S)?degF(x(称为)多序列S的联合线性复杂度。设序列Aj的周期为N,记

AjN(x)为Aj,1?j?t的第一个周期所对应的多项式。由于:

1?xN ,1?j?t fj(x)?gcd(1?xN,AjN(x))那么F(x)?lcm(f1(x),f2(x),?,ft(x))

1?xN1?xN1?xN?lcm(,,?,)gcd(1?xN,A1N(x))gcd(1?xN,A2N(x))gcd(1?xN,AtN(x))

26

1?xN ?gcd(1?xN,A1N(x),A2N(x),?,AtN(x))定义5.3.1 设Fp上周期为N的t?维多序列S?(A1,A2,?,At)，其中

Aj?(aj0,aj1,aj2,?)，如果S?(A1,A2,?,At)满足Aj?(a0j,a?1j,a2j,，)其中

1?j?t，则称S为S的广义对偶多序列。周期为N的t?aji?1?a，jii?0,1,2,?，

维多序列S?(A1,A2,?,At)的极小多项式F(x)是指序列A1,A2,?,At的次数最低的共同特征多项式，显然F(x)?lcm(f1(x),f2(x),?,ft(x))，其中fj(x)是Aj，1?j?t的极小多项式，那么L(S)?deg(F(x))称为多序列S的联合线性复杂度。设序列Aj的周期为N，记AjN(x)为Aj，1?j?t的第一个周期所对应的多项式。

1?xN由于fj(x)? ，1?j?t，

gcd(1?xN,AjN(x))则：F(x)?lcm(f1(x),f2(x),?,ft(x))

1?xN1?xN1?xN ?lcm(,,?,) NNNNNNgcd(1?x,A1(x))gcd(1?x,A2(x))gcd(1?x,At(x))1?xN ?

gcd(1?xN,A1N(x),A2N(x),?,AtN(x))引理5.3.1 设Fp上周期序列的S?极小多项式为fs(x)?(1?x)tg(x)，其中t为非负整数g(1)?0.S的生成函数s(x)??sixi????i?0rs(x),其中gcd(rs(x),fs(x))?1，则S?fs(x)的对偶序列S?的生成函数：

?(p?1)g(x)?rs(x)(1?x),?(1?x)g(x)?(p?1)fs(x)?(1?x)rs(x)??(p?1)(1?x)g(x)?rs(x)(1?x)??,s(x)?2(1?x)g(x)fs(x)(1?x)??(p?1)(1?x)tg(x)?r(x)(1?x)s,?t?1(1?x)g(x)??t?0t?1 t?2?(1?x)fs(x),?1?f(x),??S的极小多项式为：fs(x)??1?xs?fs(x),???fs(x),??t?0g(1)?rs(1)?p,t?1g(1)?rs(1)?p,t?1t?2

推论5.3 .1 设Fp上周期多序列S?(A1,A2,?,At)，N-周期序列Aj，1?j?t的生成函数Aj(x)??ajix?ii?0rj(x)fj(x)，其中gcd(rj(x),fjx())?，且1fj(x)是Aj的极小多

27

项式，记fj(x)??crxr(c0?cm?1)，以lj记x?1时fj(x)根的次数(lj?0)，即：

r?0mfj(x)?(1?x)jgjx(,)其中gj(1)?0，则对Aj按位取反序列Aj的生成函数：

?(p?1)g(x)?r(x)(1?x)jj?,lj?0(1?x)gj(x)?(p?1)fj(x)?(1?x)rj(x)??(p?1)(1?x)gj(x)?rj(x)(1?x)Aj(x)???,lj?1 2(1?x)g(x)fj(x)(1?x)j??lj(p?1)(1?x)gj(x))?rj(x)(1?x)?,lj?2lj?1?(1?x)gj(x)?l?(1?x)fj(x),?1?fj(x),?的极小多项式为： Ajfj(x)??1?x?fj(x),???fj(x),lj?0gj(1)?rj(1)?p,lj?1gj(1)?rj(1)?p,lj?1lj?2

证明 由引理5.3.1和多序列的广义对偶序列的定义可以直接得到。 定理5.3.1设Fp上周期t?维多序列S?(S0,S1,?)?(A1,A2,?,At)的广义对偶多序列S?(S0,S1,?)?(ASi?(a1i,a2i,?,ati)，Aj?(aj0,aj1,aj2,?)，,,A)1,A2?t，其中

Aj?(aj0,aj1,aj2,?)，aji?1?aji，i?0,1,2,?，1?j?t，fj(x)和fj(x)分别表示Aj与Aj的极小多项式。如果：fj(x)?(1?x)jgj(x)，1?j?t，lj?0，其中：gj(1)?0，则：S的极小多项式F(x)与S的极小多项式F(x)存在以下关系：

l?(1?x)F(x),?1?F(x),?F(x)??1?x?F(x),???F(x),证明 由推论5.3.1知

lj?0gj(1)?rj(1)?p,lj?1gj(1)?rj(1)?p,lj?1lj?2

若fj(x)?(1?x)jgj(x)，1?j?t，lj?0，gj(1)?0，则Aj的极小多项式为：

l(),?(1?x)fjx?1?f(x),?fj(x)??1?xj?fj(x),???fj(x),lj?gj(1)?rjgj(1)?rj(1)?p(1)?plj,?lj,?lj?20

11而：F(x)?lcm(f1(x),f2(x),?,ft(x))，F(x)?lcm(f1(x),f2(x),?,ft(x))。那么：

28

（1）当lj?0时，

F(x)?lcm(f1(x),f2(x),?,ft(x))

?lcm[(1?x)f1(x),(1?x)f2(x),?,(1?x)ft(x)] ?(1?x)lcm[f1(x),f2(x),?,ft(x)]

?(1?x)F(x)

（2）当gj(1)?rj(1)?p，lj?1时，

F(x)?lcm(f1(x),f2(x),?,ft(x))

111?lcm(f1(x),f2(x),?,ft(x))

1?x1?x1?x?11lcm(f1(x),f2(x),?,ft(x))?F(x) 1?x1?x（3）当gj(1)?rj(1)?p，lj?1时，

F(x)?lcm(f1(x),f2(x),?,ft(x))

?lcm(f1(x),f2(x),?,ft(x))?F(x)

（4）当lj?2时，

F(x)?lcm(f1(x),f2(x),?,ft(x))

?lcm(f1(x),f2(x),?,ft(x))?F(x)

从而得证。

推论5.3.2：在上述记号下，

?L(S)?1,?L(S)?1,?L(S)??L(S),???L(S),lj?0gj(1)?rj(1)?p,lj?1

lj?2gj(1)?rj(1)?p,lj?1证明 由引理5.3.1的结论及周期多序列的联合线性复杂度定义可以直接得出结果。

29

第六章 总结

6.1 论文工作总结

周期序列的线性复杂度和k-错线性复杂度是度量流密码强度的两个重要指标。本文的研究从最基本的极小多项式开始，首先讨论了F2上的序列S?与其对偶序列S的生成函数，极小多项式和线性复杂度之间的关系.在此基础上进一步探讨了FP上序列S?与其对偶序列S的生成函数，极小多项式和线性复杂度之间的关系；接着在F2上线性复杂度为2n?1的2n?周期二元序列的2-错（或3-错）线性复杂度的已有结论的基础上，更进一步讨论了线性复杂度为2n?1的

2n?周期二元序列的4-错（或5-错）线性复杂度，并计算出相应的期望值，推

??动了周期序列稳定性的进一步研究；以上都是对单序列的线性复杂度和k-错线性复杂度进行了研究，本文最后的部分在以上研究的基础上分别提出了F2和FP上周期多序列的广义对偶序列的定义，讨论了F2上二元周期多序列及其对偶序列的极小多项式之间关系，并计算出它们之间线性复杂度的关系，接下来进一步讨论了FP上p元周期多序列及其广义对偶序列的极小多项式之间的关系，并计算出它们之间线性复杂度的关系。 6.2 结束寄语

本人在学习过程中有以下的想法需要进一步去探讨：

1、针对周期序列及其对偶序列的特殊关系，可以对对偶序列的线性复 杂度和k-错线性复杂度进行相关的研究；

2、在讨论线性复杂度为2n?1的2n?周期二元序列的k?错线性复杂度 （k=4,5）的基础上可以进一步讨论线性复杂度为一般值的情况； 3、探讨其他周期上序列的k?错线性复杂度，并计算出相应的期望值； 4、在本文讨论的基础上可以进一步进行F2上周期多序列及其广义对偶多序列的线性复杂度和k-错线性复杂度相关的研究；

5、在本文讨论的基础上可以进一步进行FP上周期多序列及其广义对偶多序列的线性复杂度和k-错线性复杂度相关的研究；

30

本文来源：https://www.bwwdw.com/article/2sc6.html