（计算机应用技术专业论文）信息安全中有限环上的纠错码和序列密码研究.pdf

摘要 摘 要 纠错码理论和密码学是信息安全的理论基础，序列密码是密码学的两个组成部分之一。目 前，有限域上的纠错码理论和序列密码理论不仅已发展得很完善而且已广泛应用于生产实际 中。随着生产技术的不断发展和理论研究的不断深入，有限环上的纠错码理论和序列密码理论 的研究不仅具有重要理论意义而且具有重要的实际价值。 几十年来，研究d eb r u i j n 序列的生成算法一直是序列密码研究领域中的一个核心问题， 尽管已有大量的生成2 元d eb r u i j n 序列的有效算法，但由于有限环上运算的复杂性，有限环 z t 上d eb r u i j n 序列的生成算法与实际需要还有相当太的差距，本文从多个方面给出了生成有 限环磊上d eb r u i j n 序列的不同生成算法；近十年来，有限环上的纠错码理论的研究是纠错码 理论研究领域中的一个研究热点，本文从多个方面深入地研究了有限环上线性码、循环码的各 种性质，具体研究内容如下： 1 建立了有限环z 。上移位寄存器序列的理论。本文定义了女元移位寄存器和d eb r u i j n g o o d 图，研究了移位寄存器的状态图的性质和n 级d eb r u i j n - g o o d 图g 的自同构的结构；分 析了两类特殊的 元移位寄存器的状态图中圈的结构；利用从级 元d eb r 曲n g o o d 图到n 一1 级k 元d eb r u i j n g o o d 图之间的 一1 d 一同态，给出了d eb r u i j n g o o d 图中 元自对偶圈和 拟自对偶圈的结构定理。 2 研究了d eb r u i j n 序列的k 次齐次复杂度。复杂度是衡量d eb r u i j n 序列复杂性的一个 标准，本文定义了d eb r u i i n 序列的a 次齐次复杂度，并利用非线性问题线性化的方法，研究了 d eb r u i j n 序列的k 次齐次复杂度的性质；并给出了 次齐次复杂度的上界。 3 系统地研究了 元d eb r u i j n 序列的各种生成方法。本文建立了并圈法构造 元d e b r u i j n 序列的原理，并利用并圈法原理，通过合并纯轮换移位寄存器的状态图中的所有圈，给 出了一个产生女元d eb r u i j n 序列的递归算法；定义了可生成所有循环圈的算子，通过并置所 有循环圈的周期约化，提出了一个生成 元d eb r u i j n 序列的无记忆算法，并由此，首次给出了 d e b r u i i n 穿列的升元算法，而且这两个算法每步运算可生成一列元素而不是一个元素，因而减 少了运算次数，加快了生成速度，因而，这两个算法是生成k 元d eb r u i j n 序列的有效生成算 法；利用从n 级 元d e b r u i j n - g o o d 图到n 一1 级女元d e b r u i i r t - g o o d 图的d 一同态的性质，给出 了 元d eb r u i j n 序列反馈函数的一种升级算法和三种不同的派生方法，从一个给定的k 元d e f 正1 b r u i j n 序列的反馈函数，三种派生方法分别可产生 一1 个，k ( k - - 1 ) 2 个和11 f 1 个新的k 元 【3j d eb r u i j n 序列的反馈函数。 4 建立了有限环z 。上的码的深度分布理论。本文定义了有限环z 上码字的深度和码的 深度分布，给出了有限环互上码字的深度和码的深度分布的一些性质，研究了z 上线性码和 线性循环码的深度谱，证明了矿t 2 z 型线性码的深度谱至少含有k 。+ 岛个非零值，和一类4 4 型 台肥工业大学博士学位论文 线性循环码的深度谱为 n ，n l ，n 一 + 1 ) ；利用组合数学、图论和数论知识，给出了两种计 算有限环五上码字深度的递归算法。 5 研究了四元素环f 。+ u f 。上线性码和循环码的性质。本文给出了环r + u f 。上线性码 及其对偶码的生成矩阵；利用从环f 。+ ”f 2 到域凡上的g r a y 映射证明了环f z + u f 。上线性 码的g r a y 像仍为线性码，以及线性码的g r a y 像与其对偶码的g r a y 像是互为对偶码；建立了 环f 2 + u f ：上循环码与商环a = r b ( ，一1 ) 中主理想以及( 1 十u ) 一循环码与商环且 = r b ( ，一1 - - u ) 中主理想的一一对应关系，其中r = f z + u f z ；证明了环凡十u f z 上长度为 n 的( 1 十“) 一循环码的g r a y 像是域f ：上长度为2 “的循环码。 6 对有限环z 。上纠错码理论进行了以下几个方面拓展性研究： 研究了g a l o i s 环g r ( q 1 ) 的结构及其元素表示法；建立了g a l o i s 环g r ( q 1 ) 上的多项式 理论，给出了h e n s e l 引理和h e n s e l 提升；定义了g a l o i s 环g r ( q 4 ) 中的迹映射，证明了迹映射 的传递性；给出了g r ( g 朋) 中循环码的迹表示。 定义了g a l o i s 环上的迹码和子环子码的概念，证明了g a l o i s 环g r ( q ”) 上一个码的对偶 码的迹码是该码的子环子码的对偶码。 定义了环z d + l 到z ，的一个g r a y 映射，研究了该映射的性质，并通过该映射，给出了由 z ，+ 上的线性码的生成矩阵计算它的g r a y 像的生成矩阵的方法；证明了环z ，上的码为循 环码当且仅当它的g r a y 映射像是一个准循环码；构造了一个同构映射，利用环z p * + l 上 ( 1 一矿) 一线性循环码和( 1 一f 矿) 一线性循环码的对应关系，研究了环乙一上( 1 一f 矿) 一线性循环 码的一些性质，给出了环z ，一，上( 1 一p ) 一线性循环码的生成多项式和码字的个数。 研究了环z ，t 上线性码的深度分布的性质，并给出了一种计算环z ，的码字深度的递归 算法。 定义了环五上线性码的对称重量计数公式，利用离散的h a d a m a r d 变换，建立了线性 码与其对偶码之问的对称形式的m a e w 皿r s 恒等式。 上述研究成果不仅丰富了序列密码和纠错码理论的内容，也拓宽了传统的序列密码和纠 错码理论的应用范围和研究范围。 关键词：序列密码；d eb r u i j n 序列；纠错码；线性码；循环码；g r a y 映射 摘要 v a b s t r a c t e r r o r - c o r r e c t i n gc o d i n gt h e o r ya n dc r y p t o g r a p h ya r et h et h e o r e t i c a lb a s e so fi n f o r m a t i o n s a f e t y t h e o r yo fs t r e a mc i p h e r s ，n a m e l yt h e o r yo fs e q u e n c ec i p h e r s ，i so n eo f t h et w o c o m p o n e n tp a r t so fc r y p t o g r a p h y a tp r e s e n t ，e r r o r c o r r e c t i n gc o d i n gt h e o r ya n dt h e o r yo f s t r e a mc i p h e r so v e rf i n i t ef i e l d sh a v eb e e nn o to n l yd e v e l o p e dp e r f e c t l yb u ta l s oa p p h e dw i d e l yt o t h ep r o d u c t i v ep r a c t i c e w i t ht h es u c c e s s i v ed e v e l o p m e n to fp r o d u c t i o nt e c h n i q u ea n dt h e s u c c e s s i v ed e e p g o i n gr e s e a r c h e so nt h e o r y ，r e s e a r c h e so ne r r o r e o r r e t i n gc o d i n gt h e o r ya n d t h e o r yo fs t r e a mc i p h e r so v e rf i n i t er i n g sh a v en o to n l yi m p o r t a n tt h e o r e t i a ls i g n i f i c a n c eb u ta l s o i m p o r t a n tp r a c t i c a lv a l u e d u r i n gt h ep a s ts e v e r a ld e c a d e s ，r e s e a r c ho na l g o r i t h m sf o rg e n e r a t i n gd eb r u i j ns e q u e n c e si s a l w a y sak e yp r o b l e mi nt h es t u d yf i e l d o fs t r e a mc i p h e r s a l t h o u g hn u m b e r so f e f f e c t i v e a l g o r i t h m sf o rg e n e r a t i n gb i n a r yd eb r u i j ns e q u e n c e sh a v eb e e ng i v e n ，t h e r ei ss t i l lac o n s i d e r a b l y b i gg a ph e t w e e na l g o r i t h m sf o rg e n e r a t i n gd eb r u i ns e q u e n c e so v e rf i n i t er i n gz a n dt h ep r a c t i c a l r e q u i r e m e n td u et ot h ec o m p l e x i t yo fo p e r a t i o n so v e rf i n i t er i n g s i nt h i sd i s s e r t a t i o na r e p r e s e n t e dd i f f e r e n ta l g o r i t h m sf o rg e n e r a t i n gd eb r u i j ns e q u e n c e so v e rf i n i t er i n g sz f r o mv a r i o u s a s p e c t s i nr e c e n td e c a d e ，r e s e a r c h e so ne r r o r c o r r e c t i n gc o d i n g t h e o r yo v e rf i n i t er i n g sh a v e d r a w ni n t e n s i v ea t t e n t i o ni nt h ef i e l do fe r r o r c o r r e c t i n gc o d i n gt h e o r y t h i sd i s s e r t a t i o nm a k e sa d e e p g o i n gr e s e a r c hf o rv a r i o u sp r o p e r t i e so fl i n e a rc o d e sa n de y e f i ec o d e so v e rf i n i t er i n g s t h e d e t a i l sa r eg i v e na sf o l l o w s 1 t h e o r yo fs h i f t r e g i s t e rs e q u e n c e so v e rf i n i t er i n g 五i se s t a b l i s h e d t h i sd i s s e r t a t i o n d e f i n e sk - a r ys h i f tr e g i s t e ra n dk - a r yd eb r u i j n - g o o dg r a p h ，s t u d i e sp r o p e r t i e so ft h es t a t eg r a p h o fs h i f tr e g i s t e ra n dt h es t r u c t u r eo fs e l f i s o m o r p h i s r n so fn - s t a g ed eb r u i j n g o o dg r a p h ；a n a l y z e s s t r u c t u r eo fc y c l e si ns t a t eg r a p h so ft w oc h s so fs p e c i a lk - a r ys h i f t r e g i s t e r s b yu s i n g 1n h o m o m o r p h i em a p p i n g sf r o mn s t a g ek - a r yd eb r u i j n - g o o dg r a p ho n t o ( n 一1 ) 一s t a g ek - a r yd e b r u i j n - g o o dg r a p h ，as t r u c t u r et h e o r e mo fk - a r ys e r f - d u a lc y c l e sa n dq u a s i s e l f d u a lc y c l e si s g i v e n 2 t h eh o m o g e n e o u sc o m p l e x i t yo fd e g r e eko fd eb r 删ns e q u e n c e si ss t u d i e d t h e c o m p l e x i t yi sas t a n d a r dw h i c hm e a s u r e sc o m p l e x i t yo fd eb r u i j ns e q u e n c e s t h i sd i s s e r t a t i o n d e f i n e st h eh o m o g e n e o u sc o m p l e x i t yo fd e g r e e o fd eb r u i j ns e q u e n c e s ，s t u d i e sp r o p e r t i e so ft h e h o m o g e n e o u sc o m p l e x i t yo fd e g r e eko fd eb r u i j ns e q u e n c e sb yu s i n gl i n e a r i z a t i o nm e t h o do fn o n l i n e a rp r o b l e m ，g i v e si t su p p e rb o u n d 3 ：v a r i o u sa l g o r i t h m sf o rg e n e r a t i n gk - a r yd eb r u i j ns e q u e n c e sa l es t u d i e ds y s t e m a t i c a l l y t h i sd i s s e r t a t i o ne s t a b l i s h e sp r i n c i p l e so fm e t h o do fj o i n i n gc y c l e sf o rg e n e r a t i n gk - a r yd eb r u i j n s e q u e n c e s , g i v e sar e c u r s i v ea l g o r i t h mf o rt h eg e n e r a t i o no fk - a r yd eb r u i j ns e q u e n c e sb yj o i m n g a l lc y c l e si nt h es t a t eg r a p ho fp u r ec y c l i n gr e g i s t e ro nt h ep r i n c i p l e s a no p e r a t o rf o rg e n e r a t i n g a l ln e c k l a c e si sd e f i n e d ，a n dam e m o r y l e s sa l g o r i t h mf o rt h eg e n e r a t i o no fk - a r yd eb r m j n i 1 合肥工业大学博士学位论文 s e q u e n c e si sg i v e nb yj u x t a p o s i n gt h ep e r i o d i cr e d u c t i o n so ft h en e c k l a c e s ，a n dt h e na ni n n o i a t o r y a l g o r i t h mo fr a i s i n ge l e m e n t si sy i e l d e df r o mt h em e m o r y l e s sa l g o r i t h m e a c ho p e r a t i o n a ls t e po f t h et w oa l g o r i t h m sp r o d u c e sas t r i n go fe l e m e n t si n s t e a do fo n ee l e m e n t t h et w oa l g o r i t h m sa r e e f f e c t i v ef o rg e n e r a t i n gk - a r yd eb r u i i ns e q u e n c e ss i n c et h e yr e d u c et h et i m e so fo p e r a t i o n ，a n d a c c e l e r a t et h es p e e do fg e n e r a t i o n b yu s i n gp r o p e r t i e so fd h o m o m o r p h i cm a p p i n g sf r o m ”一s t a g e k - a r yd eb r u i j n - g o o dg r a p ht o ( 一1 ) s t a g ek - a r yd eb r u i j n g o o dg r a p h w eg i v et h r e e a l g o r i t h m so fd e r i v a t i o na n da na l g o r i t h mo fr a i s i n gs t a g ef o rg e n e r a t i n gf e e d b a c kf u n c t i o n so fk a r yd e b r u i j ns e q u e n c e s 。w h e r e t h e t h r e ea l g o r i t h m so f d e r i v a t i o nc a np r o d u c ek - - 1 ， 旺一1 ) 2 a n d f 正 l 。lf _ 1n e wf e e d b a c kf u n c t i o n ss e p e r a t e l yf r o mag i v e nf e e db a c kf u n c t i o no fk - a r yd eb r u i j n o s e q u e n c e s 4 t h e o r yo fd e p t hd i s t r i b u t i o no fc o d e so v e raf i n i t er i n gz 4i se s t a b h s h e d t h i sd i s s e r t a t i o n d e f i n e st h ed e p t ho fae o d e w o r da n dt h ed e p t hd i s t r i b u t i o no fc o d e so v e raf i n i t er i n gz ，g i v e sa n u m b e ro fp r o p e r t i e so nt h ed e p t ho fc o d e w o r d sa n dt h ed e p t hd i s t r i b u t i o no f i n e a rc o d e so v e r r i n g 五，a n ds t u d i e st h ed e p t hs p e c t r u m so fl i n e a rc o d e sa n dl i n e a rc y c h cc o d e so nr i n gz l ，a n di t i sp r o v e dt h a tt h ed e p t h s p e c t r u mo fh n e a rc o d eo ft y p e4 1 2 2h a sa tl e a s tk l + 2n o n z e r ov a l u e s ， a n dt h ed e p t hs p e c t r u mo fl i n e a rc y c h cc o d eo ft y p e4 i s h ，n 一1 ，”一k + 1 b yu s i n g e o m b i n a t o r ym a t h e m a t i c s ，t h e o r yo fg r a p ha n dn u m b e rt h e o r y ，t w or e c u r s i v ea l g o r i t m sf o r c o m p u t i n gt h ed e p t ho fae o d e w o r do nr i n gz 4a r ep r e s e n t e d 5 p r o p e r t i e so fl i n e a rc o d e sa n dc y c l i cc o d e so v e rf o u r e l e m e n t r i n gf 2 + u f 2a r es t u d i e d t h i sd i s s e r t a t i o ng i v e sg e n e r a t o rm a t r i x e so fl i n e a rc o d e sa n dt h e i rd u a lc o d e ，p r o v e st h a tg r a y i m a g eo fah n e a rc o d eo v e rr i n gf 2 + u f 2 i sa l s oal i n e a rc o d e ，a n dg r a yi m a g eo fal i n e a rc o d ea n d i t sd u a lc o d ea r ed u a lt oe a c ho t h e rb yu s i n gg r a ym a p p i n gf r o mr i n gf z + u f 2t of i e l df 2 o n e t o o n ec o r r e s p o n d e n c eb e t w e e nc y c l i cc o d e so v e rr i n gf 2 + u f 2a n dm a i ni d e a l si nq u o t i e n tr i n ga m r k ( ，一1 ) ，a n dt h a tb e t w e e n ( 1 + ) 一c y c h ec o d e so v e rr i n gf e + u f 2a n dm a i ni d e a l si n q u o t i e n t r i n gb 。= r e x l o w - - 1 - - u ) a r eg i v e n ，w h e r er = f 2 + u f 2 ，a n d i ti sp r o v e dt h a tg r a y i m a g eo fa ( 1 + “) 一c y c l ec o d eo fl e n g t hn o v e rr i n gf 2 + u f 2i sac y c l i cc o d eo fl e n g t h2 no v e rf i e l d r 6 i nt h i sd i s s e r t a t i o n ，t h ee x t e n s i v er e s e a r c h e so ne r r o r c o r r e c t i n gc o d i n gt h e o r yo v e rf i n i t e r i n g 磊a r em a d ei nt h ef o l l o w i n ga s p e c t s s t r u c t u r eo fg a l o i sr i n gg r ( q ”) a n dr e p r e s e n t a t i o no fi t se l e m e n ta r es t u d i e d ，p o l y n o m i a l t h e o r yo v e rg a l o i sr i n gg r ( 矿) i se s t a b l i s h e d ，a n dh a n s e l sl e m m aa n dh e n s e ll i f ta r eg i v e n a t r a c em a po v e rr i n gg r ( ，) i sd e f i n e d ，a n di ti sp r o v e dt h a tt h et r a c em a ph a st r a n s i t i v i t y ，a n d t h e nt h et r a c er e p r e s e n t a t i o no fc y c l ec o d e so v e rr i n gg r ( g 拼) i sg i v e n t r a c ec o d ea n ds u b r i n gs u b c o d eo v e rr i n gg r ( 矿) a r ed e f i n e d ，a n di t i sp r o v e dt h a tt h e t r a c ec o d eo fd u a lc o d eo fac o d ei st h ed u a lc o d eo fs u b r i n gs u b c o d e t h i sd i s s e r t a t i o nd e f i n e sg r a ym a pf r o mr i n gz ，+ 1t or i n gz p ，s t u d i e sp r o p e r t i e so ft h e m a p a n dg i v e sam e t h o dw h i c hc a nc a l c u l a t eg e n e r a t o rm a t r i xo fi t sg r a yi m a g ef r o mg e n e r a t o r m a t r i xo fal i n e a rc o d eo v e rr i n gz ，i ti sp r o v e dt h a tac o d eo v e rr i n g 乙i sac y c l i cc o d e ，i f a n do n l yi fi t sg r a yi m a g ei saq u a s i c y c l i cc o d e a ni s o m o r p h i s mo fr i n g sb e t w e e nl i e a r ( 1 一户) 一 摘要 _ ，一一 c y c l i cc o d e sa n dl i n e a r ( 1 一 ) 一c y c f i cc o d e so v e rr i n g z ，t li sc o n s t r u c t e d b yu s i n gt h e i s o m o r p h i s m ，an o m b e ro fp r o p e r t i e so fl i n e a r ( 1 一肇) 一c y c l ec o d e s a r es t u d i e d ，a n dt h e n u m b e r so fg e n e r a t o rp o l y n o m i a l sa n dc o d e w o r d so fl i n e a r ( - t p o c y c f i cc o d e sa r eg i v e n - an u m b e ro fp r o p e r t i e so fd e p t hd i s t r i b u t i o no fl i n e a rc o d e so v e rr i n gz ，a r es t u d i e d ，a n d ar e c u r s i v ea l g o r i t h mf o rc o m p u t i n gt h ed e p t ho fc o d e w o r do v e rr i n gz i sa l s og i v e ni nt h i s d i s s e r t a t i o n t h i sd i s s e r t a t i o bd e f i n e sas y m m e t r i z e dw e i g h te n u m e r a t o ro fh n e a r c o d eo v e rr i n gz b b yu s i n gd i s c r e a t eh a d a m a r dt r a n s f o r m ，as y r a m e t r i z e dm a c w i n l a m si d e n t i t yb e t w e e n al i n e a r c o d eo v e rr i n g 五a n di t sd u a lc o d ei sg i v e n t h er e s e a r c hr e s u l t sp r e s e n t e da b o v en o to n l ye n r i c ht h ec o n t e n to fs t r e a mc i p h e r sa n de r r o r c o r r e c t i n gc o d i n gt h e o r y ，b u ta l s ow i d e nt h ea r e ao fs c i e n t i f i ci n v e s t i g a t i o na n dt h ea p p f i e d areao f t h et r a d i t i o n a ls t r e a mc i p h e r sa n de r r o r c o r r e c t i n gc o d i n gt h e o r y k e yw o r d s ：s t r e a mc i p h e r ；d eb r u i j ns e q u e n c e ；e r r o r c o r r e c t i n gc o d e ；l i n e a rc o d e ；c y c f i e c o d e ；g r a ym a p 合肥工业大学 本论文经答辩委员会全体委员审查，确认符合合 肥工业大学博士学位论文质量要求。 答辩委员会签名( 工作单位、职称) 揣硇删捌貉流域 委员：等也c 、中i 虱孛叶戈、叙梭、待移 毒缎跌襁犬占，锵黼) 黝勤膨姒沪叛缓于爹矜 刻政l 删髯撒、衔夕 导师： 掰毛张 叶向东 王捍贫 方廷健 章璞 吴先良 周永务 刘心报 教授、博导 教授、博导 教授、博导 教授、博导 教授、博导 教授、博导 教授、博导 邵惠鹤教授、博导 蒋继发教授、博导 朱功勤教授、博导 邵惠鹤 朱功勤 梁进 吴先良 刘业政 教授、博导 教授、博导 教授、博导 教授、博导 教授、博导 同行评议专家名单 计算数学 计算机软件 计算机应用 代数学及应用 计算机应用 信息管理系统 信息管理系统 同行评阅专家名单 计算机应用 计算机图形学 计算数学 答辩委员会名单 计算机应用 计算数学 应用数学 计算机应用 信息管理系统 答辩委员会主席 中国科学技术大学 北京大学 中科院智能所 上海交通大学 安徽大学 合肥工业大学 合肥工业大学 上海交通大学 同济大学 合肥工业大学 上海交通大学 合肥工业大学 中国科学技术大学 安徽大学 合肥工业大学 邵惠鹤教授、博导计算机应用 上海交通大学 合肥工业大学博士学位论文 致谢 值此论文完成之际，衷心地向辛勤培养我的导师杨善林教授表示崇高的敬意和深深的谢 意。感谢杨老师给予我学业上的谆谆教导、生活上无微不至的关怀及工作上的指导和帮助。在 撰写论文期间杨老师从论文的选题思路、论文的撰写结构到具体的问题如何讨论等多个方面 给予我启发与指导，使我顺利地完成了博士学位论文，在此再次向杨老师表示感谢! 杨老师身 上的那种永不知疲倦的拼搏精神、超前的开拓性工作思路和脚踏实地的工作作风都给我留下 了深刻的印象并将成为我以后学习和工作中的楷模。 感谢合肥工业大学计算机网络系统研究所为本人提供了良好的学习条件，感谢刘业政、粱 昌勇、马溪骏、周永务、刘心报等老师的各种帮助。 感谢合肥工业大学管理学院、研究生院、学科学位处、计算机学院的领导、老师和朋友对我 的帮助和关心。 感谢合肥工业大学理学院领导，特别是苏化明教授和何晓雄教授，在我读博期间给予的支 持和关照，感谢理学院的全体同仁对我工作的理解和支持。 感谢合肥工业大学的副校长刘光复和教务处的领导，特别是李和平处长，在我读博期间给 予我工作上的指导和帮助，使我能顺利地搞好教务工作，才使我有较充裕的时间来完成学业和 论文。 感谢我的夫人陈秀长期对我的事业的鼓励、理解、支持和奉献，甚至不惜牺牲自己的专业 和事业，长期为我创造美好的生活环境和工作环境，正是由于她的鼓励和付出，才使我能考上 博士并按期完成学业和论文。也感谢我的儿子朱永恺给我精神上的快乐和心理上的满足，为我 的工作和事业增添了动力。 感谢各位评审专家在百忙中挤时间对论文进行了仔细的评阅。 最后，再次向所有帮助和关心过我的朋友们表示衷心的感谢l 第一章引言 第一章引言 1 1 研究信息安全领域中的序列密码和纠错码的意义 当今世界信息技术迅猛发展，社会正进入或已经进入信息社会。信息化是信息社会的特 征。信息化以通信和计算机为技术基础，以数字化和网络化为技术特点。随着计算机网络的普 及，大量的电子数据通过网络传输到世界各地成为可能，极大地促进社会经济的发展，也给人 们的生活和工作带来了极大的方便；但在人们享受信息化带来的巨大变革的同时，人们也承受 着信息被篡改、泄露、伪造等诸多信息不安全的威胁，尤其是在传输具有重大经济价值或关系 到国家、军队的命运等重要数据的过程中任何一点泄露或差错都可能造成不可估量的损失， 因此，可以说信息安全问题不仅关系到个人的财产或隐私的安全，而且关系到金融、交通、商 业、医疗、电力等涉及国民经济命脉的事业安全，甚至直接影响军事和国家的安全，因此受到各 国政府的高度重视， 随着信息技术的发展，信息安全的内涵在不断的延伸，从最初的信息保密性( 保证信息不 泄露给未经授权的人) ，拓展到信息的完整性( 防止信息被未经授权的人篡改保证真实的信息 从真实的信源无失真地到达真实的信宿) 、信息的可用性( 保证信息及信息系统确实为授权者 所用，防止由于计算机病毒或其它人为因素造成的系统拒绝服务或为敌手可用) 、信息的可控 性( 对信息及信息系统设施安全监控管理) 、信息的不可否认性( 保证信息行为人不能否认自己 的行为) ，进而发展到目前的攻击、防范、检测、控制、管理、评估等六个方面的基础理论和实施 技术。因此，信息安全领域是一个综台、交叉的学科领域，要提高信息的安全性，人们必须综合 利用纠错码理论、密码学、计算理论与技术、网络技术等诸多学科的长期积累和最新发展成果， 提出系统的( 而不是个别的) 、完整的( 而不是零碎的) 、协同的( 而不是独立的) 懈决信息安全的 方案。 解决信息安全的方案的核心是密码技术，密码学是研究密码理论和技术的学科，主要研究 分组密码、序列密码、公钥密码、认证码、数字签名、身份识别、密钥管理等理论与内容，而密码 学的基础是纠错码理论。因此可以说没有好的纠错码理论就没有好的密码理论，没有好的密码 理论就段有好的密码技术，没有好的密码技术就投有信息的安全。因此，为了不断提高信息的 安全性，不仅要加强信息安全的核心技术密码技术的研究还要加强密码理论的基础理论 纠错码理论的研究。因此，本文研究信息安全领域中有限环上的序列密码和纠错码理论中 的问题不仅具有理论意义，而且具有实际价值。 1 2纠错码和密码学的发展历史和现状 1 2 1 纠错码的发展历史与现状 1 9 4 8 年，s h a n n o n 在通信的数学理论一文中提出了著名的信道编码定理，开创了纠 2合肥工业大学博士学位论文 错码理论的研究方向，莫定了纠错码理论的基石。从此以后，h a m m i n g 口 ，b o s e 、c h a u d h u r i 、 h o c q u e n g h e m ( b c h ) 5 一引、m a s s e y $ - - 1 2 、m a c w i l l i a m s 1 h “、g o p p a l l 6 , 1 7 ，n e c h a e v e l 引、冯贵 良“”等纠错码专家先后创造性地提出了一系列设计好码和有效译码的方法，使纠错码理论 实现了一系列的跨越式发展，也使得纠错码理论受到了越来越多的通信和数学工作者，特别是 代数学家的重视，使纠错码理论无论在理论上还是在实际应用中都得到飞速发展。迄今，纠错 码理论已有5 6 年的历史，其发展过程大致分以下四个阶段。 第一阶段为上世纪5 0 年代至6 0 年代初，这是纠错码从无到有、得到迅速发展的年代。主 要研究各种有效的编码方法和译码方法。奠定了线性分组码的理论基础；1 9 5 9 年和1 9 6 0 年， 由b o s e 、c h a u d h u r i 和h o c q u e n g h e m 提出纠正多个随机错误的循环码，即著名的b c h 码o “3 的构造方法，b c h 码是迄今为止所发现的一类最好的线性纠错码类，在编码理论中起着重要 作用；给出了纠错码的基本码限。 第二阶段为上世纪6 0 年代至7 0 年代初，这是纠错码发展过程中最为活跃的时期，不仅提 出了各种各样的编码译码方法，而且还研究了码的重量分布、译码错误概率等纠错码实用化问 题，所有这些问题的研究为纠错码理论的应用打下了坚实基础。在此期间，以有限域理论为基 础的线性分组码理论已趋成熟。 第三阶段为上世纪7 0 年代至8 0 年代，这是纠错码发展史中具有极其重要意义的时期。在 理论上，以g o p p a 为首的一批学者构造了一类g o p p a 码，其中一类子码能达到s h a n n o n 在信 道编码定理中所提出的码所能达到的性能，这在纠错码历史上具有划时代意义；在应用上，由 于大规模集成电路和微机的迅速发展，使纠错码理论得到了广泛的应用，并取得了巨大成功。 如美国在上世纪7 0 年代初发射的。旅行者”号宇宙飞船中，成功地应用了纠错码技术，使宇宙 飞船在极其遥远的3 0 亿公里的距离外向地面传回了天王星、海王星等许多宝贵的图片资料。 第四阶段为上世纪8 0 年代至今，这是纠错码理论取得突破性发展时期在此期问，开创了 代数几何码和有限环上的纠错码理论的新研究方向。在1 9 8 1 年，g o p p a 1 6 3 利用代数曲线构造 了一类代数几何码，开创了代数几何码研究的先河，但并未引起人们太多的关注；1 9 8 2 年 t s f a s m a n 、z i n k 、v l a d u t 口”共同证明了一个