不可约多项式本源多项式..docx

有限域第一次大作业一、实验内容（1）构造有限域.（2）找到有限域上的任意元素的极小多项式；（3）找到上的一个本原多项式。二、算法设计（1）我们知道有限域的表达有三种形式：，为的根；；；在这里我们主要通过找到上的一个次可约多项式来构造有限域，并进行相应的运算。由于只要找到一个上的不可约多项式，我们采用的算法：随机生成一个次上的多项式，判断多项式为不可约的，代码见附录；通过我们得到了一个次的不可约多项式，则即为我们想要的有限域，在这有限域上可以直接进行相应的代数运算，代码见附录；（2）找到有限域上的任意元素的极小多项式的思路第一步：通过元素的共轭元个数来判断极小多项式的次数；第二步：通过的共轭元生成极小多项式；第三步：进一步判断该元素是否为本原元，若是，则生成的极小多项式就是上的本原多项式。代码见附录；（3）由于上述方法（2）生成的极小多项式不一定是本原多项式，因此，我们还给出一个能找到上的本原多项式的方法，该方法也是基于随机生成多项式并判断是否为本原多项式，我们知道一个次不可约多项式是本原多项式的条件是其周期达到最大，由于，所以只要时，若，则就是本原多项式，所用的算法思路如下第一步：随机产生一个上的次多项式；第二步：利用方法一判断该多项式是否为不可约的；第三步：进一步判断该多项式是否为本原多项式。代码见附录；三、实验结果（1）第一问产生的不可约多项式我们选择作为我们的所要的不可约多项式第一问有限域上元素的运算（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^20pol_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(i1res==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;););//用元素的阶判断极小多项式的周期并判断出元素是