下载文档原格式
本原多项式的判别新算法张静远;占顺【摘要】设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。
由于本原元的存在，有限域中的元素可以表示为本原
元的幂的形式。
在构建有限域时，需要选择一个本原多项式。
本原多项式是一个多项式，满足它的根可以生成一个有限域。
具体地，如果一个多项式P(x)满足以下条件之一，那么它就是一个本原多项式：
1. P(x)是一个不可约多项式；
2. P(x)是一个首一多项式，且它的根全部属于一个有限域。
选择合适的本原多项式是构建有限域的关键步骤之一。
根据有限域的阶来选择本原多项式，可以使用数学算法（如Berlekamp算法）来寻找合适的本原多项式。
有限域及其本原多项式在信息编码、密码学等领域有广泛的应用。
不可约多项式的判别一个多项式是否可约取决于它的系数所在的域。
下面给出了一些判别不可约多项式的方法。
1. 整数域中的多项式：在整数域中，两个常用的判别方法是Eisenstein 判别法和 Modulus 判别法。
- Eisenstein 判别法：设 P(x) 是一个系数为整数的多项式，且可以表示为 P(x) = a₀ + a₁x + a₂x² + ... + aₙxⁿ。
如果存在一个素数 p，满足以下条件：- p 不能整除 aₙ；- p 能整除 a₀, a₁, ..., aₙ₋₁；- p²不能整除 a₀；那么多项式 P(x) 在整数域中是不可约的。
- Modulus 判别法：设 P(x) 是一个系数为整数的多项式，且可以表示为 P(x) = a₀ + a₁x + a₂x² + ... + aₙxⁿ。
如果存在一个素数 p，使得 P(x) 在有限域 Zₙ 上可约（即 P(x) 在模 p 的意义下有一个非常数的因子），那么多项式 P(x) 在整数域中是不可约的。
2. 实数域、复数域和有理数域中的多项式：在这些域中，不可约多项式的判别较为简单，只需要使用带余除法进行因子分解判别即可。
带余除法即根据多项式除法的原理，如果存在一个多项式 Q(x)和 R(x)，使得 P(x) = Q(x)B(x) + R(x) 并且 R(x) 为零次或者次数小于 B(x) 的多项式。
如果 R(x) 为零次多项式，则 P(x) 是可约的；如果 R(x) 的次数大于等于 1，则 P(x) 是不可约的。
需要注意的是，对于高次多项式，进行带余除法可能会非常复杂，需要借助计算机进行多项式除法运算。
综上所述，对于一个多项式的可约性的判别需要根据具体的域和具体的算法进行分析。
以上只是给出了一些常用的判别方法，实际的判别可能需要更加复杂的计算。
有限域第一次大作业一、实验内容（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 是否为本原多项式。
判定有限域上不可约多项式及本原多项式的一种高效算法王鑫;王新梅;韦宝典【摘要】提出了一个判定有限域上任一多项式是否为不可约多项式、本原多项式的高效的确定性算法.分析了多项式次数与其不可约因式之间的内在联系,给出了有限域上任意n次多项式是否为不可约多项式、本原多项式的一个充要条件.通过利用欧几里得算法,该判定仅需做O((log2n)n3)次域上乘法,属于多项式时间,易于硬件实现.为扩频通信与序列密码寻找和利用不可约多项式构造线性反馈移位寄存器提供了一种有效算法.【期刊名称】《中山大学学报（自然科学版）》【年(卷),期】2009(048)001【总页数】4页(P6-9)【关键词】有限域;不可约;本原;多项式时间算法;扩频通信;序列密码【作者】王鑫;王新梅;韦宝典【作者单位】西安电子科技大学综合业务网国家重点实验室,陕西,西安,710071;西安电子科技大学综合业务网国家重点实验室,陕西,西安,710071;中山大学电子与通信工程系,广东,广州,510275【正文语种】中文【中图分类】TP309有限域上的不可约多项式与本原多项式在密码，编码理论及随机数的产生等方面有着广泛的应用。
这是由于在扩频通信与序列密码中被广泛应用的伪随机序列，可在连续波雷达中用作测距信号，在遥控系统中用作遥控信号，在多址通信中用作地址信号，在数字通信中用作群同步信号，还可用作噪声源在保密通信中起加密作用。
这些伪随机序列大部分是利用有限域上的不可约多项式和本原多项式通过反馈移位寄存器和其它非线性逻辑产生的。
另一方面，多项式理论尤其是不可约多项式和本原多项式又是分析伪随机性能和密码体制的一种有效工具，因此研究有限域上的不可约多项式与本原多项式具有重要意义[1-4]。
设GF(q)为一个含q个元素的有限域，其中q=pk，p为一素数，k为正整数，那么对于任一正整数n，一定存在GF(q)上的n次不可约多项式[5]。
目前，判定有限域上一个n次多项式是否不可约的方法一般有确定性(构造性)和概率性两种算法[6]。
gf(2^16)的本原多项式1. 概述在计算机科学和信息技术领域，有一个重要概念叫做有限域（finite field），简称GF。
有限域是一种具有有限元素数量的数学结构，其中的加法和乘法运算满足特定的性质。
在有限域中，有一个重要的概念叫做本原多项式（primitive polynomial），它在有限域的构建和运算中起着关键作用。
本文将介绍gf(2^16)的本原多项式及其相关概念。
2. 有限域GF(2^16)有限域GF(2^16)是一个由2的16次方个元素构成的有限域。
在这个有限域中，加法和乘法操作可以用非常高效的方式进行计算，因此在很多密码学和编码领域有着重要的应用。
GF(2^16)的本原多项式是构建这个有限域的基础之一。
3. 本原多项式的定义在有限域中，本原多项式是一种特殊的不可约多项式。
所谓不可约多项式，是指它不能被分解成两个次数更低的多项式相乘的形式。
本原多项式具有特定的性质，能够生成该有限域中的所有非零元素。
在构建有限域GF(2^16)时，选择一个适合的本原多项式非常重要。
4. gf(2^16)的本原多项式在gf(2^16)场中，关于本原多项式的选择存在多种不同的标准。
其中一种常用的本原多项式是x^16 + x^5 + x^3 + x^2 + 1。
这个多项式是一个16次多项式，也是一个不可约多项式。
使用这个本原多项式可以构建出一个包含2^16个元素的有限域，满足有限域的加法和乘法运算规则。
5. 本原多项式的作用在实际的应用中，gf(2^16)的本原多项式在很多编码和加密算法中都扮演着重要的角色。
通过选择不同的本原多项式，可以构建出不同的有限域结构，从而适用于不同的场景和要求。
本原多项式的选择对于实际系统性能和安全性都有着重要的影响，因此需要根据具体的情况和需求来进行合适的选择。
6. 结论gf(2^16)的本原多项式是有限域GF(2^16)中的一个重要概念，它在有限域的构建和运算中起着关键作用。
有限域第一次大作业
一、实验内容
（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 αα= 为上的一个生成元；在这里我们主要通过找到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 -= 时，若()|f x ()11 1,,n i p p x i k -⎛⎫ ⎪-= ⎪⎝⎭ ，则()f x 就是本原多项式，所用的算法思路如下
第一步：随机产生一个2F 上的20次多项式()f x ；
第二步：利用方法一判断该多项式()f x 是否为不可约的；
第三步：进一步判断该多项式()f x 是否为本原多项式。
pari 代码见附录4；
三、实验结果
（1）第一问产生的不可约多项式
我们选择()20191814136++1f x x x x x x x =++++作为我们的所要的不可约多项式 第一问有限域上元素的运算
（2）第二问中产生的极小多项式
（3）第三问中产生的本原多项式
附录：
（1）**找到20次不可约多项式**
find_irreducible_polynomial (p,deg)={
a=1;
while(a,px=x^deg;
for(i=2,deg,px+=random(p)*x^(i-1););//随机产生一个F2上的20次多项式
px+=1;
fx=px*Mod(1,p);
res=lift(fx);
if(polisirreducible(fx)==1,print(res);a=0;);)//若多项式是不可约的，则输出并
} //停止循环
(2)**构造有限域F2^20并进行运算**
create_a_finite_filied (fx, fx1, fx2)={ //fx为F2上的20次不可约多项式，fx1及
pol_Mod=Mod(1,2)*fx; fx2 为F2上的次数小于20的多项式，即gg1=fx1*Mod(1,2); 为有限域F2^20里的元素
gg2=fx2*Mod(1,2);
rest=lift(lift(Mod(gg1*gg2,pol_Mod))); //F2^20里的元素进行乘法运算
rest1=lift(lift(Mod(gg1+gg2,pol_Mod))); //F2^20里的元素进行加法运算
rest2=lift(lift(Mod(gg1-gg2,pol_Mod))); //F2^20里的元素进行减法运算
rest3=lift(lift(Mod(gg1/gg2,pol_Mod))); //F2^20里的元素进行除法运算
print("fx1*fx2=",rest);
print("fx1+fx2=",rest1);//输出所有的元素运算的结果
print("fx1/fx2=",rest2);
print("fx1/fx2=",rest3);
}
（3）**找到任意元素的极小多项式并判断是否为本原多项式**
find_a_minimal_polynomial (fy, fy1)={//fy为F2上是不可约多项式，Fy1为域F2^20
pol_Mod=Mod(1,2)*fy;上任意一个元素
gg1=fy1*Mod(1,2);
tty=Mod(gg1,pol_Mod); //将多项式Fy1转化为域F2^20上的元素
n=2^(20)-1;
fa_table=factorint(2^20-1)[,1];//将2^20-1分解得到其素因子
fa_leath=#fa_table;//找到2^20-1的素因子的个数
ppx=1;
for(i=1,20,res = tty^(2^(i-1));ppx*=(x-res);if(i>1&&res==gg1,break;););
//用元素的共轭元判断极小多项式的次数并生成极小多项式
res=lift(lift(ppx));
print("fx="res); //输出极小多项式
for(j=1,fa_leath,if(tty^(n/fa_table[j])==1,print("fx is not primitive polynomial ");return;););
//用元素的阶判断极小多项式的周期并判断出元素是否为本原元及多项式是否为本原多项式
print("fx is primitive polynomial");//输出本原多项式
}
(4)**找到f2^20上的本原多项式**
find_a_primitive_polynomial (p,deg,fx)={//p为任意素数，deg是想找本原多项
pol_Mod=fx*Mod(1,2);式的次数，fx为F2上的20次不可约
a=1;多项式
while(a,px=x^deg;
for(i=2,deg,px+=random(p)*x^(i-1);); //随机生成一个多项式
px+=1;
fx=px*Mod(1,p);
res=lift(fx);
if(polisirreducible(res)==1, //判断多项式是否为不可约的
n=p^deg-1;
fa_table=factorint(n)[,1];
fa_leath=#fa_table;
tty=tty=Mod(res,pol_Mod); //将多项式Fy1转化为域F2^20上的元素
j=1;
flot=1;
while(j<=fa_leath,if(tty^(n/fa_table[j])==1,flot=0;break;);j++;);//不是本原
if(flot=1,print("fx is primitive polynomial fx=",res);a=0;););); //是本原多项式并输出}。
