（应用数学专业论文）函数域上的格基约化算法和多序列线性反馈移位寄存器综合.pdf

摘要 多序列线性反馈移位寄存器综合问题，即求能同时生成多条序列的最短 的线性反馈移位寄存器问题，在密码、编码、数学、信号处理及控制理论等 领域都有非常重要的应用，因而许多领域的工作者对此产生极大的热情，涌 现出很多的方法，所以不仅探求新的算法，而且探求各种综合算法之间的内 在关系，都成为在这些领域中常盛不衰的研究课题，具有极其重要的理论研 究意义与巨大而潜在的应用价值。 本文利用函数域上的格理论为多序列综合问题建立了一个新的数学模 型，利用格基约化算法完美地实现了多序列综合问题，我们将这一新的多序 列综合算法称为格基约化多序列综合算法，简称为l b r m s 算法。该算法能 导出几乎所有的现有综合算法，因而是一个统一性的算法。作为该算法在译 码上的直接应用，我们同样可以在h t 界和r o o s 界下来译有多个伴随序列 的b c h 码 具体地说主要贡献在于： 1 ) 利用了有理函数域上的格这一代数工具为多序列综合问题建立了一 个新的直观的单变元的向量形式的数学模型。由于格中的元素是用向量这一 为大家所熟悉的表示方法来给出的，使得多条序列中每条序列作为同一向量 的一个分量，而在利用g r s b n e r 基理论做序列综合时，多条序列的区分主要 依靠多变元来表示，所以本人认为向量的表示更为简单和易被接受。其次， 由于在格中使用了赋值和投射函数使得多项式与序列的生成关系非常容易 通过元素的两个函数值来反映。再次，多序列的极小多项式与所利用的格的 某个子集合中长度最短的元素相对应，使得序列综合问题有了直观的解释 最后，由于新模型中要找的元素必然在格的约化基中，因而格基约化算法就 能彻底地解决多序列综合问题。 2 ) 众所周知，l l l 格基约化算法在数学和密码学等领域都得到了广泛 的应用，有理函数域中的格基约化算法与l l l 算法有相似之处，但又有所 不同，本文的应用有可能是此算法在密码编码领域中的首次应用，因此格理 论就为序列密码等领域的研究提供了新思路。 1 1 1 1 v 摘要 3 ) 由于l b r m s 算法中格元素是将全序列的信息都放进去了，因此当 要综合的序列长度很大时，占用的存储空间就会很大，使得算法效率下降， 针对这一问题，我们将l b r m s 算法做了改进，导出了一个迭代算法，便于 计算机实现，同时也便于与其它迭代算法相比较。 4 ) 改进后的l b r m s 迭代算法很容易导出m a s s e y 猜想，广义b e r l e k a m p m a s s e y 算法和n o r t o n 算法，如果只考虑单序列情形，本算法可以导出b e l e r k a m p m a s s e y 算法，连分式算法和欧几里德算法，因而本算法具有更高的视 野，为序列综合问题提供了统一的方法 5 ) 本文将欧几里德环的概念推广到模上，即提出了欧几里德模的新概 念，而且将通常的欧几里德算法和连分式算法统一起来，进一步得到模上的 欧几里德算法，利用该算法可以导出l b r m s 算法和f e n g - t z e n g 的广义欧 几里德算法的等价性。 6 ) 前面均考虑的是序列元素取自域的情况，而环上序列综合问题同样在 密码，编码和信号处理等方面有非常重要的意义，本文将域上多项式环的格 基约化算法推广到整环多项式环上，进而解决了整环上的多序列综合问题。 7 ) 本文将著名的关键方程推广到关键方程组，进而利用l b r m s 算法 实现在h t 界和r o o s 界下译b c h 码的译码问题。 关键词多序列线性反馈移位寄存器综合，单序列线性反馈移位寄存器综 合，格，格基约化算法，关键方程，译b c h 码 a b s t r a c t m u l t i s e q u e n c el i n e a rf e e d b a c ks h i f t r e g i s t e rs y n t h e s i sp r o b l e m ，a i m e d a t f i n d i n gt h es h o r t e s tl i n e a rf e e d b a c ks h i f t r e g i s t e rt h a tc a ng e n e r a t et h eg i v e n m u l t i p l es e q u e n c e ss i m u l t a n e o u s l y , p l a y sa ni m p o r t a n tr o l e i nm a n yf i e l d s s u c ha sc r y p t o g r a p h y ，c o d i n gt h e o r y ，m a t h e m a t i c s ，s i g n a lp r o c e s s i n ga n d c o n t r o lt h e o r y r e s e a r c h e r sf r o mm a n yd i f f e r e n tf i e l d sh a ds h o w nag r e a td e a l o fi n t e r e s ti nt h ep r o b l e ma n dd e v e l o p e dm a n ya l g o r i t h m st ot h i sq u e s t i o n t h e r e f o r et h er e s e a r c ht of i n dn e w a l g o r i t h m sa n ds t u d y t h ei n t e r r e l a t i o n s h i p a m o n g t h o s ea l g o r i t h m sa r es t i l lh o tr e s e a r c ht o p i c si nt h e s ef i e l d sa n da r eo f g r e a tt h e o r e t i c a la n dp r a c t i c a ls i g n i f i c a n c e i nt h i sd i s s e r t a t i o nw ec o n s t r u c ta n e w ，i n t u i t i v e ，o n e v a r i a b l ea n d v e c t o r f o r mm a t h e m a t i c a lm o d e lf o rm u l t i s e q u e n c el i n e a rf e e d b a c ks h i f t r e g i s t e r s y n t h e s i sp r o b l e mb ym e a n so fl a t t i c et h e o r yi nf u n c t i o nf i e l d s ，a n ds ow e c a nc o m p l e t e l ys o l v et h i sp r o b l e mv i al a t t i c eb a s i sr e d u c t i o na l g o r i t h m a c c o r d i n g l yt h i sn e wa l g o r i t h mi s c a l l e dl a t t i c eb a s i sr e d u c t i o nm u l t i s e q u e n c e s y n t h e s i sa l g o r i t h m ( l b r m s ) h o w e v e r ，s i n c ei tr e q u i r e sm u c hs t o r a g ea n d b e c o m e si n e f f i c i e n tw h e nt h el e n g t ho fs e q u e n c e si sv e r yl a r g e ，t h eo r i g i n a l l b r m s a l g o r i t h mi sa d a p t e d t oa ni t e r a t i v ea l g o r i t h m b yf u n d a m e n t a l l yp r o c e s s i n gt ot h ea d j u s t e dl b r m sa l g o r i t h ms u c ha s d i s c a r d i n gt h ei n i t i a lb a s i sa n dc o n v e r t i n gap o l y n o m i a li n t oi t sr e c i p r o c a l w ec a ne a s i l yd e d u c em a s s e yc o n j e c t u r e ，f e n g - t z e n g g e n e r a l i z e db e r l e ! m m p m a s s e ya l g o r i t h ma n d n o r t o n sa l g o r i t h m a sf a ra st h es i n g l e s e q u e n c ec a s e i sc o n c e r n e d ，w ea l s od e d u c eb e l e r k a m p - m a s s e ya l g o r i t h m ，m i l l sc o n t i n u e d f r a c t i o n sa l g o r i t h ma n de u c l i d e a na l g o r i t h mf r o ml b r m s a l g o r i t h m i no r d e rt os h o wt h a tl b r m s a l g o r i t h mi se q u i v a l e n tt of e n g - t z e n g g e n e r a l i z e de u c l i d e a na l g o r i t h m ，t h en e wc o n c e p ta b o u te u c l i d e a nm o d u l e i sp r o p o s e da n ds ob ym e a n so fe u c l i d e a na l g o r i t h mi nm o d u l e sw eg i v ea n a l g o r i t h mw h i c hc a nb er e g a r d e da sam o d i f i e dl b r m sa l g o r i t h m h e n c e w ee a s i l yg e tt h ed e s i r e dr e s u l t v v l a b s t r a c t t mn o ww ec a nd d u c ea l m o s ta l le x i s t i n gs y n t h e s i sa l g o r i t h m sf r o m l b r m s a l g o r i t h ma n d h e n c ei ti sau n i f i e da p p r o a c ht om u l t i s e q u e n c 88 y n 。 t h e s i sp r o b l e m a si t sd i r e c ta p p l i c a t i o n ，w ec a l ld e c o d i n gb c h c o d e si nw h i c hm u l t i p l e s v n d r o m es e q u e n c e sa r ea v a i l a b l eu pt ob o t hh t b o u n da n dr o o sb o u n d i nt h ea b o v ew eo n l yd e a lw i t ht h ed i g i t si ns e q u e n c e sf r o mf i e l d s i n a d d i t i o n ，w ea l s os o l v em u l t i s e q u e n c es y n t h e s i sp r o b l e mw h e nt h ed i g i t s i s f r o mi n t e g r a ld o m a i ni n s t e a do f f i e l d s f i n a u y ，t h ec o n c l u s i o nr e m a r k i sd r a w na n ds o m ef u t u r er e s e a r c ht o p i c s a r ed i s c u s s e d k e yw o r d s ：m u l t i s e q u e n c el i n e a rf e e d b a c ks h i m r e g i s t e rs y n t h e s i s p r o b l e m ，s i n g l e - s e q u e n c el i n e a rf e e d b a c ks h i f t r e g i s t e rs y n t h e s i sp r o b l e m ，l a t t i c e 一 1 a t t i c eb a s i sr e d u c t i o na l g o r i t h m ，k e ye q u a t i o n ，d e c o d i n gb c h c o d e s 第一章绪论 1 1 研究背景及意义 当今世界已步入信息时代，信息安全已成为人们越来越关注的焦点，而 密码技术为其提供了有利的保障。根据密钥的特点，密码体制分为私钥密码 体制和公钥密码体制，按加密方式又可分为流密码( s t r e a mc i p h e r ) 和分组 密码( b l o c kc i p h e r ) 两种，前者又称为序列密码。分组密码通常是按固定规 模将明文分组，对每组独立地进行运算。流密码利用密钥序列将明文逐比特 加密。流密码理论相对比较成熟，主要原因之一在于数学这一工具用于流密 码的研究，使得其已成为一种主要的加密方式。 最出色的流密码就是一次一密乱码本( o n e t i m e p a d ) ，即明文消息与一 个同样长的无重复的随机序列逐位相加，在假定唯密文攻击下，s h a n n o n 7 0 1 证明了；即使是具有无限计算资源的密码分析者，也决不能从所有其他有意 义的明文中识别出真正的明文。该体制的缺点是需要无限的密钥量，这种方 法是极为不实用的，因为在安全信道上传送的密钥流很大，很难实现。 受该密码体制的启发，人们构造伪随机序列来加密明文序列，这种伪随 机序列是在一个秘密的密钥控制下，由一个称为密钥序列发生器的确定性算 法所产生的，因此流密码体制安全取决于密钥序列的“随机性”，下面我们 讨论检验这种“随机性”的三个重要的指标：周期，线性复杂度和均匀分布 特性。 在假定已知明文攻击的情形下，密码分析者完全可以得到流密钥，为使 体制安全起见，密钥序列是不可预测的，即不论观测到多少密钥序列数字， 要预测后续的密钥序列数字仍相当于对它们进行随意猜测。也就是说，密钥 分析者要想确定真密钥，他通过可靠地预测密钥序列是办不到的。而不可预 测性的必要条件是密钥序列具有长周期，由周期可确定一个线性递归式。因 此，如果知道了周期的值及密钥序列的第一个周期，则完全可以确定了密钥 序列的其余部分。 为了度量周期序列的随机性，g o l o m b 在 3 1 】中提出了众所周知的“随 机性公设”：第一，在序列的一个周期内，“0 ”与“1 ”的个数相差不超过 1 个；第二，在每个周期内，长度为i 的游程占游程总数的；1 ，这里假定至 2 第一章绪论 少有两个长为i 的游程；第三，周期的自相关函数是二值的。通常称符合上 述三条标准的序列为伪随机序列。然而，伪随机序列是高度可测的，如果用 l 表示所考虑序列的极小多项式的次数，贝4 只需取连续的2 l 比特就足以完 全确定长度为2 l 一1 序列的其余部分。 因此随机性概念亦应反映由前面所有数字序列来预测序列的下一个数字 的不可能性。定义有穷序列随机性的一个重要方法是基于r s o l o m o n o v 7 1 和a k o l m o g o r o v 4 1 】所提出的不可预测性概念。他们用一个能生成这个序 列的最短图灵机程序的长度描述有穷序列的“不可模仿性”。另一种度量有 穷序列的随机性的方法是由a l e m p e l 和j z i v 提出的所谓“线性复杂度” 的方法 4 3 j ，规定用产生该序列的最短的线性反馈移位寄存器的长度来度 量，这个长度也称为该序列的线性复杂度。一般来讲，要求出能产生给定序 列的最短非线性反馈移位寄存器，一般是一件不可行的事。但是，如果要求 出能够产生已知序列的最短线性反馈移位寄存器，已有一个有效的综合算法 ( 即b e r l e k a m p m a s s e y 算法 3 ，4 6 ) 。因此，对于不可预测的密钥序列而言， 能产生给定序列的最短线性反馈移位寄存器的长度必须足够大。因此密钥序 列的线性复杂度已被视为一个具有头等重要性的设计参数f 6 5 l 。 因此求给定序列的线性复杂度的问题，简称为序列综合问题，是序列密 码中最基本也是最广泛的问题，尽管在这方面已有大量的方法和文献，但是 继续的研究，特别是用新的数学工具对其的研究都将是非常有意义的事情。 在对序列密码的研究中，许多较为理想的数学工具使得流密码的得到长足的 发展，例如代数理论、频谱理论等f 8 9 序列综合问题有许多应用，其中一个非常重要的应用就是编码理论中的 译码问题，在译一些循环码过程中，例如b c h 码，r e e d - s o l o m o n 码和1 一 变元的g o p p a 码 3 ，5 ，6 ，4 5 ，6 1 ，7 4 ，确定关键方程中的错位多项式问题就 是序列的线性反馈移位寄存器综合问题，该问题是译码问题的关键之处。 我们知道b c h 码界是基于b c h 码的零点集合( d e f i n i n g z e r os e t ) 中 包含一个连续的根集来给出的，因而译码时只有一个伴随序列( s y n d r o m e s e q u e n c e ) 可获得。然而，许多循环码的零点集包含不只一个连续的根集， h t 界 3 3 】和r o o s 界 6 4 】就是基于这些码导出的，改进了b c h 码界，因 而需要解决有多个伴随序列的循环码译码中的确定错位多项式问题，也就是 需要求多序列综合问题，即 5 j 1 研究背景及意义 3 求能同时生成m 条序列s ( “，s ( m ) 的最短的线性反馈移位寄存器问 题。 显然多序列综合问题可以看成单序列综合的推广，它不仅能解决编码理 论中的译码问题，同样在流密码中也得到研究 5 2 。序列的线性复杂度轮 廓( 1 i n e a rc o m p l e x i t yp r o f i l e ) 问题在流密码中不仅具有理论价值而且在应用 上非常重要，很多讨论只是对于单序列的研究 5 0 ，5 l ，6 5 ，8 3 ，目前已开始 讨论多序列的情况 5 3 ，8 4 1 。 我们主要的研究问题就是求生成给定的多条有穷序列的最短的线性反 馈移位寄存器，该问题已有很多的方法，下一节将详细介绍，但是我们将使 用新的方法即函数域中的格基约化算法来研究它，希望这个方法能为序列密 码的研究提供新思路。 本文中我们主要利用了由s c h m i d t 6 8 提出的函数域中的f 卜格基约 化算法，该算法非常类似于著名的l l l 算法，l l l 算法是由a ，k l e n s t r a ， h w ，l e a s t r a 和l l o v 缸z 提出的f 4 4 1 ，它的名字就取自于三作者的首字 母，实数域r 作为基域构成的向量空间的子集又构成一个自由z 一模，就称 为一个z 一格，l l l 算法就是将格的一组基变换为所谓的“约化基”，也就是 满足一定条件的一组基，该算法是确定性算法，也是多项式时间算法。l l l 格基约化算法在数学和密码学等领域都得到了广泛的应用，尤其被用于对各 种密码体制的攻击，如对背包体制的攻击 4 2 ，6 9 和r s a 体制的攻击 1 6 ， 因此得到了人们的青睐。 而 陋卜格基约化算法是对由l a u r e n t 级数域f ( 暖- 1 ) ) 作为基域构成 的向量空间内的f 】_ 自由模，即一个f 卜格上的一组基变换为所谓的 “约化基”，该算法非常简单，也是确定性算法，我们相信这个算法也会像 l l l 算法一样将在许多领域得到广泛的应用。 该算法也常被称为函数域上的整基约化算法，这是因为函数域，记为 f ，是有理函数域f 伍) 有限扩张，因此f 在f 中的整闭包o f 是满秩的 自由f i x 一模，即o f = o 墨1f 捌岫，其中n 表示扩张次数，u l ，为 一组整基，由于f 为函数域，因此f 上的所有赋值均为离散赋值，而l l l 算 法使用了黔中通常的内积，这也正是造成函数域上的整基约化算法与l l l 算法不同的主要原因。 序列综合问题还与连分式综合算法f 4 9 、欧几里德算法 7 3 和p a d 逼 4 第一章绪论 近( 7 l 有关，还用于解稀疏矩阵【1 5 ，8 2 和稀疏插值【2 5 ，该问题还可以解 决控制理论的部分实现问题 1 ，3 2 ，3 8 ，3 9 ，4 0 1 ，并且参数取自数域上的部分 实现( p a r t i a lr e a l i z a t i o n ) 问题就等价于单序列综合问题，参数取自向量空间 的部分实现( p a r t i a lr e a l i z a t i o n ) 问题就等价于多序列综合问题，另外序列综 合问题可用于数字信号处理中的源编码和数据压缩等 4 ，4 6 ，例如要处理 的信源数字1 2 7 比特，三表示生成该序列的最短的移存器的长度，用7 比 特表示这种压缩方式，我们就可以用2 + 7 比特来传输1 2 7 比特，其中l 比特代表联结多项式的系数，l 比特代表l f s r 的初始状态。 总的看来，序列综合问题在密码、编码、数学、信号处理及控制理论等领 域都有重要的应用，对该课题的研究是非常有意义的。本文主要是利用函数 域上的格基约化算法解决多序列综合问题，单序列综合只是它的特殊情形。 1 2 国内外研究现状 序列综合问题在密码、编码、数学和控制论等领域中均有很重要的应用， 因而许多领域的工作者对此产生极大的热情，在这方面涌现出很多的方法， 因此不仅探求新的算法，而且探求各种综合算法之间的各种内在的关系，成 为在这些领域中常盛不衰的研究课题， 单序列综合算法中最著名的是b e r l e k a m p - m a s s e y 算法，事实上，b e i e r k a m p 在译b c h 码时给出了一个算法 3 ，m a s s e y 在 4 6 中简化了这个 算法，将之用于序列复杂度分析中的线性反馈移位寄存器综合问题，后来人 们就将这个算法叫做b e f l e k a m p - m a s s e y 算法，简称为b m 算法，该算法是 一个迭代算法，速度快存储小，便于计算机使用，目前被广泛地使用。值得 一提的是正是由于这个有效的算法，使得用产生序列的最短的线性反馈移位 寄存器的长度来定义序列的线性复杂度不足之处，没有很好的数学模型为 其解释。 另外比较经典的方法有m i l l s 的连分数算法【4 9 】，s u g i y a m a 等的欧几 里德算法f 7 3 】。这些算法有很好的数学解释，但由于这两种算法需进行除法 运算，并记录大量的中间结果，因而速度比b m 算法要慢，所需的设备也 较多。 这些看似不同的算法促使许多学者研究它们之间的关系，有大量的文献 1 3 本文的主要贡献与章节安排 5 致力于此 9 ，1 3 ，1 7 ，2 2 ，2 8 ，2 9 ，4 0 ，8 1 】，结论表明b m 算法、连分数算法、 欧几里德算法这三种算法是完全等价的。 多序列综合问题也有很多算法。1 9 7 2 年m a s s e y 提出了一个猜想性的 迭代算法，后来丁存生给出了证明2 0 1 。另外两个经典的算法由冯贵良和k k t z e n g 提出的，我们将其分别称做广义欧几里德算法 2 6 】和广义b m 算 法 27 。广义欧几里德算法主要是将通常的欧几里德算法推广到多除数的情 形，再利用它给出多序列综合算法，广义b m 算法是对b m 算法的推广，主 要通过对矩阵的变换得到基本迭代算法( f u n d a m e n t a li t e r a t i v ea l g o r i t h m ) ， 从而可以逐条序列做类似于b m 算法的多序列综合，这种由单条到多条的 思想经常用于多序列综合算法中f 3 6 1 。 近来n o r t o n 利用l a u r e n t 级数域中的有理逼近给出了单条和多条序列 综合算法 5 4 ，5 5 ，5 6 ，5 7 ，5 8 ，5 9 ，6 0 ，他的算法表明利用l a u r e n t 级数来表 示序列的好处，我们的研究利用了这个优点，进一步使用了格基约化算法完 美地解决了序列综合问题，而n o r t o n 诸多算法要么使用硬凑要么使用下面 介绍的g r s b n e r 基理论。 另外的综合算法主要基于g r s b n e r 基理论，g r 6 b n e r 基理论是计算代 数中的重要内容，有着广泛的应用范围f 2 ，8 1 。g r s b n e r 基实质就是多元多 项式环的理想的满足一定条件的一组生成元，许多学者利用它解决序列综合 问题| 5 5 ，6 6 ，6 7 ，8 5 ，8 6 ，8 7 1 。 尽管有如此多种多序列综合算法，但对于算法之间的比较却很少，主要 原因在于多序列情形比较复杂，数学模型不够清晰。 1 3 本文的主要贡献与章节安排 本文利用函数域上的格理论为多序列综合问题建立了一个新的数学模 型，利用格基约化算法完美地实现了多序列综合问题，我们将这一新的多序 列综合算法称为格基约化多序列综合算法，简称为l b r m s 算法。该算法 能导出几乎所有的现有综合算法，因而是一个统一性的算法。作为该算法在 译码上的直接应用，我们可以根据h t 界和r o o s 界来译有多个伴随序列的 b c h 码。 ， 具体地说主要贡献在于： 6 第一章绪论 1 ) 利用了有理函数域上的格这一代数工具为多序列综合问题建立了一 个新的直观的单变元的向量形式的数学模型。由于格中的元素是用向量这一 为大家所熟悉的表示方法来给出的，使得多条序列中每条序列作为同一向量 的一个分量，而在利用g r s b n e r 基理论做序列综合时，多条序列的区分主要 依靠多变元来表示，所以本人认为向量的表示更为简单和易被接受。其次， 由于在格中使用了赋值和投射函数使得多项式与序列的生成关系非常容易 通过元素的两个函数值来反映。再次，多序列的极小多项式与所利用的格的 某个子集合中长度最短的元素相对应，使得序列综合问题有了直观的解释。 最后，由于新模型中要找的元素必然在格的约化基中，因而格基约化算法就 能彻底地解决多序列综合问题。 2 ) 众所周知，l l l 格基约化算法在数学和密码学等领域都得到了广泛 的应用，有理函数域中的格基约化算法与l l l 算法有相似之处，但又有所 不同，本文的应用有可能是此算法在密码编码领域中的首次应用，因此格理 论就为序列密码等领域的研究提供了新思路。 ， 3 ) 由于l b r m s 算法中格元素是将全序列的信息都放进去了，因此当 要综合的序列长度很大时，占用的存储空间就会很大，使得算法效率下降， 针对这一问题，我们将l b r m s 算法做了改进，导出了一个迭代算法，便于 计算机实现，同时也便于与其它迭代算法相比较 4 ) 改进后的l b r m s 迭代算法很容易导出m a s s e y 猜想，广义b e r l e k a m p m a s s e y 算法和n o r t o n 算法，如果只考虑单序列情形，本算法可以导出b e l e r k a m p m a s s e y 算法，连分式算法和欧几里德算法，因而本算法具有更高的视 野，为序列综合问题提供了统一的方法。 5 ) 本文将欧几里德环的概念推广到模上，即提出了欧几里德模的新概 念，而且将通常的欧几里德算法和连分式算法统一起来，进一步得到模上的 欧几里德算法，利用该算法可以导出l b i i m s 算法和f e n g - t z e n g 的广义欧 几里德算法的等价性。 6 ) 前面均考虑的是序列元素取自域的情况，而环上序列综合问题同样在 密码，编码和信号处理等方面有非常重要的意义，本文将域上多项式环的格 基约化算法推广到整环多项式环上，进而解决了整环上的多序列综合问题。 7 ) 本文将著名的关键方程推广到关键方程组，进而可以利用l b r m s 算 i 3 本文的主要贡献与章节安排 法实现在h t 界和r o o s 界下b c h 码的译码问题。 本文的组织结构如下： 第一章( 本章) 介绍了序列综合问题的背景和意义，以及国内外进行的 一些研究工作。 第二章首先给出序列综合中常用的概念和符号，介绍了有理函数域中的 格基约化算法及约化基的一些性质 第三章首先为多序列综合问题建立了新的数学模型，重点描述了格基约 化多序列综合算法，进而导出它的迭代算法。 第四章将改进的格基约化多序列综合算法与m a s s e y 猜想，n o r o n 算法 和f e n g t z e n g 的广义b m 算法做比较，从而得到格基约化多序列综合算法 可以导出这三个算法。 第五章提出欧几里德模的新概念，利用模上的欧几里德算法导出了格基 约化多序列综合算法与f e n g - t z e n g 的广义欧几里德算法的等价性。 第六章格基约化多序列综合算法在单序列情形时可导出著名的b m 算 法和连分式算法。 第七章给出整环上的多序列综合算法。 第八章将著名的关键方程推广到关键方程组，进而可以利用l b r m s 算 法在h t 界和r o o s 界下译b c h 码。 第九章对本文的研究工作进行了总结，并展望了下一步的工作。 第二章 基本概念及i 卜格基约化算法 本章首先给出了序列线性移位寄存器综合中常用的概念，以及本文今后 利用的f x 卜格基约化算法及约化基的一些性质 2 1 基本概念 用于产生流密钥的最有用的装置之一是线性反馈移位寄存器( l f s r ) 其一般形式如图2 1 所示 图2 ，1 ：线性反馈移位寄存器 反馈系数c o ，c d _ l ，c d 和输出数字8 0 ，s l ，都取自任意域 的元 素，用于产生输出序列的延迟单元的数目d ，称为l f s r 的长度( 级数) ， 而每个延迟单元，称为l f s r 的级，d 个级的内容，称为l f s r 的状态。规 定最初寄存在d 级的d 个数字s o ，s d l 为l f s r 的初始状态，并且它可 以随意地选择。 l f s r 能生成一条序列s = ( 8 0 ，s 1 ) ，3 ，) ，岛f ，今后如不特 别声明，f 为任意的域，在流密码和编码中常用有限域，而在控制论和逼近 理论中常用无限域，因此我们采纳f 为任意的域，包含各种情况。 8 5 2 1 基本概念 对所有的女芝d ，该序列满足 9 c o s 七+ c l s k l + - + c d 8 k d = 0( 2 1 ) 式( 2 1 ) 叫做一个d 阶线性递归关系式。 多项式 c ( x ) = c o x “+ + c d 一1 x + c d f i x ( 2 2 ) 称为序列s 或该l f s r 的零化多项式( a n n i h i l a t i n g p o l y n o m i a l ) ，记为a n n ( s ) ： x 为未定元。式( 2 1 ) 左边又叫做第k 个校验子，记做如( a ) ，s ) 。当c o = 1 时，首一的零化多项式叫做特征多项式( c h a r a c t e r i s t i cp o l y n o m i a l ) 。 此时另一个重要的多项式是 d ( x ) = 1 + c l x + + c d x 4 ，( 2 3 ) 该多项式的次数至多为d ，称为序列s 或该l f s r 的联结多项式( c o n n e c t i o n p o l y n o m i a l ) ，应当指出，联结多项式d ( x ) 与c ( x ) 是互反多项式，即有 d ( x ) = x 8 c ( x 1 ) ( 2 4 ) 次数最小的特征多项式称做序列s 的极小多项式( m i n i m a lp o l y n o m i a l ) ， 因此极小多项式的次数就是生成序列s 的最短的线性反馈移位寄存器的长 度，又称为序列s 的线性复杂度，常记为l c ( s ) 。次数最小的联结多项式称 做序列s 的极小联结多项式当c d 0 时，该l f s r 称为非退化的l f s i 毛， 当o d = o 时，该l f s r 称为退化的l f s r ，因此极小联结多项式的次数小 于等于序列s 的线性复杂度，所以如果用联结多项式来表示l f s r 的话，需 要专门指出其的级数或线性复杂度，因而用极小多项式来表示更为方便。 例2 1 给定f 2 上的一条序列( 1 ，0 ，1 ，0 ，0 ) ，它的极小多项式为x 3 + x ， 它的线性复杂度为3 ，但它的极小联结多项式为1 + x 2 。 常需要考虑求有限长序列的最短的线性反馈移位寄存器，序列s 的长度 为的初始子段，记为 s l = ( 8 0 ，- 一，s 一1 )( 2 5 ) 1 0 第二章基本概念及f i x 一格基约化算法 求序列s i n 的最短的线性反馈移位寄存器也简称为单序列综合问题， 多序列综合问题的数学描述为： m 条长度为的序列，记为 s ( 1 ) i n = ( s p ， s ( 2 ) i n = ( s 乎， s ( m = ( s 5 m ，s 妲t ) 求髓同时生成序列s ( 1 l n ，s ( m ) i n 的最短的线搓反馈移位寄存器也 简称为多序列综合问题。 称多项式g ( x ) = g ；o 乌x 。一，为序列s ( t ，t 一，s i 的零化多项 式( 相应地，特征多项式和极小多项式) ，如果c ( x ) 是s ( 1 j ，s ( ) i 中 的每条序列的零化多项式( 相应地，特征多项式积极小多项式) ，将s ( 1 ) | ， s ( ”i 的零化多项式记为a n n s ( ”) i n 】，显然有 a n n s ”i n = n a n n ( s 。) ( 2 7 ) i = 1 由于次数大于等于的多项式必然为多序列的一个零化多项式，因此 序列s ( 1 ) j j ，s ( “f 的综合问题必然有解，多序列的综合问题也就是求它 们的一个极小多项式，极小多项式的次数称为m 条序列s ( 1 ) 1 ，s ( “i n 的联合线性复杂度( j o i n t l y l i n e a rc o m p l e x i t y ) ， 将l f s r 在f 上的半无限输出序列s 的x 一变换定义为 了( s ) = + s l x + 8 2 x 2 + ，( 2 8 ) x 为未定元，t ( s ) 称为序列s 的形式幂级数，这里的变换只是为了将序列 的所有数字按正确的顺序存入而。形式”两字，意指该幂级数的收敛或是 发散在这里是无关紧要的。有的文献称其为序列的母函数，或生成函数。如 果把形式幂级数的加法和乘法的代数运算视为相应的多项式运算，则具有这 种加法和乘法的f 上的全体形式幂级数的集合构成具有单位元的交换环， 就称为 上的形式幂级数环，用f 1 l 表示。 62 ，【 、j、j l ，一，一 0 p s s 5 2 j 基本概念 1 1 半无限输出序列s 满足满递归关系式( 2 1 ) ，其联结多项式d ( x ) 定义 如上，则 t ( s ) = 黑 d e g ( q ( 驯 d ， ( 2 9 ) 其中q ( x ) 由t ( s ) 和d ( x ) 完全确定，式( 2 9 ) 称为序列s 的有理真分式表 示。反过来，且正如我们所知，序列的形式幂级数为形如式( 2 9 ) 的一个有理 表示，则d ( x ) 为序列s 的联结多项式。进一步，如果g c d ( d ( x ) ，q 僻) ) = 1 且d ( o ) 0 ，则d ( x ) 为生成序列s 的极小的联结多项式。 如果只考虑s 的前n 位，记为s i n ，s i 满足满递归关系式( 2 1 ) ，则 t ( s i n ) ；器m o d d e g ( 孵) ) d ) ( 2 1 0 ) 其中q ( x ) 为 上次数小于d 的多项式，也由t ( s i n ) 和d ( x ) 完全确定， 式( 2 1 0 ) 称为序列s 的部分有理表示。反过来，如果式( 2 1 0 ) 成立，则d ( x ) 是序列s i n 的一个联结多项式。 令”是有理函数域f ( x ) 的无穷赋值，f 【x 对于 的完备化得到一个 l a u r e n t 级数域f ( 畔“) ) = k 赋值v 在k 上的延拓仍记为口。详细地 说，我们有 并且映射 。 k = f ( ( x - 1 ) ) = a i x ii o z ，啦f ( 2 1 1 ) i = i 0 k - - - + z u o 。) ”。铲扩。h 赫口栅翥 。1 2 且 满足 1 ) ( a ) = o 。当且仅当o = o 。 2 ) u ( a 卢) = v ( a ) + ( 卢) ，卢k 。 3 ) v ( a + 卢) 芝m i n v ( a ) ，口( 卢) ) 如果 ( o ) 口( 卢) ，则等式成立。 1 2 第二章基本概念及可捌一格基约化算法 将l f s r 在职上的半无限输出序列s 的x _ 。一变换定义为 r ( s ) = s o x 一1 + s i x 一2 + s 2 。x 一3 + 一k ，( 2 1 3 ) r ( s ) 称为序列s 的形式负幂级数，这种表示在连分式综合算法中使用过 1 3 ， 1 7 ，4 9 ，8 1 】，事实上序列的形式负幂级数表示在控制论中早已使用i l ，3 2 ，3 8 ， 3 9 ，4 0 ，后来n o r t o n 的算法中也使用了这种表示方法，但他使用的与本文 咯有不同，即 r ( s ) = 8 0 + s l x 一1 + s 2 x 一2 + ( 2 1 4 ) 半无限输出序列s 满足满递归关系式( 2 1 ) ，其特征多项式c ( x ) 定义如 上，则有 r ( s ) = 器，d e g ( p ( 驯 d e g ( 叫) ) ( 2 1 5 ) 其中p ( x ) 为f 上次数小于d 的多项式，由r ( s ) 和c ( x ) 完全确定， 上式也称为序列s 的有理表示。同样有序列s 它的形式负幂级数为形如式 ( 2 1 5 ) 的一个有理表示，则c ( x ) 就是它的一个特征多项式。进一步，如果 g c d ( c ( , x ) ，p ( x ) ) = l 且c ( o ) o ，则c ( x ) 为生成序列s 的极小多项式。 如果只考虑s 的前位，记为s f ，s i n 满足满递归关系式( 2 1 ) ，则 c ( x ) r ( s l n ) 三p ( x ) m o dx - ，d e g ( p ( x ) ) d e g ( c ( x ) ) ( 2 1 6 ) 其中多项式p ( x ) 由r ( s l n ) 和c ( x ) 完全确定反过来，如果序列s i n 满 足式( 2 1 6 ) ，则c ( x ) 是序列的一个特征多项式。 因此联结多项式与序列相应的形式幂级数相联系，而序列相应的形式负 幂级数与特征多项式联系起来研究比较方便，前面我们说到特征多项式的次 数就等于l f s r 的级数，因而综合问题中考虑特征多项式和极小多项式比联 结多项式和极小联结多项式更方便，所以我们用序列对应的形式负幂级数来 表示序列，即在l a u r e n t 级数域研究。 显然n o t o n 定义的形式负幂级数造成不同之处在于p ( x ) 的次数必然 大于0 。 5 2 2f i x 一格基约化算法 2 2f x - 格基约化算法 1 3 本节首先介绍陋卜格的定义，再给出f 陋卜格基约化算法及约化基的 一些性质。 令n 为任意的正整数，“的一个集合a