第３３卷第２期 吉首大学学报（自然科学版） Ｊｏｕｒｎａｌ ｏｆ Ｊｉｓｈｏｕ Ｕｎｉｖｅｒｓｉｔｙ（Ｎａｔｕｒａｌ Ｓｃｉｅｎｃｅ Ｅｄｉｔｉｏｎ） Ｖｏｌ＿３３ Ｎｏ．２ Ｍａｒ．２Ｏ１２ ２Ｏ１２年３月 文章编号：１００７—２９８５（２０１２）０２—００２８—０７ ２ｎ周期平衡二元序列的８错线性复杂度 周建钦 ，赵起 ，崔洪成 （１．安徽工业大学计算机学院，安徽马鞍山 ２４３００２；２．杭州电子科技大学通信工程学院，浙江杭州 ３１００１８） 摘 要：线性复杂度和ｋ错线性复杂度分别是流密码密钥流序列强度和稳定性的重要度量指标．通过研究周期为２”的 二元序列线性复杂度，基于Ｇａｍｅｓ—Ｃｈａｎ算法，讨论了线性复杂度小于２ 的２ 一周期二元序列的８错线性复杂度的分布，给 出其对应８错线性复杂度为２ 。，２一 ，２ 和２一。一２ ＿了的原始二元序列计数公式． 关键词：周期序列；线性复杂度； 错线性复杂度； 错线性复杂度分布 中围分类号：ＴＮ９１１；ＴＮ９１８．１ 文献标志码：Ａ ＤＯＩ：１０．３９６９／ｊ．ｉｓｓｎ．１００７—２９８５．２０１２．０２．００８ 线性复杂度是衡量密钥流序列随机性的一个重要指标，但高线性复杂度并不一定能保证序列是安全 的．有些序列的线性复杂度极不稳定，如果改变这些序列一个周期段中１个或几个元素，其线性复杂度发 生很大的变化，那么该序列仍然是密码学意义上的弱序列．我国学者丁一肖一单 最早注意到这个问题，因 而率先创立了流密码的稳定性理论，并提出了重量复杂度、球体复杂度等流密码稳定性度量指标．随后国 外学者Ｓｔａｍｐ Ｍａｒｔｉｎ等Ｅ。 也引入了类似“球体复杂度”的线性复杂度稳定性度量指标——忌错线性复杂 度．设ｓ是周期为Ｎ的ｑ元序列，当改变ｓ的一个周期中至多ｋ（０≤ｋ≤Ｎ）位后，得到的所有序列的线 性复杂度中最小的线性复杂度，称为Ｓ的ｋ错线性复杂度． 苏明 。 提出研究周期为２ 的二元序列的ｋ一１，２时ｋ一错线性复杂度；Ｒｕｅｐｐｅｌ Ｒ Ａ＿４ 给出线性复杂 度为Ｌ的周期为２ 的二元序列的具体个数；Ｍｅｉｄｌ Ｗ＿５ 给出ｋ一１，２时线性复杂度为２ 的周期为２ 的二 元序列的ｋ错线性复杂度分布情况；朱凤翔等＿６ 给出ｋ一２，３时线性复杂度为２”一１的周期为２ 的二元 序列的ｋ错线性复杂度的分布；谭林等 给出ｋ一１，２时Ｆ 上２ 一周期序列的ｋ一错误序列的计数，并给出 了Ｆ 上２”一周期序列的１一错误序列个数的均值． 由于线性复杂度小于２ 的２”一周期二元序列具有偶数个非０元素，因而又称为平衡二元序列．笔者通 过研究周期为２”的二元序列线性复杂度，基于Ｇａｍｅｓ—Ｃｈａｎ算法［８］，讨论了线性复杂度小于２ 的２”一周期 二元序列的８错线性复杂度的分布，给出其对应８错线性复杂度为２一。，２ 。，２一 和２一。一２ 的原始二元 序列计数公式，并全部通过计算机编程进行了验证． １ 预备知识与引理 文中所涉及序列都是在ＧＦ（ｑ）域上，设ＧＦ（ｑ）域上的２个向量ｘ一（ｚ 和ｙ一（ １ Ｙ ２ ＋Ｙ ）． 。 ｚ。 … 一 ） ３ … Ｙ 一ｌ ），则定义ｘ＋ｌ，一（ｚ１＋ １ ｚ ２－＋－Ｙ ２ ３＋Ｙ ３ … 一１＋ 一１ ＊收稿日期：２０１１—１Ｏ一２２ 基金项目：安徽省自然科学基金资助项目（１２０８０８５ＭＦ１０６） 作者简介：周建钦（１９６３一），男，山东巨野人，安徽工业大学计算机学院教授，硕士．主要从事通信、密码学与理论计算 机科学研究． 第２期 周建钦，等：２ 周期平衡二元序列的８错线性复杂度 对于序列Ｓ，若存在正整数Ｔ，使得Ｓ件 ：ｓ （ —Ｏ，１，２，３，…）成立，则称Ｓ为周期序列，最小正整数Ｔ 称为序列Ｓ的最小周期．若序列Ｓ满足Ｓ，＋ｎ ｓ，一 ＋ Ｓ，一 ＋…＋ａＬｓ，～ 一ｏ（ｊ≥Ｌ），其中Ｌ为正整数， ａ ，ａ ，ａ。，…，。 是ＧＦ（ｑ）中的元素，则称序列Ｓ是一个Ｌ阶线性递归序列（也称差分方程），称最小的整 数Ｌ为该递归序列的线性复杂度Ｃ（Ｓ）． 序列Ｓ一（ｓ ，ｓ ，ｓ。，…）的生成函数定义为ｓ（ｘ）一ｓ。＋ｓ ｚ＋ｓ。ｚ ＋…一∑Ｓ ＬＸ ，有限序列ｓ‘ 一（ｓ ， 一０ ｓ ２，ｓ ３，…，ｓ 一１）的生成函数定义为ｓ‘ （ｚ）一ｓ。＋ｓ１ ＋ｓ ２ ＋…＋ｓ ｚ ．若Ｓ是周期序列，ｓ‘” 是它的 第一周期，则ｓ（ｚ）可以表示成 ｓ（ ）一ｓｎ（ｚ）（１＋ｚ ＋Ｘ ２ｎ＋ｚ ｓ ＋…）一 １一） Ｓ （ｚ）／ｇｃｄ（ｓ （ｚ），１一ｚ ） ｇ（ｚ） Ｚ ｎ（１一ｚ ）／ｇｃｄ（ｓ”（ｚ），１一ｚ ）一ｆ （ ）’ 且－厂 （ｚ）一（１一ｚ ）／ｇｃｄ（ｓ”（ｚ），１一ｚ ），ｇ（ｚ）一ｓ （ｚ）／ｇｃｄ（ｓ （ｚ），１一ｚ”）．显然，ｇｃｄ（ｇ（ ），ｆ （ｚ））一 １，ｄｅｇ（ｇ（ｚ））＜ｄｅｇ（ｆ （ ）），ｆ （ｚ）是Ｓ的极小多项式，且－厂 （ｚ）的次数是序列Ｓ的线性复杂度，记为 Ｌ（Ｓ）． 设Ｎ一２ ，则１一ｚ ＝＝：１一ｚ。”一（１一 ）。 一（１一ｚ） ．因而对于周期为２ 的二元序列，求其线性复 杂度可以转化为求ｓ （ｚ）中因式（１—５Ｃ）的次数． 下面的２个引理是众所周知的结果，也可参见文献Ｅｓ－１： 引理１ 设周期为Ｎ＝２”的二元序列Ｓ，其线性复杂度Ｌ（Ｓ）一Ｎ，当且仅当该序列的一个周期的 Ｈａｍｍｉｎｇ重量为奇数． 因为Ｈａｍｍｉｎｇ重量为奇数的序列去掉１个１即变为Ｈａｍｍｉｎｇ重量为偶数的序列，所以下面主要考虑 Ｈａｍｍｉｎｇ重量为偶数的序列． 引理２ 设周期为２ 的二元序列ｓ 和Ｓ。．若Ｌ（Ｓ ）≠Ｌ（５ ２），则Ｌ（Ｓ ＋Ｓ ）一ｍａｘ｛Ｌ（Ｓ１），Ｌ（ｓ。））； 若Ｌ（Ｓ１）一Ｌ（Ｓ ２），则Ｌ（Ｓ１＋Ｓ ）＜Ｌ（Ｓ１）． 若最少改变二元序列Ｓ的ｋ个元素，序列Ｓ的线性复杂度即可下降，根据引理２，则这ｋ个位置为１的 二元序列其线性复杂度也必为Ｌ（Ｓ）．因而ｋ错线性复杂度的计算可以转化为求Ｈａｍｍｉｎｇ重量最小的二 元序列，使得其线性复杂度也为Ｌ（Ｓ）． 引理３ 设Ｅ 是周期为Ｎ一２ 的二元序列，它的第一周期序列只在第ｉ位置元素是ｌ，其他位置元素 全为０（０＜ｉ＜Ｎ）．若Ｊ—ｉ＝＝＝２ （１＋２ａ），ｎ＞０，０≤ｉ＜ ＜Ｎ，ｒ≥０，则Ｌ（Ｅ ＋Ｅ，）一２ 一２ ． ２ 周期为２ 平衡二元序列的８错线性复杂度 定义１ 定义映射 ；＊＿）１）． 设Ｓ 一｛Ｓ ｏ，Ｓ１，ｓ ２，…， 一１｝是二元序列Ｓ的第１个周期， ≥１，根据Ｇａｍｅｓ—Ｃｈａｎ算法， 从Ｆ 到Ｆ ， （ｓ ）＝ （ｓ ，ｓ｛ ，…ｓ ５ ）＿ ）一（５ ＋５ ，ｓ ＋ｓ ＋ ，…， ；；ｉ上 一 ＋ 定义１的映射 满足以下性质：（ｉ）ｗ（ （５‘” ））≤Ｗ（ｓ‘ ）；（ｉｉ） （ （５‘ｎ ）），ｗ（ｓ（” ） 引理４［ 奇偶性相同；（ｉｉｉ）集合 （ ）一｛ ∈Ｆ；，ｔ＿ ｌ ｎ＋ｌ（ ）一ｓ‘” ）的大小为２ ． ｆ１ 一 引理５［４］ 设Ｎ（Ｌ）表示周期为２ ，线性复杂度为Ｌ的二元序列个数，则 Ｌ一０， １ Ｌ≤２ ． 给出线性复杂度小于２ 的２”一周期二元序列的全部８错线性复杂度分布非常重要，但也相当困难，下 面讨论几种特殊情况． 定理１ 设Ｎ ｓ（２一。）表示周期为２”，线性复杂度Ｌ（Ｓ）＜２ ，８错线性复杂度为２ 。的二元序列Ｓ的 个数， ＞３，则 Ｎ ８（２ 。）一［２ （２ 一４）（２ 一８）（２ 一１２）（２ 一１６）（２ 一２０）（２ 一２４）（２ 一２８）／８ １］２ …一． 证明 设序列５“’线性复杂度为２一 的二元序列，则Ｓ 的个数为２ ～一． 设序列“ ，Ｗ（ｕ ）一Ｏ，易知存在一个序列Ｗ（ｖ ）一４，使得“ ＋ 的线性复杂度为２一 ，即Ｓ ３０ 吉首大学学报（自然科学版） 第３３卷 十 的８错线性复杂度小于２ ． 设序列“ ，Ｗ（ｕ ）一２，易知存在一个序列Ｗ（ｖ ）一２，４或６，使得Ｕ ＋ ‘ 的线性复杂度为２ ， 即Ｓ ＋Ｕ 的８错线性复杂度小于２一。． 设序列“ ’，Ｗ（ｕ ）一４，易知存在一个序列Ｗ（ｖ ）一Ｏ，２，４，６或８，使得“ ＋ ‘” 的线性复杂度为 ２一 ，即Ｓ ＋Ｕ ’的８错线性复杂度小于２ ． 设序列“ ，Ｗ（ｕ ’）＝＝＝６，易知存在一个序列Ｗ（ｖ ）一２，４，６，８，使得“ ＋ ２ ，即５ ＋“ 的８错线性复杂度小于２ ． 设序列“ ，Ｗ（ｕ“ ）一８，且 的线性复杂度为 中至少２个非０元素距离为２一 的倍数．易知存在一个序列 “ ， Ｗ（ｖ ’）一４，６或８，使得Ｕ ＋ 得“ ＋ 一线性复杂度为２ ，即Ｓ ＋“ ’的８错线性复杂度小于２ ． ，使 的个数为２ （２ 一４）（２” 设序列“ ’，Ｗ（ｕ ’）一８，且“ 中不存在２个非０元素距离为２一。的倍数．易知不存在序列 线性复杂度为２一 ，即Ｓ“ ＋Ｕ ’的８错线性复杂度等于２ ．序列 ８）（２ 一１２）（２ 一１６）（２ 一２０）（２ 一２４）（２ 一２８）／８ １． 因而，８错线性复杂度为２一。的二元序列Ｓ的个数为 Ｎ ８（２ 。）一［２ （２ 一４）（２ 一８）（２”一１２）（２”一１６）（２ 一２Ｏ）（２ 一２４）（２ 一２８）／８ １］２ 一证毕． ． 例如，当 一４时， ［２ （２”一４）（２”一８）（２ 一１２）（２ 一１６）（２ 一２Ｏ）（２ 一２４）（２”一２８）／ｓ！］２ … 一Ｏ，即线性复杂度 小于Ｌ（Ｓ）＜２ ，８错线性复杂度为８的二元序列Ｓ的个数为０． 当 一５时， ｒ２”（２”一４）（２”一８）（２”一１２）（２ 一１６）（２ 一２０）（２ 一２４）（２”一２８）／８ １］２。… 一（３２×２８×２４× ２Ｏ×１６×１２×８×４）×２ 一８ ３８８ ６０８，通过计算机验证，线性复杂度小于Ｌ（Ｓ）＜２ ，８错线性复杂度为 ８的二元序列ｓ的个数为８３ ８８６ ０８． 定理２ 设Ｎ。（２一。）表示周期为Ｌ（Ｓ）＜２ ，线性复杂度２ ，８错线性复杂度为２ 。的二元序列Ｓ的 个数，＂＞４，则 Ｎ。（２ 。）一｛２ （２ 一８）（２”一１６）（２ 一２４￣／４ １＋２ （２ 一８）（２”一１６）（２ 一２４）（２”一３２）（２ 一４Ｏ）／６ １＋ （２ 。）（ ）。＋（２ 。）（ ）（ ）（２＂－１６）ｃ２”一２４ ／ｚ ＋（ 。）（ ）（２＂－８）（２＂－１６）￣ （２”一２４）（２ 一３２）／４ １＋２ （２”一８）（２”一１６）（２”一２４）（２ 一３２）（２ 一４０）・ ｃ２ 一４８ ２ 一ｓｚ ／８ ＋（２ 。）（ ） ＋（２ 。）（ ）。ｃ２ 一ｚ４ （２＂－３２）／ｚ ＋ （２ ）（ ）（ ）ｃ２ 一 ６ （２＂－２４ （２＂－３２ ｃ２”一４０ ／４：＋ （／２ 一０、／８、 １）【２） 一８）（２ 一 ６）（２ 一２４）（２ 一３２）（２”一４０）（２”一４８）／６ １＋ （２ 。）（ ）（ ） （２ 一２）（ ）＋ｃ２”一１６ ２ 一２４ ／ｚ ＋ （２ ）（ ） （２—３２一 ）（ ）（ ）ｃ２ 一２４，＋（２ 。 一 ）（ ）・ （２ 一１６）（２”一２４）（２”一３２）／３ １＋（２ 一８）（２ 一１６）・ （２ 一２４）（２ 一３２）（２”一４０）／５ １］｝２ …～． 证明 设序列Ｓ 线性复杂度为２ 。的二元序列，则ｓ 的个数为２ 一～． 设序列Ｕ ，Ｗ（ｕ ）一０，易知存在一个序列Ｗ（ｖ ）一８，使得 ’＋ ’的线性复杂度为２一。，即５ ’ ＋“ 的８错线性复杂度小于２ 。． 设序列Ｕ ，Ｗ（ｕ“ ）一２，易知存在一个序列Ｗ（ｖ ）一６或８，使得“ ｝７９ 的线性复杂度为２ 。． 第２期 周建钦，等：２”周期平衡二元序列的８错线性复杂度 ３１ 即５ ＋Ｕ 的８错线性复杂度小于２一。． 设序列 ，Ｗ（ｕ ）一４，且 ｈ’中至少２个非０元素距离为２ 。的倍数．易知存在一个序列Ｗ（ｖ ） 的线性复杂度为２一。，即Ｓ ４－Ｕ 的８错线性复杂度小于２一。． ：４，６或８，使得“ ４－ 得 ４－ 设序列Ｕ ，Ｗ（ｕ ）一４，且Ｕ 中不存在２个非０元素距离为２一。的倍数．易知不存在序列７３ ，使 的线性复杂度为２一。，即Ｓ ４－Ｕ 的８错线性复杂度等于２一。．这样序列Ｕ 个数为Ｃ１— ２ （２ 一８）（２ ～１６）（２ 一２４）／４ １． 一设序列Ｕ ，，Ｗ（ｕ ）一６，且Ｕ 中至少３个非０元素距离为２ 。的倍数．易知存在一个序列Ｗ（ｖ ’） ２，４，６或８，使得 ＋ 的线性复杂度为２一。，即Ｓ ４－Ｕ 的８错线性复杂度小于２ 。． ，使 设序列“ ，，Ｗ（ｕ ’）一６，且“ ’中不存在３个非０元素距离为２一。的倍数．易知不存在序列 得“ ＋ 的线性复杂度为２一。，即ｓ ４－“ 的８错线性复杂度等于２一。． 倍数。 得到序列 个数为 分成２种情况考虑：（ｉ）不存在２个非０元素距离为２ 倍数；（ｉｉ）只有２个非０元素距离为２ 。的 ｃ２—２ （２＂－８ （２＂－１６ ｃ２＂－２４ ｃ２ 一３２）（２＂－４０ ／６ ＋（２ 。）（ ）（ ）（ ）＋ （２ 。）（ ）（；）ｃ２ 一 ６ ｃ２ 一２４）／２ ＋（２ 。）（ ）・ （２ 一８）（２”一１６）（２”一２４）（２ 一３２）／４ １． 设序列 ，Ｗ（ｕ ）一８，且 中至少４个非０元素距离为２一。的倍数．易知存在一个序列ｗ（ ） 一０，２，４，６或８，使得Ｕ ＋ 设序列Ｕ ，Ｗ（ 的线性复杂度为２ 。，即５ ＋Ｕ“ 的８错线性复杂度小于２ 。． ）一８，且Ｕ 中不存在４个非０元素距离为２一。的倍数．易知不存在序列 ｈ ，使 得Ｕ ＋ 的线性复杂度为２一。，即ｓ ＋ 的８错线性复杂度等于２ 。． 同样可以分成２种情况考虑：（ｉ）不存在３个非０元素距离为２一。倍数；（ｉｌ）只有３个非０元素距离 为２ 。倍数． 得到序列“ｈ 个数为 Ｃ３．７－－２ （２ 一８）（２ 一１６）（２ 一２４）（２ 一３２）（２ 一４０）（２ 一４８）（２”一５２）／８ １＋ （２ ）（ ）（ ）（ ）（ ）＋（２ｎ３－。）（ ）（ ）（ ）ｃ２ 一２４ ｃ２ 一３２ ／２ ＋ （２ 。）（ ）（ ）ｃ２”一 ｅ （２＂－２４）（２＂－３２）ｃ２ 一４。，／４ ＋ （２ 。）（ ）（２＂－８）（２＂－１６）（２＂－２４）（２＂－３２）（２＂－４０）（２＂－４８） ＋ （２ －） （２一。 ）（２８ｘ／，＋（２＂－ （２＂－２４） ＋ （２ 。）（；）［（２ 。２一 ）（ ）（ ）ｃ２ 一２４，＋ （２－３１）（ ）（２＂－１６ （２＂－２４ 一：＋ （２”一８）（２ 一１６）（２ 一２４）（２ 一３２）（２ 一４０）／５ １． 综上所述，序列 ’个数为 Ｃ４：Ｃ１＋Ｃ２＋Ｃ３—２”（２”一８）（２ 一１６）（２ 一２４）／４ １＋２ （２ 一８）（２ 一１６）（２ 一２４）（２ 一３２）・ ｃ２ 一４。，／６ ＋（２ 。）（ ）。＋（２ 。）（ ）（ ）（２＂－１６）ｃ２”一２４ ／２ ＋ （２ 。）（ ）ｃ２”一８ ｃ２ 一 ６ ｃ２ 一２４ ｃ２”－３２）／４ ＋ ３２ 吉首大学学报（自然科学版） 第３３卷 ２”ｃ２”一８ ｃ２”一 ｅ ｃｚ 一２４， ２ 一３ｚ ｃ２ 一４。 ｃ２ 一４８ ｃ２”一５２ ／８ ＋（２ 。）（ ） ＋ （２ 。）（ ）。ｃ２”－２４）ｃ２”——３２ ／２ ＋（ 。）（ ）（ ）ｃ２ —— ６ ｃ２ｎ－２４）ｃ２”－３２）． ｃ２ ——４。 ４ —＋一（２ 。）（ ）ｃ２ ——８ ｃ２”－１６）ｃ２ －－２４） ２”——ｓ２ ｃ２ －－４０）￣ ｃｚ 一４８ ／６ ＋（２ 。）（ ）（ ） （２一。 一２）（ ）＋ｃｚ 一 ６ ｃｚ －２４）／２ ＋ （２ 。）（；） （２”一。 —— ）（ ）（ ）ｃ２ ——２４ —＋一（２ 一。 —— ）（ ）ｃ２ —— ｅ ｃ２ ——２４ ・ （２ 一３２）／３ １＋（２ 一８）（２ 一１６）・（２ 一２４）（２ 一３２）（２ ～４０）／５ １］． 因而，８错线性复杂度为２一 的二元序列Ｓ的个数为Ｎ。（２ 。）一ｃ４・２ 一～． 证毕． 例如，当ｎ一５时，Ｎ。（２一。）一７ ４８０ ３２０×８—５９ ８４２ ５６０，通过计算机验证，线性复杂度小于Ｌ（Ｓ）＜ ２。，８错线性复杂度为４的二元序列Ｓ的个数为５９ ８４２ ５６０． 定理３ 设Ｎ （２一 ）表示周期为２ ，线性复杂度Ｌ（ｓ）＜２”，８错线性复杂度为２一 的二元序列Ｓ的 个数，则 Ｎ。ｃ２一 一（ ＋（ ）十（ ）＋（６ｎ）＋（ ）一２ （ ））２ Ｌ１． 证明 设序列ｓ 线性复杂度为２ 的二元序列，则ｓ 的个数为２ …～． 设序列Ｕ ，Ｗ（ｕ ’）一０，２，４，６，易知不存在 ，使得 ＋ ’线性复杂度为２ 一（２ 。＋２一。＋ ＋ 线性复杂度为２一 一（２ ＋２ 。＋ ２ ）一２一 ，即Ｕ ＋５ 的８错线性复杂度等于２ ． 易知存在序列Ｕ ’，７２ ，Ｗ（ｕ ）一Ｗ（ｖ ）一８，使得 ２” ）一２一 ，即“ ＋５“ 的８错线性复杂度小于２ ． 设序列“ 且Ｗ（Ｕ ）一８，则 的个数为（ ）． 假设序列ｂｔ ， ，Ｗ（Ｕ ）一Ｗ（ ’）一８，使得“ ＋ 线性复杂度为２ ．这样１６个非０兀素的 组合个数为２一 ． 设序列“ ’，Ｗ（ｕ ）一８，且Ｕ 中８个非０元素属于这样１６个非０元素的组合，则Ｕ 的个数为 ２ （ ）． 设序列Ｓ 线性复杂度为２一 的二元序列，序列 ，Ｗ（ｕ ）一０，２，４，６或８，且Ｕ 中８个非０元素 不属于这样１６个非０元素的组合，可知５ ＋Ｕ ’的８错线性复杂度为２一 ．这样Ｓ ＋“ 的个数为 （ ＋（ ）＋（ ）＋（ ）＋（ ）一２ （ ））ｚ ４＿１． 证毕． 例如，当 一 时，ｃ 十（ ）＋（ ）＋（ ）＋（ ）一２一 （ ） ｚ。 Ｌ１一ｃ ＋ ２。＋（１４６）＋Ｉ１６）＋Ｉ１８６）一 （１Ｒ６））２—９ ９４９，通过计算机验证，线性复杂度Ｌ（ｓ）＜２ ，８错线性复杂度为１的二元序列ｓ的个数为。 ９４９． 当 一ｓ时，ｃ ＋（ ）十（ ）＋（ ）＋（ ）＿２．－４（ ） ２ ４＿ｌ—ｃ ＋４９６＋（ ）＋（ ）＋（３８２）一 ２（ ））一２２ ８７ｏ ４ｌ８，通过计算机验证，线性复杂度Ｌ（ｓ）＜２ ．８错线性复杂度为２的二元序列ｌｓ的个数 第２期 周建钦，等：２ 周期平衡二元序列的８错线性复杂度 ３３ 为２２ ８７０ ４１８． 定理４ 设Ｎ （２一。一２ ）表示周期为２ ，线性复杂度Ｌ（Ｓ）＜２ ，８错线性复杂度为２ 。一２．－ｉ的 二元序列＇ｓ的个数， ＞３，３＜Ｊ≤ ，则 Ｎ ８ ｃ２—３—２一 ＝ ＋（ ）＋（ ）＋（ ）＋（ ）一２—８ ｃ（ ）一２ 一２—３一ｃ２ ９＋ 一２一 ，ｃ（ ）一 ２）］２ ＿。． 证明 设序列Ｓ 线性复杂度为２一。一２”．７的二元序列，３＜Ｊ≤ ，则Ｓ 的个数为２ Ｌ ＿。． 易知存在序列 ， ，Ｗ（ｕ ）一Ｗ（ｖ ）一８，使得 ＋７３ 线性复杂度为２ 一（２ 。＋２一。＋ ２一 ）一２一。一２一，即 ＋ｓ 的８错线性复杂度小于２一。一２一． 设序歹０ 且Ｗ（ｕ ’）一８，贝Ⅱ “ 的个数为（ ）． 假设序列 ， ，Ｗ（ ）一Ｗ（ｚ， ）＝＝＝８，使得Ｕ ＋ 线性复杂厦为２ 。一２ －ｊ．这样１６个非Ｏ 比特组合的个数为 一２一 ，且每个组合都与另外２个组合有包含８－＇ｉ－￣ｌｚ ｏ比特的交集・这样８个非 ０比特等距离分布，构成集合Ａ１，Ａ１的个数为２一。．例如，其８个位置可以为｛ｉ，ｉ＋２ 。，ｉ＋２一。，ｉ＋２ 。 ＋２ 。，ｉ＋２一 ，ｉ＋２一 ＋２一。，ｉ＋２一 ＋２ 。，ｉ＋２一 ＋２ 。＋２一。｝． 设序列“ ，Ｗ（ｕ ）一８，且 中８个非０元素属于这样１６个非０元素的组合或者Ａ１，则 的个 数为Ｃ１：２一。 （（。）一２）＋２、 ， 。． 假设序列 ’，７３ ，Ｗ（ｕ ’）一ｗ（ ）＝８，使得“ ＋口 线性复杂度为２ 。一２…，３＜ｍ＜Ｊ．这 样１６个非０元素的组合构成集合Ａ２，Ａ２的个数为２ 。 ．Ａ２的每个元素包含Ａ１的２个元素． 设序列“ ，Ｗ（ｕ ）一８，且Ｕ 中８个非０元素属于这样１６个非０元素的组合且不属于Ａ１，则 的个数为２—８＋ｍ（（ ）一２）． 由于ｔ 一５ ＋Ｍ ’＋ 的线性复杂度为２一。一２ Ｊ，因此ｓ ’＋ｔ ’一 ＋ ．此时，Ｓ ＋“‘ ） 与ｔ ’＋ ’相同． 对于３＜ ＜ ，所有这样 的个数为ｃ２一 ｊ－１ ２—８ （（ ）～２ 一（２—８ 一２一 ｃ（ ）一２）． 因而８，错线性复杂度为２一。一２ 的二元序列Ｓ的个数为 Ｎ ｃ２ ３—２ 一ｃ ＋（ ）＋（ ）＋（ ）＋（ ）一Ｃ１一Ｃ２／２ ２Ｚ．－３＿ｚ．－Ｊ＿ｌ— ＋（ ）＋（ ）＋（ ）＋（ ）一２一州ｃ（ ）一２ 一２ ３一 （２”一９十Ｊ一２ 一。）（（１ｆ ）一２）－Ｉ２ 一。一２ —Ｊ一１． 证毕． 容易验证定理３是Ｊ一４时定理４的特例． 例如，当ｎ一４，Ｊ：４时， ［ ＋（ ）＋（ ）＋（ ）＋（ ）一２ ＿８州ｃ（ ）一２，一２ ＿。一ｃ２ ＿８州一２卜 ｃ（ ）一２ ／２ 一９ ９４９， 即线性复杂度Ｌ（Ｓ）＜２ ，８错线性复杂度为１的二元序列Ｓ的个数为９ ９４９，与定理３的 一４时结果相同． 当 一５， 一４时， ＋（ ）＋（ ）＋（ ）＋（ ）一２。 ｃ（ ）一２ 一２ ｓ—ｃ２ 卧４—２ ｓ，ｃ（ ）一２ ］－２－：２２ ８７。４ ８， ３４ 吉首大学学报（自然科学版） 第３３卷 即线性复杂度Ｌ（Ｓ）＜２ ，８错线性复杂度为２的二元序列Ｓ的个数为２２ ８７０ ４１８．与定理３的 一５时结 果相同． 当 一５，Ｊ一５时， ＋（ ）＋（ ）＋（ ）＋（ ）一２ ８ ｃ（ ）－２）－２ ５－３一（２ｓ－９＋ｓ＿２５－ｓ）（（ ）一２ ２。一４５ ｓ８ｅ ４ｚ。， 通过计算机验证，线性复杂度Ｌ（Ｓ）＜２ ，８错线性复杂度为３的二元序列Ｓ的个数为４５ ５８６ ４２０． 参考文献： ［１］ＤＩＮＧ Ｃｕｎ－ｓｈｅｎｇ，ＸＩＡＯ Ｇｕｏ—ｚｈｅｎ，ＳＨＡＮ Ｗｅｉ—ｊｕａｎ．Ｔｈｅ Ｓｔａｂｉｌｉｔｙ Ｔｈｅｏｒｙ ｏｆ Ｓｔｒｅａｍ Ｃｉｐｈｅｒｓ ＥＭ２．ＬＮＣＳ ５６１．Ｂｅｒｌｉｎ Ｓｐｒｉｎｇｅｒ—Ｖｅｒｌａｇ，１９９１：８５—８８． ［２］ ＳＴＡＭＰ Ｍ，ＭＡＲＴＩＮ Ｃ Ｆ．Ａｎ Ａｌｇｏｒｉｔｈｍ ｆｏｒ Ｔｈｅｋ—Ｅｒｒｏｒ Ｌｉｎｅａｒ Ｃｏｍｐｌｅｘｉｔｙ ｏｆ Ｂｉｎａｒｙ Ｓｅｑｕｅｎｃｅｓ ｗｉｔｈ Ｐｅｒｉｏｄ ２ ＥＪ］． ＩＥＥＥ Ｔｒａｎｓａｃｔｉｏｎｓ ｏｎ Ｉｎｆｏｒｍａｔｉｏｎ Ｔｈｅｏｒｙ，１９９３，３９（４）：１ ３８９—１ ４０１． Ｅ３］ 苏 明．周期序列复杂度的分布［Ｄ］．天津：南开大学博士论文，２００４． ［４］ ＲＵＥＰＰＥＬ Ｒ Ａ．Ａｎａｌｙｓｉｓ ａｎｄ Ｄｅｓｉｇｎ ｏｆ Ｓｔｒｅａｍ Ｃｉｐｈｅｒｓ［Ｍ］．Ｂｅｒｌｉｎ：Ｓｐｒｉｎｇｅｒ—Ｖｅｒｌａｇ，１９８６． Ｅ５］ ＭＥＩＤＬ Ｗ．Ｏｎ ｔｈｅ Ｓｔａｂｉｌｉｔｙ ｏｆ ２ 一Ｐｅｒｉｏｄｉｃ Ｂｉｎａｒｙ Ｓｅｑｕｅｎｃｅｓ ＥＪ］．ＩＥＥＥ Ｔｒａｎｓａｃｔｉｏｎｓ ｏｎ Ｉｎｆｏｒｍａｔｉｏｎ Ｔｈｅｏｒｙ，２００５．５１ （３）：１ １５１—１ １５５． Ｅ６］ ＺＨＵ Ｆｅｎｇ—ｘｉａｎｇ，ＱＩ Ｗｅｎ－ｆｅｎｇ．Ｔｈｅ ２－Ｅｒｒｏｒ Ｌｉｎｅａｒ Ｃｏｍｐｌｅｘｉｔｙ ｏｆ ２ 一Ｐｅｒｉｏｄｉｃ Ｂｉｎａｒｙ Ｓｅｑｕｅｎｃｅｓ ｗｉｔｈ Ｌｉｎｅａｒ Ｃｏｍｐｌｅｘｉ— ｔｙ ２ 一１［Ｊ］．Ｊｏｕｒｎａｌ ｏｆ Ｅｌｅｃｔｒｏｎｉｃｓ（Ｃｈｉｎａ），２００７，２４（３）：３９０—３９５． ［７］ 谭林，戚文峰．Ｆ ２上２ 周期序列的ｋ错误序列ｌ－Ｊ］．电子与信息学报，２００８，３０（１１）：２ ５９２—２ ５９５． ［８］ ＧＡＭＥＳ Ｒ Ａ，ＣＨＡＮ Ａ Ｈ．Ａ Ｆａｓｔ Ａｌｇｏｒｉｔｈｍ ｆｏｒ Ｄｅｔｅｒｍｉｎｉｎｇ ｔｈｅ Ｃｏｍｐｌｅｘｉｔｙ ｏｆ ａ Ｂｉｎａｒｙ Ｓｅｑｕｅｎｃｅ ｗｉｔｈ Ｐｅｒｉｏｄ ２“［Ｊ］． ＩＥＥＥ Ｔｒａｎｓａｃｔｉｏｎｓ ｏｎ Ｉｎｆｏｒｍａｔｉｏｎ Ｔｈｅｏｒｙ，１９８３，２９（１）：１４４—１４６． ８－Ｅｒｒｏｒ Ｌｉｎｅａｒ Ｃｏｍｐｌｅｘｉｔｙ ｏｆ ２＂－Ｐｅｒｉｏｄｉｃ Ｂａｌａｎｃｅｄ Ｂｉｎａｒｙ Ｓｅｑｕｅｎｃｅｓ ＺＨＯＵ Ｊｉａｎ—ｑｉｎ 。ＺＨＡＯ Ｑｉ 。ＣＵＩ Ｈｏｎｇ—ｃｈｅｎｇ （１．Ｃｏｍｐｕｔｅｒ Ｓｃｉｅｎｃｅ Ｓｃｈｏｏｌ，Ａｎｈｕｉ Ｕｎｉｖｅｒｓｉｔｙ ｏｆ Ｔｅｃｈｎｏｌｏｇｙ，Ｍａ’ａｎｓｈａｎ ２４３００２，Ａｎｈｕｉ Ｃｈｉｎａ； ２．Ｔｅｌｅｃｏｍｍｕｎｉｃａｔｉｏｎ Ｓｃｈｏｏｌ，Ｈａｎｇｚｈｏｕ Ｄｉａｎｚｉ Ｕｎｉｖｅｒｓｉｔｙ，Ｈａｎｇｚｈｏｕ ３１００１８，Ｃｈｉｎａ） Ａｂｓｔｒａｃｔ：Ｔｈｅ ｌｉｎｅａｒ ｃｏｍｐｌｅｘｉｔｙ ａｎｄ ｔｈｅ ｋ－ｅｒｒｏｒ ｌｉｎｅａｒ ｃｏｍｐｌｅｘｉｔｙ ｏｆ ａ ｓｅｑｕｅｎｃｅ ｈａｖｅ ｂｅｅｎ ｕｓｅｄ ａｓ ｔｈｅ ｉｍ— ｐｏｒｔａｎｔ ｍｅａｓｕｒｅｍｅｎｔ ｏｆ ｋｅｙｓｔｒｅａｍ ｓｅｑｕｅｎｃｅ ｓｔｒｅｎｇｔｈ．Ｂｙ ｓｔｕｄｙｉｎｇ ｌｉｎｅａｒ ｃｏｍｐｌｅｘｉｔｙ ｏｆ ｂｉｎａｒｙ ｓｅｑｕｅｎｃｅｓ ｗｉｔｈ ｐｅｒｉｏｄ ２ ，ｂａｓｅｄ ｏｎ Ｇａｍｅｓ—Ｃｈａｎ ａｌｇｏｒｉｔｈｍ，８一ｅｒｒｏｒ ｌｉｎｅａｒ ｃｏｍｐｌｅｘｉｔｙ ｄｉｓｔｒｉｂｕｔｉｏｎ ｏｆ ２”一ｐｅｒｉｏｄｉｃ ｂｉ— ｎａｒｙ ｓｅｑｕｅｎｃｅｓ ｗｉｔｈ ｌｉｎｅａｒ ｃｏｍｐｌｅｘｉｔｙ ｌｅｓｓ ｔｈａｎ ２ ｉｓ ｄｉｓｃｕｓｓｅｄ．Ｔｈｅ ｃｏｍｐｌｅｔｅ ｃｏｕｎｔｉｎｇ ｆｕｎｃｔｉｏｎｓ ｏｎ ２ 一 ｐｅｒｉｏｄｉｃ ｂａｌａｎｃｅｄ ｂｉｎａｒｙ ｓｅｑｕｅｎｃｅｓ ｗｉｔｈ ８一ｅｒｒｏｒ ｌｉｎｅａｒ ｃｏｍｐｌｅｘｉｔｙ ２ 一。。２ 一。，２ 一 ａｎｄ ２”一。——２” ａｒｅ ｄｅ— ｒｉｖｅｄ ｒｅｓｐｅｃｔｉｖｅｌｙ． Ｋｅｙ ｗｏｒｄｓ：ｐｅｒｉｏｄｉｃ ｓｅｑｕｅｎｃｅ；ｌｉｎｅａｒ ｃｏｍｐｌｅｘｉｔｙ；ｋ－ｅｒｒｏｒ ｌｉｎｅａｒ ｃｏｍｐｌｅｘｉｔｙ；ｋ—ｅｒｒｏｒ ｌｉｎｅａｒ ｃｏｍｐｌｅｘｉｔｙ ｄｉｓ— ｔｒｉｂｕｔｉｏｎ （责任编辑 陈炳权）
