（通信与信息系统专业论文）几类伪随机序列的研究.pdf

摘要 伪随机序列在密码学、扩频通信、计算、控制等领域都有广泛的应用。 伪随机序列的设计和分析一直是国际上的研究热点，寻找新的方法来设计更 多性质良好的序列，以及寻找更有力的工具来分析清楚已有序列的性质，都 是非常有价值的工作。 在本文中，我们对伪随机序列中的几个问题进行了深入的研究，这些问 题是：带进位的反馈移位寄存器( f c s r ) 、二元序列的2 - a d i c 复杂度、周期 序列的广义离散傅立叶变换和周期序列的1 一e r r o r 线性复杂度、两类邑r 导 出序列的独立r 一样式分布和部分周期性质、利用函数域设计序列等等。 具体地说主要贡献如下： 1 ) 给出了f c s r 序列分布的明显公式，利用这个公式讨论了f c s r 序 列的游程分布等分布性质。讨论了f c s r 序列的通常自相关和算术自相关。 证明了二元f c s r 序列在某些条件下具有大的1 - e r r o r 和2 - e r r o r 线性复杂 度。 2 ) 指出了二元周期序列线性复杂度和2 - a d i c 复杂度的一个显著的差别， 讨论了这个差别对序列综合的影响。基于这一观察，给出了更加合理的二元 周期序列对称2 - a d i c 复杂度的概念。计算了二元周期序列2 - a d i c 复杂度和 对称2 - a d i c 复杂度的期望值。给出了二元周期序列k - e r r o r2 - a d i c 复杂度和 k e r r o r 对称2 - a d i c 复杂度的非平凡下界。 3 ) 指出i e e et r a n s a c t i o n so ni n f o r m a t i o nt h e o r y 上1 9 9 8 年和2 0 0 4 年的两篇论文的结果本质上是一祥的。 4 ) 将周期序列的广义离散傅立叶变换应用到周期序列的1 - e r r o r 线性复 杂度的研究中去，构造了许多具有大的1 - e r r o r 线性复杂度的序列，改进了 n i e d e r r e i t e r 的结果。 5 ) 利用g a l o i s 环上的指数和估计分析了两类磊z 导出序列的独立r 一样 式分布，证明了它们都是渐进均匀的，所得结果改进了以前的公开结果。 6 ) 利用g a l o i s 环上的混合指数和估计与离散傅立叶变换，给出了g a l o i s 环上的部分指数和估计。 7 ) 利用g a l o i s 环上的部分指数和估计，分析了两类邑z 导出序列的部 分周期分布和部分周期独立r 一样式分布，证明了它们也都是渐进均匀的。 摘要 8 ) 利用函数域的k u m m e r 扩张构造了一类新的具有低相关和高线性复 杂度的二元周期序列，并且使用椭圆函数域的理论给出了一些具体例子。在 某些情况下，我们的构造方法比x i n g 等学者的构造方法更好， 关键词线性复杂度，k - e r r o r 线性复杂度，f c s r ，2 - a d i c 复杂度，k - e r r o r 2 - a d i c 复杂度，g a l o i s 环上的指数和，g a l o i s 环上的部分指数和，周期序 列的r 一样式，函数域，函数域的k m n m e r 扩张。 a b s t r a c t r e s e a r c ho ns e v e r a lp s e u d o r a n d o ms e q u e n c e s h o n g g a n gh u ( c o m m u n i c a t i o n sa n di n f o r m a t i o ns y s t e m ) d i r e c t e db yp r o f e s s o rd e n g g u of e n g p s e u d o r a n d o ms e q u e n c e sa g ew i d e l yu s e di nc r y p t o g r a p h y , c o m m u n c i a - t i o n s ，c o m p u t a t i o n ，c o n t r o l ，e t c t h ed e s i g na n da n a l y s i so fp s e u d o r a n d o m s e q u e n c e sa r eh o tr e s e a r c ht o p i c si nt h ew o r l da l lt h et i m e l o o k i n gf o rn e w m e t h o dt od e s i g nm o r es e q u e n c e sw i t hn i c ep r o p e r t i e s a sw e l la sl o o k i n gf o r s t r o n g e rm a t h e m a t i c a lt o o lt oa n a l y z et h ep r o p e r t i e so fe x i s t i n gs e q u e n c e si n d e t a i l ，i sv e r yv a l u a b l e i nt h i sd i s s e r t a t i o n ，w ec a r r yo u td e e pr e s e a r c ho ns o n l ep r o b l e m si n t h ef i e l do fp s e u d o r a a d o ms e q u e n c e s t h e s ep r o b l e m sa r e ：f e e d b a c kw i t h c a r r ys h i f tr e g i s t e r ( f c s r ) ，t h e2 - a d i cc o m p l e x i t yo fb i n a r ys e q u e n c e s ，t h e r e l a t i o n s h i pb e t w e e nt h eg e n e r a l i z e dd i s c r e t ef o u r i e rt r a n s f o r ma n dt h e1 一 e r r o rl i n e a rc o m p l e x i t yo fp e r i o d i cs e q u e n c e s ，t h ed i s t r i b u t i o no fi n d e p e n d e n t r p a t t e r na n dp a r t i a lp e r i o dp r o p e r t i e so ft w oc l a s s e so fb i n a r ys e q u e n c e s d e r i v e df r o m 扬l ，p s e u d o r a n d o ms e q u e n c e sf r o mf u n c t i o nf i e l d ，e t c o u rm a i nc o n t r i b u t i o n s & r el i s t e db e l o w ： 1 ) t h ee x p l i c i tf o r m u l a f o rt h ed i s t r i b u t i o no ff c s r s e q u e n c e si sd e r i v e d w i t ht h ea i do ft h i sf o r m u l a ，w ea n m y z et h ed i s t r i b u t i o n a lp r o p e r t i e so f f c s rs e q u e n c e si nd e t a i l w ea l s od i s c u s st h ec o i d i i o ua u t o c o r r e l a t i o n ss a d a r i t h e m e t i ca u t o c o r r e l a t i o n so ff c s rs e q u e n c e s ，a n dt h el i n e a rc o m p l e x i t y o fs o m eb i n a r yf c s rs e q u e n c e su n d e r1o r2s y m b o l ss u b s t i t u t i o nw i t h e n e v e r yp e r i o di sp r o v e dt ob el a r g eu n d e rs o m ec o n d i t i o n s 2 ) as i g n i f i c a n td i f f e r e n c eb e t w e e nt h el i n e a rc o m p l e x i t ya n dt h e2 - a d i c c o m p l e x i t yi sp o i n t e do u t ，a n dt h ei n f l u e n c eo ft h i sd i f f e r e n c eo nt h es e q u e n c e s y n t h e s i sp r o b l e mi sd i s c u s s e d b a s e do nt h i so b s e r v a t i o n ，w ep r o p o s eam o r e r e a s o n a b l ec o n c e p to ft h es y m m e t r i c2 - a d i cc o m p l e x i t y , t h ee x p e c t e dv a l u e s o ft h e2 - a d i cc o r n p l e x i t ya n dt h es y m m e t r i c2 - a d i cc o m p l e x i t yo fp e r i o d i c i n a b s t r a c t i v b i n a r ys e q u e n c e sa r ed i s c u s s e d n o n t r i v i a ll o w e rb o u n d so nt h ek e r r o r2 - a d i c c o m p l e x i t ya n dt h es y m m e t r i c2 - a d i cc o m p l e x i t yo fp e r i o d i cb i n a r ys e q u e n c e s & r eg i v e n 3 ) w ep o i n to u tt h a tt h ec o n t e n t so ft w op a p e r si ni e e et r a n s a c t i o n s o ni n f o r m a t i o nt h e o r ya l ee s s e n t i m l yt h es a m e 4 ) w ec o n s t r u c tm a n yp e r i o d i cs e q u e n c e sw i t hv e r yl a r g e1 - e r r o rl i n e a r c o m p l e x i t yo v e rbb yt h eg e n e r a l i z e dd i s c r e t ef o u r i e rt r a n s f o r mo fp e r i o d i c s e q u e n c e s t h er e s u l t so fn i e d e r r e i t e ra r ei m p r o v e d 5 ) w i t ht h eh e l po fc e r t a i ne x p o n e n t i a ls l n n so v e rg a l o i sr i n g s ，w ea r i a - l y z et h ei n d e p e n d e n tr p a t t e r nd i s t r i b u t i o ni nt w oc l a s s e so fb i n a r ys e q u e n c e s d e r i v e df r o m 邑ht h e ya l eb o t hp r o v e dt ob ea s y m p t o t i c a l l yu n i f o r m t h e n e wr e s u l t si m p r o v et h ek n o w no n e s 6 ) w ee s t i m a t es o m ei n c o m p l e t ee x p o n e n t i a ls t l u so v e rg a l o i sr i n g sb y c e r t a i nh y b r i de x p o n e n t i a ls u n l so v e rg a l o i sr i n g s 7 ) b yt h ei n c o m p l e t ee x p o n e n t i a ls l l i d l so v e rg a l o i sr i n g sd e r i v e db y u s ，w ea n a l y z et h ep a r t i a lp e r i o dd i s t r i b u t i o na n dp a r t i a lp e r i o dr p a t t e r n d i s t r i b u t i o ni nt w oc l a s s e so fb i n a r ys e q u e n c e sd e r i v e df r o mz 8 ) b yt h ek u m m e re x t e n s i o n so ff u n c t i o nf i e l d s ，w ec o n s t r u c tan e w c l a s so fb i n a r ys e q u e n c e sw i t hl a r g el i n e a rc o m p l e x i t ya n dl o wc o r r e l a t i o n w ea l s og i v es o m ee x a m p l e sw h e nt h eu n d e r l y i n gf u n c t i o nf i e l d sa r ee l l i p t i c f u n c t i o nf i e l d s i ns o m ec a s e s ，o u rr e s u l t sa l eb e t t e rt h a nt h o s eo fx i n ge ta 1 k e yw o r d s ：l i n e a rc o m p l e x i t y , k - e r r o rl i n e a rc o m p l e x i t y , f c s r ，2 - a d i c c o m p l e x i t y , k - e r r o r2 - a d i cc o m p l e x i t y , e x p o n e n t i a ls u n lo v e rg a l o i sr i n g s ，i n - c o m p l e t ee x p o n e n t i a ls u mo v e rg a l o i sr i n g s ，r p a t t e r no fp e r i o d i cs e q u e n c e s ， f u n c t i o nf i e l d ，k u m m e re x t e n s i o no ff u n c t i o nf i e l d s 研究成果声明 本人郑重声明：所提交的学位论文是我本人在指导教师的指导下进 行的研究工作获得的研究成果。尽我所知，文中除特别标注和致谢的地 方外，学位论文中不包含其他人已经发表或撰写过的研究成果，也不包 含为获得中国科学院电子学研究所或其它教育机构的学位或证书所使用 过的材料。与我一同工作的合作者对此研究工作所做的任何贡献均已在 学位论文中作了明确的说明并表示了谢意。 特此申明。 签名：锅# 幼习 日期：神t j - 关于学位论文使用权的说明 本人完全了解中国科学院电子学研究所有关保留、使用学位论文的 规定，其中包括：电子所有权保管、并向有关部门送交学位论文的原 件与复印件；电子所可以采用影印、缩印或其它复制手段复制并保存 学位论文；电子所可允许学位论文被查阅或借阅；电子所可以学术 交流为目的，复制赠送和交换学位论文；电子所可以公布学位论文的全 部或部分内容( 保密学位论文在解密后遵守此规定) 。 签名：钥譬) 羽日期：矽d 6 7 导师签名： 。，l 设曩 日期：矿d t6 7 第一章绪论 1 1 研究背景和意义 随着计算机和通信网络的广泛应用，信息安全越来越受到人们的重视， 而密码技术是保证信息的安全性的关键技术。随着社会的进一步发展，密码 技术将得到更加广泛的应用，这将为密码学的发展提供更加广阔的舞台。 s h a n n o n 在1 9 4 9 年发表了著名论文“保密通信的信息理论”，这是密码 学由一门艺术成为一门科学的标志。到了上个世纪7 0 年代，人类开始进入 信息时代，密码学也进入了快速发展的时期。1 9 7 6 年，d i f f e 和h e l l m a n 发表了“密码学的新方向”，提出了公钥密码体制，使密码学经历了一场变 革。1 9 7 7 年，p d v e s t 、s h a m i r 和a d l e m a u 提出了著名的r s a 算法。同 年，美国公布了由i b m 公司研制的数据加密标准( d e s ) 。从此以后，密码 学不再局限于政治和军事，其商用价值和社会价值得到充分肯定。大量的密 码学论文开始出现，许多有关信息安全的工业标准被公布，进入这一领域的 公司和大学也越来越多 当今的密码体制根据密钥的特点可以分为对称密码体制和非对称密码 体制。在对称密码体制中，加密密钥和解密密钥相同，或者从一个容易得到 另一个。然而在非对称密码体制中，加密密钥和解密密钥不同，从一个很难 得到另一个，加密和解密是可分离的按照具体实现方式对称密码体制又可 分为序列密码和分组密码两种基本方式。在序列密码体制中，加密时将明文 消息字符流逐位地加密成密文消息字符流，解密时则将密文消息字符流逐位 地解密成明文消息字符流。下面用二元时的例子来说明。设 m o ，m 1 ，小是明文比特流， ，k 1 ，觑，是密钥比特流， c 0 ，c l ：，q ，是密文比特流， 那么相应的加解密变换是 g = m 。o 鬼 序列密码加解密实现方式简单，速度快，而且理论相对比较成熟( 一个 重要原因是数学这一工具可以有效地用来研究它) ，因而受到广泛重视。序 第一章绪论 2 列密码算法的安全强度取决于相应的密钥流的质量，因而产生好的密钥流是 序列密码体制的关键问题。s h a ：m o n 证明了如果密钥流序列是真随机的， 那么相应的序列密码体制将是完善保密的。通常有下面几种方式来产生真随 机序列：使用随机噪声、使用计算机时钟、测量键盘反应时间等等。真正随 机的序列是不能重复产生的，即使你用相同的输入对序列发生器操作两次， 你将得到两条完全不同的序列。在一般的应用环境中生成和使用真随机序列 是不现实的，因此人们便退而使用伪随机序列做为密钥流，于是如何产生和 评价伪随机序列便成为序列密码的一个非常重要的问题。 在密码学的其它领域，伪随机序列也被广泛使用，比如著名的d s a 和 e c d s a 数字签名算法这两个数字签名算法分别基于有限域上的离散对数 和椭圆曲线上的离散对数这两个困难问题，在签名过程中需要使用伪随机 数。虽然求解有限域和椭圆曲线上的离散对数都是困难的，但是如果签名过 程中使用的伪随机数不安全，这两个签名算法将很容易被攻击。 伪随机序列在扩频通信中也有重要应用。从上个世纪8 0 年代开始，数字 无线通信开始成为主流，实际的系统有g s m 等。由于无线信道是开放的，通 信环境很容易受到各种干扰，使得信号传输的可靠性降低。另一方面，无线 业务的快速增长要求无线网络具有高度的灵活性，以逶应业务的发展变化。 这些都是传统的无线通信系统无法解决的。扩频通信将待传输的信号用伪随 机序列调制，实现频谱扩展后再传输，很好地解决了上面的i 可题。扩频时使 用的伪随机序列，要求具有低的非平凡自相关和互相关，这保证了同步相关 的输出远远大于非同步相关的输出，大大降低了信号之间的干扰。在扩频通 信中，所有用户可以共用同一频带，简化了系统的设计，提高了灵活性。而 且扩频通信还具有保密、高精度测量等优点。寻找扩频时所需要的伪随机序 列是国际上众多学者长期以来一直进行的工作。另一方面，对于现在已经找 到的那些伪随机序列，分析清楚它们的各种性质也是非常有意义的。虽然人 们已经知道了它们的许多性质，但仍然有更多的秘密不为人知，这需要更加 有力的数学工具。 此外，伪随机序列在编码、计算、控制等领域中也有广泛的应用。 从上面的讨论可以看出，伪随机序列不是一个孤立的问题，它与数学、 通信、计算机等等许多领域都有联系，它既有很强的理论背景，也有很强的 应用背景，因此从事这方面的研究是有意义的。而且这方面的问题将一直被 第一章绪论 3 人们讨论下去。 一条周期序列应该尽可能满足以下几个随机性准则( 我们用f 2 上的序 列做为例子) ： 1 ) 大的周期：任意确定性算法生成的序列都是周期的，要想获得好的随 机性，周期应该尽量大； 2 ) 平衡性：比如在二元序列的一个周期段中，0 与1 的个数相羞要尽 量小。一条不平衡的伪随机序列在实际应用中无疑会带来安全隐患； 3 ) 高的线性复杂度；一条序列的线性复杂度定义为生成该序列的最短 线性反馈移位寄存器的长度。如果用l 表示所考虑序列的线性复杂度，使用 b e r l e k a m p m a s s e y 算法，只需连续的2 l 比特就可以恢复整条序列，因此低 线性复杂度的序列做为密钥流是很不安全的。 4 ) 良好的统计特性：在文献 2 1 中，g o l o m b 认为对于一条伪随机序 列，在每个周期内，它的0 一游程和1 一游程的数目基本相等。 5 ) 二值自相关函数：同样地，在文献 2 1 中，g o l o m b 认为对于一条伪 随机序列，它的周期自相关函数应该是二值的。但是，在一般情况下这个要 求难以达到，人们退而要求伪随机序列的自相关函数应该是低值的。 对于有限序列，人们也提出了许多衡量其随机性的指标。比如：频数、 块内频数、跟随性、重叠子序列、游程变化、游程分布等等。下面我们给出 两个例子。s o l o m o n o v 7 2 】和k o l m o g o r o v 4 1 用能生成这条序列的最短图灵 机程序的长度描述这条序列的随机性。另一种度量有穷序列的随机性的方法 是由l e m p e l 和z i v 提出的所谓“线性复杂度“的方法 4 8 ，规定用产生该 序列的最短线性反馈移位寄存器的长度来度量随机性计算能产生给定序列 的最短非线性反馈移位寄存器是很困难的，但是b e r l e k a m p - m a s s e y 算法能 够有效地计算出产生给定序列的最短线性反馈移位寄存器。因此，这是一个 非常实用的参数。 1 9 9 4 年，k l a p p e r 和g o r e s k y 提出了一种新的产生伪随机序列的移位 寄存器结构一带进位的反馈移位寄存器( f c s r ) ，并提出了二元序列复杂 度的新的度量指标一2 一a d i c 复杂度。在此后的这些年中，k l a p p e r 、c o r e s k y 以及其他许多学者做了很多有关f c s r 的有价值的工作。f c s r 和l f s r 既有许多相似之处，也有许多不同之处。有关f c s r 和2 - a d i c 复杂度的问 题值得我们进一步考虑。 第一章绪论 4 如果一条序列虽然具有大的线性复杂度，但是改变少量元素后会引起线 性复杂度的显著降低，那么这条序列序列用到密码学中也是不安全的。基于 这一想法，d i n g 和s t a m p 独立提出了k - e r r o r 线性复杂度的概念。由于这 一想法的重要性，此后这个领域一直受到广泛关注。直到现在，仍然有许多 问题没有解决。 从上个世纪中叶以来，人们研究最多的是有限域上的序列。到了上个世 纪8 0 年代末，环上的序列开始成为人们关注的热点。由于环的结构比域的 结构更复杂，因此环上的序列不但数目更多，而且密码学性质更好，更难于 攻击。研究环上的序列需要更深入的数学工具，而且人们研究的时间也还很 短，这方面还有许多问题没有搞清楚。 寻找更多更好的扩频序列一直是人们最求的目标。到目前为止，人们已 经找到了许多这样的序列，比如：g o l d 序列、k a s a m i 序列、g m w 序列、 级联g m w 序列、n o 序列等等。x i n g 等学者首次使用函数域来构造伪随 机序列，他们使用函数域的a r t i n s c h r e i e r 扩张构造了一类具有低相关和高 线性复杂度的二元周期序列。由于这一思想提出还不久，是否能构造出更多 的性质好的伪随机序列值得进一步考虑。 1 2 国内外研究现状 首先我们介绍f c s r 和2 - a d i c 复杂度方面的研究进展情况 在文献f 3 3 1 中，k l a p p e r 和g o r e s k y 提出了带进位的反馈移位寄存器 ( f c s r ) 。这种移位寄存器的结构与线性反馈移位寄存器( l f s r ) 的结构很 相似，主要区另h 是引入了记忆，分析f c s r 的数学理论是p - a d i c 数理论。 f c s r 的输出序列我们称为f c s r 序列，当f c s r 序列的周期达到最大时， k l a p p e r 和g o r e s k y 将其称为f 一序列。f 一序列是m - 序列的算术版本。在文献 f 14 中，k l a p p e r 和g o r e s k y 将原始的f c s r 推广到了2 - a d i c 数的分歧扩张 的情况，并分析了在这种情况下输出序列的性质。基于这种新的f c s r ，他 们找到了求和发生器的明显弱点【6 3 。在文献 1 5 】中，k l a p p e r 和g o r e s k y 系统地研究了j 一序列的性质，比如它们的构造和统计性质等等。q i 和x u 利用指数和估计证明了2 一序列在部分周期内0 和1 的分布是渐进均匀的 f 6 0 。k l a p p e r 和g o r e s k y 在文献 1 6 】中讨论了f c s r 序列的综合问题，给 第一章绪论 5 出了有理逼近算法，该算法可以有效地找出生成给定序列的最短f c s r 。 后来，他们在文献f 3 4 中又给出了一种d _ f c s r 的移位寄存器结构，并在文 献3 9 1 中详细分析了s f c s r 序列的分布特点。关于f c s r 序列的线性复 杂度，文献7 0 中给出了它们的下界。 关于f c s r 和d _ f c s r 的具体实现方式，文献 17 中讨论了两种结构： f i b o n a c c i 结构和g a l o i s 结构在文献f 1 8 1 中，k l a p p e r 和g o r e s k y 给出了 周期序列算术相关的概念，并且构造了具有理想算术互相关的大的序列簇。 受到b l a h u t 定理的启发，g o r e s k y 、k l a p p e r 和w a s h i n g t o i 2 在文献 1 9 中研究了二元周期序列的傅立叶变换和它的2 - a d i c 复杂度的关系，给出了 带进位版本的b l a h u t 定理。竹卜序列和它们的采样序列之间的移位等价关 系是容易确定的，但f 一序列却要复杂很多。在文献 2 0 中，作者利用指数 和估计证明了在某些情况下f 一序列和它的采样序列不是移位等价的，而且 作者猜想f 一序列和它所有的采样序列都不是移位等价的。在文献 4 6 中， k l a p p e r 和x u 设计了完备环上的反馈移位寄存器，这是l f s r 和f c s r 的 共同推广。 下面我们介绍序列的b e r r o r 线性复杂度方面的研究进展情况 d i n g 8 和s t a m p 7 1 独立地提出了k - e r r o r 线性复杂度的概念。在文 献8 1 中，作者初步分析了二元序列的k - e r r o r 线性复杂度的一些性质，并且 提出了一个猜想：周期序列的线性复杂度和k - e r r o r 线性复杂度存在制约关 系，它们不可能同时取得很大的值。n i e d e r r e i t e r 在文献 5 9 中构造了许多 同时具有大的线性复杂度和大的k - e r r o r 线性复杂度的周期序列，从而否定 了d i n g 的这个猜想。文献7 1 1 给出了周期为2 “的二元序列的k - e r r o r 线性 复杂度的快速计算方法。k a i d a 、u e h 盯a 和i m a m u r a 在文献 4 5 中将该 算法推广到了b m 上周期为矿的序列的情况。文献 7 】讨论了周期序列在 一个符号替换下的线性复杂度，证明了周期序列的1 - e r r o r 线性复杂度可以 由该序列的极小多项式计算出来。关于一般情况下周期序列k - e r r o r 线性复 杂度，文献 3 2 】给出了它们的非平凡下界 对于某些特殊周期序列，几位日本学者在文献 4 4 】中确定了最小的k 使 得这些序列的k - e r r o r 线性复杂度严格小于它们的线性复杂度。对于1 - e r r o r 线性复杂度这种特殊情况，文献 4 2 给出了3 个陕速算法计算周期为2 ”一1 的二元序列的1 - e r r o r 线性复杂度，并给出了几条设计具有大的1 - e r r o r 线性 第一章绪论 6 复杂度的二元周期序列的准则。在文献5 2 1 中，作者设计了一个快速算法计 算周期序列的k - e r r o r 线性复杂度谱。该算法在文献6 4 1 中被s m a g e a n 改 进。m e i d l 和n i e d e r r e i t e r 在文献 5 6 中研究了周期序列的离散傅立叶变换 和k - e r r o r 线性复杂度之间的关系。 接着我们介绍一下g a l o i s 环上序列的研究进展情况 近1 0 多年来，环上的序列设计和分析一直是国内外的热点。文献f 5 研究了邑z 上本原序列的最高权位序列的最小周期和极小多项式。在文献 6 1 中，作者给出了z 2c 上本原序列的最高权位序列的线性复杂度的下界。 h u a n g 在文献f 3 0 1 中证明了具有重要密码学价值的保墒定理。k u m a r 等 著名学者在文献【3 6 中给出了g a l o i s 环版本的w e l l 指数和估计，这个指 数和估计对于设计和分析g a l o i s 环上序列具有基础性的作用。后来在文献 4 9 中，l i n g 和o z b u d a k 在特征为p 2 的情况下改进了这类指数和。在文献 6 8 中，k u m a r 和他的合作者又给出了一类c a l o i s 上的混合指数和( h y b r i d e x p o n e n t i a ls l i m ) 估计，并利用这样的指数和估计分析了一些g a l o i s 环导出 序列的非周期自相关。受到文献 3 6 】和 6 8 的启发，此后人们又给出了一些 类似的g a l o i s 环上的指数和估计f 6 9 1 。 在文献【1 2 中，f a n 和h a r t 利用文献 3 6 中的指数和估计分析了邑z 上本原序列的最高权位序列的0 、i 分布，改进了文献f 6 1 1 中的结果。r 一样 式分布是有限域上周期序列的重要性质文献【1 0 和 9 讨论了一般g a l o i s 环上的极大长序列的最高权位序列的独立r 一样式分布，证明了它们是渐进 均匀的。在文献 5 0 】中，几位作者研究了磊上的k e r d o c k 码导出的二元序 列，证明它们具有大的线性复杂度、高的非线性度和低的互相关和非平凡自 相关。在文献 7 5 】中，两位作者利用 5 0 】中的方法，分析了最高权位序列的 0 、1 分布，进一步改进了文献1 2 中的结果 最后我们介绍一下函数域在序列设计中的应用情况， 有限域和有限环一直是序列设计的常用方法，x i n g 等学者首次将函数域 引入到序列设计中来，找到了一系列性质良好的序列。在文献 8 4 】中，x i n g 和 l a m 设计了许多具有几乎完美线性复杂度轮廓的序列( a l m o s tp e r f e c t i n e m - c o m p l e x i t yp r o f i l e ) 。在文献( 嘲中，x i n g 和他的合作者又改进了文献 8 4 】 中的方法在文献f 8 1 ，8 5 j 中，x i n g 进一步将这一套方法推广到多序列的 情况。x i n g 等几位学者在文献阳1 中利用函数域的a r t i n s c h r e i e r 扩张构 第一章绪论7 造了一类具有低相关和高线性复杂度的二元周期序列，并且分别就有理函数 域和椭圆函数域两种情况给出了具体例子。 姐3 本文的主要结果和章节安排 在本文中，我们对伪随机序列的设计和分析中的几个问题进行了深入研 究，主要有：带进位的反馈移位寄存器( f c s r ) 和二元序列的2 - a d i c 复杂 度、周期序列的广义离散傅立叶变换和周期序列的1 - e r r o r 线性复杂度、环 邑s 导出序列的独立r 样式分布和部分周期性质、函数域与序列设计等等。 具体地说主要贡献如下： 1 ) 给出了f c s r 序列分布的明显公式，利用这个公式讨论了f c s r 序 列的游程分布等分布性质。利用一般情况下f c s r 序列的指数表示分析了 一个周期内元素之间的关系。讨论了f c s r 序列的通常自相关和算术自相 关。证明了二元f c s r 序列在某些条件下具有大的1 - e r r o r 和2 - e r r o r 线性 复杂度。 2 ) 指出了二元周期序列线性复杂度和2 - a d i c 复杂度的个显著的差别， 讨论了这个差别对序列综合的影响。基于这一观察，给出了更加合理的二元 周期序列非对称2 - a d i e 复杂度的概念。计算了二元周期序列2 - a d i c 复杂度 和非对称2 - a d i c 复杂度的期望值。给出了二元周期序列k - e r r o r2 - a d i c 复杂 度和k e r r o r 非对称2 一a d i c 复杂度的非平凡下界 3 ) 指出i e e et r a n s a c t i o n so l li n f o r m a t i o nt h e o r y 上1 9 9 8 年和2 0 0 4 年的两篇论文的结果本质上是一样的。 4 ) 将周期序列的广义离散傅立叶变换应用到周期序列的1 - e r r o r 线性复 杂度的研究中去，构造了许多具有大的1 - e r r o r 线性复杂度的序列，改进了 n i e d e r r e i t e r 的结果。 5 ) 利用g a l o i s 环上的指数和估计分析了两类邑z 导出序列的独立r 。样 式分布，证明了它们都是渐进均匀的，所得结果改进了以前的公开结果。 6 ) 利用g a l o i s 环上的混合指数和估计和离散傅立叶变换，给出了g a l o i s 环上的部分指数和估计。 7 ) 利用g a l o i s 环上的部分指数和，分析了两类邑z 导出序列的部分周 期分布和部分周期独立r 一样式分布，证明了它们也都是渐进均匀的。 第一章绪论 8 8 ) 利用函数域的k u m m e r 扩张构造了一类新的具有低相关和高线性复 杂度的二元周期序列，并且使用椭圆函数域的理论给出了一些具体例子。在 某些情况下，我们的结果比以前的公开结果更好。 本文的章节安排如下： 第一章( 本章) 介绍了研究伪随机序列的背景和意义，以及国内外的研 究进展。 第二章给出了以后各章会共同用到的一些基本概念，并简单讨论了它们 的性质。 第三章分析f c s r 序列的统计性质和线性复杂度，对二元周期序列的 2 - a d i c 复杂度进行深入研究。 第四章利用周期序列的广义离散傅立叶变换研究周期序列的1 - e r r o r 线 性复杂度，改进了n i e d e r r e i t e r 的结果。 第五章对邑z 导出序列进行了深入分析。 第六章利用函数域的k u m m e r 扩张构造一类新的具有低相关和高线性 复杂度的二元周期序列，并给出了具体例子。 第二章基本概念和性质 为了方便以后四章的工作，我们在这一章中给出它们会共同用到的一些 基本概念，并简要讨论这些概念的一些性质。对于以后各章单独需要的那些 概念和预备知识，我们则在各章中分别给出。 2 1 序列的周期和线性复杂度 日是有q 个元素的有限域，其中g 是某个素数的方幂。本章考虑的序 列都是只上的。 定义2 1 设s = ( 8 0 8 1 8 2 ) 是e 上一条半无限序列，如果存在正整数丁和 非负整数”o 使得s 。+ t = 对任意n n o 都成立，我们称序列s 是终归 周期的，t 称为s 的一个周期。序列s 的所有周期的最小值称为它的最小 周期，记为p ( s ) 。如果他o = 0 ，我们称序列s 是周期的。 如果s = ( 8 0 8 1 8 2 ) 是最小周期为于的周期序列，我们也把它记为 s = ( $ 0 8 1 8 t 1 ) 。 定义2 2s = ( 8 0 8 1 s 2 ) 是日上一条半无限序列，它的线性复杂度定义为满 足如下条件的最小的k ：是一个非负整数，存在d o ，d 1 ，d k 日，d o ，d k 0 使得下面的关系成立 d o s ；+ d i s 1 + + d k s i + k = 0 ，任意i 20 s 的线性复杂度记为l ( s ) 。 需要指出的是，如果s = ( 8 0 s 1 s 。) 是最小周期为t 的周期序列，那么 l ( s ) st 。 线性反馈移位寄存器( l f s r ) 是产生伪随机序列的非常有用的装置之 一，它的一般形式如图2 1 所示( 本图来自文献 3 4 ) 。 记号和条件同定义2 2 ，多项式 y ( x ) = d o x 。+ + d k 一1 x + d k b 陋 称为序列s 的零化多项式。当d o = 1 时，首一的零化多项式称为特征多项 式。此时多项式 9 ( x ) = x k ，( z 一1 ) = 1 + d l x + + d k z 9 第二章基本概念和性质 图2 1 ：线性反馈移位寄存器 1 0 称为序列s 的联结多项式。次数最小的特征多项式称为序列s 的极小多项 式。因此极小多项式的次数就是生成序列s 的最短的线性反馈移位寄存器 的长度，即序列s 的线性复杂度。 1 9 6 7 年，b e r l e k a m p 给出了一个迭代算法来译b c h 码3 。两年后， m a s s e y 将其成功用于线性移位寄存器的综合问题 5 4 。b m 算法可以有效 地计算序列的线性复杂度，它的时间复杂度为o ( n 2 ) ，空间复杂度为o ( n ) 。 因此，如果一条序列的线性复杂度太低，它在密码学上是不安全的。 下面介绍塌上的形式幂级数环玛 m 】。任意日盼 中的元素a ( x ) 可 以表示成未定元。的形式幂级数 。 以扛) = o o + a l z + a 2 x 2 + + a i x 。+ = a ( x 。 i = n 其中a i 称为a ( x ) 的系数。日 m 】中的两个元素a ( x ) = 茎。a l x 。和b ( x ) = 墨0 b i 相等，当且仅当它们的所有系数相等，即a i = b l ，任意i 0 任 意r 吲中的多项式尸( z ) = p o 十p l x + + p n x “可以看成形式幂级数 p ( x ) = p oq - p l x + + 扩+ o x ”1 十o x 计2 + ，于是f g m 成为【旧 的子集。日 m 中的加法和乘法定义为： 在这种规定下， 玛 m 】形成一个整环。如果a ( z ) b ( 。) = 1 ，我们称4 ( z ) 和b ( x ) 互为乘法逆元。 0 蚴 + | | z6 ：i + z0 ：l 石 k啪 。脚 z6 枷 z 0 ! l 第二章基本概念和性质 定理2 1 玛盼】 中的元素a ( x ) = ；o o o a i z 。是乘法可逆的当且仅当n o 0 ，如果它的乘法逆元存在那么必定唯一。 序列的周期与多项式的周期或阶有密切的联系，下面介绍多项式的周期 及其性质。 定义2 3 设f ( x