实验二：有限域上的运算

1、实验二：有限域GF28上的加减乘除运算实现姓名韦能龙班级11信息平安学号11350023实验目的通过上机操作,使学生对有限域的概念、性质及运算有一个充分的熟悉,为接下来现代密码学的学习打好根底.实验内容及要求1、学生自己生成一个有限域GF28并输出2、在生成的有限域中,随机选取两个元素进行加减乘除运算并输出结果实验结果(可续页)(包括实验代码、实验结果)思路：本实验需要解决的几个问题：1、用什么方法存储多项式最好？我用的是向量来储存多项式,比方：ployntemp;temp.push_back(make_pair(1,0);说明多项式temp中只有一项,为xA0,如果再执行temp.push_

2、back(make_pair(1,4);那么多项式temp变为*人0+*人4make_pair中第一个元素是系数,第二个是次数2、怎么生生成域？用递归生成,我们知道成域GFpn会有2的n次方个元素,只要能求出2的n-1个,就可以求出2的n个由于当为n时,n-1中的每一个多项式添加一个xAn次方就可以了.3、实现四那么运算,尤其是在乘法和除法时,还有一个模运算的？由于是在二维的情形下啊的,所以实验中的加法减法的答案是同一个,至于乘法,乘出来的多项式的次数每循环一次都会减小至少1,所以最终会小于8的除法就是先求逆,由于我们知道域中的每个多项式都会有逆而且逆唯一并就在域中,所以用穷搜素的方法在于中一

3、个一个试,只要相乘模xA8+xA4+xA3+x+1为1的就是逆.1、学生自己生成一个有限域GF28并输出,如下列图：该域息共有256个元素,它们是:61171人Ax21+xa2x、+k人21+x'l*x'2乂八31+x"3廿31*x'l*x"3x2+x31+xa2+x、3Ul+/2+/3i+xm+?3X1*4x'1+x>1+xA1*x>X人2廿41+父2+乂-4x£2仪工171廿2廿1x人3+xFdxNxF1+x"1+x2+x"4U3C1+xa3+xa4U1+U3+U41+x"l+x&quo

4、t;3+x4U2K3K41+xa2+x"3+x"4x"Hx"2+x"3+x"41+x"1+x"2+x"3+x'Mx51+xa5X、十x,51+x"1+x"5>A-x2r5"2W5x、+<2+<51小、4123513.,51+xa3+x"5x、,k3H51+x1+x"3+x"5x'2*x"3+x"5xk2r-3H5D&学封软件£十十、匚十1201酰里取01丸RHeasE20i&

5、#177;exEI11®x"2+x"H+k"5+x"6+k"71+xG+x"出力+黑"#冥"x"1+x"2+x"4+x"5*k"6+x"71+x*1+k"2+x*'4+x5+jcE+/了x*xF*wF*3r9X*T1+工"3十小斗+8“5+16+47mF+x*.5*工飞士071+<1+x*3*k"4+x*5+k*6*m*7rl+xA2+x'3+xH+x'5+x"G+5t&quo

6、t;?x"1+x"+k3*x+k*5*x*6+x"71+x*1+K*2tK*3*x'»t*x*5*x*B*x*T2、任选两个多项式进行四那么运算:tat'1+k-2*i-3*x4+xS+k,&+xT1+x*1+m*2+x3+x*M+x*5*x*«+x*?装机年的两个各项式为x3+«5+x7l-hc*1+n*2+x*4两个多项式相加为：1+x1+x2+x3+x+*5+x7两个各项式相减为；1+x*W*2*x3*x*4+)f*5+x*7其十多项式相乘为；1+-1+.3+04I+x'+mF+xF的逆多项式为：

7、1+x'1+x'2+xa?*x'4+x'&西卜及项式相除为：1*x*1t«*2+x*3*x*T的按任意键继续一代码如下：/*本实验需要解决的几个问题：1、用什么方法存储多项式最好我用的是向量来储存多项式,比方：ployntemp;temp.push_back(make_pair(1,0);说明多项式temp中只有一项,为xA0,如果再执行temp.push_back(make_pair(1,4);那么多项式temp变为*人0+*人4make_pair中第一个元素是系数,第二个是次数2、怎么生生成域用递归生成,我们知道成域GFpn会有2的n次方个

8、元素,只要能求出2的n-1个,就可以求出2的n个由于当为n时,n-1中的每一个多项式添加一个xAn次方就可以了.3、实现四那么运算,尤其是在乘法和除法时,还有一个模运算的由于是在二维的情形下啊的,所以实验中的加法减法的答案是同一个,至于乘法,乘出来的多项式的次数每循环一次都会减小至少1,所以最终会小于8的除法就是先求逆,由于我们知道域中的每个多项式都会有逆而且逆唯一并就在域中,所以用穷搜素的方法在于中一个一个试,只要相乘模xA8+xA4+xA3+x+1为1的就是逆.*/#include<iostream>#include<vector>#include<ctime

9、>#include<cstdlib>usingnamespacestd;intconstN=8;typedefvector<pair<int,int>>ployn;/V是xA8+xA4+xA3+x+1为1ploynV;/用递归方法求出域vector<ployn>make_field(intn)(vector<ployn>field;if(n=0)(/如果n=0,说明域只有0和1两个元素ployntemp;temp.push_back(make_pair(1,0);field.push_back(temp);)else(field

10、=make_field(n-1);/先求彳#出n-1时的域的多项式的集合ployntemp1,temp2;temp1.push_back(make_pair(1,n);intsize=field.size();field.push_back(temp1);for(intj=0;j<size;j+)(temp2=fieldj;temp2.push_back(make_pair(1,n);/在每一项多项式后面添加xAn次方field.push_back(temp2);)returnfield;/输出多项式voidshow1(ploynp)(for(intj=0；j<p.size()-1

11、；j+)(if(pj.second!=0)cout<<"x"<<"A"<<pj.second<<"+"elseif(pj.second=0)cout<<1<<"+")cout<<"x"<<"A"<<pp.size()-1.second<<endl;)/输出域voidshow(vector<ployn>_field)(cout<<&qu

12、ot;该域总共有"<<_field.size()+1<<"个元素,它们是："<<endl;cout<<0<<""cout<<1<<""for(inti=1;i<_field.size();i+)show1(_fieldi);)ploynaddition(ploynp1,ploynp2)(inti=0,j=0;ploynp3;/*声明一个数组,数组的下标表示项的次数,数组存储的是系数,初始为0这样只要遍历一下两个多项式,项的次数相同(也就

13、是下标相同的,每遍历一次就加1)*/intaa15=0;for(intp=0;p<p1.size();p+)aap1p.second+;for(intp=0;p<p2.size();p+)aap2p.second+;遍历两个多形式后,这里把系数为不为偶数的项都留下来,就是加法的最后结果/由于加法次数不会增大,所以不需要进行模运算.for(inti=0;i<=14;i+)if(aai%2!=0)p3.push_back(make_pair(1,i);returnp3;ploynSimplify(ploynp)/*这是个模运算,递归基是多项式次数小于8,我存储的多项式阶从左到右是

14、上升的.这个函数利用了类似欧几里得算法,每循环一次次数都会下降,直到次数小于8*/if(p.back().second<N)returnp;ploynp5;ploynv1=V;intaa=p.back().second-N;for(inti=0;i<v1.size();i+)(v1i.second+=aa;p5=addition(v1,p);returnSimplify(p5);/乘法的实现类似于加法,只是后面有个模运算ploynMultiplication(ploynp1,ploynp2)(ploynp3;intaaa15=0;for(inti=0;i<p1.size();

15、i+)for(intj=0;j<p2.size();j+)aaap1i.second+p2j.second+;for(inti=0;i<=14;i+)if(aaai%2!=0)p3.push_back(make_pair(1,i);returnSimplify(p3);ploynqiu_ni(vector<ployn>field,ploynp)ployna,b;inti=1;/在域中用穷搜素的方法寻找逆元for(;i<field.size();i+)a=Multiplication(fieldi,p);if(a.size()=1&&aa.size(

16、)-1.second=0)returnfieldi;)intmain()srand(time(0);V.push_back(make_pair(1,0);V.push_back(make_pair(1,1);V.push_back(make_pair(1,3);V.push_back(make_pair(1,4);V.push_back(make_pair(1,8);vector<ployn>field;field=make_field(N-1);show(field);/输出域intnum1,num2;num1=rand()%255;num2=rand()%255;ploynp1=fieldnum1;ploynp2=fieldnum2;ploynp3;cout<<"随机选的两个多项式为："<<endl;show1(p1);show1(p2);p3=addition(p1,p2);cout<<"两个多项式相加为："<<endl;show1(p3);cout<<"两个多项式相减为："<<endl;show1(p3);p3=Multiplication(p1,p2