（基础数学专业论文）广义自缩序列特例的扩展及其密码性质.pdf

摘要 本文在广义自缩序列特例的基础上，在有限域上进行扩展，构造了g f ( 3 ) 上的广义自缩序列的特例。它的构造如下： 设 n = ( n o ，n l ，0 2 ，- ) 是g f ( 3 ) 上的n 级m 一序列，顺序地，k = o ，l ，2 ，如果k = o ，则放弃输出； 如果虬= l ，则输出。；如果n * = 2 ，则输出n 眦这样得到输出序列记为 6 = ( 6 0 ，6 1 ，) 可以得到2 3 ”1 为序列b 一个周期。 在第二章中我们通过对其游程的分析，得到了它的重要的密码学性质，主 要结论为： 定理l 在序列b 的连续2 3 “一1 个比特中，长度为- 5 的1 游程0 1 1 1 0 与 2 1 1 1 0 各2 3 个，故序列b 的最小周期为2 扩。 定理2 任意取定k ，3 s k - 5 ，则序列b 的长度为k 的1 游程个数为1 0 2 3 ”一( + 5 ) 个。 定理3 在序列b 的一个周期内，o ，l ，2 出现的频率相等，均为2 3 n 。 定理4 序列b 的线性复杂度l ( b ) 3 ” 在第三章，我们针对构造的序列通过实例证明了定理的正确性和可行性。 关键词：游程；周期；线性复杂度；涉及尺寸。 a b s t r a c t i nt h i sp a p e r ，w ee x p a n dt h ef i e l do ft h es p e c i a lg e n e r a l i z e ds e l f - 8 h r i n k i n gs e q u e n c ei n 3 i t h eo t h e rw o r d ，、v eb u i l das p e c i a lg e n e r a l i z e ds e l f - s h r i n k i n gs e q u e n c ei ng f ( 3 ) t h e yc a nb eb u i l ta 8f o l l o w s l e t = ( “o ，o l ，n 2 ，+ ) a m 一8 e q u e n c eo f d e g r e en o v e r g f ( 3 ) f 0 re 粕h 惫= o ，1 ，2 ，i nc a s en 七= o ，w eg u po u t p u t t i n g ；i nc a s en 女= 1 ，w eo u t p u tn k 一1 ；i nc a s en k = 2 ，w eo u t p u tn 一2 1 w r ec a n g e tt h es e q u e n c e 6 = ( 6 0 ，6 1 ，幻，t ) i ti sc 出1 e dt h es e p e c i a lg e n e r a l i z e ds e l f - s h r i n k i n gs e q u e n c ei ng f ( 3 ) i ti se a s i l ys e e n t h a t2 3 ”一1i so n eo f t h ep e r i o d so f t h es e q u e n c e i nc h a p t e r2 ，w ef i n di t si m p o r t a n tc r y p t o g r a p h yp r o p e r t i e s 。f n l es e q u e n c eb ya n a i n g i t sp a t t e r n s s o m ei m p o r t a n tc o n c l l l s i o n 8a sf o l l 侧s t h e o r e m1 i t i s t w e n t y - t h r e e t h a t t h en u m b e ro f l 一p a t t e r no l l 1 0a l l d2 1 1 1 0 o f l e n 酗hn 一5i n2 3 “1c o n t i n u 0 1 l sb i t so f 6 s ot h el e a s tp e r i o do fbi s2 t3 “ t h e o r e m2f b rt h es e q u e n o e6 ，v k ，3 七s 礼一5 ，i ti s1 0 2 3 “一( 十5 ) t h a tt h en u m b e r o f1 一p a t t e r no fl e i 培t h 七 t h e o r e m3i no n el e a s tp e r i o do f6 ，w ec a n 丘n dt h a 七t h ep r o b a b i l i t yo f0 ，1 ，2i se q u a l ， a n d i t i s2 3 n2 t h e o r e m4t h el i n e a rc o m p l 嘶t yo f6s a t i s f ) rt h ei n e q u a l i t y 三( 6 ) 3 ” i nc h a p t e r3 ，w eg i v es e v e r a le x a m p l e st op r o o fs o m ep r o p e r t i e so fo u rs e q u e n c e k e yw o r d ：p a t t e r n ；p e r i o d 】l i n e a rc o m p l e x i t y ；l e n g t ho fd i g i t u 郑重声明 本人的学位论文是在导师指导下独立撰写并完成的，学位论文没有剽窃、 抄袭等违反学术道德、学术规范的侵权行为，否则，本人愿意承担由此产生的 一切法律责任和法律后果，特此郑重声明 学位论文作者：j 羚 6 年伊月弘日 第一章引言 本文主要研究广义自收缩序列的特例扩展到g f ( 3 ) 上的情形，研究此类序 列的最小周期、线性复杂度等密码学性质。 d o n c o p p e r s m i t h 1 1 在1 9 9 3 年给出了互缩生成器的模型，他生成的互缩序列 如下： 设 o = ( o o ，n l ，n 2 ，t ) ， 6 = ( ，h ，6 2 ，) 分别为g f ( 2 ) 上的a 级和b 级m 一序列； 又设 9 c d ( 2 “一1 ，2 b 一1 ) = 1 ；bs2 a 一1 对于t = o ，l ，2 ，如果玩= l ，则输出毗；否则放弃输出。如此得到了输出序列 z = ( 匈，乱，砘，) 称。为互缩序列。 它主要有如下性质； 1 互缩序列z 的最小周期为2 b 一1 ( 2 一1 ) ； 2 互缩序列。的线性复杂度l 为：且2 日一。 3 后没有发 现自缩序列的最小周期小于2 n 在 3 j 中作者给出了广义自缩序列的概念，它的定义如下 设 n = ( n o ，n 1 ，0 2 ，) 是g f ( 2 ) 上的n 级m 一序列。设 g = ( 9 0 ，9 1 ，一，如一1 ) g f ( 2 ) ” 序列”= ，”，忱，) 使得 = 9 0 0 k + 9 1 n 女一1 + 。+ g n l n 一n + 1 ( 即当g = o 时 是全。序列；当g = ( 1 ，o ，o ，o ) 时是。；当g 为其他情 形时口是n 的平移序列。) 对于七= o ，1 ，2 ，如果n 女= 1 ，则输出，否则 放弃输出。这样得到输出序列记为6 ( ”) 或6 ( g ) ，称其为广义自缩序列。 我们称序列族 b ( n ) = 6 ( g ) ，g g f ( 2 ) ” 为基于m ，序列n 的广义自缩序列族。 广义自缩序列有两个性质： 1 w i l l im e i e r 给出的自缩生成器生成的自缩序列都是广义自缩序列； 2 广义自缩序列的最小周期都是2 一t 的因子。 广义自缩序列中，大部分序列的最小周期都达到了2 一，而当序列的最小 周期为2 ”1 时，其线性复杂度则大于2 ”2 故广义自缩序列中大部分序列都 有好的密码性质，但不能保证所有的都有。故【3 】中给出了一个广义自缩序列 的特例，它的定义如下： 设 = ( n o ，l ，n 2 ，- ) 为g f ( 2 ) 上的n 级m 一序列。顺序地对于南= o ，l ，2 ，如果n k = 1 则输出 。* 一。；如果= o 则放弃输出。这样得到输出序列 6 = ( 6 0 ，6 1 ，6 2 ，) 则是广义自缩序列的一种特例。 广义自缩序列特例有较好的游程分布，这使它们有了较大的最小周期，由 于它们的最小周期为2 的方幂，进而有较大的线性复杂度。 它的主要性质有： 1 序列b 的最小周期在所给的条件下为2 一- ； 2 序列b 的线性复杂度l 在所给的条件下满足：三( 6 ) 2 一z ； 3 序列b 的长度为k 的1 游程共有2 一。个； 4 序列b 的长度为1 的。游程的个数为u ，则2 ”4 2 u 2 n “+ 8 。 在 3 】中1 3 2 页定理9 2 7 中，由于作者计算错误，得到2 n 一2 茎u 茎2 n s + 8 ， 进而得到“长度为1 的1 游程数量大约是长度为1 的。游程数量的2 倍”的错 误结论，但更正为2 一a 一2 墨2 n _ 4 + 8 后，此条不好的性质将会不存在。 而本文将此特例由g f ( 2 ) 扩展到g f ( 3 ) 上，则得到了一个比原序列的最小 周期与线性复杂度都要大的结果，此结果具有更好的密码性质，且适用于软件 实现。 3 第二章广义自缩序列特例及其扩展 本章主要有四个部分内容。首先在2l 介绍一下m 一序列及其主要性质， 然后在22 比较详细的介绍【 中的广义自缩序列的特例，在23 介绍其扩展 序列的构造及其最小周期和游程分布，在24 中介绍扩展序列的几个重要密 码性质。 52 1m 一序列及其密码学特性 我们已经知道，在g f ( g ) 上由n 次不可约特征多项式生成的序列的最小周 期整除q ”一1 。则有一种特殊的序列，它们的最小周期达到了r l 。 定义2 1 1 设 = ( 咖，0 1 ，n 2j - ) 是g f ( 口) 上的n 级线性移位寄存器序列，它满足线性递归关系式 机+ 0 1 0 女一l + c 2 0 女一2 + - - + o en = 0 ，南2 竹 其中o 。如果n 的周期是矿1 ，我们就说。是最长q 元n 级线性移 位寄存器序列，简称m - 序列。 m 一序列有许多出色的密码学特性，但同时在所有最小周期相同的序列中线 性复杂度最低。这些都源于深刻的代数机理，- 序列的极小多项式的任一个 根的阶都是q t c l ，我们称其为有限域上的本原元，称一序列的极小多项式为 本原多项式。 g f ( 口) 上的n 级n 卜序列s 主要有以下性质： 性质l 序列s 的最小周期为矿一1 ，线性复杂度为n 性质2 对任意z g f ( q ) ，z o ，在s 的一个最小局期内z 出现q 一次，o 出现q ”11 次 性质3 序列s 的极小多项式生成所有的非。序列均为一序列，它们是序 列s 的平移等价序列 4 性质4 设序列s 的k 个平移等价序列屯，j = l ，2 ，一，任取k 个常数嘶 g f ( g ) ，j = 1 ，2 ，。则序列 k 叩| ，= 1 或为。序列，或为s 的一个平移等价序列。 性质5 对于k ，15 5n ，称 丐= ( 0 ，s j + 1 ，s j 十1 ) g f ( q ) 。 为序列s 的一个k 维状态向量。则在连续矿1 个k 维状态向量丐，j = o ，旷一2 中，每个非。的向量。g f ( g ) 出现q 一次，o 向量出现矿一1 次 性质6 如果 岛一l n ，( 勺，勺+ 1 ，十 1 ) = ( b ，n ，一，n ) ，s j + 女。 是一个长为k 的a 游程。将序列s 的一个最小周期首尾相连，则游程分布如下： 游程的总个数为佃一1 ) 口“；对于1s 女兰n 一2 ，每个n g ，长为k 的a 游程有( q 1 ) 2 q ”一“个；长为m 1 的。游程有q - 1 个；对于每个。o ，长 为n - l 的a 游程有q - 2 个，长为n 的a 游程有1 个。 性质7 记序列s ( h ，d ) 为： s ( ，d ) = ( 8 d ，8 d + ，8 “2 ，- ) 称s ( h ，d ) 为s 的h 间隔采样序列，则s ( ，d ) 是m - 序列当且仅当9 础( ，q “一1 ) = 1 ； 当g d 旷一1 ) = l 时，z 一一序列s ( ，d ) 的极小多项式与起始位置d 无关，仅仅 与采样间隔h 有关 性质8 所有间隔采样序列s ( ，d ) ，h = l ，一，矿一2 ，d = o ，q ”2 ， 鲥( h ，矿一1 ) = l ，遍历了所有的n 级m - 序列。 5 一女聃 勺0 称 4 当给定g f ( 口) 上一个本原多项式，( z ) ，任取一个多项式9 ( z ) ，9 ( 。) o ， d e 9 ( 口) n 一2 ；+ 3 至札一2 。取 k = ( k ，6 。+ 1 ，b 。+ 七+ 1 ) r 则在集合 佤13 = o ，1 ，2 ，2 ”1 1 ) 中，“序列b 的长度为k 、涉及尺寸为n 一2 的1 游程”的个数等于1 或3 。 引理2 2 8 任意取定k 满足：七2 ；2 七+ 3 n 一2 ；七+ 3 曼礼一2 。取 6 。= ( k ，6 s + 一，k + k + 1 ) 则在集合 瓜fs = o ，1 ，2 ，2 ”1 1 ) 中，“序列b 的长度为k 、涉及尺寸不超过n 一2 的1 游程”有奇数个。 定理2 2 9 设n 为奇数，系数c 1 ，c 3 ，c n - 4 ，靠一。中有偶数个1 ，一1 c n 一2 = 1 0 。则序列b 在连续2 “一1 个比特中，长度为学的1 游程有奇数个，因此序列 b 的最小周期为2 一，。 定理2 2 1 0 设n 为奇数，系数c 1 ，c 3 ，_ 4 ) 靠一2 中有偶数个1 ，一1 一2 = 0 0 。则序列b 在连续2 1 个比特中，长度为堡的1 游程有奇数个，因此序列 b 的最小周期为2 一- 。 定理2 2 1 1 设n 为奇数，系数c l ，c 3 ，c n _ 4 一。中有奇数个1 ，一1 一2 = 1 1 。则序列b 在连续2 ”_ 1 个比特中，长度为n 笋的1 游程有奇数个，因此序列 b 的最小周期为2 ”1 。 定理2 2 1 2 设n 为奇数，系数c ，c 3 ，_ 4 ，c 。一2 中有奇数个1 ，一1 一2 一 o o 。则序列b 在连续2 “1 个比特中，长度为字的l 游程有奇数个，因此序列 b 的最小周期为2 1 。 定理2 2 1 3 设n 为偶数，系数c ，c 3 ， 或o o 。则序列b 在连续2 ”1 个比特中， 9 ，c n “一1 中有偶数个1 ，岛一1 一2 = 0 1 长度为字的l 游程有奇数个，因此 序列b 的最小周期为哥一。 定理2 2 1 4 设n 为偶数。系数c ，龆， 或0 0 。则序列b 在连续哥- 1 个比特中 序列b 的最小周期为2 一- 。 ，c 。m 一j 中有奇数个1 ，一1 “一。二= 叫 长度为雩的l 游程有奇数个，因此 以上的6 个定理已经证明了序列b 在全部1 6 种情形中的8 种情形下最小 周期为2 一。剩下的8 种情形是： ( 1 ) 为奇数，系数c 1 ，国，自一2 中有偶数个1 ，一1 一2 = 1 1 或0 1 ； ( 2 ) n 为奇数，系数c ，盘，一，“岛一2 中有奇数个1 ，一1 2 1 0 或0 1 ； ( 3 ) n 为偶数，系数q ，c 3 ，_ 3 、l 中有偶数个l ，1 岛一f1 l 或l o ； ( 4 ) n 为偶数，系数c l ，c 3 ，自q 一1 中有奇数个l ，岛一1 一2 = 1 1 或1 0 似乎在这8 种情形下仍然能证明序列b 的最小周期为2 1 ，只不过需要化 为更加精细的子情形来讨论讨论过程略。 所以我们可以说在一定条件下上述广义自缩序列的特例的最小周期为2 一， 定理2 2 1 5 任意取定k ，1 兰k 兰学，则序列b 的长度为k 的1 游程共有 2 n “_ 3 个。 定理2 2 1 6 当n 为奇数时，序列b 的1 游程的最大长度不超过n 一2 + 掣； 当n 为偶数时，序列b 的l 游程的最大长度不超过n 一2 + 2 。 定理2 2 1 7 设某个固定的t ，使得m = 吣2 = l ，此时得到序列b 的一个 输出比特k 一。一l 。则想要得到序列b 的长度为1 的。游程6 。1 6 。= 1 0 1 ， 当且仅当序列a 在以下各种互不重台的情形中； 情形a 1t m + 1 a 蚪d f - 3 m + 4 = 1 0 1 1 1 ； 情形a 2m 吼1 n o 。川n 卅= 1 毗1 0 1 ； 情形b 1 吼。州- 。抖k + 5 毒l o l 仉l 吡； 情形b 2 kn 8 。+ 5 = 1 l l o t l o l 。 1 0 其中o k 是长度为k 的。串，2 。 定理2 2 1 8 设序列b 的长度为1 的。游程的个数为u ，则2 7 一一2s “s 2 n a + 8 。( 原书中为2 n 一2s 珏曼2 n 一5 + 8 ，而导出“长度为1 的1 游程数量 大约是长度为1 的。游程数量的2 倍”的错误结论，其实长度为1 的1 一游程和 。一游程的数量基本平衡。) 2 3广义自缩序列特例的扩展 在本节中我们根据上节的构造，将广义自缩序列扩展到g f ( 3 ) 上，然后考 察其性质。 定义2 3 1 设 n = ( o o ，o l ，n 2 ，) 是g f ( 3 ) 上的n 级m _ 序列，n 7 ，顺序地，k = o ，1 ，2 ，如果o f o ，则放 弃输出；如果n 。= 1 ，则输出口；如果n t = 2 ，则输出n m 。这样得到的输出序列 记为 b = ( ，6 1 ，6 2 ，) 可以得到2 妒一，为序列b 一个周期。 下面我们研究它的游程性质： 引理2 3 2 设某个固定的t ，使得n f n 州= l ，此时得到序列b 的一个输出 比特6 。：1 。则当且仅当在以下4 种情形中，得到长度为1 的1 游程+ 1 + ( + 指 。或2 ) ： ( 1 ) o 一1 0 血件1 0 t + 2 n 汁3 = 0 1 1 0 0 ； ( 2 ) 0 亡一1 t o + 1 n + 2 0 抖3 = 2 1 1 0 0 ； ( 3 ) o t 一1 0 o 抖1 0 t + 2 口t + 3 = 0 1 1 0 1 ； ( 4 ) t i n t n t + l o t + 2 t + 3 = 2 1 1 0 1 。 其中( 1 ) ( 3 ) 得到0 1 0 ，( 2 ) ( 4 ) 得到2 1 0 。 引理2 3 3 设某个固定的t ，使得。f _ l ，o = 2 ，此时得到序列b 的一个输出 比特6 s = n f l 。则当且仅当在以下5 种情形中，得到0 l o ： ( 1 ) o t 一1 o 抖1 t + 2 n 冲3 n t 十4 = 0 1 0 2 0 0 ； ( 2 ) t 一1 0 o + i n t + 2 n 蚌3 0 t + 4 = 0 1 0 2 0 l ； ( 3 ) n t 一1 n 口t + 1 0 t + 2 0 抖3 = 0 1 0 2 2 ； ( 4 ) n t 一1 n o t + 1 件2 0 件3 吼+ 4 = 0 1 2 2 0 1 ； ( 5 ) o 一l o n 蚪i n t + 2 n t + 3 毗+ 4 = 0 1 2 2 0 0 。 当且仅当在以下5 种情形中，得到0 1 2 ： 2 3 4 5 o t i n t n + 1 t + 2 n 抖3 = 0 1 0 2 1 ； n t l o t n + 1 凸t + 2 n t + 3 毗+ 4 = 0 1 0 2 0 2 n 一l 口f n e + 1 血t + 2 口t + 3 = 0 1 2 2 1 ； n t n 一 l + 1 0 t + 2 n t + 3 = 0 1 2 2 2 l o t 吼+ i n t + 2 0 抖3 吼+ 4 = 0 1 2 2 0 2 。 当且仅当在以下5 种情形中，得到2 1 2 ( 1 ) n 一l o o 件1 0 件2 q 抖3 = 2 1 0 2 1 ； ( 2 ) o 一l t + 1 血t + 2 n h 3 = 2 1 2 2 1 ； ( 3 ) o 一l o t 件1 n c 十2 n 蚪3 0 l + 4 = 2 1 0 2 0 2 ； ( 4 ) 口t l o f n 汁1 8 t + 2 n h 3 = ：2 1 2 2 2 ； ( 5 ) o 一1 毗+ 1 血t + 2 n 抖3 啦+ 4 = 2 1 2 2 0 2 。 当且仅当在以下5 种情形中，得到2 1 0 2 3 n t n 一 0 t l n n t + 1 0 t + 2 0 抖3 吼+ 4 = 2 1 0 2 0 0 吼n + d n + n t + 2 n f + 3 n t + 4 = 2 1 0 2 0 o t + 2 “抖3 = 2 1 0 2 2 ； 4 ) o 一l t n 。+ l o t + 2 n 抖3 毗+ 4 = 2 1 2 2 0 ( 5 ) n 一1 n n 抖1 口蚪2 凸+ 3 0 抖4 = 2 1 2 2 0 0 。 引理2 3 4 若生成序列b 有长度大于1 的1 游程，则除最后两个1 以外的 其他1 必为1 生成。 证明只需证明最简单的情况，即长度为2 和3 的1 游程即可。 先证明长度为2 的1 游程的情况。 ( 反证法) 若第一个l 不为l 生成，则必为2 生成，不妨设原序列为1 * 2 ( + 为。或2 ) 。 若十为o ，则有三种情况( 1 ) 1 0 2 2 ( 生成“1 0 ”，舍去) ；( 2 ) 1 0 2 1 ( 生成 “1 2 ”舍去) ；( 3 ) 1 0 2 叶( 十为o ，l 或2 ) ，若为1 0 2 0 0 ，生成“l o ”，舍 去；若为1 0 2 0 1 ，生成“1 0 ”，舍去；若为1 0 2 0 2 ，生成“1 2 ”，舍去。故 必 不为o 。 若 为2 ，则有三种情况( 1 ) 1 2 2 2 ( 生成“1 2 ”，舍去) ；( 2 ) 1 2 2 l ( 生成 “1 2 ”舍去) ；( 3 ) 1 2 2 0 宰( 为o ，1 或2 ) ，若为1 2 2 0 0 ，生成“l o ”，舍 去；若为1 2 2 0 l ，生成“1 0 ”，舍去；若为1 2 2 0 2 ，生成“1 2 ”，舍去。故 必 不为2 。故* 必为1 现在我们说明一下长度为3 的l 游程的情况。 长度为3 的1 游程和长度为2 的l 游程相比，只是增加了一种特殊的情 况，就是0 1 1 2 2 + 十和2 1 1 2 2 + + 这两种情况。这两个特殊的情况生成游程0 1 1 1 + 和2 1 1 1 ，其中+ 为。或2 。则我们可以看到他们最短要生成长度为3 的1 游 程，不包含在上述的情况之中，引理得证。 定理2 3 5 取定3 冬奄佗一5 ， ( a ) 若想得到序列b 的一个长度为k 的1 游程 k 一1 以以+ 1 ，以+ 一1 坑+ = 0 1 1 1 0 当且仅当在以下9 种情况下( 为表达方便，我们可令原序列为 1 3 以下各种情况和这种情况的原序列相同) ： ( 1 ) 0 1 1 1 1 0 l + ；( 2 ) 0 1 1 + 1 1 0 0 十 ( 3 ) 0 1 1 - 1 0 2 2 + ；( 4 ) 0 1 1 1 0 2 0 0 ( 5 ) 0 i l1 2 0 0 + ；( 6 ) 0 1 1 1 2 0 l ( 7 ) o l l1 0 2 0 l ；( 8 ) 0 1 1 1 2 2 0 l m f 9 ) 0 1 1 一1 2 2 0 0 。 ( b ) 若生成k 一1 b 曲 f 1 1 2 1 1 0 1 4 f 3 1 2 1 l - 1 0 2 2 $ 6 $ + k 一1 k b = 2 1 1 - 1 0 ( 2 ) 2 1 f 4 ) 2 l ( 5 ) 2 1 1 1 2 0 弧；( 6 ) 2 l l ( 7 ) 2 1 1 1 0 2 0 1 ；( 8 ) 2 1 1 f 9 ) 2 1 1 1 2 2 0 0 。 ( c ) 若生成k 1 6 。k + 1 虬+ t 一1 以舳= 2 1 1 ，1 2 ( 1 ) 2 1 1 1 2 1 + ；( 2 ) 2 1 1 ( 3 ) 2 1 1 1 0 2 1 + ；( 4 ) 2 1 1 ( 5 ) 2 1 1 1 2 2 1 ；( 6 ) 2 l l - f d ) 若生成札、1 k k + 1 以+ 一1 屯+ t = 0 1 1 - 1 2 ( 1 ) 眦i 1 2 1 ；( 2 ) o l l ( 3 ) 0 1 1 1 0 2 1 + ；( 4 ) o l l ( 5 ) o n 1 2 2 1 ；( 6 ) o l l 、 其中+ 表示g f ( 3 ) 上任一元。 但是我们没有分析当；l ，2 时的情况， 当 一1 时，我们只须对引理2 32 和2 0 1 0 的情况有3 p 一5 + 4 ，铲一1 3 掣“ 0 1 2 的情况有3 3 ”5 + 23 6 = 1 13 n “ 2 1 0 的情况有33 “一5 + 4 分“= 1 3 - 铲“ 2 1 2 的情况有3 ，3 n 一5 + 2 3 ”6 = 1 1 3 n “ 当且仅当在以下9 种情况下t l 1 0 0 ： 1 0 2 0 0 ： 1 2 0 1 ： 1 2 2 0 1 ： 当且仅当在以下6 种情况下 1 2 0 2 ： 1 0 2 0 2 ： 1 2 2 0 2 。 当且仅当在以下6 种情况下 1 2 0 2 ： l ( 】2 0 25 1 2 2 0 2 。 下面我们对这两种情况进行分析。 3 进行分析。我们发现： 种； 种； 种； 种。 则长度为1 的1 游程共有4 8 - 驴一6 个。 当：2 时，我们对定理2 3 5 进行分析，并且对照引理2 3 4 的情况，我们 发现分析长度为2 的1 游程的时候要去掉引理2 3 4 中长度为3 的情况，对应 定理2 3 5 为( a ) ( b ) 中的( 8 ) ( 9 ) 和( g ) ( d ) 中的( 5 ) ( 6 ) 。则去掉之后可以发现，长 度为2 的1 游程的个数为6 6 3 ”7 。 定义2 3 6 在定理2 3 5 各种情况中，数字的个数称为此类情况的涉及尺 k + 4 寸。( 例：丽f 简+ 的涉及尺寸为k + 4 ) 。 引理2 3 7 涉及尺寸。墨n 时，此类情况在一个最小周期中出现的次数为 3 “一o ，a n 。 定理2 3 8 由定理2 3 5 ，在b 的连续2 t3 “一1 个比特中，长度为n 一5 的1 游 程0 1 1 l o 与2 1 1 1 0 各2 3 个，故序列b 的最小周期为2 3 “。 证明由于2 3 为素数故只能出现在一个周期之中。定理得证 定理2 3 9 当礼27 时，序列b 的长度为1 的1 游程有4 8 妒一6 个；序列b 的长度为2 的1 游程有6 6 驴一，个；当3 k 1 ) ： ( 1 ) 2 1 0 k 1 1 ；( 2 ) 2 1 0 k 1 0 2 ； ( 3 ) 2 0 2 0 七1 1 ；( 4 ) 2 0 2 0 k 1 0 2 ； ( 5 ) 2 1 2 仉1 1 ；( 6 ) 2 1 2 如1 0 2 ； ( 7 ) 2 2 2 0 女1 1 ；( 8 ) 2 2 2 0 1 0 2 。 若想得到序列b 的一个长度为l 的。游程1 0 2 ，则当且仅当在以 下1 1 种情形中( 其中k 2 ) ： ( 1 ) 1 1 0 k 2 1 ；( 2 ) 1 1 0 女2 0 2 ；( 3 ) 1 0 2 0 k 2 1 ； ( 4 ) 1 0 2 0 k 2 0 2 ； ( 5 ) 1 1 2 吼2 1 ；( 6 ) 1 1 2 0 2 0 2 ； ( 7 ) 1 2 2 0 女2 1 ；( 8 ) 1 2 2 0 2 0 2 ； ( 9 ) 1 0 2 2 1 ；( 1 0 ) 1 0 2 2 2 ；( 1 1 ) 1 0 2 2 0 2 。 若想得到序列b 的一个长度为1 的。游程2 0 2 ，则当且仅当在以 下1 1 种情形中( 其中k 2 ) ： ( 1 ) 2 l o 2 1 ；( 2 ) 2 l 叽2 0 2 ； ( 5 ) 2 1 2 0 k 2 1 ；( 6 ) 2 1 2 0 女2 0 2 ( 9 ) 2 0 2 2 1 ；( 1 0 ) 2 0 2 2 2 ； ( 3 ) 2 0 2 叽2 1 ； ( 7 ) 2 2 2 0 k 2 1 ； f 1 1 1 2 0 2 2 0 2 。 ( 4 ) 2 0 2 0 七2 0 2 ( 8 ) 2 2 2 0 七2 0 2 定理2 3 1 5 设序列b 的长度为1 的。游程的个数为u ，则根据引理2 3 7 可知 4 6 3 n 一6 一1 6 札4 6 3 “一6 + 1 2 0 52 4广义自缩序列特例的扩展的几个重要性质 上一节我们通过游程分析得到了序列的最小周期，现在分析序列的另一个 密码学性质，即序列的线性复杂度，也就是生成序列的极小多项式的次数，本 节主要解决这一问题。 定理2 4 1 在序列b 的一个周期内，o ，1 ，2 出现的频率相等，均为2 3 n 。 证明序列b 中元素有两种生成方式：由l 生成和由2 生成。 生成1 的情况有1 l ，1 0 2 ，1 2 2 ，1 1 2 ，由于a 为m 一序列，则在一个最小周期内1 l 出现3 “一2 次，1 0 2 ，1 2 2 ，1 1 2 出现了3 “一3 次，则一共出现了2 3 n 一2 次。 同理，2 ，o 也出现了2 3 n 一2 次，定理得证。 引理2 4 2 【3 j 设序列s 的周期为n ( 未必是最小周期) ，记以下两个多项式 他) = 丽吲班丽 则s ( 。) 是序列s 的极小多项式，且s ( 。) = 籍。 定理2 4 3 序列b 的线性复杂度l ( b ) 3 n 。 证明由引理2 4 2 知，序列b 的极小多项式 f k 、 l 一。2 3 1 ( 1 + 。) 3 1 ( 1 一z ) 3 ”1 7 ( 叫2 面丽i 弦可万弋珂2 面丽毫驴专车哥商确 其中g c d ( a b ) 为a 与b 的最大公约数，s ( z ) 为序列b 的生成函数。 故，( z ) 必为( 1 + z ) 。( 1 一z ) 6 的形式。若，( z ) 次数小于3 n ，则as3 n ， 6 3 “。即 ( 1 + z ) 23 2 ( 1 一z ) 2 3 2 s 2 旷1 ( z ) 设s 2 矿。1 ( z ) = ( 1 + 。) 2 - 驴- 2 ( 1 一。) 23 2 ( z ) ，其中 ( z ) 的次数不超过2 3 n 。则 s 23 1 ( z ) = ( 卜z 4 伊。) 忍( z ) = ( z ) + z 43 2 2 h ( z ) 1 8 由于h ( z ) 的次数不超过2 3 ”，而z as ”2 2 ( z ) 的次数不小于4 3 n ，而 s ( z ) 为生成函数，故有一个长度至少为 4 3 ”一2 2 3 “2 1 = 2 3 “一2 一l 的。游程，而，( z ) 的次数又小于3 “_ ，矛盾。故l ( b ) 3 n 。定理得证。 我们发现，由于生成的序列是自缩序列，它们的线性复杂度虽然增大很多， 但是它们的周期减小了，所以我们就要想办法弥补这样一个缺陷。我们有下列 的方法： 定义2 4 4 对g f ( 3 ) 上的广义自缩序列 6 = ( 6 0 ，6 1 ，6 2 ，) 取 ( j 1 ，如，一，血) ， 1 j 1 j 2 1 日寸 其最小周期将大于原序列a 的最小周期p ( n ) ，其最长的1 一 游程的长度不小于扎一1 + 半个，因此其线性复杂度 工。n 一1 + 掣 证明由于坟取遍一个最小周期时，定义2 4 4 中的每个五也取遍了一个最 小周期。而b 的一个最小周期中有2 3 “一2 个1 ，故共有2 七3 n 一。个1 多出，故 2 七3 “一2 + 2 3 n 1 1 q 为c 的一个周期，即 p ( c ) = 2 ( + 3 ) 3 2 而b 中长度最长的1 一游程仅有一个，且长度不小于n 一1 ，令其为 ( 坟，饥+ l ，- 一，玩+ 。一1 ) = ( 2 ，1 ，1 ，一，1 ) 则玩= 2 ，输出2 和连续k 个1 ；对应6 = 1 ，则输出至少连续k 个l ；对 应于6 t + 2 = 1 ，c 输出至少k - 1 个1 ；对应于6 = l ，c 至少输出1 个 1 ；对应于 以+ b + 1 = 6 e + k + 2 = = 也+ n 一1 = 1 c 至少输出连续n k - 1 个1 ，共n 一1 + 坐笋个1 ，故最长1 一游程的长度不 小于n 一1 + 半竽，故其线性复杂度 定理得证 工。n 一1 + 堡垡堕 2 0 第三章广义自缩序列特例的例子 在前面的章节中我们研究了广义自缩序列的特例的情况，分析了它的密码 学性质。本节我们通过几个例子来简单的验证一下这些性质的正确性。 例3 1 我们取n = 7 的情况，当n = 7 时我们取g f ( 3 ) 上的多项式，( 。) = l + 。+ 茁3 + z 7 作为极小多项式，我们可以用它来生成一个序列。如果初始向量 为( 1 ，1 ，l ，1 ，1 ，l ，1 ) ，我们通过程序( 附加程序见2 6 - 2 7 页) 生成的序列的一个最小 周期如下： 1 1 1 1 1 1 1 0 1 0 2 2 0 0 1 1 2 1 2 2 0 0 0 1 1 0 0 2 1 2 1 0 1 1 0 1 2 0 2 1 1 0 1 2 1 2 1 0 1 0 1 0 1 0 0 1 2 0 2 1 2 2 2 0 1 1 1 2 1 2 2 2 1 2 0 1 1 0 0 1 0 吡1 2 0 1 0 0 1 1 0 2 2 1 0 0 1 2 2 1 2 2 0 0 2 2 0 2 0 0 1 0 1 1 0 2 0 2 2 0 0 1 0 ( ) 0 1 2 1 0 1 1 2 2 1 2 2 2 1 1 1 0 0 0 1 1 1 0 2 0 0 0 2 0 0 2 1 2 2 1 0 1 2 0 0 2 0 0 0 1 2 1 2 2 0 1 2 2 2 0 2 2 0 2 0 1 0 1 2 1 2 2 2 2 1 1 2 1 2 0 0 0 2 2 0 2 2 1 0 2 1 2 0 0 0 0 1 1 0 2 0 0 1 1 1 1 2 0 2 n 2 2 1 0 2 2 0 2 0 2 2 2 0 1 1 2 1 2 0 2 1 1 1 0 0 2 2 0 0 0 0 0 1 0 0 2 1 2 2 2 2 2 0 0 2 2 2 0 2 2 1 1 1 2 0 0 2 0 2 1 0 1 1 0 2 1 1 0 1 0 0 0 2 0 0 0 0 0 0 1 2 1 1 0 2 0 2 0 2 1 2 0 2 0 0 2 0 1 0 1 1 2 1 1 2 0 1 2 2 2 1 1 0 1 2 2 1 2 1 1 2 1 2 1 2 1 0 2 2 2 1 1 2 0 0 2 2 0 0 2 1 2 0 0 1 2 2 2 0 1 0 2 1 0 2 0 2 2 2 1 0 2 0 1 1 0 1 1 0 2 2 0 1 2 0 2 0 1 0 2 1 2 0 2 1 2 0 1 1 2 1 0 2 0 2 加0 2 2 1 1 2 0 2 叽2 0 0 1 0 0 l 0 0 2 0 0 1 1 2 0 0 1 2 0 1 1 2 0 1 1 2 2 2 0 1 2 0 0 2 2 1 2 0 2 2 2 0 0 2 1 0 2 1 2 2 1 2 2 1 2 0 0 0 1 0 2 1 2 2 0 0 1 0 2 1 0 1 1 1 1 2 2 0 0 0 2 0 1 1 2 0 2 0 0 0 2 2 1 1 0 2 0 1 1 1 0 2 1 2 1 0 0 2 2 0 2 1 2 2 1 1 0 0 1 0 1 0 2 0 0 0 0 2 1 0 1 1 2 0 0 0 0 2 0 1 0 0 2 1 0 1 0 0 2 2 0 1 2 1 1 1 2 0 1 1 1 0 1 2 1 0 0 1 2 0 0 0 0 0 2 2 1 0 1 1 2 1 2 u 2 2 1 2 0 1 2 2 1 2 0 2 1 0 2 2 2 2 0 0 1 0 1 2 2 0 1 2 1 0 2 1 2 1 2 1 1 1 0 0 1 0 2 2 0 1 0 2 0 1 1 2 2 0 2 2 0 0 2 2 1 1 1 1 1 2 1 0 0 1 1 1 2 2 0 1 2 0 1 1 0 2 2 2 2 1 2 2 1 1 1 2 2 1 1 2 2 2 0 2 1 1 1 2 l l l 0 1 0 1 0 2 2 1 2 2 2 2 0 2 1 0 2 1 0 1 2 0 2 0 2 2 0 2 2 2 2 0 2 2 2 0 2 0 0 2 2 2 2 0 1 0 1 2 2 1 0 0 2 0 1 1 1 1 1 2 0 1 2 0 1 2 2 0 0 2 1 1 1 2 0 2 0 2 1 1 1 1 2 0 0 0 2 0 2 0 0 1 2 2 0 2 2 1 2 0 0 1 0 1 0 1 1 2 2 0 0 1 1 1 2 1 1 0 1 0 2 1 1 2 0 1 0 1 0 2 1 2 1 1 2 0 0 0 1 1 1 2 0 2 2 0 0 0 1 2 2 1 0 1 1 1 2 1 0 1 0 2 2 2 1 0 0 2 2 2 0 0 1 2 2 1 1 0 2 2 2 0 0 0 0 1 0 1 1 2 0 2 1 2 1 0 2 0 1 2 2 2 2 0 1 2 2 1 1 1 1 0 0 0 2 0 2 1 2 2 0 2 2 2 1 1 1 1 2 1 2 l 0 0 1 0 2 1 1 0 2 2 1 1 2 2 0 2 0 2 1 0 2 0 1 0 1 0 0 0 0 2 1 1 0 2 0 0 2 0 2 2 2 2 2 0 1 1 0 0 0 1 2 0 1 0 0 2 0 1 0 2 0 0 2 1 1 0 0 2 1 0 0 1 2 1 2 1 1 0 1 2 0 0 0 2 1 1 1 1 1 1 2 2 2 1 2 1 0 2 1 0 0 0 2 1 0 0 2 1 2 0 1 0 0 0 2 2 1 2 2 0 1 1 0 1 2 2 0 0 0 0 2 2 2 2 2 2 2 0 2 0 1 1 0 0 2 2 1 2 1 1 0 0 0 2 2 0 0 1 2 1 2 0 2 2 0 2 1 0 1 2 2 0 2 1 2 1 2 0 2 0 2 0 2 0 0 2 1 0 1 2 l l l 0 2 2 2 1 2 1 1 1 2 1 0 2 2 0 0 2 0 0 2 2 1 0 2 0 0 2 2 0 1 1 2 0 0 2 1 1 2 1 1 0 0 1 1 0 1 0 0 2 0 2 2 0 1 0 1 1 0 0 2 0 0 0 2 1 2 0 2 2 1 1 2 1 1 1 2 2 2 0 0 0 2 2 2 0 1 0 0 0 1 0 0 1 2 1 1 2 0 2 1 0 0 1 0 0 0 2 1 2 1 1 0 2 1 l 1 0 1 1 0 1 0 2 0 2 1 2 1 1 1 1 2 2 1 2 1 0 0 0 1 1 0 1 1 2 0 1 2 1 0 0 0 0 2 2 0 1 0 0 2 2 2 2 1 0 1 2 2 1 1 2 0 1 1 0 1 0 1 1 1 0 2 2 1 2 1 0 1 2 2 2 0 0 1 1 0 0 0 0 0 2 0 0 1 2 1 1 1 1 1 0 0 1 1 1 0 1 1 2 2 2 1 0 0 1 0 1 2 0 2 2 0 1 2 2 0 2 0 0 0 1 0 0 0 0 0 0 2 1 2 2 0 1 0 1 0 1 2 1 0 1 0 0 1 0 2 0 2 2 1 2 2 1 0 2 1 1 1 2 2 0 2 1 1 2 1 2 2 1 2 1 2 1 2 0 1 1 1 2 2 1 0 0 1 1 0 0 1 2 1 0 0 2 1 1 1 0 2 0 1 2 0 1 0 1 1 1 2 0 1 0 2 2 0 2 2 0 1 1 0 2 1 0 1 0 2 0 1 2 1 0 1 2 1 0 2 2 1 2 0 1 0 1 2 0 0