有限域上本原多项式与不可约多项式判定(共53页).doc

《有限域上本原多项式与不可约多项式判定(共53页).doc》由会员分享，可在线阅读，更多相关《有限域上本原多项式与不可约多项式判定(共53页).doc（53页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、精选优质文档-倾情为你奉上摘要本文前面部分介绍了有限域理论的基础知识。然后根据有限域的相关知识，对王鑫和王新梅在1中提出的判定不可约多项式及本原多项式的一种高效算法进行了论证。该算法提出了三个条件作为判定有限域上多项式的不可约性的充要条件，并在有限域上多项式不可约的前提下，附加了一个条件作为判定有限域上多项式为本原多项式的充要条件。文章的后面部分，使用Microsoft Visual Studio 2008软件，用c+语言编程实现了有限域上的模运算、乘法运算、快速指数算法、欧几里得算法、整数分解算法等核心模块，并最终实现了王鑫和王新梅在1中提出的判定方法，实现了对有限域上的多项式是否为不可约多

2、项式及本原多项式的判定。关键词：有限域 不可约多项式 本原多项式专心-专注-专业ABSTRACTWe introduce the basic knowledge of finite fields theory in the front of this paper. According to the knowledge of finite fields, we discuss an efficient algorithm, which is used to determine whether a polynomial over finite fields is irreducible (prim

3、itive) or not, proposed by Wang Xin and Wang XinMei in 1. Three conditions are proposed by it as a necessary and sufficient condition to determine irreducible polynomials over the finite field. And under the precondition that the polynomial is irreducible over finite fields, the algorithm proposes a

4、 condition as the necessary and sufficient condition to determine whether a polynomial is primitive or not over finite fields. In the latter part, by using Microsoft Visual Studio 2008 software, we make the mode operations, multiplication operations, fast exponential algorithm, Euclid algorithm, int

5、eger factorization algorithm modules come true in c+ language. And finally achieved the decision method proposed by Wang Xin and Wang XinMei in 1, realized the determination that whether the polynomial over finite fields is irreducible (primitive) or not.Keywords：finite field irreducible polynomials

6、 primitive polynomials目录第一章 绪论1.1 研究背景和研究意义有限域理论作为现代代数的重要分支，在密码学，编码理论，组合理论，大规模集成电路设计等诸多领域都发挥着重要作用，它的应用极大地推动了这些学科的发展，其中，许多相关领域的研究热点都可以归结为有限域理论中的关键问题，这使得有限域理论日益得到重视、充实和推动。作为有限域理论研究的重要分支，有限域上的不可约多项式与本原多项式在密码、编码理论及随机数的产生等方面有着尤其广泛的应用。例如伪随机序列在扩频通信与序列密码中被广泛应用，它可以在连续波雷达中被用作测距信号、在遥控系统中被用作遥控信号、在多址通信中被用作地址信号，在

7、数字通信中被用作群同步信号，还可被用作噪声源在保密通信中起加密作用。这些伪随机序列大部分是利用有限域上的不可约多项式和本原多项式，通过反馈移位寄存器和其它非线性逻辑产生的。另一方面，多项式理论尤其是不可约多项式和本原多项式又是分析伪随机性能和密码体制的一种有效工具，因此对限域上不可约多项式与本原多项式相关理论的研究具有重要的意义。作为使用有限域上不可约多项式和本原多项式的先决条件，如何快速得到有限域上的不可约多项式和本原多项式这一课题也一直没有淡出人们的视线。如果没有多项式的确定，又谈何使用它？因此快速找出给定的有限域上给定次数的所有不可约多项式及本原多项式与快速确定给定的有限域上给定次数的多

8、项式是否为不可约多项式及本原多项式这两个课题的重要性可想而知。本次毕业设计的题目是“有限域上不可约多项式与本原多项式的判定”，目前，对于这一课题的研究依旧在进行，一些研究学者相继提出自己的判定算法（文献1、3等），但是尚无一个公认的高效算法去实现有限域上多项式不可约性与本原多项式的快速判定。许多书中（文献2、4等）等同样提出了一些经典的算法，但是由于其效率较低，无法满足实际应用的需求。但同时有限域上不可约多项式与本原多项式的应用却日益广泛与重要，对于课题的研究已经迫在眉睫。1.2 相关领域的研究进展2004年，王泽辉和方小洵在文献3中写道，确定一个上次不可约多项式时，一般整系数多项式不可约性的

9、判定定理用不上，此时确定型（构造性）算法技术上比较复杂，一般常采用概率型算法，目前较好的算法成功率为（较大时），需计算次多项式与次多项式的最小公因式，算法的时间复杂度为，属于指数时间算法，而对于由低阶构造高阶的解决方案要用到整数的标准分解。另外，确定一个次本原多项式的难度更大。他们在文献3中提出的方法是对于一大类整数（为素数乘于素数或的积），分别给出有限域上次多项式是不可约多项式与本原多项式的一个充要条件，该条件可以通过次上乘法加以验证，易于硬件实现。同时提出了可约多项式的一个充分条件，借此减少验证时间，并得到用次上乘法确定一个次不可约多项式及一个次本原多项式的高效算法。2009年，王鑫和王新

10、梅等人在其文献1中提出了一个判定有限域上任一多项式是否为不可约多项式、本原多项式的高效确定算法，分析了多项式次数与其不可约因式之间的内在联系，给出了有限域上任意次多项式是否为不可约多项式，本原多项式的一个充要条件，通过利用欧几里得算法，该判定仅需做次域上乘法，属于多项式时间，易于硬件实现。他们提出的算法对文献3中提出的算法有了很大的进步，在判定过程中适用性更加广泛。其他的一些判定算法大多出现在需要使用有限域上不可约多项式与本原多项式作为工具的课题中，并未单独作为改进算法或高效算法判定有限域上多项式不可约性和本原性提出，在此不做赘述。对于这一课题的研究从未间断，但是所取得的成果每次都是昙花一现般

11、，两个成果间的周期很长，对于现阶段对安全性要求越来越高的实际情况下，新的有限域上性能优良的不可约多项式及本原多项式的发现十分重要，而现阶段的算法也必将日渐无法满足实际需要。1.3 本文主要的研究成果和内容安排本文运用文献24中关于有限域的相关知识，对王鑫和王新梅等人在其文献1中提出的判定有限域上不可约多项式与本原多项式的充要条件进行了论证，而后使用Microsoft Visual Studio 2008软件，用c+语言编程实现了有限域上的模运算、乘法运算、快速指数算法、欧几里得算法、整数分解算法等核心模块，并最终实现了王鑫和王新梅在1中提出的判定方法，实现了对有限域上的多项式是否为不可约多项式

12、及本原多项式的判定。论文的第一章为绪论部分，在绪论部分中，我们主要介绍了该课题研究背景、研究意义、研究现状以及本文的研究成果和各章节结构安排；在第二章中，参考文献2，对域、有限域以及有限域上的多项式等知识点进行了简要介绍，对基本定义以及相关的定理进行了初步的描述与证明；第三章中对王鑫和王新梅等人在其文献1中提出的判定有限域上不可约多项式与本原多项式的充要条件进行了论证，其中引理的证明参考了文献4中的相关知识。本次毕业设计我们使用Microsoft Visual Studio 2008软件，用c+语言编程实现算法，在第四章中我们对实现判定有限域上不可约多项式及本原多项式的算法进行了介绍，并对其中

13、的模运算、乘法运算、快速指数算法、欧几里得算法、整数分解算法等核心模块进行了描述。第五章中我们对程序的运行进行了测试，使用的是文献7中的上的30次以下的本原多项式。第六章为结论部分，对本次论文情况进行了总结，并提出了本次课题的不足之处以及可以改进的地方。第二章 有限域的基础知识本章中，我们将对有限域理论的基本知识进行介绍，作为下一章节中有限域上不可约多项式及本原多项式判定的铺垫，章节中相关的定义及引理若无特殊标注，则引自谢敏著的文献2。2.1 群、环、域 本节中对群、环和域三种结构进行定义，为后面引出多项式环以及有限域的相关内容做铺垫。定义2.1.1（群） 设为某种元素组成的一个非空集合，若在

14、内定义一个称为乘法的运算“”，满足以下条件：（1）（封闭性），有；（2）（结合性），有；（3）在中有一个元素，对中任意元素，有，元素称为单位元；（4）对中任一元素，都存在中的一个元素，使得，称为可逆元，称谓的逆元，记作，则称关于“”形成一个群（Group），记作，通常在不混淆的情况下省略“”，用来表示一个群，也简记为。关于群的定义，我们特别需要注意以下两点（一）群中的运算并不一定可交换，但当它满足交换律时，则称群为交换群或Abel群。（二）若非空集合中定义的运算只满足定义2.1.1中的条件（1）和（2），则称为半群。定义2.1.2（环） 设为某种元素组成的一个非空集合，若在内定义两种运算（通常

15、表示为加法运算“”和乘法运算“”）， 中所有元素满足以下条件：（1）R关于加法运算“”构成一个Abel群；（2）R关于乘法运算“”构成一个半群；（3），有，即分配律成立。则称R关于“”和“”形成一个环（Ring），记作，通常在不回产生混淆的情况下省略“”和“”，用来表示一个环。关于环的概念我们需要注意以下一点：（一）加法单位元一般记作，称为零元。定义2.1.3 如果一个环中的非零元全体在乘法运算“”下构成群，则称该环为除环（或斜域）。定义2.1.4（域） 可交换的除环称为域。定义2.1.5 一个域如果包含有限个元素，则称其为有限域，其元素的个数称为该域的阶。2.2 多项式环 本节对有限环上的多

16、项式的相关理论做简单介绍，因为有限环上的多项式的许多定义以及性质可以类推到有限域上，可以说，有限域上的多项式即是具有特殊限制条件的有限环上的多项式。设是一个环，是不属于环的一个符号，是任意非负整数，形如，的形式和，叫做系数属于环的的多项式，其中称为环上的不定元，叫做该多项式的次项，叫做次项的系数。我们考虑环上的的多项式的全体，记为，对中的多项式而言，系数为零的项可以任意删去和添上。因此，总可以假设中任意两个多项式，含有相同次数的x的整数次幂，即可设，从而和相等，当且仅当对应系数相等，即，定义中的加法运算“”和乘法运算“”如下：为定义乘法，记，定义其中。易知关于上述定义的加法运算“”和乘法运算“

17、”构成环。中所有系数均为零的元素称为零多项式，记为0（0表示零多项式或环中的零元，需视情况而定），它是中的加法零元，的加法逆元为定义2.2.1 关于上述加法运算“”和乘法运算“”构成的环称为环上的多项式环。定义2.2.2 设，则称多项式的次数为，记为。称为的首系数。若环含有单位元1，则将首系数为1的多项式称为首一多项式。约定。定义2.2.3 设，。若存在，使得，则称整除，记作。叫的因式，叫做的倍式。否则称不能整除，记作。定义2.2.4 设，非常数。若有,使得，则或为常数（0次多项式），那么称为多项式环中的不可约多项式或中的素元。定理2.2.1 设，则存在多项式，使得其中。定理2.2.2（唯一分

18、解定理） 设，则必有其中,，, 为中互不相同的不可约多项式，均为正整数，并且若不记不可约因式的次序，这个分解式是唯一的。定理2.2.3 设，则为域当且仅当为域上的不可约多项式。同类似，中的元素即为次数小于的次数的所有上的多项式，其中的加法、乘法运算分别为模多项式的加法和乘法运算。若，则。定义2.2.4 设，,若,则称是的一个根。定理2.2.4 设，则是的一个根当且仅当。证 利用定理2.2.1，我们有其中,，将代入上式得从而由是的一个根的定义知定理成立。由定理2.2.4知，若在域上有根，则在上一定可约，反过来则不一定成立。定理2.2.5 设，则在上最多有个不同的根。定义2.2.5 设，正整数，若

19、 ，而则称为的重根。定义2.2.6 设，称为的一阶导数。定理2.2.6 设，则为的重根当且仅当既是的根又是的根。证 设为的重根，由定义2.2.5知，而，设其中，则 由知，且而从而既是的根又是的根。是的根，设，则又因为是的根，故从而必有继而即为的重根。推论2.2.6 设，若为的重根，则为的重根。定义2.2.7 设，为域上个不全为零的多项式，首一多项式称为，的最大公因式，是指满足：（1），；（2）若有，则。可记为，。推论2.2.6 设，若，则没有重根。定义2.2.8 当，称和互素。2.3 域的有限扩张本节中，对有限域的结构做简要介绍。定义2.3.1 设为一个域，为的一个非空子集，如果相对于中的加法

20、和乘法，也构成一个域，则称为的一个子域，为的一个扩域（也称为的一个扩张）。定义2.3.2 没有真子域的域称为素域。定义2.3.3 设是的一个子域，。若存在，使得，则称为上的代数元，否则称为超越元。若扩域中的元素都为上的代数元，则称为的代数扩域（或代数扩张）。假设是上的代数元，考虑集合对任意，有即，。又因为，有即，。所以是的一个理想，称为代数元在中的零化理想。又由为主理想整环知，存在，使得若限定为首一多项式，则由唯一确定。定义2.3.4 以上由代数元唯一确定的首一多项式，称为在上的极小多项式。在上的次数指的次数。定理2.3.1 设为上的代数元，则其在上的极小多项式满足：（1）为中的不可约多项式；

21、（2）任意属于，。证 （1）为的一个根，故若，且，则从而或而，是不可能的。因此，为中的不可约多项式。(2)由的定义即知由上分析知，是中以为根的多项式中次数最小者。定义2.3.5 为域的一个扩张，将看成上的向量空间，若是有限维的，则称为的有限扩张，上向量空间的维数称为扩张次数，记为。定理2.3.2 域K的每一个有限扩张都是代数扩张。证 设为的有限扩张，则对中任一元素来说，这个元素作为的向量关于是线性相关的，故存在一组不全为零的元素，使得这就说明是上的代数元，从而是的代数扩张。定理2.3.3 设为上的次代数元，为在上的极小多项式，则（1）；（2），且，为在上的一组基。2.4 有限域的性质本节中，我

22、们通过几个定理来探讨有限域的性质。定理2.4.1 设为一个有限域，则，其中为的特征，为在其素域上的扩张次数。定理2.4.2 为阶有限域，则对任意，有。定理2.4.3 设，为素数，则必存在一个阶有限域，并且在同构的意义下，这个域是唯一的。定理2.4.4 设为一个阶有限域，则的每一子域的阶形如，其中为的正因子。反之，若为的正因子，则恰有一个阶子域，且中的元素属于当且仅当。定理2.4.5 有限域的乘法群是一个循环群。定义2.4.1 循环群的生成元称为有限域的本原元。定理2.4.6 设为一有限域，为其有限扩张，则为的单扩域，即，其中为的任一本原元。2.5 有限域上的多项式在本节中，我们将多有限域上的多

23、项式的相关定义及定理做简单的介绍。由前面章节介绍的内容知道，若为一次不可约首一多项式，是的一个根，则，称为的极小多项式。但是不一定是的本原元。我们将根为本原元的极小多项式称为本原多项式。定义2.5.1 设为有限域上的一个次不可约首一多项式，若的根为的本原元，则称为中的本原多项式。定义2.5.2 设，称使得成立的最小正整数为多项式的周期或阶，记为。定理2.5.1 设为有限域上的一个次不可约多项式，为的一个根，则的全部根为，并且这个根是互异的。定理2.5.2 设为一次不可约多项式，则等于在中任一根的阶，特别地，为本原多项式当且仅当。定理2.5.3 设是的扩域中的元素，则在中的极小多项式为其中为的次

24、数，它由 决定，并且。2.6 本章小结在本章中，我们主要对域、有限域以及有限域上的多项式等知识点进行了简要介绍，对基本定义以及相关的定理进行了初步的描述与证明，意在为下一章中介绍有限域上不可约多项式与本原多项式的判定方法做出铺垫，章内相关定义及定理参考谢敏著文献2中相关内容。第三章 有限域上不可约多项式和本原多项式的判定方法3.1 引言在本章中，根据文献2、4中的已有的公理及定理，证明了王鑫，王新梅等人在文献1中提出的判定有限域上的次多项式为不可约多项式的充要条件，以及判定有限域上的次多项式为本原多项式的充要条件，本章所证明的判定方法将作为后面有限域上不可约多项式与本原多项式判定程序实现的依据

25、。3.2 有限域上多项式不可约性的判定本节中根据文献2、4中关于有限域以及有限域上的多项式的相关知识，论证了判定有限域上的次多项式为不可约多项式的充要条件。定义3.2.11 设,非常数。若有,使得，则或为常数（0次多项式），那么称为多项式环中的不可约多项式或中的素元。设是上的一个次多项式，上的多项式，满足整除，则称，对模同余，记为.我们知道，如果存在一个上的次不可约多项式，取为模，对上的全体多项式进行等价分类，那么它的剩余系， 含有个不同的多项式.2(1)叫做模的一组完全剩余系，除去0叫做模的一组缩系对于一般的上的次多项式，(1)也是模的一组完全剩余系，其中与互素的全体多项式叫做模的一组缩系2

26、我们定义(1)中的加法和乘法与多项式的相同，但所得和、积要用去除在这样的定义下，运算是封闭的在这两个运算下，的剩余系(1)构成一个含个元素的有限域，它是的一个扩域，记为我们还知道任一有限域的元素个数一定是某个素数p的方幂，而且在同构意义下，元素个数相等的有限域是唯一的2引理3.2.12 如果有一个上的次不可约多项式，那么它一定是的因式。证 设次不可约多项式的缩系是，.设不整除，与整数缩系的性质类似，此时， 也是一缩系，所以有 ，或对上任意一个多项式，都有取，就得到.证完2引理3.2.22 设是一个次不可约多项式，且，则.证 设，由 ，所以.对于模，有个不同的多项式由于同余方程根的个数不超过，故

27、， 证完2引理3.2.32 设，则.证 不妨设，由辗转相除法得， ，, ,其中.因此，.由此即得. 证完引理3.2.42 在定理4.1.2的条件下，则有整除.证 可设，由整除，可得整除，再由定理4.1.3得整除，故.另一方面由定理4.1.2，于是，即得整除.引理3.2.52 在上，多项式无重因式.证 在特征为的域上，多项式如果有重因式，仍有的次数大于零.设，则，于是，故无重因式，由不整除，便知无重因式. 证完2引理3.2.61 为一有限域，其中，则：，其中是上所有次首一不可约多项式的乘积。证 由引理3.2.4知，是一个次不可约多项式，再加上引理3.2.5已经证明无重因式，不难推断出引理3.2.

28、6中的结论。该引理表明: 实际上是由上次数整除的所有（相异，没有重复的）首一不可约多项式的乘积所构成。例如：当,就等于上的所有的1、2、3和6次首一不可约多项式乘积。引理3.2.71 次多项式,设的所有不可约因式为，)，则当且仅当, ，且对所有，)均有。证 由引理3.2.5知没有重因式，再由引理3.2.6，该结论成立。设自然数的因式分解为, 为素数，是正整数，)，用表示对应的，令 ,，,则有：引理3.2.81 上的次多项式为不可约多项式的充要条件是：（1）；（2）对任意，;（3）对任意的,均有，首先对上述三个条件做简单的解释。条件（1）旨在说明是由以的因子为次数的不可约多项式之积；（2）表明无

29、一次因式；（3）是为了说明事实上并不含有次数小于的不可约因式。因此只能为一次不可约因式。证 为了证明定理3.2.8，首先要证明这样一个结论：对任意的自然数,有成立。事实上，设，那么。因为是素数，故,从而。反之，设，则对，有，且至少存在一个满足 (否则与矛盾)。故，。由引理3.2.6，为不可约多项式，故（1）成立。而由题设，的次数是大于等于2的，因此条件（2）成立。又对任意的，成立。否则，设，。因为是不可约多项式，且，故有，从而,再由引理3.2.4，这与矛盾。故（3）成立。 由于无重因式，所以无重因式，故可设在的因式分解为：，其中为的互不相同的不可约因式。由条件（2）知，因无一次因式，即均非一次

30、因式，故有，从而。又因为，所以（对任意的）(否则，若存在因式，则有，进而，这与，矛盾)。因此，再由引理证明的一开始所证结论，可得，因此的次数只能为，而为不可约多项式，所以首一时，即为一不可约多项式。3.3 有限域上多项式本原性的判定定义3.3.11 设是上次不可约多项式。如果满足的最小正整数为，则称为上的本原多项式。定理3.3.11 上的次多项式为本原多项式的充要条件是：（1）为上的不可约多项式。（2）对的任意因子（大于1），均有.证 必要性显然，下证充分性。为不可约多项式。（反证）设存在,使得。因，从而，,设,及的素因子为，则也为的素因子，因此存在正整数，使得，也即。那么由上述,可得,也即，

31、与条件（2）矛盾。故对任意的t，均有，即为本原多项式。3.4 本章小结在本章中，论证了王鑫，王新梅等人在文献1中提出的判定有限域上不可约多项式与本原多项式的充要条件，其中，上的次多项式为不可约多项式的充要条件是：（1）；（2）对任意，;（3）对任意的,均有，上的次多项式为本原多项式的充要条件是：（1）为上的不可约多项式。（2）对的任意因子（大于1），均有.根据这两个充要条件，我们编程实现了有限域上不可约多项式与本原多项式的判定。第四章 程序实现在本章中，我们主要介绍了实现有限域上不可约多项式和本原多项式判定算法的程序实现部分，该部分的核心思想即是第三章中提出的判定有限域上多项式为不可约多项式和

32、本原多项式的充要条件。4.1 程序总流程本次毕业设计的判定部分程序实现的主流程图如下：图4.1.1 程序判定部分主流程图如图4.1.1所示，程序根据使用者输入的有限域的阶以及有限域上的多项式，首先判定该多项式是否为有限域上的不可约多项式，而后在其在有限域上不可约的前提下，判定其在有限域上的本原性，最终输出判定结果。4.2 数据结构本节主要介绍实现有限域上不可约多项式和本原多项式判定的程序的数据结构以及其上的基本操作。4.2.1 有限域上多项式的表示我们采用类的变量类型存储有限域上的多项式，定义多项式类及其成员变量的代码如下class Polynomialunsigned int ord;vec

33、tor pol;其中，无符号整型变量ord用于存储有限域的阶；整型向量pol用于存储多项式的系数，其中，向量的第n位存储多项式相应次数为n的变量系数，例如对于多项式x5+4x2+x+3,存储为向量的形式即3,1,4,0,0,1。4.2.2 多项式读入模块多项式读入模块pol_s_in( )定义为class Polynomial public:void pol_s_in( unsigned int a , string b );/*用字符串构造多项式类*/;该模块主要实现了将字符串型的多项式转化为4.1.1节中的向量类型，以供后续模块使用。4.2.3 运算符根据程序设计的需要，重载了取模运算“%

34、”、乘法运算“*”、判断是否相等运算符“=”。分别实现了基于多项式向量以及有限域的阶的三种运算该部分定义如下： class Polynomial public:friend Polynomial operator%( Polynomial& a , Polynomial& b );friend Polynomial operator*( Polynomial& a , Polynomial& b );friend bool operator=( Polynomial& a , Polynomial& b ); ;4.3 基础算法本节主要介绍实现判定有限域上多项式不可约性和本原性的过程中用到的主

35、要数学算法及其程序实现。4.3.1 快速指数算法在判定算法实现的过程中，需要计算形如的运算，程序实现过程中，对于整除性的判断，我们使用来判别其是否整除，显然当和过大时，计算代价将会相当大，因此，在这里们使用快速指数算法进行计算。实现快速指数算法的程序流程图如图4.3.1.1所示（见下页）：图4.3.1 快速指数算法4.3.2 整数分解算法在4.4节不可约性判定中，第三步涉及将一个整数的全部素因子找到并用于后续判定，在此，我们涉及了算法实现了快速找到的全部素因子，算法的流程图如图4.3.2.1：图4.3.2.14.3.3 欧几里得算法4.4 不可约性判定根据第三章的相关知识介绍，不可约性的判定分

36、为三步，流程如下：图4.4.1其中的三个判定模块的实现如下：（1）根据充要条件中的第一条，的判定由快速指数算法实现，计算，代码如下if( !(fastExponentialAlgorithm(p,pol.size()-1) = Q1 ) ) return false;其中Q1为多项式“1”。（2）根据充要条件中的第二条，对于，计算所有是否为0。for(int i = 0,n,sum ; i ord ; i+ )n = i ;sum = pol0 ;for( unsigned int j = 1 ; jpol.size() ; j+ )sum = ( sum + polj * n ) % ord

37、 + ord ) % ord ;n = n * i % ord;if(sum = 0)return false;（3）首先使用整数分解算法将多项式的最高次项次数分解，存储于向量vfac中vFac = factorization( pol.size()-1 );然后首先使用快速指数算法求出的余数，然后使用欧几里得算法求出，如果结果为多项式“1”则通过（1）（2）（3）步最终判定为不可约多项式。4.5 本原性判定参照不可约性判定的条件（1），使用快速指数算法容易实现对的任意因子（大于1），均有的判定，结合4.4节中不可约性的判定，最终确定多项式为有限域上的本原多项式。第五章 程序测试程序的测试数据

38、为有限域上30次以下的本原多项式，数据来自参考文献7的附录A部分，图5.1为输入数据，图5.2和图5.3为程序运行结果。图5.1 测试用本原多项式图5.2 程序开始界面图5.3 测试结果图5.3由于篇幅有限，故未将所有多项式结果体现出来，全部30个多项式通过测试。该程序还可以通过手动输入有限域的阶以及多项式的方式进行测试多项式在有限域上的不可约性和本原性，见图5.4。图5.4 手动输入多项式测试第六章 总结与展望本文运用文献24中关于有限域的相关知识，对王鑫和王新梅等人在其文献1中提出的判定有限域上不可约多项式与本原多项式的充要条件进行了论证，而后使用Microsoft Visual Stud

39、io 2008软件，用c+语言编程实现了有限域上的模运算、乘法运算、快速指数算法、欧几里得算法、整数分解算法等核心模块，并最终实现了王鑫和王新梅在1中提出的判定方法，实现了对有限域上的多项式是否为不可约多项式及本原多项式的判定。在实现本次课题的过程中，发现以下地方还存在不足，有后续的研究价值：（1）在算法的循环中，多项式的平方操作被大量重复，如何提高多项式平方操作的效率是值得思考的。在文献3中，提出了在扩域上的快速乘法算法，通过分析快速模约简算法、求逆算法、中国剩余定理（CRT）、多项式乘法等算法后，结合Winograd短卷积算法，讨论模多项式的因子项的选择对于有限扩域乘法的乘法次数和减法次数

40、的影响，从而得出关于模多项式的最优选择问题，很大程度上提高了扩域上乘法的效率，与本文中的算法相结合可以提高一定的效率。（2）本文的算法实现全部为软件实现，而实际应用中算法的一些模块可以用硬件来实现，这样可以在很大程度上提高有限域上不可约多项式与本原多项式的判定时间，如何将软件与硬件相结合来完成判定是下一步研究的方向之一。（3）算法面向的有限域上的一般多项式，而目前有许多研究方向针对有限域上的一些有特点的多项式，比如文献8中提出的对于一大类整数（为素数乘于素数或1的积），分别各处有限域上次多项式是不可约多项式与本原多项式的一个充要条件，该条件可通过次上乘法加以验证，易于硬件实现，等等情况，之后的

41、一个研究方向可以将有限域上的多项式进行一定的分类，首先判定多项式的特殊性，而后“因式而异”进行判断，以提高效率。（4）有限扩域上的多项式由于仅系数的形式域素域上不同，对判定定理无影响，因此没有在程序中单独实现，但是现实中扩域上的多项式应用也是非常广泛，因此，在扩域上的多项式的表现形式以及程序的算法实现上还是大有文章的，后续研究可以基于有限扩域上的多项式如何表示以及运算如何进行来开展研究。致谢首先感谢我的毕业设计导师谢敏，在整个的毕业设计过程中，她不但及时对我的毕业设计作出指导，并且能够及时为我答疑解惑，甚至牺牲自己的休息时间来辅导我的毕业设计，同时，在教导毕业设计课题相关知识的同时，她更注重培

42、养我独立分析问题，查阅资料，提出假设，解决问题的能力，是我在完成毕业设计的同时，更学习到了如何进行科学研究，如何合理利用自己的时间主动学习，这些收获令我获益匪浅。其次要感谢我的女朋友魏雯，她在我毕业设计的过程中一直督促我，鼓励我，让我对于完成这次挑战充满了信心和决心，在她的帮助下，我克服了许多来自自己方面的障碍，知道最终完成我的毕业设计。最后，还要感谢我的朋友们，他们在我毕业设计的过程中，给予我莫大的帮助，提供给我舒适的学习氛围，让我能够安心完成自己的毕业设计。参考文献1 王鑫，王新梅，韦宝典.判定有限域上不可约多项式及本原多项式的一种高效算法.中山大学学报：自然科学版，2009 48（1）2

43、 谢敏，信息安全数学基础，西安电子科技大学出版社。2006.113 王泽辉，方小洵.Fp上不可约多项式与本原多项式的高效确定算法J.中山大学学报：自然科学版，2004 43（6）：89-924 柯召，孙琦.数论讲义M.北京:高等教育出版社，20035 MCELIECE R J Finite field for computer scientists and engineersM.Boston Kluwer Academic Publisher 1987.6 钱能，C+程序设计教程，清华大学出版社。2005.97 靳蕃，组合设计与编码，工业技术图书馆。1990.58 余光雷，扩域的乘法及其快速实现.中山大学学报2010.5附录程序源代码如下：Hello.h该文件打印出欢迎界面#ifndef HELLO#define HELLO#includeusing namespace std;void hello()cout/endl;cout/ 本科毕业设计 /endl;cout/ 有限域上不可约多项式和本原多项式的判定 /endl;cout/ 学号： 姓名：周博 导师：谢敏 /endl;cout/endl;#endifpolynomial.h该文件实现了有限域上