（概率论与数理统计专业论文）关于有限域gf2m中元素的两种表示方法.pdf

南开大学学位论文使用授权书 j i i iiii ii ii i iii iii iiii y 1813 910 根据南开大学关于研究生学位论文收藏和利用管理办法，我校的博士、硕士学位获 得者均须向南开大学提交本人的学位论文纸质本及相应电子版。 本人完全了解南开大学有关研究生学位论文收藏和利用的管理规定。南开大学拥有在 著作权法规定范围内的学位论文使用权，即：( 1 ) 学位获得者必须按规定提交学位论文 ( 包括纸质印刷本及电子版) ，学校可以采用影印、缩印或其他复制手段保存研究生学位论 文，并编入南开大学博硕士学位论文全文数据库；( 2 ) 为教学和科研目的，学校可以将 公开的学位论文作为资料在图书馆等场所提供校内师生阅读，在校园网上提供论文目录检 索、文摘以及论文全文浏览、下载等免费信息服务；( 3 ) 根据教育部有关规定，南开大学向 教育部指定单位提交公开的学位论文；( 4 ) 学位论文作者授权学校向中国科技信息研究所和 中国学术期刊( 光盘) 电子出版社提交规定范围的学位论文及其电子版并收入相应学位论文 数据库，通过其相关网站对外进行信息服务。同时本人保留在其他媒体发表论文的权利。 非公开学位论文，保密期限内不向外提交和提供服务，解密后提交和服务同公开论文。 论文电子版提交至校图书馆网站：h t t p ：2 0 2 1 1 3 2 0 1 6 1 ：8 0 0 1 i n d e x h t m 。 本人承诺：本人的学位论文是在南开大学学习期间创作完成的作品，并已通过论文答 辩；提交的学位论文电子版与纸质本论文的内容一致，如因不同造成不良后果由本人自负。 本人同意遵守上述规定。本授权书签署一式两份，由研究生院和图书馆留存。 作者暨授权人签字： 王 垩 2 01 0 年5 月2 7 日 论文题目 关于有限域g f ( 2 m ) 中元素的两种表示方法 姓名于军学号 21 2 0 0 7 0 0 5 2答辩日期 2 0 1 0 年5 月2 1 日 论文类别博士口学历硕士 硕士专业学位口高校教师口1 4 等学力硕士口 院f 系 骶数学科学学院 专业概率论与数理统计 联系电话 1 3 0 1 1 3 5 5 6 9 7 e m a i l c a v i a r m a i l n a n k a i e d u c n 通讯地址( 邮编) ：南开大学西区公寓3 号楼3 门5 0 4 室( 3 0 0 0 7 1 ) 备注： 注：本授权书适用我校授予的所有博士、硕士的学位论文。由作者填写( 一式两份) 签字后交校图书 馆，非公开学位论文须附南开大学研究生申请非公开学位论文审批表。 南开大学学位论文原创性声明 本人郑重声明：所呈交的学位论文，是本人在导师指导下进行研究工作所 取得的研究成果。除文中已经注明引用的内容外，本学位论文的研究成果不包 含任何他人创作的、己公开发表或者没有公开发表的作品的内容。对本论文所 涉及的研究工作做出贡献的其他个人和集体，均己在文中以明确方式标明。本 学位论文原创性声明的法律责任由本人承担。 学位论文作者签名： 王至2 0 1 0 年5 月2 7 日 非公开学位论文标注说明 根据南开大学有关规定，非公开学位论文须经指导教师同意、作者本人申 请和相关部门批准方能标注。未经批准的均为公开学位论文，公开学位论文本 说明为空白。 论文题目 申请密级 口限制( 2 年) 口秘密( 1 0 年)口机密( 2 0 年) 保密期限 2 0 年月 日至2 0 年月 日 审批表编号批准日期 2 0 年月 日 南开大学学位办公室盖章( 有效) 限制- k2 年( 最长2 年，可少于2 年) 秘密l o 年( 最长5 年，可少于5 年) 机密2 0 年( 最长l o 年，可少于l o 年) 摘要 摘要 本文在介绍有限域g f ( 2 m ) 中元素的多项式表示和本原元幂次表示这两种表 示方法及其一些应用的基础上，通过两种表示方法之间的对应关系，一方面给出 了一种适合于m 比较大时由有限域元素的本原元幂次表示到多项式表示的计算 方法，另一方面构造了由g f ( 2 m ) 到其本身的两个映射岛和p 0 ，然后独立的给 出了计算这两个映射的像的几种方法，并进一步推导出两个映射的一些性质最 后通过这些计算方法和性质，说明了g f ( 2 m ) 中非零元素及其在两个映射下的像 在多项式表示下与m 序列存在的一些关系，并采用新的方法重新证明了求有限 域g f ( 2 m ) 中非零元素的平方根的算法，同时给出了关于如何对g f ( 2 m ) 中非零 元素进行对数运算的一些构想 关键词：有限域元素表示多项式表示本原元幂次表示有限域对数运算 a b s t r a c t a b s t r a c t t h i sw o r ki so nt h eb a s i so fi n t r o d u c i n gt h ep o l y n o m i a lr e p r e s e n t a t i o na n dt h e p r i m i t i v ee l e m e n tp o w e rr e p r e s e n t a t i o no f t h ee l e m e n t si nf i n i t ef i e l d sg f ( 2 m ) t h r o u g h t h er e l a t i o nb e t w e e nt w ot y p e so f r e p r e s e n t a t i o n s ，t h ew o r ks h o w sa na l g o r i t h mw h i c h i su s e df o rg e t t i n gt h ep o l y n o m i a lr e p r e s e n t a t i o nf r o mt h ep r i m i t i v ee l e m e n t p o w e rr e p r e s e n t a t i o no ft h ee l e m e n t si nf i n i t ef i e l d s t h ea l g o r i t h mw o r k sb e t t e rw h e nmi sm o r e l a r g e o nm eo t h e rh a n d ，t h i sw o r kc r e a t e st w om a p p i n g s 如a n dp of r o mg f ( 2 仇) t o t h e m s e l v e sa l s ot h r o u g ht h er e l a t i o n t h e r e f o r e ，t h ew o r ks h o w sa l g o r i t h m so fg e t t i n g t h ei m a g eu n d e rt h et w om a p p i n g si n d e p e n d e n t l ya n dd e r i v e ss o m e p r o p e r t i e so ft h e t w om a p p i n g sf u r t h e r w i t ht h e s ea l g o r i t h m sa n dp r o p e r t i e s ，t h i sw o r ks h o w ss o m e r e l a t i o n sb e t w e e nt h em s e q u e n c ea n dt h ee x p l a n a t i o nu n d e rt h ep o l y n o m i a lr e p r e - s e n t a t i o no ft h ee l e m e n t so fn o n z e r oi ng f ( 2 m 、a n dt h e i ri m a g e su n d e rt h et w om a p p i n g s t h ew o r ka l s op r o v e st h ea l g o r i t h mw h i c hg e t t i n gs q u a r er o o t so ft h ee l e m e n t s o fn o n z e r oi nf i n i t ef i e l d sg f ( 2 m ) w i t han e wm e t h o d ，a n dg i v e ss o m ev i s i o na b o u t h o wt oa c h i e v et h e l o g a r i t h m i co p e r a t i o no ft h ee l e m e n t si ng f ( 2 m 、 k e yw o r d s ：r e p r e s e n t a t i o no ft h ee l e m e n t si nf i n i t ef i e l d sp o l y n o m i a lr e p r e s e n t a - d o np r i m i t i v ee l e m e n tp o w e r r e p r e s e n t a t i o nl o g a r i t h m i co p e r a t i o ni nf i n i t ef i e l d s i i 目录 目录 摘要i a b s t r a c t 第一章引言 1 第二章预备知识3 第三章有限域g f ( 2 m ) 上元素的两种表示方法 9 3 1 多项式表示 9 3 2 本原元幂次表示1 0 3 3 两种表示法之间的关系1 0 3 4 对照表的建立ll 3 5 利用平方法计算多项式表示 1 4 第四章有限域g f ( 2 m ) 上元素的两个映射1 6 4 1 关于表示方法的规定1 6 4 2 两个映射的定义1 7 4 3 r e ( o ( x ) 和r o ( i ) ( x ) 的计算方法1 9 4 4 r e ( i ) ( x ) 和r o ( 0 ( x ) 作为多项式的一些性质 2 4 4 5 r e ( i ) ( x ) 和r o ( i ) ( x ) 与m 序列的关系3 l 4 5 r e ( i ) ( x ) 和r o ( i ) ( x ) 的应用3 2 第五章结论3 6 参考文献3 9 致谢4 2 个人简历4 3 i 第一章引言 第一章引言 有限域( 伽罗华域) 在现代信息编码，计算机代数，信息处理，密码学中都有着 广泛的应用【l 】g f ( 2 m ) 作为有限域的特例，由于其元素与计算机的二进制存储结 构相匹配，因而是使用最多的一类有限域，它的代数运算广泛的用于椭圆曲线密 码协议和基于离散对数的密码系统【2 】 关于g f ( 2 m ) 中元素运算的快速工程实现，包括硬件实现和软件实现，已成 为重要研究领域特别是软件实现，已经越来越广泛的应用于通讯，密码和多媒体 应用方面【3 】对于其中应用较多的乘法运算，除法运算，幂运算和求逆运算，如何 提高它们的效率一直是关注和研究的重要问题例如对于应用最为广泛的乘法运 算，从最基本s h i f t a n d a d d 算法开始，文献【4 】【5 】【6 】分别给出了效率更高，更易于实 现的算法而文献【7 】将这些常用运算中比较成熟的算法作了一个归纳总结然而 这些计算方法随着研究的深入，仍在不断的更新巾，更快更好的方法不断被提出 来例如文献【8 】中又给出了更高效率的乘法算法这些算法都是基于有限域中元 素的某一种特定的表示方法不同的表示方法，其代数运算的实际操作方法也不 一样而且，有限域元素表示方法的选择，都是为了使元素之间的代数运算简捷方 便文献【7 】和【8 】都是基于最常用的表示方法，即在后面介绍的多项式表示法构成 有限域g f ( 2 m ) 的另一种最常用的方法是采用正规基表示法，这种表示法更适合 于硬件实现【9 】，这里不予关注 在有限域g f ( 2 m ) 中，为了提高g f ( 2 m ) 中元素幂运算的效率，文献 1 0 l q l 入 了非零元素的开平方运算，并给出了求g f ( 2 m ) 中非零元素平方根的算法以及相 应的算法证明而在实际的运算操作中，在m 不大的情况下，g f ( 2 m ) 中元素的许 多运算都是直接利用此非零元素的本原元幂次表示来实现具体计算方法分为 三步，首先把参加运算的g f ( 2 m ) 中元素由多项式表示法转换为本原元幂次表示 法，再利用这些元素的本原元幂次表示法完成运算，最后把运算结果由本原元幂 次表示法转换为多项式表示法，而g f ( 2 m ) 中元素两种表示方法之问的转换可以 通过查询预先计算出来的对照表来实现g f ( 2 ) 中元素的幂运算，对数运算，甚 至是乘法运算，除法运算和求逆运算，都可以采用这种方法 对于g f ( 2 m ) 中元素的这两种表示方法，一般只是研究和考虑如何快速的建 第一章引言 立二者之问的对照表【li i 而对于m 比较大的情况，预先建立对照表的这种方法 不再适用，因而在有限域g f ( 2 m ) 中元素之间进行对数运算还是一个难题，特别 是在m 1 0 2 4 时这一点在文献 1 2 】中有介绍参照前述的方法，我们只要找到 有限域g f ( 2 m ) 中元素的多项式表示法和本原元幂次表示法两种表示法之间的 相互转换的方法，然后利用元素的本原元幂次表示法，可以比较容易的完成对数 元算本文针对m 比较大的情况，以文献 1 3 】中介绍的平方法作为基础，给出了有 限域g f ( 2 m ) 中非零元素由本原元幂次表示到多项式表示的一种方法，而得到有 限域g f ( 2 m ) 中非零元素由多项式表示到本原元幂次表示的可行算法，则比较困 难在研究探讨这一问题的过程当中，根据g f ( 2 m ) 中非零元素的两种表示方法 之问的关系，本文自行构造了两个由g f ( 2 m ) 到其本身的映射岛和p 0 ，并通过 独立的研究得到了这两个映射的像的几种计算方法，而且进一步推导出两个映 射的一些性质根据这些计算方法和性质，本文一方面给出了g f ( 2 m ) 中非零元 素及其在两个映射下的像在多项式表示下与m 序列存在的一些关系，另一方面 重新证明了求有限域g f ( 2 m ) 中非零元素的平方根的算法，同时给出了关于如何 对g f ( 2 m ) 中非零元素进行对数运算的一些构想 本文除第一章的引言外，第二章的内容丰要是介绍本文所要用的一些关于有 限域方面的预备知识第三章里介绍了有限域g f ( 2 “) 中元素的两种表示方法及 其相互关系，介绍如何建立两种表示方法之间的可= 换对照表，并给出根据g f ( 2 m ) 中元素的本原元幂次表示得到相应的多项式表示的一种计算方法在第四章，围绕 两个由g f ( 2 m ) 到其自身的两个映射p 毒和p 0 给出两个映射的像的计算方法，并 推导出它们的一些性质根据这些性质，讨论g f ( 2 m ) 中非零元素以及在两个映 射下的像在多项式表示下的向量，其分量与m 序列存在的一些关系同时给出了 一种新的求g f ( 2 m ) 中非零元素平方根的算法的证明方法，并对g f ( 2 m ) 中非零 元素的对数运算实现提出一些构想最后一章除了对前几章的结论进行一下总结 外，还简要介绍了一下可以进一步探讨的问题和方向 2 第二章预备知识 第二章预备知识 这一章的主要内容是介绍本篇文章用到的一些预备知识这些预备知识来源 于文献【1 3 】和【1 4 】，预备知识中列出的定理和推论都没有给出具体证明，这些证明 都在两个文献中具体有述 定义2 1 设g 是一个非空集合假定在g 中规定一种运算“”，通常叫作乘 法运算，即对于g 中任意两个元素a 和6 可以对它们进行乘法运算，把运算的结 果记作a 6 ，叫作它们的积我们还要求g 中任意两个元素经乘法运算的结果，即 它们的积，仍是g 中的元素，也就是说，g 对于乘法运算是封闭的我们说g 对于 所规定的乘法运算是一个交换群，如果以下运算法则成立： j 对任意a ，b g ，有a b = b a 2 对任意a ，b ，c g ，有( a b ) c = a ( b c ) 3 g 中有唯一一个元素，把它记作e 对一切a g ，都有a e = a 4 对任意a g ，g 中有唯一一个元素，把它记作a ，满足a a - 1 = e 通常做乘法运算时，把“”省略，直接以0 6 表示元素a 和b 的积e 称为g 的 单位元素，a - 1 称为a 的逆元素 有时我们也把交换群g 中的运算记作“+ ”，叫作加法运算，并且把g 中两个 元素a 与b 经加法运算的结果记作a + 6 ，叫作a 与b 的和这时要把上述交换群 定义四条法则中的运算符号“”改成“+ ”，e 改记成0 ，a - 1 改记成一a 有时把0 叫 作g 的零元素，一。叫作元素a 的负元素 设f 是一个非空集合假定在f 中规定了加法( 记作“+ ”) 和乘法( 记作“”) 两 种运算，并假定f 对于这两种运算都是封闭的如果以下条件成立： j f 对于加法运算来说是一个交换群，并把这个交换群的单位元素记作o 2 f 中全体非0 元素所组成的集合p 对于f 中规定的乘法运算来说也是一个 交换群 3 第章预备知识 i 对任意a ，b ，c f ，有a ( b + c ) = a b + a 巴 那么f 对于所规定的加法运算和乘法运算是一个域 对任意的a ，b f ，域f 中对减法运算“一”规定为a b = a + ( 一6 ) ，对除法 运算“”的规定为a b = a ( b - t ) ，其中b 0 集合f 对于加法运算来说，构成了一个交换群，这个交换群叫作域f 的加法 群集合p 对乘法运算来说是一个交换群，这个交换群叫作域f 的乘法群 设集合k 是f 的一个子集如果k 在f 的运算下也构成一个域，那么我们 就称k 为f 的子域，而f 称为k 的扩域( 或扩张) 如果f 的元素个数无限，那 么f 就叫作无限域如果f 的元素个数有限，那么f 就叫作有限域 定义2 2 设g 是任意一个交换群，如果g 中含无限多个元素，g 就叫无限交 换群：如果g 仅含有限个元素，g 就叫有限交换群g 中元素的个数就叫作g 的 阶，记作i g i 若a 是g 中任意的一个元素，如果对于任意的正整数珥都有a n e ，a 就叫作一个无限阶元素如果有正整数n 使a n = e ，a 就叫作一个有限阶元 素，而具有性质a n = e 的最小正整数佗就叫作a 的阶 定义2 3 设g 是一个佗阶交换群( n 为正整数) 如果g 中有一个礼阶元素a 存在，那么 g = = o o = e ，0 1 = o ，a 2 ，a n _ 1 ) 就叫作( n 阶) 循环群，而a 叫作g 的一个生成元任一一个有限域的乘法群都是 循环群，该乘法群的生成元叫作这个有限域的本原元 定义2 4 设f 和f 7 是两个域，如果可以在f 和f ，的元素之间建立一个一 一对应 仃：ah 盯( o ) ( a f ，a ( a ) f 7 ) ， 并且这个对应保持域的加法运算与乘法运算，那么我们就说f 和f 7 同构，而盯是 从f 到f ，的一个同构映射或同构对应或简称同构 定理2 1 设q 是任一素数而m 是任一正整数，那么总存在着一个恰含g m 个 元素的有限域，且任意两个元素个数相同的有限域一定同构 4 第- 章预备知识 我们一般用日表示含有q 个元素的有限域，用踟或者g f ( q m ) 表示含q m 个元素的有限域特别的，局表示只含有0 和1 的域局对加法的规定是，若两个 元素相同，即同为1 或同为0 ，则和为o ，否则和为1 易对乘法的规定是，若相乘 的两个元素都为1 ，则积为1 ，否则积为0 定义2 5 设f 是一个预先给定的域，而x 是一个符号( 或者文字) 设i 是个 非负整数，形如a i x ，a i f 的式子，叫作系数属于f 的( 符号) x 的单项式而 有限个系数属于f 的单项式a o x o ，a l x l ，a n x n ( 其中扎是任意非负整数，并 且a o ，a 1 ，a n f ) 的形式和 a o x o + a l x l + + a n x n( 2 1 ) 叫作系数属于f 的x 的多项式，或简称域f 上的x 的多项式在多项式( 2 1 ) 中， a i x z 叫作它的i 次项，a t 叫作它的i 次项的系数 设f ( x ) = a o x o + a l x l + + x n 如果a n 0 ，我们就说f ( x ) 是t t 次多项 式，记作d e gf ( x ) = 佗，并说a n 是f ( x ) 的首项系数 我们把f 上x 的多项式的全体所组成的集合记作f m 特别的，f 2 m 就表 示数域易上的x 的多项式的全体所组成的集合需要说明的是，f 2 吲中多项式 的加减法与乘法运算中，会涉及到各项系数的运算，这些运算都是遵循易上的运 算法则，因此对任意的，( 。) ，g ( x ) f 2 m ，都有f ( x ) + g ( z ) = f ( x ) 一夕( z ) 所 以，在r 吲中，加与减是不加区别的而且对于，2 0 ) ，就等于f ( x ) 中各单项式的 平方和 定理2 2 设o ( z ) 和6 ) 是f x 】中的两个多项式，而6 ( z ) 0 ，那么f z 】中 有唯一的一对多项式q ( z ) 和r ( z ) 具有下面的性质： 口( z ) = q ( z ) 6 ( z ) + r ( z ) ，其中d e gr ( x ) d e g6 ( z ) 上述定理中所得到的q ( z ) 叫作用6 ) 做除式去除被除式o ( z ) 所得的商，而 r ( z ) 叫作用b ( z ) 去除o ( z ) 所得的余式我们记 ? ( z ) = n ( z ) r o o d6 ( z ) 如果r ( z ) = 0 ，就称6 ( z ) 整除o ( z ) 或者n ( z ) 能被6 ( z ) 整除，记作6 ( z ) in ( z ) 这 时就把6 0 ) 叫作a ( z ) 的因式，把n ( z ) 叫作6 ( z ) 的倍式如果一个多项式除了常 数多项式和本身之外，没有其它的因式，那么我们称它为不可约多项式 5 第二章预备知识 设口是某一素数的幂，f ( x ) 日i x 】是一个非零多项式如果f ( 0 ) 0 ，定 义f ( x ) 的阶为满足( x ) iz e 一1 的最小正整数e ，并记作o r d ( f ( x ) ) 如果厂( o ) = o ，则一定能写成f ( x ) = x h g ( x ) 的形式，其中h 为正整数，g ( x ) 日 z 】且g ( o ) o ，这时我们把f ( x ) 的阶定义为g ( x ) 的阶y ( x ) 的阶有时也称为多项式f ( x ) 的 周期设f ( x ) 的次数为正整数m ，若o r d ( f ( z ) ) = q m 一1 ，则f ( x ) 被称为是岛上 的本原多项式 定理2 3 设a l ( x ) ，a 2 ( x ) 和b ( x ) 都是f i x 】中的多项式，而b ( x ) 0 那么 ( a l ( x ) 士n 2 ( 。) ) m o db ( x ) = a l ( x ) r o o db ( z ) 土a 2 ( x ) m o d6 ( z ) ， ( a l ( x ) a 2 ( x ) ) m o db ( x ) = ( a l ( x ) m o d6 ( z ) ) ( 0 2 ( z ) r o o d6 ( z ) ) ) m o d6 ( z ) 定理2 4 设c 是一个正整数，f ( x ) 岛i x 若f ( x ) 0 ，则f ( x ) iz 。一1 当且 仅当o r d ( f ( x ) ) lc 定义2 6 设k 是f 的一个子域，m 是f 的任何子集我们把k ( m ) 定义为 所有含有m 和k 的子域的交，称为添加m 中的元素得到的k 的扩域( 或扩张) 当m = 口1 ，如，如 - 时，我们记k ( m ) = k ( 0 1 ，如，如) 特别k ( o ) 称 为单扩域( 或单扩张) ，0 称为k ( o ) 在k 上的定义元设口f ，如果0 满足k 上 的一个非零多项式，则称p 为k 上的代数元如果k 的一个扩张中的每个元素 都是k 上的代数元，则该扩张称为代数扩张设，y 是f 中子域k 上的一个代数 元，那么k x 1 中满足夕( 7 ) = 0 的次数最小的多项式叫作7 在k 上的极小多项 式这里f 可以看成k 上的向量空间，若f 作为k 上的向量空间是有限维的，则 称f 是k 的有限扩张，向量空问的维数称为扩张次数，记为 f ：捌设o l 是域f 的某一扩域中的元素，若对于多项式f ( x ) f i x 】有，( q ) = 0 ，则称o l 是y ( x ) 的 一个根( 零点) 或者说o l 满足。厂 ) 如果域f 的一个扩域e 是包含f ( x ) 的所有根 的f 的最小扩域，则e 叫作f i x l 中n 次多项式y ( x ) 在f 上的一个分裂域 定理2 5 设f ( x ) f i x ，乜f 那么a 是y ( x ) 的一个根当且仅当 一o z ) i ，( z ) 定理2 6 设f ( x ) 是日【z 】中一个m 次不可约多项式，则y ( x ) 有根o t 在日m 中而且，( z ) 的所有根正好为日。中如下m 个元素：o l ，o f f ，q q 2 ，o l q 一1 6 第二章预备知识 定理2 , 7 设f ( x ) 是【z 】中一个次数为m 的不可约多项式，那么， ) 在日 上的分裂域为m 定理2 8 设p 是域k 上的一个代数元，极小多项式为g ，d e g ( g ) = 咒，n 为正 整数那么 j k ( o ) 与k m ( 夕) 同构，这里g x ( a ) 表示一个集合，这个集合的每个元素表 示的是k m 巾的一类多项式，同一类多项式除以夕( z ) 所得的余式都相同，不 同类的多项式除以9 ( z ) 所得的余式都不同 2 - 【k ( 0 ) ：k 】= 1 ，口，p 肛1 ) 是g ( 0 ) 在k 上的一组基 3 每一个o g ( 0 ) 都是k 上的代数元，其次数整除n 接下来简要介绍一下昆上m 序列的概念 图1 1 设如上图所示的电路图是初始状态为( a o ，a l ，a n 1 ) 的线性移位寄存 器，这里面a t f 2 ，i = 0 ，1 ，2 ，勺f 2 ，j = 0 ，1 ，2 ，n 不断的给其加 移位脉冲，它就会输出一序列a o ，a 。，a 2 ，满足线性递推关系 钒= fc i a 鼬，k n ( 2 2 ) i = l 这个序列就称为( n 级) 线性移位寄存器序列如果c ，l 0 ，则称此序列为非退化的 线性移位寄存器序列而多项式 ，( z ) = 扩+ c i x 肛 t = 1 称为此线性移位寄存器的特征多项式而把满足关系式( 2 2 ) 的n 级线性移位寄 存器序列称作由，( z ) 产生的( 二元) t t 级线性移位寄存器序列，简称由f ( x ) 产生 的序列我们通常用符号a ( f ) 表示由f ( x ) 产生的所有序列的全体组成的集合 7 第二章预备知识 定理2 9 非退化的死级线性移位寄存器序列一定是周期序列，而且它的周期 不大于2 n 一1 当n 级线性移位寄存器序列的周期达到最大值2 n 一1 时，该周期序列就叫作 最长二元礼级线性移位寄存器序列，简称为m 序列 定理2 1 0 设f ( x ) 是马上的n 次多项式，则一个非0 序列7 - a ( f ) 是n 级 m 序列当且仅当f ( x ) 是n 次本原多项式 设佗次多项式f ( x ) = c o + e l x + c 2 x 2 + + a n x n 岛m ，则用，7 ( z ) 表示 多项式，( z ) 的微商，且规定 ，协) = 龟。1 gm o d2 ) t = 1 8 第三章有限域g f ( 2 ) 上元素的两种表示方法 第三章有限域g f ( 2 m ) 上元素的两种表示方法 有限域上元素的表示方法是有限域实际应用时需要解决的基础问题，有限域 元素表示方法的不n , - 7 p a 直接影响算法和实现的效率 1 4 1 在g f ( 2 m ) 中，元素有 几种不同的表示方法，这里介绍两种表示方法，一种是多项式表示，也叫多项式基 表示【1 5 】，另一种是本原元幂次表示 3 1 多项式表示 设p ( z ) 是岛上的m 次不可约多项式，则根据定理2 6 ，存在q g f ( 2 m ) 是 p ( z ) 的一个根，且b ( q ) = g f ( 2 m ) 此时，根据定理2 7 ，g f ( 2 m ) 可以看作是p ( z ) 在昂上的分裂域，再根据定理2 8 ，g f ( 2 m ) 中的每个元素都可以唯一的表示成易 上o l 的小于m 次的多项式，因此称为多项式表示为了方便计算，我们也可以把 有限域g f ( 2 m ) 看作易m ( z ) ) 1 4 1 ，这是因为f 2 x ( m o dp ( z ) ) 到足m ( z ) ) 的一一对应 夕( z ) hg ( z ) + ( z ) ) ( 3 1 ) 是个同构对应这里p ( z ) ) = 七( z ) p ( z ) i 尼( z ) 易吲) ，表示f 2 m 中p ( z ) 的所 有倍式所组成的集合 1 3 1 ，9 ( x ) f 2 z 且d e g9 ( x ) d e gp ( z ) 这样，g f ( 2 m ) 的 每个元素都可以唯一的表示成易上x 的小于m 次的多项式 在实际的运算操作中，为了方便，在表示g f ( 2 m ) 中一个元素时，只是存储其 对应多项式的各项系数在f 2 m 中，多项式各项的系数只是l 或者0 ，此时存储的 各项系数可以看作是一个向量，即把g f ( 2 m ) 看作是足上的向量空间这样，多 项式表示也可以看作是向量表示，而 1 ，q ，o ! m - 1 ) 就是对应的这组基，其 中o 如前所述，是本原多项式p ( x ) 的一个根因此，多项式表示有时也称为多项 式基表示 在一些文章中，把 1 ，乜，q m - 1 这组基称为标准基 1 6 】，则g f ( 2 m ) 中 元素在标准基下的坐标向量表示与多项式表示在实际形式上是致的 9 第三章有限域g f ( 2 “) 上元素的两种表示方法 3 2 本原元幂次表示 有限域中的每一个元素都能由一个本原元的幂次唯一的表示出来 1 7 1 根据前 面定义2 3 ，在g f ( 2 m ) 中，除0 之外的所有元素构成的乘法群是一个2 m 一1 阶的 循环群设q 是g f ( 2 m ) 中的一个本原元，则集合 o ，1 ，o l ，q 2 ，q 2 ”- 2 】包 含了g f ( 2 m ) 中所有的2 m 个元素这种由0 和本原元的适当幂次来表示有限域 元素的方法就是本原元幂次表示法 1 4 1 为了使多项式表示与本原元幂次表示之间建立一个固定的联系，我们要求，在 本原元幂次表示法中，g f ( 2 m ) = o ，1 ，q ，q 2 ，a 2 ”以) 中的本原元o e 就是 多项式表示法中不可约多项式p ( z ) 的根，这样就保证了p ( z ) 是毋上的本原多项 式 本原元幂次表示法更多的是应用于理论方面，以利于简化问题，这将在后面得 以体现在实际的运算操作中，只有在m 不大( m 一般不超过1 6 ) 的情况下，当计 算有限域g f ( 2 m ) 中元素之间的相乘相除，求非零元素的逆以及进行幂运算和对 数运算时，会用到本原元幂次表示法具体使用时，需要预先建立一个g f ( 2 ) 中 元素的本原元幂次表示与多项式表示的对照表，这种预先计算的对照表可以简化 运算和提高实现效率 5 】本原元幂次表示只是在计算的中间过程中使用，输入的 原始数据和作为结果的输出数据一般都还是采用多项式表示形式两种表示方法 之间的对照表的建立方法将在后面叙述 3 3 两种表示法之间的关系 设p 0 ) 是f 2 上的m 次本原多项式，o g f ( 2 m ) 是p ( z ) 的一个根，则o l 就 是有限域g f ( 2 m ) 的乘法群g f 。( 2 m ) = g f ( 2 m ) 一 o 的一个本原元首先，本原 元幂次表示法中的零元素与多项式表示法中的零元素单独建立起一种对应，其他 非零元素则按照如下形式对应： o l hz m o d p ( z ) ， 其中i = 0 ，1 ，2 ，2 m 一2 这种对应的建立，存在一个结论作为前提，即对任意的0 j ，则 x m o d p ( z ) = x jm o d p ( z ) ， ( z 一x j ) r o o dp ( z ) = ：0 x j ( x 一歹一1 ) r o o dp ( z ) = 0 又因为p ) 是f 2 吲中的m 次本原多项式，那么同时也是一个常数项不为1 的不 可约多项式，因此必有p ( z ) i ( x i - j - 1 ) 根据定理2 4 ，可知p ( x ) 的阶o r d ( p ( x ) ) 能 被i 一歹整除而作为毋上的本原多项式，p 0 ) 的阶o r d 0 ) ) = 2 m 一1 ，这样就 与i j 2 m 一1 产生了矛盾因此上述结论正确 这种对应关系也确立了一种方法，即已知有限域g f ( 2 m ) 上元素的本原元幂 次表示，计算出相应的多项式表示 3 4 对照表的建立 在建立对照表时，需要进行计算的g f ( 2 m ) 中元素所对应的本原元幂次是连 贯的，即依次要计算1 = o t o ，q ，q 2 ，q 2 2 的多项式表示，因此可以用将有 限域局 z 】( m o dp ) ) 中的元素乘以z 的电路图来实现 1 3 】设 p ( z ) = 1 + c l x + c 2 x 2 + + c m l x m 一1 + 。m ，( 3 2 ) 并假定c i l = c 2 = = q 。= 1 ，1 i l i 2 i m m 一1 ，而其余 的勺= 0 ，j i l ，i 2 ，i m 电路图如下所示： 第第 ol 使使 第 l 挝 綮 勉 使 第 & 图3 1 l l 第三章有限域g f ( 2 “) 上元素的两种表示方法 如果将上图巾的这m 个寄存器从左到右各位依序置以a o ，a 1 ，a m l ，这 时我们说这个电路的状态是( a o ，a l ，a 2 ，a m - i ) ，那么加上一个移位脉冲 后，这个移位寄存器的状态成为 ( a m - 1 ，a o + a m - l c l ，a l + a m l c 2 ，a m - 2 + a m 一1 c m 1 ) ( 3 3 ) 如果令状态( a o ，a 1 ，a 2 ，a m - 1 ) 对应多项式 咖+ a l x + a 2 x 2 + + a m - i x m 一1 ， 那么加上一个移位脉冲后，这个寄存器的状态( 3 3 ) 就对应多项式 a m 一1 + ( a o + a m _ l c l ) x + ( a l + a m - i c 2 ) x 2 + + ( a m 一2 + a m - l c m 一1 ) z m 一1 = ( x ( a o + a l x + a 2 x 2 + + a m - i x m 一1 ) ) r o o dp ( z ) 因此，对于上述移位寄存器来说，加一个移位脉冲的作用就相当于“乘以x ，再 除以m 次多项式p ( x ) 取余式的作用”这样，如果令这个移位寄存器的初始状态 为( 100 0 ) ，那么加一个移位脉冲后我们就会得到相应于x 的状态，加2 个 移位脉冲后就会得到相应于x 2m o dp ( x ) 的状态，加3 个移位脉冲后就会得到相应 于z 3m o dp ( x ) 的状态，；以此类推，一般的，加i 个移位脉冲后就会得到相 应于x r o o d p ( x ) 的状态，其中i = 0 ，1 ，2 ，【1 3 】但在实际计算中，对照表中 一般只包含2 m 一2 个元素，因此只计算到i = 2 m 一2 即可 以本原多项式p ( x ) = x 5 + x 2 + 1 为例，给出有限域g f ( 2 5 ) 中各非零元素的 本原元幂次表示和多项表示的对照表 对应的电路图如下图所示： 图3 2 具体的对照表，见表3 1 这里g f ( 2 5 ) 中非零元素的多项式表示都是以向量的 形式给出，向量中元素为多项式中由低次项到高次项的各项系数 下面的定理给出了有限域g f ( 2 m ) 中元素在多项式基下的坐标分量与m 序 列之间关系这个定理也可以作为一利嘶方法来建立对照表【11 1 ，但这种方法实现 起来不如前面提到的方法简便 1 2 第三章有限域g f ( 2 ”) 上元素的两种表示方法 定理3 1 设p ( x ) 是足上一个形如( 3 2 ) 式的m 次本原多项式，q g f ( 2 m ) 是p ( x ) 的一个根，有限域g f ( 2 m ) 中元素q ( i = 0 ，1 ，) 在标准基 1 ，q ， o t t o - 1 ) 下的坐标向量为( t ( i ) o ，t ( 0 1 ，柏m 一1 ) ，这里对于j = 0 ，l ，m 一 1 ，柏j f 2 则0 1 序列t ( o ) j ，t ( 1 ) j ，t ( 2 ) j ，对任意的0 j m 都构成一m 序 列 证明因为形如( 3 2 ) 式的p ( x ) 是本原多项式，则若证明0 1 序列t ( o ) j ，t ( 1 ) j ， t ( 2 ) j ，对任意的0 j 仇都构成一m 序列，根据定理2 1 0 ，需要证明两点： 1 该序列是非零序列 这是显然的，否则有限域g f ( 2 m ) 中元素就会少于2 m 个 2 对任意满足k m 和0 j 仇的非负整数k ，j ，该序列满足递归关系式 t ( k m ) j + c l t ( k + l m + c 2 t ( k + 2 一m + + c m l t ( k 一1 ) f f + 亡( j c h = 0 ( 3 4 ) 因为a 是p ( x ) 的一个根，所以有 p ( a ) = 1 + c l o t + c 2 0 t 2 + + c m 一1 0 1 m 一1 + q m = 0 1 3 第三章有限域g f ( 2 ”) 上元素的两种表示方法 于是，对任意满足m k 2 仇1 的正整数k ，有 0 k - m ( 1 + c 1 0 + c 2 0 2 + + c , n 一1 0 n l 一1 + 0 m ) = q 七一m + c 1 0 七+ 1 一m + c 2 q 彪+ 2 一m + + c m 一1 q 七一1 + q 七 = 0 ( 3 5 ) 既然q 七一m ，q 七+ 1 一m ，0 七+ 2 一m ，0 七，0 七满足递推关系式( 3 5 ) ，那么作 为m + 1 个m 维向量，0 七一m ，0 k + 1 一m ，扩+ 2 一m ，舻，0 南分别在多项式 基 1 ，0 ，0 m - 1 】下同一位置的坐标分量t c k m ) j ，t ( k - r e + 1 ) j ，t k ) j 也 符合递推关系式( 3 4 ) 这样就证明了结论 口 3 5 利用平方法计算多项式表示 已知g f ( 2 仇) 中非零元素的本原元幂次表示，来计算相应的多项式表示时，上 面给出的建立对照表的方法在m 不大的情况下是一种非常快速有效的方法如果 在m 很大的情况下，则可以采用平方法来计算 设有限域g f ( 2 m ) 中非零元素的本原元幂次表示为0 。，e = 0 ，1 ，2 m 一 2 ，p ) 为足上的m 次本原多项式，则计算0 e 的多项式表示的平方法如下( 1 3 】 1 利用平方法通过计算依次得到g f ( 2 m ) 中元素0 2 0 ，0 2 1 ，0 2 2 ，q 2 1 的 多项式表示，这样需要依次计算xr o o dp 向) ，z 2r o o dp p ) ，x 2 2r o o dp