有限域上本原多项式与不可约多项式判定.doc

摘要摘要本文前面部分介绍了有限域理论的基础知识然后根据有限域的相关知识，对王鑫和王新梅在[1]中提出的判定不可约多项式及本原多项式的一种高效算法进行了论证该算法提出了三个条件作为判定有限域上多项式的不可约性的充要条件，并在有限域上多项式不可约的前提下，附加了一个条件作为判定有限域上多项式为本原多项式的充要条件文章的后面部分，使用Microsoft Visual Studio 2008软件，用c++语言编程实现了有限域上的模运算、乘法运算、快速指数算法、欧几里得算法、整数分解算法等核心模块，并最终实现了王鑫和王新梅在[1]中提出的判定方法，实现了对有限域上的多项式是否为不可约多项式及本原多项式的判定关键词：有限域 不可约多项式 本原多项式ABSTRACTABSTRACTWe 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 (primitive) 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 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, integer 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 primitive polynomials 目录 i目录第一章 绪论 11.1 研究背景和研究意义 11.2 相关领域的研究进展 21.3 本文主要的研究成果和内容安排 3第二章 有限域的基础知识 52.1 群、环、域 52.2 多项式环 62.3 域的有限扩张 102.4 有限域的性质 122.5 有限域上的多项式 132.6 本章小结 14第三章 有限域上不可约多项式和本原多项式的判定方法 153.1 引言 153.2 有限域上多项式不可约性的判定 153.3 有限域上多项式本原性的判定 203.4 本章小结 21第四章 程序实现 234.1 程序总流程 234.2 数据结构 244.2.1 有限域上多项式的表示 244.2.2 多项式读入模块 244.2.3 运算符 254.3 基础算法 254.3.1 快速指数算法 254.3.2 整数分解算法 264.3.3 欧几里得算法 274.4 不可约性判定 274.5 本原性判定 28第五章 程序测试 29第六章 总结与展望 31致谢 33参考文献 35附录 37第一章 绪论 3第一章 绪论1.1 研究背景和研究意义有限域理论作为现代代数的重要分支，在密码学，编码理论，组合理论，大规模集成电路设计等诸多领域都发挥着重要作用，它的应用极大地推动了这些学科的发展，其中，许多相关领域的研究热点都可以归结为有限域理论中的关键问题，这使得有限域理论日益得到重视、充实和推动。

作为有限域理论研究的重要分支，有限域上的不可约多项式与本原多项式在密码、编码理论及随机数的产生等方面有着尤其广泛的应用例如伪随机序列在扩频通信与序列密码中被广泛应用，它可以在连续波雷达中被用作测距信号、在遥控系统中被用作遥控信号、在多址通信中被用作地址信号，在数字通信中被用作群同步信号，还可被用作噪声源在保密通信中起加密作用这些伪随机序列大部分是利用有限域上的不可约多项式和本原多项式，通过反馈移位寄存器和其它非线性逻辑产生的另一方面，多项式理论尤其是不可约多项式和本原多项式又是分析伪随机性能和密码体制的一种有效工具，因此对限域上不可约多项式与本原多项式相关理论的研究具有重要的意义作为使用有限域上不可约多项式和本原多项式的先决条件，如何快速得到有限域上的不可约多项式和本原多项式这一课题也一直没有淡出人们的视线如果没有多项式的确定，又谈何使用它？因此快速找出给定的有限域上给定次数的所有不可约多项式及本原多项式与快速确定给定的有限域上给定次数的多项式是否为不可约多项式及本原多项式这两个课题的重要性可想而知本次毕业设计的题目是“有限域上不可约多项式与本原多项式的判定”，目前，对于这一课题的研究依旧在进行，一些研究学者相继提出自己的判定算法（文献[1]、[3]等），但是尚无一个公认的高效算法去实现有限域上多项式不可约性与本原多项式的快速判定。

许多书中（文献[2]、[4]等）等同样提出了一些经典的算法，但是由于其效率较低，无法满足实际应用的需求但同时有限域上不可约多项式与本原多项式的应用却日益广泛与重要，对于课题的研究已经迫在眉睫1.2 相关领域的研究进展2004年，王泽辉和方小洵在文献[3]中写道，确定一个上次不可约多项式时，一般整系数多项式不可约性的判定定理用不上，此时确定型（构造性）算法技术上比较复杂，一般常采用概率型算法，目前较好的算法成功率为（较大时），需计算次多项式与次多项式的最小公因式，算法的时间复杂度为，属于指数时间算法，而对于由低阶构造高阶的解决方案要用到整数的标准分解另外，确定一个次本原多项式的难度更大他们在文献[3]中提出的方法是对于一大类整数（为素数乘于素数或的积），分别给出有限域上次多项式是不可约多项式与本原多项式的一个充要条件，该条件可以通过次上乘法加以验证，易于硬件实现同时提出了可约多项式的一个充分条件，借此减少验证时间，并得到用次上乘法确定一个次不可约多项式及一个次本原多项式的高效算法2009年，王鑫和王新梅等人在其文献[1]中提出了一个判定有限域上任一多项式是否为不可约多项式、本原多项式的高效确定算法，分析了多项式次数与其不可约因式之间的内在联系，给出了有限域上任意次多项式是否为不可约多项式，本原多项式的一个充要条件，通过利用欧几里得算法，该判定仅需做次域上乘法，属于多项式时间，易于硬件实现。

他们提出的算法对文献[3]中提出的算法有了很大的进步，在判定过程中适用性更加广泛其他的一些判定算法大多出现在需要使用有限域上不可约多项式与本原多项式作为工具的课题中，并未单独作为改进算法或高效算法判定有限域上多项式不可约性和本原性提出，在此不做赘述对于这一课题的研究从未间断，但是所取得的成果每次都是昙花一现般，两个成果间的周期很长，对于现阶段对安全性要求越来越高的实际情况下，新的有限域上性能优良的不可约多项式及本原多项式的发现十分重要，而现阶段的算法也必将日渐无法满足实际需要1.3 本文主要的研究成果和内容安排本文运用文献[2][4]中关于有限域的相关知识，对王鑫和王新梅等人在其文献[1]中提出的判定有限域上不可约多项式与本原多项式的充要条件进行了论证，而后使用Microsoft Visual Studio 2008软件，用c++语言编程实现了有限域上的模运算、乘法运算、快速指数算法、欧几里得算法、整数分解算法等核心模块，并最终实现了王鑫和王新梅在[1]中提出的判定方法，实现了对有限域上的多项式是否为不可约多项式及本原多项式的判定论文的第一章为绪论部分，在绪论部分中，我们主要介绍了该课题研究背景、研究意义、研究现状以及本文的研究成果和各章节结构安排；在第二章中，参考文献[2]，对域、有限域以及有限域上的多项式等知识点进行了简要介绍，对基本定义以及相关的定理进行了初步的描述与证明；第三章中对王鑫和王新梅等人在其文献[1]中提出的判定有限域上不可约多项式与本原多项式的充要条件进行了论证，其中引理的证明参考了文献[4]中的相关知识。

本次毕业设计我们使用Microsoft Visual Studio 2008软件，用c++语言编程实现算法，在第四章中我们对实现判定有限域上不可约多项式及本原多项式的算法进行了介绍，并对其中的模运算、乘法运算、快速指数算法、欧几里得算法、整数分解算法等核心模块进行了描述第五章中我们对程序的运行进行了测试，使用的是文献[7]中的上的30次以下的本原多项式第六章为结论部分，对本次论文情况进行了总结，并提出了本次课题的不足之处以及可以改进的地方第二章 有限域的基础知识 13第二章 有限域的基础知识本章中，我们将对有限域理论的基本知识进行介绍，作为下一章节中有限域上不可约多项式及本原多项式判定的铺垫，章节中相关的定义及引理若无特殊标注，则引自谢敏著的文献[2]2.1 群、环、域 本节中对群、环和域三种结构进行定义，为后面引出多项式环以及有限域的相关内容做铺垫定义2.1.1（群） 设为某种元素组成的一个非空集合，若在内定义一个称为乘法的运算“”，满足以下条件：（1）（封闭性），，有；（2）（结合性），，，有；（3）在中有一个元素，对中任意元素，有，元素称为单位元；（4）对中任一元素，都存在中的一个元素，使得，称为可逆元，称谓的逆元，记作，则称关于“”形成一个群（Group），记作，，通常在不混淆的情况下省略“”，用来表示一个群，也简记为。

关于群的定义，我们特别需要注意以下两点（一）群中的运算并不一定可交换，但当它满足交换律时，则称群为交换群或Abel群二）若非空集合中定义的运算只满足定义2.1.1中的条件（1）和（2），则称为半群定义2.1.2（环） 设为某种元素组成的一个非空集合，若在内定义两种运算（通常表示为加法运算“”和乘法运算“”）， 中。