（应用数学专业论文）域f2上pn—周期序列的差错线性复杂度谱.pdf

域e 上p “一周期序列的差错线性复杂度谱 摘要 序列密码是密码学最主要的和最重要的组成部分之一。在序列密码中，线 性复杂度和k 一错线性复杂度是衡量序列的密码强度的重要工具，而相关的一些 著名的算法也相继被提出，如b e r l e k a m p m a s s e y 算法，g a m e s c h a n 算法， s t a m p m a r t i n 算法等等。 l a u d e r 和p a t t e r s o n 首先对于域只上的2 。一周期序列定义了差错线性复杂 度谱，并且给出了确定域只上2 。一周期序列差错线性复杂度谱的 l a u d e r p a r t v r s o n 算法。差错线性复杂度谱作为一种复杂度的度量工具，可以很 好的展示出周期序列的线性复杂度随着差错量的不断增加而变化的情况，有重 要的研究价值，对于域上的各种周期序列的差错线性复杂度谱进行分析并给出 能够确定差错线性复杂度谱的算法是很有意义的 在本文中。对于域e 上周期为p 6 的周期序列，其中2 是模p 2 的一个本原 根，在已有的线性复杂度算法和七一错线性复杂度算法的基础上，对域e 上p 4 一 周期序列的差错线性复杂度谱进行了分析，并且提出了确定域e 上p 。一周期序 列的差错线性复杂度谱的一个快速算法。另外，本文还探讨了在保持高线性复 杂度和七一错线性复杂度的同时，如何选取合适的差错序列使密钥序列中0 与1 数量更加平衡，并且给出了相应的算法。 关键词：序列密码p 。一周期序列线性复杂度七一错线性复杂度差错线性复 杂度谱算法差错序列 t h ee r r o rl i n e a rc o m p l e x i t ys p e c t r ao fb i n a r y s e q u e n c e s w i t hp e r i o d p ” a b s t r a c t s t r e a mc i p h e ri sa nm a i na n di m p o r t a n tp a r to fc r y p t o g r a p h y i ns t r e a mc i p h e r s ， t h el i n e a rc o m p l e x i t ya n dt h ek e r r o rl i n e a rc o m p l e x i t yp l a ya ni m p o r t a n tr o l ef o r j u d g i n gt h ec r y p t o g r a p h i cs t r e n g t ho fas e q u e n c e ，a n ds o m ec o r r e l a t i v ea l g o r i t h m s a r ep r o p o s e di ns u c c e s s i o n ，s u c h 豁b e r l e k a m p m a s s e ya l g o r i t h m ，g a m e s - c h a n a l g o r i t h m ，s t a m p m a r t i na l g o r i t h m ，a n ds oo n f o rb i n a r ys e q u e n c e sw i t hp e r i o d 2 。，l a n d e ra n dp a r t e r s o nf i r s ti n t r o d u c e dt h e c o n c e p to ft h ee 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 ，a n dt h e yp r o p o s e d t h e l a u d e r - p a r t e r s o na l g o r i t h mf o rd e t e r m i n i n gt h ee r r o rl i n e a rc o m p l e x i t ys p e c t r ao f b i n a r ys e q u e n c e sw i t hp e r i o d2 。a s ac o m p l e x i t ym e a s u r e ，t h ee r r o rl i n e a r c o m p l e x i t ys p e c t r u mc a nr e v e a lh o wt h el i n e a rc o m p l e x i t yo fas e q u e n c ev a r i e sa s a ni n c r e a s i n gn u m b e ro ft h eb i t so ft h es e q u e n c ea r ec h a n g e d i ti si n t e r e s tt o i n v e s t i g a t et h ed i s t r i b u t i o no ft h ee r r o rl i n e a rc o m p l e x i t ys p e c t r af o rr a n d o m s e q u e n c e so faq i v e np e r i o d ，a n di t i si n t e r e s tt of i n da ne f f i c i e n ta l g o r i t h mf o r d e t e r m i n i n gt h et h ee r r o rl i n e a rc o m p l e x i t ys p e c t r ao ft h es e q u e n c e i n t h i sp a p e r ，f o rb i n a r ys e q u e n c e sw i t hp e r i o d p 。，w h e r e2i s ap r i m i t i v e r o o t ( m o dp 2 ) ，t h ee r r o rl i n e a rc o m p l e x i t ys p e c t r u mi sa n a l y s e do nt h eb a s eo ft h e k n o w na l g o r i t h m so ft h el i n e a rc o m p l e x i t ya n dt h ek - e r r o rl i n e a rc o m p l e x i t y , a n d af a s ta l g o r i t h mf o rd e t e r m i n i n gt h ee r r o rl i n e a rc o m p l e x i t ys p e c t r u mi sp r e s e n t e d i na d d i t i o n ，h o wt oc h o o s ea l le r r o rs e q u e n c et ob a l a n c et h en u m b e ro f0a n d1o fa s e q u e n c ew i t ht h et h el i n e a rc o m p l e x i t ya n dt h e k - - e r r o rl i n e a rc o m p l e x i t yr e m a i n h i g hi sd i s c u s s e d ，a n dc o r r e l a t i v ea l g o r i t h m sa r ep r e s e n t e da l s o k e y w o r d s ：s t r e a mc i p h e r ；p 。一p e r i o d i cs 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 r l i n e a rc o m p l e x i t y ；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 ；a l g o r i t h m ；e r r o r s e q u e n c e ； 图2 1 图2 2 图2 3 图2 - 4 插图清单 s 的差错线性复杂度谱1 4 s 的临界差错线性复杂度谱1 5 c e l c s ( s ，0 ，2 7 ，0 ) 的递归过程1 7 j 的差错线性复杂度谱1 9 独创性声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工作及取得的研究成果。据我所 知，除了文中特别加以标志和致谢的地方外，论文中不包含其他人已经发表或撰写过的研究成果， 也不包含为获得金起王些太堂 或其他教育机构的学位或证书而使用过的材料与我一同工作 的同志对本研究所做的任何贡献均已在论文中作了明确的说明并表示谢意 学位论文作者签字：商是泰签字日期：口7 年磊日 学位论文版权使用授权书 本学位论文作者完全了解金a i 王些太堂有关保留、使用学位论文的规定，有权保留并向 国家有关部门或机构送交论文的复印件和磁盘。允许论文被查阅或借阅本人授权金殴王些太 雯可以将学位论文的全部或部分论文内容编入有关数据库进行检索，可以采用影印、缩印或扫 描等复制手段保存、汇编学位论文 ( 保密的学位论文在解密后适用本授权书) 黝一名：声瓤黜别吾 签字日期：0 7 年多月日 学位论文作者毕业后去向： 工作单位： 通讯地址： 撕期：疟钿厂日 i ? 电话： 邮编： 致谢 首先，我要感谢我的导师朱士信教授，在这硕士阶段的三年时间里，朱老师 严格的要求和悉心的指导，让我受益匪浅。朱老师严谨的治学态度、深厚的学 术水平、精湛的教学方式都给我留下了深刻的印象。并将成为我在以后的工作 上的榜样在本文的开始，作者谨向老师致以最诚挚的敬意和由衷的感谢! 同时，感谢我的同学们! 希望在以后的学术道路上，我们能够一如既往， 互相鼓励，互相促进，共同进步 最后，特别要感谢合肥工业大学，在这里，我度过了本科和硕士两个阶段， 七年的时问。我对合肥工业大学有深厚的感情，祝愿合肥工业大学发展的越来 越好! 作者：唐淼 2 0 0 7 年5 月 第一章绪论 1 1 引言 密码技术最初起源并应用于军事或外交通信，只是出于实际的需要进行一 些设计和分析，用来保护机密信息，没有推理证明完善其理论基础。直到1 9 4 9 年香农( s h a n n o n ) 发表了论文保密系统的理论基础，这为单钥密码系统建立 了理论基础，从此，密码成为一门科学但从1 9 4 9 年到1 9 7 5 年这段时间，密 码学理论研究工作进展不大，直到七十年代中期密码学界出现了两件重要的事： 一件事是1 9 7 6 年d i f f e 和h e l l m a n 发表了论文密码学的新方向，这揭开了 密码学历史上新的一页，开创了一种崭新的密码体制一一公钥密码体制；另一 件事是美国国家标准局经过公开征集、遴选并于1 9 7 7 年正式公布实施的美国数 据加密标准( d e s ) 。这两个事件标志着现代密码学的诞生。当今世界已步入信 息时代，每天都有大量的信息通过公共通信设施和计算机网络等途径进行传播 或交换，其中如何防止敏感信息的泄漏或保证重要的信息不被篡改等问题都需 要用密码学的知识来解决，这使得密码学得到空前的发展。现在，密码学的应 用不在局限于军事或外交，它的应用已广泛的渗透在商业、网络甚至是日常生 活之中。 现代密码学从总体上可分为密码编码和密码分析两大方向：其中密码编码 是用不同的加密算法对信息进行加密以保证其安全性或者保证其真实性一一即 保密和认证；密码分析是相对密码编码而言的，主要是对加密信息的破译或者 消息的伪造，包括密码攻击、发现漏洞以及系统安全证明等等。通常都是通过 密码编码建立一套密码系统，而通过密码分析来对这个密码系统进行分析和攻 击，只有经过证明和检验的密码系统才能被认为是安全可靠的，从而应用于实 际之中，而且使用中的密码系统将一直受到密码分析者的检验，直到系统被破 解或者出现更好更安全的密码系统取代当前的系统。密码编码分为私钥密码体 制和公钥密码体制两种密码体制。其中，私钥密码体制根据对明文加密方式的 不同又分为两大类：序列密码和分组密码 序列密码，或称流密码，它的加密方式是先把报文、话音、图象和数据等 原始明文转化为明文数据序列，然后将明文序列与密钥序列进行逐位加密生成 密文序列进行发送，接受者在收到密文后，在用相同的密钥序列进行逐位解密 恢复出明文序列从序列密码的加密方式可以看出，它的安全保密性主要依赖 于密钥序列，因此，判断什么样的伪随机序列是安全可靠的密钥序列，以及如 何选取合适的伪随机序列从而得到安全可靠的密钥序列就成为了序列密码中研 究的主要的问题。通常认为一个安全的密钥序列至少要满足三个基本条件：周 期充分长，良好的随机统计特性，不可预测性充分大。 序列密码主要用于军队和国家安全部门的数据加密，其密钥序列主要采用 线性移位寄存器序列以及其变种序列如前馈序列j 非线性生成序列以及钟 控序列等等，不同部门采用的序列密码生成机制是不同的，而且采用的移位寄 存器的级数也没有统一的标准，目前一般认为带有安全参数的1 0 0 级的移位寄 存器序列就已经足够安全序列密码由于具有高效安全、实时性好以及加密和 解密容易实现等特点，在商用和网络等领域也常被使用，是一种应用广泛的密 码系统 在下一节。本文将结合发展背景介绍序列密码领域的一些基本概念、重要 的已知结论以及相关的算法。 1 2 预备知识和已知结论 在序列密码中，线性反馈移位寄存器( l f s r ) 因其实现简单、速率高、便于 分析等特点成为各种密钥序列生成器的重要部件。 一个盯级线性移位寄存器由疗个寄存器和一个反馈开关电路构成，每个寄 存器的2 种状态分别用0 和l 来代表，而0 和l 总看作是有限域只中的元素。 当加上一个移位脉冲时，就将每个寄存器中的内容( o 或1 ) 移给下一级，将最末 一级移出的内容输出。为了保持连续工作，将移位寄存器的某些级的内容，在e 中进行加法运算后，再反馈到第一级去这样不断的加移位脉冲，上述疗级移 位寄存器的输出就组成了一个序列，而这个序列适合某个线性的反馈逻辑，则 称这个序列为2 元雄级线性移位寄存器序列。类似的推广可了解由g 元h 级线性 移位寄存器产生的盯元疗级线性移位寄存器序列。 例如，开始时设第l 级的内容为口加一1 】，第2 级的内容为a n 一2 】，第疗 级的内容为口【o 】，称这个线性移位寄存器的初态是越o n 1 】a n - 1 】若反馈逻 辑为线性表达式 , , t k j = - z c l a k - i ，k ，l ，q 最 j - i 当加上一个移位脉冲后，输出a o 】，第2 级的内容为口陋一1 】，第r e 级的内容为 m 】，将a t n 】= - ( c 。口 月一1 】+ c 2 a n - 2 】+ + q 口【o 】) 反馈到第l 级。不断的加移位脉 冲，这个线性移位寄存器就将输出序列口【0 】口 1 讲2 卜。 若2 元疗级线性移位寄存器序列的反馈逻辑为表达式，则称多项式 f = l + c , x + c z x 2 + 4 - c - x 为该线性移位寄存器的联接多项式，其中qe e ，称联接多项式的互反多项式 g ( 功= 工+ c l 石p + c 2 x 卜2 + + q 为该线性移位寄存器的特征多项式。 在线性移位寄存器序列的研究开初期，一直有个问题没有被解决，即线性 移位寄存器综合问题：对于一个已知序列! ，如何构造一个最短的移位寄存器 2 来产生j 直到5 0 年代末，著名的b e r l e k a m p - m a s s e y 算法的提出解决了这个问 题，这是一个多项式时间的迭代算法，它由m a s s e y 提出，m a s s e y 同时也指出 这个算法实质上是b e r l e k a m p 在译b c h 码时从校验予求错位多项式的算法。设 长为n 的序列s - - s o s 1 s i n 一1 】，求能够产生序列的最短的线性移位寄存器 的联接多项式 ( 曲和该线性移位寄存器的长度( 级数) f 。这里规定，0 级线性 移位寄存器以f ( x ) = l 为联接多项式，0 序列由且只能由0 级线性移位寄存器产 生 算法1 2 i t 2 2 1 ：b e r l e k a m p m a s s c y 算法 输入：札0 1 】缸一1 】， ( 1 ) ：若非负整数r o 满足4 0 1 - = 可一l 】= 0 ，研一。】0 ，则对于0 i s n 。，令 ( ，：( 力，) = ( 1 ，o ) ，d l = 0 ；d = 缸h o 】，( 乙“( 功，“) = ( 1 一d o 工“，n o + 1 ) ( 2 ) ：对于 再 n ，若上= l + c i 工+ 4 - c i x 。，则计算 以= s 【】+ c l s n - 1 】+ c 2 s n 一2 】+ + e _ s n 一刀 ( 3 ) ：若以= 0 ，则工+ 。o ) = 工( 功，= ，- 若t 0 ，则有l s 册 n 使0 ，_ “- = ，则令 c + 。( x ) ，+ ) = ( ：( 力一d d ：1 x 。一。：( 功，m a x 以，n + l 一) ) ( 4 ) ：若 ld b f = l 2 ；l = 讲0 】4 - 1 】；r = a 2 7 】a 2 1 - 1 】； b = l + r ： i f b = 0t h e n a = l ； e l s e c = c + ，： a = b ： i fa o 】= 1 t h e n c = c + l ： 输出：c ( j ) = c 由定理1 2 1 不难看出，对于2 。一周期序列o ) ，若它的极小周期为2 ，设 j 7 ；4 0 s 2 - 1 】，则e ( s ) = e ( s 7 ) 用g a m e s - c h a n 算法只需知道( s ) 的连续2 个 分量即可求出d ) 的线性复杂度和极小多项式，而用b e r l e k a m p m a s s e y 算法完 成同样的工作则需要获得连续2 砸7 ) 个分量，此时，2 e ( s7 ) kt h e n c = c + 1 ： 输出：吼( s ) = c 除了上述的三个算法之外，学者们通过分析研究还给出了一些域上其它的周期序 列的算法，如域o f ( p 。) 上的p 。一周期序列的线性复杂度算法7 1 、k 错线性复杂 度算法【1 6 】；域g f ( p 4 ) 上的p 。r 一周期序列( 其中( ，p ) = 1 ) 的线性复杂度算法2 1 等 等。 其中。对于域g f ( 2 ) 上的p 。一周期序列，其中2 是模p 2 的一个本原根，肖 国镇( g x i a o ) 等学者先后给出了确定其线性复杂度的算法【3 6 1 和确定其k 错线性 复杂度的算法f 3 4 1 。首先，丁存生、肖国镇和单炜娟在流密码的稳定性理论 【9 1 一书中，设计了一个用级数求极小多项式和线性复杂度的方法，这个方法大 致可以描述为： 对于域e 上的序列= s 0 m 1 m 2 】，定义的生成函数为 ( 砷= 札o 】+ 札1 工+ j 【2 】工2 + ， 若! 是一个一周期序列且= o ) ，则 = 等= 两s ( x ) 砺g c d 丽( s ( x ) , l - x n ) = 器， 其中g e d ( s ( x ) ，1 一) 表示多项式5 ( 功和l 一工“的最大公因子， 正，) ( = ( 1 - - x ) g c d ( s ( x ) ，l 一善”) ， g ( 曲= j g c d ( s ( x ) , l - x “) 显然的，g c d ( g ( x ) ，五，) ( 力) = 1 ，d e g g ( x ) k ，则a 卜彳( 0 ) o a 0 ) o 0 a ( p - d ，c4 - - c + ( ，一1 ) ，。 o r i = o ，1 ，i - i 。c o s t i = m i n c o s t i + 】j 0 s p 一1 ，执行( 1 ) 输出：q ( s ) = c 令n = p 。，则x i a o w e i 1 _ a m i m a m u r a 算法和w e i x i a o c h e r t 算法的时间复杂 度均d ( ) 。由定理1 2 2 可以看出，对于p 。一周期序列0 ) ，若它的极小周期为p ， 设j 7 = 4 0 s p - 1 】，则c ( j ) = c 0 7 ) 。用x i a o - w e i l a m - i m a m u r a 算法只需知道0 ) 的 连续p 个分量即可求出0 ) 的线性复杂度和极小多项式，用b e r l e k a m p - m a s s e y 算法完成同样的工作需要获得连续2 c ( s 7 ) 个分量，此时，( p 一1 ) p “ c ( s 7 ) p ， 显然有p 1 的价值序列映射成为长为j = p “的价值 序列。 定义2 1 4 ：映射口，曰( 回= 0 ) ，s ( o r ) ，1 p ) i n p u t ：s = o ，o r ，| ) o u t p u t ：映射b ，b ( s ) = ( b o ) ，b ( o r ) ，l p ) f o r0 i l p 占( s ) 【f 】= s 【f 】o s i + l p o o s i + ( p - 1 ) l p 】 占( 盯) 【日；r a i n 盯【妇，盯【f + l p ，可f + ( p 一1 ) l p 定义2 1 5 ：映射工，工( s ) = 0 ) ，三( o r ) ，力 i n p u t ：s = 0 ，盯，0 o u t p u t ：工( s ) = 0 ) ，z ( o r ) ，1 p ) f o r0 s i l i o t h e n 工( s ) 【力= 1 1 0 l ( c r ) i 】= 厶。一 e s e 工o ) 【f 】= 0 工( f 】= 厶。一l , 1 注：1 对于长为珀q 向量s ，类似的定义映射b ，口o ) 【f 】= s i 】0 o j p + ( p - 1 ) t i p 】， 0 i 1 1 p 它与价值序列上的映射b 在一定意义上是一致的。 2 如果j = 【曰( s ) 】，其中 口0 ) r 表示由p 个b ( s ) 连接在一起组成的向量 口( s ) 丑0 ) b ( s ) ，则s i 】= s i + l l p 】- = 哑f + ( p 一1 ) l p 】，o i l 且t = e o s t ( s _ 肛o ) 1 9 ) 。 1a ) 对于b ( s ) 的任意一个差错向量，都存在s 的差错向量g ，使得 b ( s 0 力= b ( j ) 0 f 并且e o s t ( b ( s ) 一b ( s ) 0 ，) = e o s t ( s j o 力。 b ) 对于s 的任意一个差错向量e ，都存在b ( s ) 的差错向量，使得 b ( s 0 0 = b ( s ) o 并且e o s t ( b ( s ) 一b ( s ) 0 门e o s t ( s j o 力 2a ) 对于( 回的任意一个差错向量，都存在s 的差错向量p ，使得 l ( s o = l ( s ) 0 ，s o e = 【b ( s o e ) 】9 且e o s t ( l ( s ) 啼l ( s ) 0 厂) + t = c o s t ( s _ j o p ) 。 b ) 对于s 的任意一个满足s o e ；【b ( s oe ) 】，的差错向量e ，都存在l ( s ) 的差错 向量，使得工0 0 力= 工o ) o 厂并且e o s t ( l ( s ) _ l ( s ) o 厂) + 丁= e o s t ( s 峙s o e ) 。 ( 注意，在上述情况下，成本函数分别是用相应的成本序列b ( o - ) ，三( 盯) 来计算 的) 证明：1a ) 设厂= j 1 0 j 1 1 邝，p l 】是b ( s ) 的任意一个二元差错向量。 i n p u t s = o ，盯，d ，f 0 1 j t p i j t ；p 廿厂的曰一p u l l u p 女 户r0 s i l p d f 】= e l i + l p 】- 一e l i + o - 1 ) l p 】- 0 矿丌力= 1a n d _ ，= m i n u l 盯p + p 】= b ( 盯) 【小t h e n 印+ p 】= l 容易验证j 通过程序构造的差错向量8 是符合要求的，我们称这样构造的p 为，的b p u l l u p b ) 设p = d 0 】d l 卜4 t l 】是s 的任意一个二元差错向量，j - = 口( p ) 就是满足要求 差错向量 2a ) 设f = j i o f 1 九，p 一1 】是工( 回的任意一个二元差错向量 i n p u t ；s = o ，盯，| ) ，j - 0 u t p o t ：e u ，的工- p u l l u p 奉 f o r0 s f l i p f o r0 s j 1 且令t = c o $ t ( 8 _ 【上0 ) 】) ， 对于任意的k 2 0 ， 1 ) 如果t s k ，则( s ) 的i 错线性复杂度q ( s ) = 气一，( s ) ) 2 ) 如果0 露t ，则q ( 回= ( p - 1 ) l i p + c i ( s ) ) 证明：1 ) 当t k 时，首先证明c t ( s ) c k 一，( s ) ) 设工( s ) 的差错向量厂满 足“上( j ) 0 厂) = q r ( s ) ) 和e o s t ( ；( s ) 寸上( s ) o 厂k - t 。由引理2 1 2 ，取向量p 等于，的工一l l u p ，则s 的差错向量e 满足邵o d = ( s ) o f ，s o e = 【b 0 0e ) 】 且c o s t ( s j o 力= e o s t ( i ( s ) _ 三( s ) 0 d + r 一d + t = k 。此时，又由引理 2 1 1 得c ( s 0 力= c ( l ( s 勘= c ( 工d ) 0 ，) 。即存在s 的差错向量e 满足 e ( s oe ) = q r ( 工( s ) ) 且c o s t o 呻s 0 d 七，因此e k ( s ) s 气，r ( l ( s ) ) 接下来证明q 一，( ( s ) ) s c k ( s ) 。若p 是s 的差错向量且满足c ( s 力= 吒( s ) 和 e o s t ( s s 0 西k 。 假设s t t e 【b 0 0 明，则q ( s ) = c ( s 0 力0 - 1 ) t i p 。此时，由引理2 1 2 ， 对于l ( s ) 的差错向量f = 0 ，取9 7 为厂的l - p u l l u p ，则j o p 7 【占0 0 p ，) 】，且 e o s t ( s j o e 7 ) = t k 。又由引理2 1 1 得c ( s 0 p 7 ) = c ( l ( s o p ，) ) l p ，则说明 1 2 c i ( 印s c ( s o e 7 ) s l i p ，与前面的推断矛盾，因此假设不成立，j o e = 【b ( s 0 酬。 由引理2 1 2 ，对于满足s o e = b ( s o 州的e ，存在工( 回的差错向量， 使得c o s t ( l ( s ) 哼上o ) o ，) = c o s t ( s 专j e e ) - t s k r 且l ( s ) o f = l ( s o e ) ，则 三o ) 0 ，的线性复杂度c ( l ( s ) o 力= c ( l ( s o 力) = c ( s 0 0 = c k ( s ) 。因此， c k r ( 工( s ) ) s q ( 研 综上可得，当t 七时，二元价值序列( s ) 的k 错线性复杂度 c , c s ) = c k - t ( l ( s 9 2 ) 当0 s k t 时，首先证明c t ( 回( p - o h p + 气( b ( 劝。设b ( s ) 的差错向 量，满足c ( b ( s ) e f ) = c i ( s ) ) 和c o s t ( b ( s ) _ b ( s ) o 力s k 由引理2 1 2 ，取向 量 e 等于 ， 的 b p u l l u p ，则 向量 e 满 足 c o s t ( s 专s o 力= c o s t ( b ( s ) 一b ( s ) o n k t 并且b ( s o 力= b ( s ) o f 则 c o s t ( s - - 4 s o e ) t ，又由定义2 1 5 中映射工的定义可以看出 t = c o s t ( s - 9 陋( s ) 】) = m i n c o s t ( s j o p ，) i j o e 7 = 研0 0 e ) 】) ，因此此时一定有 j 0 e b ( s 0 叫由引理2 1 1 得，砸0 力= ( p - x ) h p + c ( b ( s 0 力) ，又由于 b ( s ep ) = 丑0 ) o f 且c ( b ( o e f ) = c ( b ( s ) ) ，则c p o e = ( p - d j ，p + c i ( 占( s ) ) 即 存在s 的差错向量e 满足c 0 0 力= - 1 ) l p + c , ( b ( s ) ) e lc o s t ( s 专j o 功k t ， 因此c 。( s ) s ( p - 1 ) l i p + c a b ( s ) ) 。 接下来证明c i ( 回( p - x ) u v + c l ( 丑( s ) ) 。若差错向量p 满足c p 0 d = q ( s ) 和 c o s t ( a - 9 j o 力s k 由引理2 1 2 ，存在口( s ) 的差错向量厂，使得 b ( s 0 力= b ( s ) o f 并且c o s t ( b ( s ) 专b ( s ) o 厂) c o s t ( s 哼j 0 e ) k 。因为 c o s t ( s 专j 0 力k t ，故此时一定有j o e 【b ( s 0 0 r 。由引理2 1 1 ， c ( s 0 力= ( p 一1 ) t i p + c i ( b ( s o 功) ，又由于c 0 0 0 = c k ( s ) 且b ( s o 力= b ( s ) o 厂， 则c k ( s ) = ( p 一1 ) ，p + c ( b ( s ) o ，) 即存在差错向量厂满足 c ( s ) = ( p - 1 ) l p + c ( b ( j ) o 门 且 c o s t ( b ( s ) 岭b ( s ) o 门k ， 因 此 c i ( 回2 ( p - 1 ) h p + c a b ( s ) ) 综上可得，当0 k t 时，二元价值序列( 的k 错线性复杂度 c a s ) = ( p - 1 ) l p + c i ( b 岱) ) 2 2 差错线性复杂度谱及临界差错线性复杂度谱 定义2 2 1 ：对于价值序列s = o ，仃，) ，称由数对( 七，c 。( s ) ) 组成的集合 ( _ j ，c k ( s ) ) 1 0 s k s c o s t ( s o ) 为s 的差错线性复杂度谱( e l c s ) 。 由引理2 1 3 ，s 的差错线性复杂度谱可以分解成b ( s ) 的差错线性复杂度 谱和l ( s ) 的差错线性复杂度谱的组合。由定义2 2 1 和引理2 1 3 容易得到以 下的引理。 引理2 2 1 ：对于价值序列s = ( j ，叮，p 。) ，设b ( s ) = ( s ) ，b ( 盯) ，p ”) ， 工( s ) = ( 工( j ) ，工( 仃) ，p ”) ，令t = c o s t ( s 一陋( s ) 】) ，u = c o s t ( l ( s ) _ 0 ) 。若b ( s ) 的 差错线性复杂度谱为 ( | | ，c a b ( s ) ) 1 0 k c o s t ( b ( s ) 斗0 ) ) ，工( s ) 的差错线性复杂 度谱为 ( 七，c k 犯( 劝j 0 s k ，则s 的差错线性复杂度谱为 ( | ，( p 一1 ) + p “q + c t ( b ( s ) ) 1 0 s k 0t h e n c e l c s ( b ( s ) ，珂，r a i n a m , 万+ r l ，c + ( p 一1 ) l i p ) 移t $ + t s l i mt h e n c e l c s ( l ( s ) ，酊+ t ，l i m ，c ) e t s e 枣f = l 宰 矿缸o 】= 0t h e n o u t p u t ( 4 ，c ) i f4 0 】= 1 a n da o 】 0t h e n o u t p u t ( t s f ，c + 1 ) 矿4 0 】= 1a n d 缈+ 讲o 】s l i m t h e n o u t p u t ( t s f + o f o 】，0 注：在算法中，在递归过程中的每一轮，用第一个序列记录当前的价值序列， 用变量趣r 和变量l i m 分别记录由初始序列递归到当前序列所实际付出的成本和 最大可能付出的成本的某一上界，所以一定要保持t s f s l i m ，用变量c 记录最小 线性复杂度的变化。 在介绍如何使用该算法来确定任意的价值序列s 的临界差错线性复杂度谱 之前，首先证明下面的这个引理 引理2 3 1 ：若价值序列s = 0 ，盯，) 的i i 缶界点中所有满足岛 0 ，l i m 一缈】的 点为( k o ，。h ( s ) ) ，( k ，( s ) ) ，则用算法c e l c s ( s ，可，l i m ，c ) 输出的所有的点为 ( 毡厂+ 七o ，c + c k , ( s ) ) ，( 您厂+ 七，c + c 七- ( s ) ) 证明：用数学归纳法证明。当，= l 时，若s o 】- 0 ，则c o s t ( $ 专0 ) = 0 ，则( 0 , 0 ) 是唯一的满足条件的临界点，而用算法输出的点也只有一个( 可，力。4 0 】_ l 且 o f o 】= 0 时，e o s t ( $ 专o ) = 0 ，其情形与4 0 = 0 时相同，故略去。若s o 】= l 且科o 】 0 ， 则e o s t ( s _ o ) = 讲o 】 0 ，若此时缈+ 研o 】s l i m ，则有两个满足条件的临界点( o 1 ) 和( o f o ，o ) ，而用算法输出的点为( 可，c + 1 ) 和( 妒+ 科o 】，c ) ；否则，缈+ 研o 】 l i m ， 那么只有一个的满足条件的临界点( 0 , 1 ) ，而用算法输出的点只有( ，c + 1 ) 。因此， 当，= 1 时，引理对于所有的s = ( j ，盯，| ) 成立。 假设对于所有的n 7 p 4 。1 ，证明引理对于所有的s = ( s ，o r ，) 成立。c e l c s ( s ，可，l i m ，c ) 分成两个子算法进行递归，按顺序进行讨论。 首先看c e l c s ( b ( s ) ，珂，m i n l i n 【l