本原多项式

嘉应学院本科毕业论文（设计）（2014届）题目：有理数域上的多项式的因式分解姓名：江志会学号：101010100学院：数学学院专业：数学与应用数学指导老师：许鸿儒申请学位：学士学位嘉应学院教务处制摘要在多项式理论中，对于有理数域上多项式的因式分解的研究有着极其重要的地位。

判断一元多项式是否能因式分解是不容易的。

本文根据多项式的可约性和有理根的判断与求法的理论，探究多项式的因式分解的方法，并进行了归纳、整理和补充。

关键词：有理数域, 可约, 因式分解AbstractIn polynomial, the research on rational polynomial factorization has an extremely important position. Determine whether a polynomial can be factoring or not is not easy. According to the theory of irreducible polynomials and rational roots, we explore polynomial factorization method, and make some the induction, consolidation and supplements.Key words： rational number field, reducible, factorization目录1 有理数域上的多项式基本内容 (1)1.1 多项式因式分解的基本概念 (1)1.2 本原多项式 (2)1.3 不可约多项式的艾森斯坦判别法 (5)2 多项式的有理根及因式分解 (7)2.1多项式在有理数域上的性质 (7)2.2多项式有理根的判定 (8)2.3多项式有理根的求法及因式分解 (11)2.4因式分解的特殊解法 (13)参考文献 (15)1 有理数域上的多项式基本内容1.1 多项式因式分解的基本概念在算术中，我们已掌握了整数分解质因数的概念，如：5315⨯=；在此基础上，通过类比,我们得到因式分解的一般定义：定义1.1.1 把一个多项式化成几个整式的积的形式，像这样的式子变形叫做把这个多项式因式分解，也叫做把这个多项式分解因式。

本原多项式的判别新算法张静远;占顺【摘要】设0-1域上多项式f(x)=xm+bm-1 xm-1+?+b1 x+1,又设g(x)=xn+an-1 xn-1+?+a1 x+1是0-1域上不可约多项式,并假定m≥n.基于整除关系式g(x)|f(x)看成由f(x)系数产生的向量经由g(x)系数产生的向量线性表出的基础上,设计了求解最小正整数m的算法,使得g(x)不仅有g(x)|xm-1,而且还可判别g(x)是否是本原多项式.【期刊名称】《杭州电子科技大学学报》【年(卷),期】2019(039)001【总页数】3页(P100-102)【关键词】0-1域;不可约多项式;本原多项式【作者】张静远;占顺【作者单位】杭州电子科技大学理学院 ,浙江杭州310018;杭州电子科技大学理学院 ,浙江杭州310018【正文语种】中文【中图分类】O151.240 引言0-1域上本原多项式在密码、编码和通信上有着广泛的应用[1-2]。

因此，求解和寻找本原多项式问题引起了学术界的关注。

郭鑫等[3]结合求解最小多项式的方法给出了一个0-1域上求解本原多项式的算法。

最近，有些学者提出通过缩小搜索范围来优化寻找本原多项式的算法[4-6]。

但是，本原多项式的寻找和生成都需要大量的计算。

目前，判别0-1域上不可约多项式是否是本原多项式还没有多项式时间算法[7-8]。

为此，本文提供一个判别不可约多项式是本原多项式且具有线性空间复杂性的算法。

1 基本概念和引理定义1 设p(x)是0-1域上一个次数大于0的多项式，如果p(x)不能表示成次数比它低的0-1域上2个多项式乘积，则称p(x)是0-1域上不可约多项式[1]。

定义2 设p(x)是0-1域上一个n次不可约多项式，若p(x)满足p(x)xm-1的最小正整数m等于2n-1，则称p(x)是0-1域上本原多项式[1]。

设f(x)=xm+bm-1xm-1+…+b1x+1，g(x)=xn+an-1xn-1+…+a1x+1并且假定m≥n。

第３４卷场Ｌ３４第１５期Ｎｏ．１ｓ计算机工程ＣｏｍｐｕｔｅｒＥｎｇｉｎｅｅｒｉｎｇ２００８年８月ＡｕｇＩｌｓｔ２００８·安全技术·文章编号一ｌ伽恤·３４２８（２ｌ啪Ｊ１５．＿０１４６—０２文献标识码ＩＡ中国分类号ＩＴＰ３０１．６求解本原多项式的快速算法郭鑫，陈克非（上海交通大学计算机科学与工程系，上海２００２４０）囊要：本原元和本原多项式是有限域理论中的２个重要的概念。

本原元的求解问题是解决实际密码序列问题的前提条件，而本原元的求解问题又可以归结为本原多项式的求解问题。

该文结合求解最小多项式的方法给出一个在二元有限域上本原多项式的求解算法，在求解过程中同时给出了相应的最小多项式，并给出了算法相应的效能分析。

关健词：有限域；本原元；本原多项式；最小多项式；陪集ＱｕｉｃｋＡｌｇｏｒｉｔｈｍｆｏｒＳｅａｒｃｈｉｎｇＰｒｉｍｉｔｉＶｅＰｏｌｙｎｏｍｉａｌＧＵＯＸｉｌｌ．ＣＨＥＮＫｅ．ｆｅｉ（ＤｃｐａｎＩｎｅｎｔｏｆＣｏｍｐｕｔｅｒＳｃｉｅｎｃｅ柚ｄＥｎｇｉｎ∞ｒｉｎｇ＇Ｓｈ柚ｇｈａｉＪｉａｏｔｏｎｇＵｎｉＶｅｒｓｉ吼ＳｈａＪｌ曲ａｉ２００２４０）ｌ舳ｓ湘ｃｔｌ蹦商ｔｉｖｅｅＩｅｍｃｎｔｓ勰ｄ硼ｒｎｉ６ｖｅｐｏＩｙｎｏＩｎｊａｌｐｌａｙｖｅｒｙｉｍｐ０啦ｎｔｒｏｌｅｓｉｎｔｌｌｅｔＩＩｅｏｒｙｏｆ凼ｅｆｉｎｉｔｅｆｉｅＩｄ．ｈｉｓｔｌｌｅｐｒｅｎｌｉｓｃｏｆｓｏｌｖｉｎｇｍｅｐｒｏｂｌｅｍａｂｏｕｔｃｏｄｅｓｃｑｕｅｎｃｅｓ柚ｄｓｅａｒｃｈｉｎｇｔｈｅｐｒｉＩＩｌｉｔｉＶｅｅｌｅｍｅｎｔｓｃ卸ｃｏｍｅｄｏｗｎｔ０ｓｅａｒ；ｃｈｉｎｇｐｒｉＩＩＩｉｔｉｖｅｐｏｌｙｎｏｍｉａＩ．Ｔｈｉｓｐａｐｅｒ画ｖｅｓａｎｅｗａｌｇｏｒｉ血ｍｆ斫ｓｅａｒｃｌｌｉｎｇｐｒｉｒｎｉｔｉＶｅｐｏＩ”ｏＩＩｌｉａｌｓｉＩｌｔｌｌｅｂｉｎａｒｙｆｉｅｌｄ咄蚯ｎｇｕ辩ｏｆｔＩｌｅａｌｇｏｒｉｔ｜ｌｍｆｂｒｓｅａｒｃＩｌｉｎｇ山ｅｍｉｎｉｍａｌｐｏｌｙｎｏｌＩｌｉａｌ，ａＩｌｄａｌｓ０ｇｉｖｅｓ叩ｔｔｌｌｅｒＩｌｉｎｉＩｌｌａｌｐｏｌｙ∞ＩＩｌｉａｌｉｎｔｔｌｅｓｅａｒｃＭｎｇｐｒｏｃｅｓｓ．Ｉｔｓｈｏｗｓｔｈｅｅ历ｃｉｅｎｃｙａｎａｌｙｓｉｓｏｆｔｌｌｅａｌｇｏｒｉｔｌｌＩｎ．ＩＫｅｙｗｏｒｄｓｌｆｉｒＩｉｔｃｆｉｅｌｄ；ｐｒｉｍｉｔｉｖｅｅｌｅｍｅｎｔ；ｐｒｉｍｉ石ｖｅｐｏｌｙｎｏｍｉａｌ；ｍｉＩｌｉｍａｌｐｏｌｙｎｏｌｌｌｉａ】；ｃｏ∞ｔ有限域上的本原多项式在密码学、扩频通信、纠错码理论、信息隐藏技术等各方面都有重要的应用，而本原多项式的寻找和生成是一个复杂的过程，需要大量的计算，尤其是当位数较高时更难得到。

有限域第一次大作业一、实验内容（1）构造有限域202F .（2）找到有限域202F 上的任意元素的极小多项式；（3）找到2F 上的一个本原多项式。

二、算法设计（1）我们知道有限域()n q F q p =的表达有三种形式：()i {}q q F ααα==，α为 ()q h x x x =-的根；()ii []()()()[],p q p F x F f x F x n f x =∈的次不可约多项式； ()iii {}0,q q F F α=U 为上的一个生成元；在这里我们主要通过找到2F 上的一个20次可约多项式来构造有限域202F ，并进行相应的运算。

由于只要找到一个2F 上的不可约多项式，我们采用的算法：()a 随机生成一个20次2F 上的多项式，()b 判断多项式为不可约的，pari 代码见附录1；通过pari 我们得到了一个20次的不可约多项式()(x)f ，则[]()2(x)F x f 即为我们想要的有限域，在这有限域上可以直接进行相应的代数运算，pari 代码见附录2；（2）找到有限域202F 上的任意元素α的极小多项式()f x 的思路第一步：通过元素α的共轭元个数来判断极小多项式()f x 的次数；第二步：通过α的共轭元生成极小多项式()f x ；第三步：进一步判断该元素α是否为本原元，若是，则生成的极小多项式()f x 就是2F 上的本原多项式。

pari 代码见附录3；（3）由于上述方法（2）生成的极小多项式不一定是本原多项式，因此，我们还给出一个能找到上的本原多项式的方法，该方法也是基于随机生成多项式并判断是否为本原多项式，我们知道一个n 次不可约多项式()f x 是本原多项式的条件是其周期达到最大1n p -，由于()()11n p f x x --，所以只要11n k p p p -=L 时，若()|f x ()11 1,,n i p p x i k -⎛⎫ ⎪-= ⎪⎝⎭L ，则()f x 就是本原多项式，所用的算法思路如下第一步：随机产生一个2F 上的20次多项式()f x ；第二步：利用方法一判断该多项式()f x 是否为不可约的；第三步：进一步判断该多项式()f x 是否为本原多项式。

爱森斯坦判别法是目前为止用来判断[]Z x 内一个多项式可约与否的最好结果。

爱森斯坦判别法 设给定n 次本原多项式01()[](1)Z n n f x a a x a x x n =+++∈≥L如果存在一个素数p ，使|(0,1,...,1)i p a i n =-，但20|,|n p a p a //，则()f x 在[]Z x 内不可约。

证明：用反证法。

设()f x 在[]Z x 内可约，即()()()f x g x h x =， 其中0101()[],()[].Z Z m m l l g x b b x b x x h x c c x c x x =+++∈=+++∈L L这里0deg ()deg ()g x f x <<。

为方便计，下面式子中多项式(),(),()f x g x h x 的系数,,i i i a b c 的下标大于其对应多项式的次数时，均认为等于零。

因为n m l a b c =，而|n p a /，故|,|m l p b p c //。

另一方面，0|p a ，而000a b c =，故0|p b 或0|p c ；不妨设0|p b ，此时因20|p a /，故0|p c /。

设|(0,...,1)i p b i r =-，但|(0)r p b r m <</。

此时|r p a ，而 011110()r r r r r a b c b c b c b c --=++++L括号中各项均含有因子p ，故0|r p b c 。

但0|,|r p b p c //，p 为素数，矛盾。

由此，()f x 在[]Z x 内不可约。

爱森斯坦判别法是目前为止用来判断Z[x]内一个多项式可约与否的最好结果。

艾森斯坦判别法是代数的定理，给出了判定整系数多项式不能分解为整系数多项式乘积的充分条件。

由高斯定理，这判别法也是多项式在有理数域不可约的充分条件。

艾森斯坦判别法是说：给出下面的整系数多项式如果存在素数p ，使得p 不整除an ，但整除其他ai ； p^2 不整除a0 ， 那么f (x ) 是不可约的。

lfsr离散数学
LFSR，即线性反馈移位寄存器，是离散数学和密码学中的一个重要概念。

LFSR是一种数字线性系统，它能够产生一个伪随机数序列。

这种寄存器通过将寄存器中的某些位进行异或操作（这是一种二进制运算），并将结果反馈到寄存器的最左端来生成序列。

参与异或的位称为抽头。

LFSR的输出状态值会呈现规律循环，且这个循环可以通过本原多项式来定义。

本原多项式是一种特殊的多项式，它的项数最少且每项系数为1，基于本原多项式所实现的电路最简单。

本原多项式具有这样的特性：本原多项式的反也是本原多项式，根据本原多项式的反也可以生成最大序列。

在实际应用中，LFSR因其简单的结构和良好的统计特性而被广泛应用于加密、通信和计算机科学等领域。

例如，它可以用于生成密钥流、伪随机数生成器和编码理论中的一些算法。

由于其与密码学的紧密联系，LFSR也在CTF（Capture The Flag）竞赛中成为常见的考点之一。

§9 有理系数多项式教学目的：讨论有理系数多项式因式分解问题教学重点：本原多项式课时：3教学方式：讲授式教学内容：对于任一个多项式，要具体做出其分解式很困难。

在此之前，我们主要先解决两个问题：一是有理系数多项式的因式分解问题可归纳为整系数多项式的因式分解问题；二是有理系数多项式环中有任意次数的不可约多项式。

一、1、][)(0111x Q a x a x a x a x f n n n n ∈++++=-- ，选取适当的)(),(x cf x f Z c 总可使乘∈是一整系数多项式，如果)(x cf 的各项系数中有公因子，就可提取出来，得：)()(),()(x g cd x f x dg x cf ==即 其中是整系数多项式，且各项的系数无异于1的公因子。

例：)355(152522322424x x x x x x --=-- 2、本原多项式：如果一个非零的整系数多项式的系数没有异于1的公因子，就称该多项式为一个本原多项式。

3、任一非零的有理系数多项式均可表成一个有理数与一个本原多项式的积，并且这种表法除了相差一个正负号是唯一的。

如果 )()()(11x g r x rg x f ==其中)(),(1x g x g 都是本原多项式，那么必有)()(,11x g x g r r ±==因为)(x f 与)(x g 只差一个常数倍，所以有理系数多项式)(x f 的分解问题可以归结为本原多项式)(x g 的分解问题。

为此，我们先引入：二、高斯引理（定理10）：两个本原多项式的积还是本原多项式。

证明：设 01110111....)(....)(b x b x b x b x g a x a x a x a x f m m m m n n n n ++++=++++=----是两个本原多项式，而011...)()()(d x d x d x g x f x h m n m n m n m n +++==-+-+++ 是它们的乘积。