（应用数学专业论文）有限环上的纠错码和序列密码中若干问题的研究.pdf

有限环上的纠错码和序列密码中若干问题的研究 摘要 目前，随着生产技术的飞速发展和理论研究的不断深入，有限环上的纠错 码理论和序列密码理论的研究不仅具有重要的理论意义而且具有重要的实际应 用价值。近十几年来，有限环上的纠错码理论的研究是纠错码理论研究领域的 一个研究热点。环而+ 矾是介于环z 与域一之间的一种四元素环，因此分享 了环z 。与域凡的一些好的性质；p u d a y a 等首先将环昂+ 蜗+ + 昂用于 最优频率跳跃序列的构造，此类环上的编码理论研究成为一个新的热点。本文 从多方面研究了b + “b + + 矿包这类环上的线性码、循环码的各种性质。几 十年来，研究d eb r u i j n 序列的有效生成算法一直是序列密码研究领域的一个 核心问题，由于二元数域f 2 的运算的简单性，目前已有大量产生二元d e b r u i j n 序列的生成算法，但是由于一般的有限域，特别是有限环上运算的复杂性，有 限环上的d eb r u i j n 序列的有效生成算法与实际需要还有相当大的距离。本文 在四元素环z 。和足+ “如上，分别给出d eb m i j n 序列的一个有效生成算法。具 体内容如下： 1 给出了环f 2 + ”f 2 的g a l o i s 环的相关理论，指出此g a l o i s 环的自同构群 不同于z 4 环上的g a l o i s 环的自同构群；定义了g a l o i s 环上的迹码的概念及子环 子码的概念，证明了此g a l o i s 环上的一个码的对偶码的迹码是该环的子环子码 的对偶码。 2 考虑环f 2 + u f 2 上的长度- = 2 的循环码，给出环f 2 + u f 2 上任意偶长度 的循环码的结构定理，更进一步给出任意长度的循环码的计数公式。 3 将k e r d o e k 码和p r e p a r a t a 码的概念引入到环对“r 上，并给出k e r d o c k 码的迹表示；当p = 2 时，建立了环e + z 幔上这两类码与域巧上的r e e d - m u l l e r 码之间的联系；并证明了一阶r e e d m u l l e r 码是环只+ 以上k e r d o c k 码的线性 子码的g r a y 像。 4 定义了环( 巴+ 峨+ + ”) ”到彤”的一个g r a y 映射，给出g r a y 映 射的几个性质，并给出该环上码为循环码的一个充要条件。 5 给出环e + “e + + u k - i c 上的线性码及对偶码的生成矩阵，建立了此 环上的线性码及其对偶码的m a c w i l l i a m s 恒等式。 6 在四元素环z 。和尼+ “f 2 上，分别给出一个由低阶d e b r u i j n 序列的反馈 函数产生任意高阶d cb r u i j n 序列的有效升级算法。 关键词：纠错码：线性码；循环码；g r a y 映射；序列密码；d eb m i j n 序歹0 r e s e a r c ho ns o m ep r o b l e m so fe r r o r - c o r r e c t i n gc o d e sa n d s e q u e n c ec i p h e r so v e r f i n i t er i n g s a b s t r a c t a tp r e s e n t ，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 ne 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 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 c a ls i g n i f i c a n c eb u t a l s oi m p o r t a n tp r a c t i c a lv a l u e 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 gt h e o r yo v e rf i n i t er i n g s h a v ed 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 er i n g f 2 + 啦i sa f o u r - e l e m e n tr i n gw h i c hs h a r e ss o m eg o o dp r o p e r t i e so f b o t hz a n d 乃 t h er i n gf p 七u f p + + 皆lf p ，w h i c hi st h eg e n e r a le a s eo fr i n gf 2 + u f 2 ，h a sa l r e a d y b e e nu s e di nt h ec o n s t r u c t i o no fo p t i m a lf r e q u e n c y - h o p p i n gs e q u e n c eb yru d a y a c o d i n gt h e o r yo v e rt h e s er i n g sh a sr e c e n t l yr e c e i v e dag r e a td e a lo f i n t e r e s ta m o n g c o d i n gt h e o r i s t s t h i sd i s s e r t a t i o nm a k e sad 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 s o fl i n e a rc o d e sa n dc y c l i cc o d e so v e rt h e s er i n g s 易+ 晦+ + 矿昂r e s e a r c ho n a l g o r i t h m sf o rg e n e r a t i n gd eb m i j ns e q u e n c e si sa l w a y sak e yp r o b l e mi nt h es t u d y f i e l do fs t r e a mc i p h e r si nt h ep a s ts e v e r a ld e c a d e s a l t h o u g hn u m b e r so fe 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 la c o n s i d e r a b l yb i gg a pb 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 j ns e q u e n c e so v e r f i n i t er i n g s ，a n dt h ep r a c t i c a lr 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 r f i n i t er i n g s i nt h i sd i s s e r t a t i o n ，w eg i v ea ne f f i c i e ma l g o r i t h mf o rg e n e r a t i n gd e b r u i j ns e q u e n c e sb yr a i s i n gs t a g eo v e rz 4a n df 2 + u f 2 ，r e s p e c t i v e l y t h ed e t a i l sa r e g i v e na sf o l l o w s ： 1 w eg i v et h et h e o r yo fg a l o i sr i n go v e rf 2 + “r ，a n ds h o wt h a tt h e a u t o m o r p h i s mg r o u po ft h i sg a l o i sr i n gi sd i f f e r e n tf r o mt h ec o r r e s p o n d i n gg r o u p o v e rz 4 t r a c ec o d ea n ds u b r i n gs u b c o d eo v e rt h i so a l o i sr i n ga r ed e f i n e d ，a n di ti s p r o v et h a tt h et r a c ec o d eo fd u a lc o d eo fal i n e a rc o d ei st h ed u a lc o d eo fs u b r i n g s u b c o d e 2 w eg i v et h es t r u c t u r eo fc y c l i cc o d e so v e rr + 如f o ra r b i t r a r ye v e nl e n g t h ， a n dd e t e r m i n et h en u m b e ro f c y c l i cc o d e sf o rag i v e nl e n g t h 3 t h ec o n c e p t so fk e r d o c kc o d ea n dp r e p a r a t ac o d ea r ei n t r o d u c e di n t ot h e r i n gb 十峨，t h et r a c er e p r e s e n t a t i o no fk e r d o c kc o d ei sg i v e n i nt h ec a s ep 2 2 ，w e g i v et h er e l a t i o n so ft h e s et w oc o d e sw i t hb i n a r yr e e d m u l l e rc o d e s ；a n dw ep r o v e t h eo n eo r d e rr e e d - m u l l e rc o d ei st h eg r a yi m a g eo fal i n e a rs u b c o d eo fk e r d o c k c o d e 4 ag r a ym a pf r o m 姬口+ 杖f 一+ 毋lf t o f j n i s d e f i n e d ，a n ds o m e p r o p o s i t i o n so ft h em a pa r eg i v e n as u f f i c i e n ta n dn e c e s s a r yc o n d i t i o na b o u tc y c l i c c o d eo v e rf p + n f p + + 世lf pi sg i v e n 5 t h eg 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 r d u a lc o d e so v e r f u f 一+ 矿if pa n dm a c w i l l i a m si d e n t i t i e sb e t w e e nl i n e a rc o d e sa n dt h e i rd u a l s a r eg i v e n 6 w eg i v ea ne f f i c i e n t a l g o r i t h mf o rg e n e r a t i n ga r b i t r a r yh i g h e rs t a g ed e b r u i j ns e q u e n c e sf r o mag i v e nf e e d b a c kf u n c t i o no fl o w e rs t a g ed eb r u i j ns e q u e n c e s b yr a i s i n gs t a g eo v e rz 4a n df 2 + 啦，r e s p e c t i v e l y k e yw o r d s ：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 l i cc o d e ；g r a ym a p ；s t r e a m c i p h e r ；d eb r u i j ns e q u e n c e 独创性说明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工作及取得的研 究成果。据我所知，除了文中特别加以标志和致谢的地方外，论文中不包含其他人 已经发表或撰写过的研究成果。也不包含为获得 盒壁王些太堂或其他教育机构 的学位或证书而使用过的材料。与我一同工作的同志对本研究所做的任何贡献均已 在论文中作了明确的说明并表示谢意。 学位敝储擗粢沾 签字蹶矽月7 日 学位论文版权使用授权书 本学位论文作者完全了解 金攫王些塞堂有关保留、使用学位论文的趣定， 有权保留并向国家有关部门或机构送交论文的复印件和磁盘，允许论文被查阅或谶 阅。本人授权 金胆王些太堂可以将学位论文的全部或部分论文内容编入有关数、 据库进行检索，可以采用影印、缩印或扫描等复制手段保存、汇编学位论文。 ( 保密的学位论文在解密后适用本授权书) 学位论文者签名 签字日期 o ( 年 导 签 7 日 电话：f 7 r ( 口弘7 卵 邮奶唧 獬 嘘私 吼胆 却名 一雠 致谢 在这三年的研究生学习阶段，我的导师朱士信教授不仅在学业上对我进行 耐心的指导，而且还在生活上给予我无微不至的关怀。朱老师严谨的治学态度、 宽广的胸怀和豁达的处世之道给我留下了深刻的印象，并将成为我以后学习和 工作中的楷模。值此论文完成之际，作者向朱老师致以最诚挚的敬意和衷心的 感谢! 在本人学习期间，还得到了苏化明老师、程正杰老师、刘丽老师等很多老 师的热心的关怀和无私的帮助，在此，向各位老师表示深深的谢意。 同时，真诚感谢师兄李平、钱建发、杨晓伟、余海峰、童宏玺，师姐 钱开燕，以及韩牟、王敏秋、王冬银、开晓山、唐淼、施敏加等同学的关 心和帮助，在此一一表示感谢。 最后，感谢我的父母、姐姐、妹妹，在我研究生学习阶段对我提供的 物质帮助和精神鼓励。正是家人的无私的帮助和奉献，才使我在研究生阶 段全身心的投入到学习之中。 作者：吴波 2 0 0 6 年5 月 1 1 引言 第一章绪论 s h a n n o n 在1 9 4 8 年发表的论文“a m a t h e m a t i c a lt h e o r yo f e o m m u n i e a t i o n ”【l 】 中首次提出了著名的有扰信道编码定理，开创了纠错码理论的研究方向，奠定 了纠错码理论的基石。根据s h a n n o n 的思想，h a m m i n g f 2 1 、b o s e 、c h a u d h u f i 、 h o c q u e n g h e m ( b c h ) 1 3 - 5 1 、m a s s e y t 6 - 8 、m a c w i l l i 锄s ) 、g o p p a 1 2 j 3 1 、n e c h a e v 【1 4 】、 冯贵良 t s , t 6 1 等纠错码理论专家先后给出了一系列设计好码和有效译码的方 法。而后，纠错码受到了越来越多的通信和数学工作者，特别是数学家的 重视，使纠错码无论在理论上还是在实际中都得到飞速发展。迄今，纠错 码已有五十多年的历史，其发展过程大致分为以下几个阶段： 2 0 纪5 0 年代至6 0 年代初，主要研究各种有效的编、译码方法，奠 定了线性分组码的理论基础，提出了著名的b c h 码，同时也给出了纠错 码的基本码限。这是纠错码从无到有得到迅速发展的年代。 2 0 纪6 0 年代至7 0 年代初，这是纠错码发展过程中最为活跃的时期。 不仅提出了许多有效的编译码方法，而且注意到了纠错码的实用化问题， 讨论了与实用有关的各种阃题，所有这些问题的研究为纠错码的实用打下 了坚实基础。在此期间，以代数方法特别以有限域理论为基础的线性分组 码理论已趋成熟。 2 0 纪7 0 年代至8 0 年代初，这是纠错码发展史中具有极其重要意义 的时期。在理论上以g o p p a 为首的一批学者，构造了一类g o p p a 码，其 中一类子码能达到s h a n n o n 在信道编码定理中所提出的s h a n n o n 码所能达 到的性能，这是纠错码历史上具有划时代意义。在这期间大规模集合电路 和微机的迅速发展，为纠错码的实用打下了坚实的物质基础，因而与实用 相关的各种技术及有关问题得到了极大关注，并在实用中取得了巨大的成 功。 自2 0 纪8 0 年代初至今，g o p p a 等从几何观点讨论分析码，利用代数 曲线构造了一类代数几何码，在这些码中，某些码的性能达到了s h a n n o n 码所能达到的性能。由于代数几何码是一类范围非常广的码，在理论上已 证明它具有优越性能，因而受到了编码理论研究者，尤其是代数几何学家 的重视，使代数几何码的研究得到迅速发展，取得了许多成果。自上世纪 7 0 年代末以来，纠错码技术已开始渗透到很多领域。利玛纠错码中的许 多编、译码原理和方法，与通信系统中其它有关技术相结合，得到了一些 令人惊喜的结果。如：纠错码与调制技术相结合所产生的t c m 技术，已 作为国际通信中标准技术而推广使用；纠错码与密码结合，可以构造出一 类既能加密签名，又具有纠错功能的密码系统；纠错码与信源编码相结合 的结果，使得通信系统更为有效与可靠。不仅如此，纠错码中的许多译码 思想和方法，与神经元网络中的能量函数有密切关系，可以用来解决神经 元网络中的一些问题。因此，可以预料，随着科学的进步和实际需要，纠 错码理论必将进一步发展，它的应用范围必将进一步扩大。 密码学是研究密码理论和技术的科学，主要研究分组密码、序列密码、 公钥密码、认证码、数字签名、身份识别、密钥管理等理论密码系统或通 信安全的一门科学。按照加密方式的不同，可将密码体制分为序列密码( 或流密 码) 和分组密码两种。在序列密码中，将明文信息逐字逐位地加密，在分组密码 中，先将明文信息分成若干个组，再逐组地加密。在当今众多的密码系统中， 最常用的密码是序列密码。原因是序列密码不存在数据扩展，实时性好，加密 与解密容易实现。 序列密码的思想起源于上世纪二十年代，最早的二进制序列密码系统是 v e r n a m 密码，它将每个英文字母变为5 位二进制电码，明文信息与密钥都为二进 制数字序列，加密是将明文序列和密钥序列逐位模2 相加进行，解密是将密文序 列和密钥序列逐位模2 相加进行。较全面地介绍序列密码的专著有文献 4 7 5 2 序列密码的安全性主要依赖于密钥序列，因而什么样的密钥序列是安全可靠的 密钥序列，以及如何生成这种序列就成了序列密码中研究的两个主要问题。目 前常用的密钥序列主要是各种移位寄存器序列，尽管级数较小的移位寄存器序 列不能直接用作密钥序列，但利用移位寄存器作为基本模块来复合构造密钥序 列是人们常采用的方法。移位寄存器序列的理论研究是从上世纪6 0 年代左右开 始的，其基本理论在文献 4 7 、4 9 - 5 2 中有系统地介绍。 在所有的移位寄存器序列中，最长( 周期最大) 的n 级非线性移位寄存器序列 不仅具有良好的伪随机特性，而且有很高的线性复杂度，因此这种序列最符合 密钥序列的要求，具有很好的安全性，也是最常用的密钥序列，人们称这种序 列为d eg r u i j n 序列，又称为m 序列。文献 5 3 - 5 6 对d eb r u i j n 序列的复杂度进 行了全面研究。如何有效快速生成d eb r u i j n 序列一直是序列密码中的研究热点 之一。下面简述研究d eb r u i j n 序列生成算法的发展历史与现状。 关于全长的非线性移位寄存器序列的研究，最早可追溯到1 8 9 4 年，当年， m a r i e n 了解决数论中的一个问题时提出了这种序列，并给出了计数公式，但直 至k j l 9 4 6 年，d eb r u i j n 为解决组合数学中的问题时，才再次讨论了这种序列，并 在文献 6 6 中用图论的方法给出了其理论算法，从此，这种序列被称为d eb r u i j n 序列。1 9 7 0 年，a l e m p e l 在文献 6 7 中定义了d eb r u i j n g o o d 图的同态，并利 用同态映射构造了d eb r u i j n 序列，这篇论文奠定了d eb r u i j n 序列的理论基础， 并掀开了研究d eb r u j n 序列生成算法的序幕。此后，f r e d r i c k s e n 等一批学者 给出了一系列构造d eb r u j n 序列的生成算法，在文献 5 7 3 中对1 9 8 2 年前的所有 生成算法进行了综述。从上世纪八十年代中期到上世纪九十年代中期是研究d e b r u i j n 序列生成算法的高潮期，也是各种算法理论的发展时期。在此期间有大 量的不同的生成d eb r u i j n 序列的算法问世，其中典型的算法有e t z i o n ”州的并 圈算法，高鸿勋的剪接算法“”熊荣华的反馈函数生成算法“”，朱士信的无记忆 算法“。从上世纪九十年代中期至今，是研究如何提高算法的有效性的时期， 即寻找在计算机上更容易实现的算法，文献 7 7 、7 8 中的算法是这时期的代表 性算法。随着密码学的不断发展人们正在寻找更有效的产生d eb r u i j n 序列的 生成算法。 1 2 本文的主要内容 目前，随着生产技术的飞速发展和理论研究的不断深入，有限环上的纠错 码理论和序列密码理论的研究不仅具有重要的理论意义而且具有重要的实际应 用价值。近十几年来，有限环上的纠错码理论的研究是纠错码理论研究领域的 一个研究热点。环几十甜乃是介于环z 。与域一之间的一种四元素环，因此分享 了环z 4 与域f 4 的一些好的性质；p u d a y a 等首先将环e + 峨+ + ”。1 e 用于 最优频率跳跃序列的构造，此类环上的编码理论研究成为一个新的热点。本文 从多方面研究了b + ”b + + 矿。昂这类环上的线性码、循环码的各种性质。几 十年来，研究d eb r u ij n 序列的有效生成算法一直是序列密码研究领域的一个 核心问题，由于二元数域f 2 的运算的简单性，目前已有大量产生二元d eb r u i j n 序列的生成算法，但是由于一般的有限域，特别是有限环上运算的复杂性，有 限环上的d eb r u i j n 序列的有效生成算法与实际需要还有相当大的距离。本文 在四元素环z 。和f 2 + u f 2 上，分别给出d eb r u i j 序列的一个有效生成算法。具 体内容如下： 1 给出了环f 2 + 讥的g m o i s 环的相关理论，指出此g m o i s 环的自同构群 不同于z 4 环上的g m o i s 环的自同构群：定义了g m o i s 环上的迹码的概念及予环 子码的概念，证明了此g m o i s 环上的一个码的对偶码的迹码是该环的子环子码 的对偶码。 2 考虑环n + “而上的长度n = 2 n 的循环码，给出环f 2 + 如上任意偶长度 的循环码的结构定理，更进一步给出任意长度的循环码的计数公式。 3 将k e r d o c k 码和p r e p a r a t a 码的概念引入到环r + “b 上，证明了它们是 一对对偶码；并给出k e r d o c k 码的迹表示；当p = 2 时，建立了环e + “只上这两 类码与域只上的r e e d m u l l e r 码之间的联系；并证明了一阶r e e d - m u l l e r 码是环 只+ “只上k e r d o c k 码的线性子码的g r a y 像。 4 定义了环( + “+ + ) ”到彤的一个g r a y 映射，给出g r a y 映 射的几个性质，证明环巴+ “十+ “上的长为n 的线性码的g r a y 像仍是 线性码，及该环上长为盯的( 1 一“) - 循环码的g r a y 像是域t 上的长为p k n 指数 为p “1 的准循环码，并给出该环上码为循环码的一个充要条件。 5 给出环0 + 辫0 + + “1 上的线性码及对偶码的生成矩阵，定义此环 上的两种重量计数子，通过h a d a m a r d 变换，建立了环0 + m 0 + + “卜1 上的 线性码及其对偶码的m a c w i t l i a m s 恒等式。 6 在四元素环z 。和r + h r 上，分别给出一个由低阶d e b m j = j n 序列的反馈 函数产生任意高阶d eb r u i j n 序列的有效升级算法。 这些内容的研究对进一步丰富纠错码在有限环上的理论及构造些性能较 好的码都有一定的指导意义。丰富了有限环上的序列密码理论，促进了序列密 码的应用。 第二章有限环上的纠错码 从1 9 4 8 年s h a n n o n 开创纠错码理论以后，人们利用有限域理论“7 1 作为工具， 建立了系统的有限域上的纠错码理论，这些理论在文献 1 1 、4 8 中有全面的研 究。近年来，编码理论中的一个突破性的进展是h a m m o n s 等人在文献 1 7 1 6 d 证 明了一些高效的二元非线性码，如p r e p a r a t a 码、k e r d o c k 码等可视为环z 。上循环 码在g r a y 映射下的像，从而环z 乃至更一般的有限环上的编码理论的研究进入 一个全新方向。文献 2 6 一 q u a t e r n a r yc o d e s 的出版标志着环z 。上的纠错 码理论已有了基本框架，随后，环z 上的纠错码理论进人全面发展时期。文献 1 9 、2 0 中引入一种介于环z 。与域f 之间的四元素环e + 峨，讨论了环旺+ 甜e 上循环码的结构、译码问题及类型i i 码的性质，同环z 相比，环e + “e 上的码 具有编、译码简单更易于实现等特点。关于环e + 峨本身的结构在文献【1 9 、 2 0 中均有详细描述，它是指剩余类环f ： u l ( u 2 ) ，其元素分别记为 0 ，1 ，“， l + u ) ，若将“视为z 。环上元素2 ，l + u 视为元素3 ，则其乘法与z 。环上乘法一致。 若将u 视为域f 4 = 0 ，1 ，屈芦2 上元素p ，l + u 视为2 ，则其加法与域f 4 上加法一 致，因而它分享了环z 。与域f 4 的一些良好性质。p _ u d a y a 等首先将环昂+ 峨 + + 矿7 r 用于最优频率跳跃序列的构造，此类环上的编码理论研究成为一个新 的热点( 见文献 1 8 2 4 1 ) 。本章从多方面研究了这类环上的线性码、循环码的各 种性质。 2 1 环f 2 + u f 2 的g a l o i s 环上的迹码 本节给出了环f 2 + u f 2 的g a l o i s 环的相关理论，指出此g a l o i s 环的自同构群 不同于z 4 环上的g a l o i s 环的自同构群：定义了g a l o i s 环上的迹码的概念及子环 子码的概念，证明了此g a l o i s 环上的一个码的对偶码的迹码是该环的子环予码 的对偶码。 2 1 1 环f 2 + | 如上的g a l o i s 环 环r = f 2 + u f 2 是有唯一极大理想 o ，“) 的局部环，r 中任意元素 都可唯一 表示为：五= ，( 旯) + 口( 五) ，r ( ) ，口( a ) e 。称z = ，( 丑) 为元素a 的二元约化，称 ki 二元多项式歹( x ) = j 一五【x 】为，( x ) = q x r 【x 】的二元约化a 如果7 0 ) ；oj - o 为五【叫中不可约多项式，称，( x ) 为r 上基本不可约多项式。特别地如果7 0 ) 为e 【x 】中m 次本原多项式，称厂( x ) 为月上m 次基本本原多项式。 设h ( x ) r x 】为m 次基本不可约多项式，称剩余类环 r ( x 】( 矗( x ) ) = d o + d i x + + 口，一l x ”- 1 + ( ( x ) ) 1 口。e r ，f = o ，1 ，- ，m ll 为r 的g a l o i s 环，记为g r ( r ，州) ，简记为。蹴- i r i - 4 ”，且氐的特征为2 。 取考= x + ( ( x ) ) ，则亭为 ( z ) 的一个根，并且r 。中元素都可唯一表示为： + d l 孝+ - - + 口卅一i 孝“一1口i r ，i = 0 , 1 ，- - ，m 一1 的形式，即= 趔翱。 映射伊：n i x 啼e x 】；厂( j ) i - - - 7 ( x ) 为环同态映射。理想( o ) ) 在p 下像为 ( ( x ) ) ，因此映射： 胄【x 】( ( x ) ) ，e 【z 】( 万o ) ) ；芝q xj + ( ( x ) ) 斗m - i 虿x t + ( 万( x ) ) 1 = 0 j ，o 也是环同态映射，也记为妒，在妒下f = x + ( 矗( 刁) 的像为手= x + ( i ( x ) ) 。故有孑 是万( x ) 的根。从而吲x ( 石( x ) ) = 碰翱，映射妒可写作 妒：r 嘲哼e 【翱；n ，卜瓦手。 i = o i = 0 于是有下面定理： 定理2 1 设h ( x ) r x 】是m 次基本不可约多项式，剩余类环 如= 埘x 】，( ( x ) ) 是特征为2 具有4 “个元素的有限环。记f = z + ( ( x ) ) ，则 矗( 孝) = 0 ，且屯中每个元素都可表示为形式： + 口l 孝+ + q 。一i 善一，q r ，i = o ，1 ，m l 即r m = 翱，理想( “) 是埘善】的唯一极大理想