（应用数学专业论文）二元周期序列k错复杂度的研究.pdf

二元周期序列k 一错复杂度的研究 摘要 伴随信息时代的到来，信息安全日益重要。如何对信息进行加密或解密， 正渐渐成为许多专家和学者的研究热点。因此，作为密码安全强度重要指标的 线性复杂度与k 一错复杂度，越来越受到关注。其核心思想就是研究如何用最少 级数的反馈移位寄存器，生成所需要的密钥序列或生成与所需要的密钥序列非常 近似的序列。对不同取值范围、不同周麓的序列进行研究，发现其线性复杂度 与k 一错线性复杂度对序列密钥的安全性评价，起着至关重要的作用。由于现在 常用的密钥序列，大多是二元序列。因此，研究e 上的二元周期序列的线性复杂 度与k 一错线性复杂度，就显得尤为重要。 为了比较深刻地刻划二元周期序列k 错线性复杂度的特性，本文给出了二元周期 序列k 错线性复杂度期望值比较精确的边界 l 舻l 1 肿i 万( 乳擘+ l ，f 熠一+ 1 ) + d ) 置寿( m , ( t + i , t x 2 - 2 - i ) - u ) 厶t - - 1 二t=l 计算出了这类序列2 错与3 错线性复杂度的期望值蜀、晟，绘出了两类特殊二元周 期序列的k 错复杂度计算结果，并且还计算了部分二元周期序列的k 错线性复杂度跳 点 “斜 t = 酸勘谚_ ) ，及其对应的屯一错线性复杂度l c r 固= 2 拜一2 绷玲+ l ( g f 磊 膨一m ) 关键词：二元周期序列线性复杂度k 一错线性复杂度期望值跳点 r e s e a r c ho nk - 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 cb i n a r y s e q u e n c e s a b s ，i r a c t t h es e c u r i t yo fi n f o r m a t i o nb e c o m e sm o r ea n dm o r ei m p o r t a n ta l o n gw i t h i n f o r m a t i o nt i m e sa r r i v e s 。h o wt oe n c r y p to rd e c i p h e r ，b e c o m e sat o p i co fg e n e r a l w h i c hi sr e s e a r c h e db ym a n ys c h o l a r sa n de x p e r t s t h e r e f o r e ，l i n e a rc o m p l e x i t ya n d k - e r r o rl i n e a rc o m p l e x i t yw h i c ha r ei n d e x so fc r y p t o g r a p hs e c u r i t y r e c e i v em o r e a n dm o r ea t t e n t i o n t h em a i ni d e ao fi ti ss t u d y i n go nh o wt ou s et h el e a s tl e v e l so f f c s rt oo b t a i nt h es e q u e n c ew h i c hw ee x p e c to rt h es e q u e n c es i m i l a rt ow h i c hw e e x p e c t i tc a nb ef o u n dt h a tl i n e a rc o m p l e x i t ya n dk e r r o rl i n e a rc o m p l e x i t ya r ev e r y i m p o r t a n ti nj u d g i n gt h es e c u r i t yo fs e q u e n c ec i p h e r , b yr e s e a r c h i n go ns e q u e n c e so f v a r i o u sf e i l do rv a r i o u sp e r i o d b e c a u s ec r y p t o g r a p ha r eu s u a l l yb i n a r ys e q u e n c e s ，i t i sm o r ei m p o r t a n tt os t u d yo nl i n e a rc o m p l e x i t ya n dk e r r o rl i n e a rc o m p l e x i t yo f p e r i o d i cb i n a r ys e q u e n c e s 。 i no r d e rt od e s c r i b ek 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 cb i n a r ys e q u e n c e s e x a c t l y , w eg i v eam o r ee x a c tb o u n do ne x p e c t e dv a l u eo fk e r r o rl i n e a rc o m p l e x i t y o fp e r i o d i cb i n a r ys e q u e n c e s ( 乏m ( t + l , t x t 一+ 1 ) + d ) 毛j ( 必够+ l ，f r z 1 ) 一，) ，卜l l 井 t = l二， l c a l c u l a t et h ee x p e c t e dv a l u e so f2 - e r r o ra n d3 - 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 c b i n a r ys e q u e n c e s ( 岛、弓) a n dk - e r r o rl i n e a rc o m p l e x i t yo fd i s t i n c ts e q u e n c e s ，a n d w ea l s oc a l c u l a t et h ej u m p p o i n t so fk - e r r o rl i n e a rc o m p l e x i t yo fs o m es p e c i a l p e r i o d i cb i n a r ys e q u e n c e sw h i c ha f ee q u a lt ok i - 唬墨+ 炉) ，a n dk l f - e r r o rl i n e a r p c o m p l e x i t y 三q 固= 2 露一州玲十l ( o i m m ) k e y w o r d s p e r i o d i cb i n a r ys e q u e n c e 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 r n p l e x i t y ：e x p e c t e dv a l u e ：j u m p p o i n t 独创性声明 黜签竹湖游纠p 学位论文版权使用授权书 本学位论文作者完全了解盒照兰城太堂有关保留、使用学位论文的规定，有权保留并向 重家有关部门或梗构送交论文的复翔件黎l 磁盘，允谗论文被查阕或借阕。本人授敷金羹王些塞 堂一可以将学位论文的全部或部分论文内容编入有关数据摩进行检索，可以采用影印、缩印或摆 描等复制手段保存、汇编学位论文。 ( 保密的学位论文在解密后适用本授权书) 名韵嘶 黼呦痧和中 学位论文豫者毕娆后去淘：f 导师签 签字目 电话： 邮编： 日 致谢 这篇论文献给所有关心我和我关心的人l 我首先褥感谢我的导师朱士信教授，德高望重的他不仅教授我知识，更教 会我对学术的严谨，他是到目前为止对我人生发展影响最深的老师；同时我还 要感谢给我上过课的其他老师，他们也对我读研期闻的学习给予了极大帮助。 各位老师的优异表现，不仅集中体现了前辈知识分子的风采，更为我们这些质 辈树立了努力奋斗的榜样。 其次我要感谢我的父母，他们是始终关心我丽又不求回报的入，今天我能 够顺利完成学业，与他们在背后的默默支持和巨大牺牲是分不开的。还有在中 学和工大结识的许多好朋友，他们在平时也给予了我很大帮助，助我克服一个 又一个困难，我理所当然地应该感谢他们。 还有我的同门师兄弟、师姐妹们，他们对我的帮助，不只表现在墨常生活 中，还更多地体现在学习上。正是因为你们的存在，让我觉得每一天都比较充 实。你们更应受到感谢! 感谢母校合肥工业大学，感谢数学系，感谢这里的老师，感谢这里的同学， 谢谢! 作者：姜光峰 2 0 0 8 年4 月董日 第一章绪论 近年来，随着社会信息他程度的增强，信息安全越来越受到关注。有关信 息安全、密码安全强度的一些概念和指标( 譬如线性复杂度与k - 错复杂度) 豳 益成为研究韵热点。 1 1k 一错复杂度研究的背景和意义 1 1 1k 错复杂度研究的背景和相关基本知识 作为密码学重要分支的序列密码，不仅在现代密码学中占据着不可或缺的 地位，蔼且在菲密码领域中，( 譬如编码、逶信) 等方面也发挥了重要作用。传 统的序列密码是在线性反馈移位寄存器产生的序列基础上加以改进德到的( 例 如钟控和线性过滤，这样得到的序列其安全性与钟控装置和非线性逻辑函数有 密切关系) 。既然是用作密码，其安全性就必然受到入们的关注，如何衡量所产 生密钥序列的安全强度历来是密码设计者和密码分析者所重视的问题。随着对 序列分析和攻击能力的提高，人们随之提出相应的各种度量密钥序列安全强度 的指标。e 。r b e r l e k a m p 和j a m e sl m a s s e y 在1 9 6 9 年提出了著名的b - m 算法， 这使得线性复杂度成为了衡量密钥序列安全强度的一个重要标准i l l 。到了上世 纪9 0 年代，s t a m p 和m a r t i n1 2 l 提出了k 一错线性复杂度的概念，使得对序列密钥 安全性的研究更进了一步。 两对序列k 一错复杂度的研究是从肘序列的线性复杂度开始豹，两者具有紧 密联系。要准确理解k 一错线性复杂度，需要先搞清楚什么是序列的线性复杂度 及其相关性质。在介绍线性复杂度与k 一错复杂度这两个概念之前，让我们先来 看看序列的伪隧机性。 1 1 1 1伪随机性 人们对序列的研究是基于对数据的加密，即序列主要用于密码方向。若是 用一条绝对随机的序列，对需要加密的数据进行加密，那自然是相当安全的。 但是这样一条绝对随机的序列好不好找呢? 答案当然是否定的。那么，人们就 想到了去找一些近似随机的序列，来代替绝对随机序列对数据加密，以达到尽 可能理想的结果。从而伪随机性的概念得以提出。 当掷一枚均匀的硬币时，若出现正面记一个l ，若出现反面就记一个o 。如 果掷的次数足够多时，譬如掷n 次后，我们记下一个随机的二元序列口茹 ( a 。a l 口2 口。- 1 ) ，它具备三条随机特性： 序列中l 的个数和o 的个数接近相等。 序列的自相关函数c a ( f ) = 口j a 。+ ，当t = o 时最高，而当t 喾o 时迅速下降 i 石 把连在一起的l ( 或o ) 称为游程，其中l ( 或o ) 的个数称为此游程的 长度。露中长为l 的游程约占游程总数的1 2 ，长为2 的游程约占游程总数的 l 2 ：，长为3 的游程约占游程总数的1 2 ，。在同样长度的所有游程中，l 游程和o 游程大致各占一半。 这三条特性是真正的二元随机序列特性。惹我们逶常寻找的序列是表面上 满足上述条件却按定规律形成的序列，故称这样的序列为伪随机序列，他们 所具备的性质称为伪随机性。 伪随机序列常被用来在保密遥信中起加密作用和在自动控制系统的识别中 模拟随机噪声。另外，在雷达、导航和密码学中也有重要应用。实际上，对予 周期序列而言，一条伪随机性好的序列应具备理想的相关性、长的周期和大的 线性复杂度。 1 1 1 2 线性复杂度 线性复杂度是序列密码中一个极为重要的概念，是刻划序列伪随机性和不 可预测性的一个重要参数1 3 , 4 1 定义1 1 若s = ( s o ，墨，s 州，& ，) 是周期为的序列，其线性 复杂度l c ( s ) 定义为能生成该序列的最短线性反馈移位寄存器的长度。 设s ( x ) 2 s 0 + s l x + s 2 x 2 + + s n x 撵扣2 s j x ，s n ( 弗= 岛+ 毛x + + 葶- l x 州 煲l s ( 矽= s ( 砖( 1 + x x 2 + ” = s e 砖( 1 一x ) = ( s ( x ) g o d ( s ( x ) ，( 1 一x ) ) ) ( ( 1 一x ) g e d ( s n ( 工) ，( 1 一x ) ) ) = g ( x ) 工( x ) 这里z 砖= ( 1 一x ) g c d ( s n ( 对，( 1 一x ) ) ， g ( x ) = s ( x ) g c d ( s ( x ) ，( 1 一x ) ) 线性复杂度的定义最初是从二元序列开始的，譬如用钟控手段得到的具有 高线性复杂度特点的钟控序列，1 9 9 3 年壶美国学者d c o p p e r s m i t h 。h k r a w c z 和ym a n s o u r 蹰人提出的收缩序列，1 9 9 4 年瑞士学者w i l li m e i e r 和o t h m a r s t a f f e l b a c h 在收缩序列发生器的基础上提出的自收缩( s e l f s h r i n k i n g ) 序列发 生器模型，均是建立在二元序列的基础上。但上个世纪八十年代后，人们在对 二元伪随机序列研究的同时，也开始对多元伪随机序列进行研究，并且取褥7 很好的成果：如p 2 g m w 序列1 4 - 7 j ( p 为素数) ，g f ( p 朋) 上的m 序列i 引。 l 。1 1 3 k 一错线性复杂度 定义1 2 若s = ( s o ，s l ，s ，& ，) 是周期为的序列，其k 一 错线性复杂度l c , ( s ) 定义为在改变k 个或更少鬣后得到的最小线性复杂度( o 2 i n 1 ) ，郎 三g ( s ) 嚣m i n l c ( s + 曼) k 瓣 其中，曼= ( e o ，e l ，p 州，e o ，) ，缝) 表示序列曼的一个周期中。l 的个数( 即e 每个周期的汉明重量) 。 1 1 2 研究k 错复杂度的意义 序列的线性复杂度衡量了序列的安全性，即复杂度越大，安全性越强。但 是，线性复杂度大的序列其安全强度未必就强。例如周期为的二元序列s 篇 ( 0 ，0 ，0 ，l ，o ，o ，0 ，l ，) ，其线性复杂度c ( s ) = n 。但是，若把该序列 每周期最后一个比特“l 改为。0 ，这条密钥序列就立即变成零序列。可见， 这样的密钥序列是极其不稳定的。这说明安全性强的序列必定是线性复杂度大 的序列，但线性复杂度大的序列，其安全性未必就好。实际上，我们可以轻易 列举出很多具有大线性复杂度的相当理想的序列，但是只需改变少数几个比特， 就可以使其线性复杂度急剧下降。这样以来，密码破译者就可以用一条线性复 杂度低 | 譬多的序列去逼近原序列，铁丽达到破译密钥的尽的。因此，k 一错线性 复杂度就应现实需求被提了出来1 2 1 。 l 。2 二元周期序列k 一错复杂度的研究现状 l 。2 1国终对线性复杂度及k 错线性复杂度的研究 自上世纪七十年代以来，对序列密码的研究越来越热门。国外学者 n i e d e r r e i t e r 对序列复杂度的研究是比较早开始的，对于特定长度的，特定周 期的序列的线性复杂度均有禳多的估计结采，尤其是给出了周期序列的线性复 杂度的分布，线性复杂度与k 错线性复杂度之闻的关系。m e i d l 对于随机周期 序列的k 错线性复杂度的统计性质，包括期望的界有了很多的研究结果g a m e s 和c h s q 在研究周期序列线性复杂度，k 错线性复杂度快速算法方面比较成功( 对 于n = 2 ”的周期序列给出了一种快速算法，大大优于原先酶b e r 王e k a 臻p 一酝s s e y 算法) 。后来m s t a m pa n dc f m a r t i n 提出了n = 2 ”的周期序列k 错线性复杂度 的算法，紧接着便引发了一系列的研究，通过探询内在的代数结构，找到递归 算法的依据，现在对于n = 2 蓐，n = p 抖，& ：2 p 撵的周期序列都有了类似的快速计算 的方法此外，还有一些其他的工作，比如k k u r o s a w a ，f s a t o ，t 。s a k a t a ，和 w k is h i m o t o 的工作，得到了在特定周期n = 2 井，p ”的周期序列的线性复杂度发 生最小跳交的错误值；a l a n 。g b l a u d e r a n d ，k e n n e t h g p a t e r s o n 的工作，给 出种高效算法得n - 元周期序列线性复杂度的错误谱并用于r e e d - m u l l e r 码 的译码中。 3 1 2 2黧内对线性复杂度及鏊错线性复杂度的研究 近十年来，国内对序列密码的研究也比较热门。国内的学者如丁存生，肖 国镇，魏仕民，戴宗铎开展了这方面的研究工作，丁存生的主要工作包括对特 定餍期序列的模式分布的研究，涛国镇老师的王作主要是针对特定周期序列如 n = 2 p “周期的周期序列的线性复杂度快速算法的研究，魏仕民的工作包括对特 定周期的周期序列的k 错线性复杂度快速算法的研究；戴宗铎老师的工作包括 对周期序列的扰动( 如添加，删除) 后序列线性复杂度的变化情况，以及般情 形下的随机周期序列的线性复杂度的期望，方差。 1 3 关于复杂度的基本知识 1 3 1二元周期序列k 错线性复杂度的部分研究成采 定义王。3 1 9 l 若s = ( s o ，最，s _ l ，& ，) 是周期为的序列，则 称 集合 ( k ，l c 。岱) ) io k n ) 为其k 一错线性复杂度谱( e r r o rl i n e a rc o m p l e x i t ys p e c t r u m ) 若t = 甄( s ) ，s 是周期为的二元周期序列，则易证 l c ( s ) = l c o ( s ) l c l ( s ) l c 7 ( s ) 序列的k 一错线性复杂度谱描述了序列的线性复杂度随改交比特的增多面下 降的程度反映了序列线性复杂度的稳定性确定密钥序列k 一错线性复杂度谱中 的各个点，对于密码设计者和密码分析者都具有重要的意义。 定义王。4 l 撙l 若s = ( s o ，墨，s m ，氐，) 是周期为的序列，其k 一 错线性复杂度为q ( s ) ，记e r r i ( s ) = m i n kl o ( s ) ，记e r r 2 ( s ) = m i n kl 三q s 是周期为的序列，其k 一 错线性复杂度为上q ( s ) ，记e r r a ( s ) - m i n kl c k ( s ) 是s 的一个周期，以下s 辟意思同此。将s 撵) 分作左右两部分，分别记作 l ( s 秘) 2 ( 岛，墨，s 2 山)r ( s 枷) = 心2 川，s 2 + i ，一i ) 若l ( s 荐) = 露( s ) ，刹e ( s ) = c ( s “) = c ( 以分“) ) ；否则， 三( s ”) + r ( s ”) = b 疗) ( “+ 一为模2 加法) ，c ( s ) = 2 - 1 + c ( 艿 ( 一) ) 。可见， c ( s ) 仅在( i s 行) a ( s = g ( s ) 。 3 证明：易知符合题意的蹋期亭列s 的每个周期s 渤含有奇数个搿圭挣，即汉瞬重 量h ( s ( 一) ) 为奇数。任意改变其中2 m 位，h ( s ( ”) ) 仍为奇数，故改变k + l 位 得到的新序列的线性复杂度均为2 嚣。因此，g + l ( s ) = m i n g 博) ，2 ” = g ( s ) 。 q 。e d 引理2 。2 对周期为2 揩的序列s ，若线性复杂度为l = 2 一一2 糠( o 主l i2 i 6 n 一1 ，ll 0 9 2 k “| b n ) ，则s 的k 一错线性复杂度o ：l 证明：由文献 2 0 ! 亳j l ，使g ( s ) l 的最小k 为2 b 妒一二( 用h 6 ( c ) 记整数e 的二进制表示的汉明重量) ，故l = 2 ”一 2 口( o 主l i2 时，2 b a - l ) = 2 s 因此，当k 26 - 1 ( 即b f - l o g ! 州1 ) 时，c k ( s ) = l 。 定理2 1 对周期为2 一、线性复杂度为l 的序列s ，若2 - 2 “1 l = 2 片一2 4 弘哇 2 ”- 2 ( f l o g 譬州1 b t + l ，o il i2 量n 一1 ，l m o g g 枷j t n 一1 ) ， 则 s 的k 一错线性复杂度q ( s ) = l 且2 - 2 一z 2 州l 2 撑一27 一z 2 若k 一错线性复杂度为g ( s ) ，则g ( s ) = l ( 2 行一2 1 l = 2 坩一艺2 口 2 打一2 。， f l o g + b t + l ，o il i2 i 矗n 一1 ，b o g + 1 j t n 1 ) 的s 数 量为2 “1 ，而2 ”一2h 1 q ( s ) 2 ”一2 ( 11 0 9 笋“l b t + l ，o il i2 气 蕲l ，嗡枷t 州) 的s 总数为芝。- b + lf - b + 2 t - i 2 ( 州一篡护h 叫i o 以lh 卸喳卅i + 1 k i 。k 2 “ 证明：由引理2 2 易得q ( s ) = l 。而由2 - 2 + 1 l = 2 ”一2 口2 ”一2 。得 2 。 2 4 2 。显然，i | 主2 = l ，l 亦为s 线性复杂度，故对予卜错线性复杂度为0 的s 数量为2 “。 k 。 由褥2 一一2 “1 ：2 口( m b f ，o 毛 毛 七 得使h ( s ) = h 的r 满足：f 胛一1 。又因s 周期为z ，放h 2 一l ，f l o g r 。 由于h ( s 国) 吨，欲求s 的k 一错线性复杂度，需通过改变原序列中相应的 h 位，使s 1 的左右两部分l ( s 件1 ) 、r ( s 1 ) 相等。设改变后的s ( f + 1 记为s ( ) ， 即应使l ( s h ) = r ( s “1 ) 且其复杂度应尽可能小。由( p 2 ) ( 见 1 8 ) 得h ( s ( “1 ) 为 奇数。因丽三岱h 1 ) 、r ( s 淤) 的汉明重量必然一奇一偶。不妨设三( s p q ) 汉明重 量为奇，r ( s ( h 1 ) 汉明重量为偶。欲使三岱h ) = 足( s h 1 ) 且其复杂度尽可能小。 则必需在l ( s h 1 ) 、r ( s h 1 ) 中分别改变，、位( f 为奇数，j 为偶数且f + 歹= h ， h 是不大于k 的最大奇数) 。 从丽得到c ( 三( u 汾= c ( 足岱1 势= c ( 1 c 2 - 1 ) ，故s 的k 一罐线性复杂 度可以表示为l t , c = 2 川+ 2 脚+ + 2 + c = 2 ”一2 ，+ 1 + c ( f 1 0 9 字枷 t n l ，1 c 2 - i ) 由上面讨论得l i h ，o 歹h - i 嘻 c 可记作c = 2 一2 4 ( 圭b t ，o 焉 乏 。，。 而对于周期为2 ，线性复杂度为c 的序列s ，使g ( s ) 2 时，k 一错线性复杂度g ( s ) 满g z2 露- 2 埘 g ( 研 2 忆2 ( o f 珂一1 ) 的周期为2 ”的序列s 的数量 m a t + l t ) ：弋j = o r 2 j ) 2 2 ”一掣一骞( 了1 ) 2 f 一2 ，“且蓦磊毛e ，+ t ，f ，：2 一妻( 了) 由定理2 2 得l o g 均1 f 露一1 ，m b ，磊为不大予膏的最大奇数， 对于 线性复杂度为2 一的序列s ，k 一错线性复杂度q 睾) = l i , c = ? _ 岁c ( i _ c s z 1 ) ， g ( s ) 取值在( 2 ”一2 川，2 一一2 ) 内且具有2 - ，记一：z 一基( o 丢 毛 12 妒互 ( 2 5 ) 拙1 t l f 嘲1 ) 1 由定理2 - 1 得ll o g 毒：1 l r 行一l ，l o g 譬+ 1 6 ，+ l 时，对于线性复杂度为五 的序列s ，k 一错线性复杂度e ( s ) = 三，9 2 - 2 一矽l = 2 一一勋z 之恕 纠馈柚! -。一_0 1 2 ( o 毛 之 毛，l 1 ) 。c ( 研取值在( 2 n 一2 m ，2 一一2 ，) 内，且具有z 名一b 畸 形式的s 数量，记为鹄) ，刘 鹄= 。吖毒州1 蔷岛；。”f 扣。乏：+ 。2 每 川r - 6 + i i - 6 + 2川( 妒乒芝2 口卜i 再记s 2 ( t ) = n 2 ( t ) ( 2 ”- 2 7 - e 2 卜。) ，s d t ) = n 2 q ) ( 2 一- 2 - 5 2 ) 则。芝卜蚝+ l ，f ? 一2 ，+ t + 1 ) + 。n - i 蠛馓1 9 f + 坳一鹅锄秽一+ 1 ) ) 坤1 - 1 哺州，j - - e m k ( t + l ，0 ( 2 ”- 2 “1 + 1 ) + ( 岛( ，) 一札( r ) ( 2 摇- 2 m + 1 ) ) 2 2 置 ( 2 6 ) 扣1 ，吨随 卜蔓巾磁8 “碳2 捧一2 ，一1 ) + n - i 妈9 ) + ( 坂o “d 一鹄) 2 荐一z l ” 扣1 ，七o g p = m k ( t + l ，) ( 2 ”- 2 - 1 ) 一。( m ( f ) ( 2 ”- 2 - 1 ) - s 2 ( t ) ) 2 2 晟 ( 2 7 ) 扭1 ，吨蟛辩j 由予定理2 。2 、定理2 1 讨论的痔列分别是每个周期中含有奇数个搿1 努和偶数 个“l 的完全不同的两类序列。故上丽讨论的l ( f ) 个序列与m o ) 个序列完全 不同。考虑到f l o g 哪 一l 1 0 9 笋们j = 0 或1 ，结合( 2 4 ) ( 2 5 ) ( 2 6 ) ( 2 7 ) 得 m k ( t + l ，f ) ( 2 嚣- 2 h + 1 ) + d 2 2 ”巨m k ( t + l ，f ) ( 2 拜- 2 - 1 ) - u d ：“墨 ) 一m o ) ( 2 一- 2 h 1 + 1 ”+ ( 墨o ) 一2 0 ) ( 2 一- 2 + 1 ) ) ) ，号谚玲l 渺_ 硝 弘二蕃l 彬- 2 - 1 ) - 删+ 赢州删之曲书( ，) ) 州懈4 瞒鳓 d 鞠啦ld i 皤 定理得证。 2 。3结论 显然，1 0 ) ( 2 ”- 2 “1 + 1 ) 一2 越。7 。 鬲 设周期为2 4 且线性复杂度为2 ”的序列的集合记兔墨，k 一错线性复杂度期望 值记为e k l ：。笋。周期为2 髓且线性复杂度不为2 “的序列的集合记为是，k 一锩线性 复杂度期望值记为幺脚扩。易知，s 中序列的每个周期中含有奇数个“l 一，且 s i 基数为i 墨i = 2 2 。，因而s ：基数为ls ：l - 2 2 。一。其中，s 2 可分解为砖、瓯两部 分， 即s 2 = s 3u s 4 ( s 3 = s is 毫s 2 ， c ( s ) 2 “一2 。( i = o l ，”n 一1 ) ， 墨= s | s 冀，e ( s ) = 2 撵一2 。( i = o ，l ，”，n - 1 ) ) 。 命题3 1 ：对于给定奇数k ，周期为2 坩的= 元序歹i j 的k 一错线性复杂度的期望值 为岛= ( e k i 脚+ 乓h 删) 2 ，( k + 1 ) 一错线性复杂度的期望值为e “篇 ( 气脚+ 粉2 。) 2 。 证明：对于周期为2 拜的二元序列s 及奇数k 。 着se s l ，则g + l ( s ) = q ( s ) 。故互堋肛2 置l 拈r ( 3 1 ) 若s 岛，则g ( s ) 2q 1 ( s ) 故l 跏妒2t 纠l # f ( 3 2 ) 由l 墨l - ls 2 | - 2 2 。一1 得2 2 。邑= 2 2 。卅e k t l = 2 + 2 2 ”1 乓胁2 即最= ( 包酗r + t | 喾) 2 将( 3 2 ) 代入褥墨2 ( 毛+ 墨i 1 胁2 - ) 2 ，间理e k + 1 2 ( 气上。2 - + 乓川胁铲) 2 q e d 因此，置一e i 盼2 。+ 脚) 2 ，玛。( 毛瑚。+ 气事2 1 ) 2 丽在【1 8 】中，e i 肛矿嚣 n - i 2 再- 4 + 2 _ 2 。瓣一2 2 。h 已给出可见，欲求磊、毛，只需求出e 2 1 删，毛科 r = 2 弓l 理3 1 ：s 是周期为2 群的二元序列，s ”为其一个周期，c ( s 择) 为其线性复杂 度。s 7 ：= 鬈+ l + 2 一一l 匕( s ) = 譬+ l 鬈+ 2 鬈一l ( s ) ( 0 r 论一王，￥为 王8 】 中映射) ( 1 ) 若h ( s 一) = 0 ，( s 7 ) 0 ( 1 r n - i ) s ”变动两位最终s ，s 7 ：= k l 。& l 壤妒) 则c 裕疗) = c ( s 4 ) 铮 s 7 = s 7 ) ( 2 ) 羲日( s ( ) = o 且日( s ”) o 或i f ( s t ) ) = 0 ，则c ( s 一) c 岱”) 证明：( 1 ) “仁若s ，= s n ，则显然有c ( s ”) 黧c ( s ( ”) 。 “假设s s ”，则由题意褥s 7 与s 耜差两位，鞠胃( s + s 7 ) = 2 。 考察s j + s ，其左右两部分分别记为l ( s ( 7 + s ( 7 ) 、r ( s ( 7 + s 7 ) 。羞 l ( s 7 + s 一) 十r ( s 7 + s 7 ) 0 ，则显然h ( s ，- 1 ) 0 ，c ( s 一) c ( s ”) 。若 l ( s 7 s 7 ) + r ( s + s 7 ) = 0 ， 则h ( s ，- ) = o ，l ( s ) ( = g ( s 7 ) ) 与五( s 7 ) ( = r ( s ( ) ) 相差一位，故线性复杂度c ( 三( s ( 7 ) ) c ( ( s ( ) ) 。 而c ( s ”) = 2 一一+ 2 - 2 + + 2 ，+ 1 + 2 7 + c ( ( s ( ) ) ， c ( s ”) = 2 ”1 + 2 拜一2 + ”+ 2 炜+ 2 7 + c ( 五( s 7 ) ) ，故c ( s ( 释) c ( s 8 ) 。 因此，c ( s 一) = c ( s ”) 时，s ( 7 = s 。 ( 2 ) h ( s 舻1 ) = 0 且月( s ( 坩) 0 时，l ( s ”) = r ( s ”) 。易得在s ”中任意变动 两位得s ，剥l ( s 8 ) r ( s 。) 或l ( s ) = r ( s “) 但与( s 栉) = 震( s 摊) 汉明重量 奇偶性不同。因而e ( s 铆) c ( s 枷) ) 。 而( s ”) = 0 时，显然有c ( s ”) c ( ”) 。 推论3 重：s 是周期为2 疗的二元序列，s ”为其一个周期，s 7 与弓i 理3 1 中同 义。若( s ( 1 ) = o ，目( s ( 7 ) 喾0 ( 1 r n 1 ) ，则在s ( ”中取两位作变动，使s 线 性复杂度保持不变的取法有【2 7i2 n - 7 1 种。 k1 天2 ， 证明：由引理3 1 得，欲使s 线性复杂度保持不变，需保证使s