实验二：有限域上的运算

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

2、p.push_back(make_pair(1,4);则多项式temp变为xA0+xA4make_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个元素，它们是: 61 八1+x1 x 2 1+xa2 x1+x2 1+xl*x2 x3 1+x3 xC Y3 1+xl*x3 x 2+x 3 1*xa2*x31+xl+x2+x3 x4 1+x4 x1+x 1+xA1*x x2+x4 l+x2+xM x1+x2+x 1+x1*x2+x x3*xxHx2+x 1+x1+x2+x4 x3+xM 1+xa3+xa4 x1+x3+xM 1+xl+x3+x4 ,2+, W4 1+xa2+x3+x4 x1+x2

4、*x3+x 1*x1*x2+x3+xH x 5 1+xa5 xl+x5 1+x1+x5AJx 2+x 5 1+xW5 x1+x2+x5 Hx1+x2+x5 x“3+x5 1+xW5 xHx3+x5 1+x1*x3+x5 x2*x3+x5 1+x2*x3+x5 x1+x2*x3+x5XX oXAj2x2H0?ypJV50l2gT0rMe+y+*y 址力ROFva r-h- xincm x in X I J/ - X + X sxEprrrrrTFIrX r- X CJ “ 一 X Z X2x2ro?ypJV侶50zls苦10字匕*己址群冈亦va夏.Inllj2X2. 10?y eJVQW lol

5、s苦 TOrMe +y * y 址fi$ROFxhx*wxiXAxx*r + a x in x in 4* + m x x - x h x h + 才x x4- x x z 仆 4 + +c i 1201 OHiSVO13Rde0se2O13.exEl - 1x2+xH+k5+x6*k71+x2+xA4+x*5+x6+xa? x1+x2+x4+x5*k6+x7 1+x1+x2+x4+x5+k6+x7 x3+xH+x5+x+x71 +xrt3+x*-4c*5+xA&*T x1+x3+x4+x5+x6+x? 1+1+x*3*k4+x*5+k*6*m*7 t2+x*3*4*x5+x*G+xAT l+

6、x2+x3+xH+x5+x6+x7 x1+x+k3*x+k*5*x6+x7 1+xa1 +)c2+x*3+xi+k5+x6+kaT2、任选两个多项式进行四则运算:x 1+k 2+x 3*x5+)t 6+x T1 +x*1 +m*2+x3+x*M+x*5*x*+x* ? 逋机选的两个多顼式为：3+x 5+x7 I+jc*1+h*2+x*4两平多项式相加为.1 *x* 1 tx*2+?c* 3+x *4+x*5+xWr式相减为； l+xl+x2+x*3+x4+x5+x7 阡i诗顼式相乘冋1+x14*3+x1+xl+ac*2+x*4的逆多璜式智1+x1+x2+xa?*x4+x&两卜罗陋丈相除为：1*

7、x*1t*2+x*3*x*T馆按任意握维陵代码如下：/*本实验需要解决的几个问题：1、用什么方法存储多项式最好我用的是向量来储存多项式，比如：plo yn temp ;temp.push_back(make_pair(1,0);说明多项式temp中只有一项，为xA0，如果再执行 temp.push_back(make_pair(1,4);则多项式temp变为xA0+xA4make_pair中第一个元素是系数，第二个是次数2、怎么生生成域用递归生成，我们知道成域 GFpn会有2的n次方个元素，只要能求出2的n-1个,就可以求出2的n个因为当为n时，n-1中的每一个多项式添加一个xAn次方就可以了

8、。3、实现四则运算，尤其是在乘法和除法时，还有一个模运算的因为是在二维的情形下啊的，所以实验中的加法减法的答案是同一个，至于乘法，乘出来的多项式的次数每循环一次都会减小至少1，所以最终会小于 8的所以除法就是先求逆，因为我们知道域中的每个多项式都会有逆而且逆唯一并就在域中， 用穷搜素的方法在于中一个一个试，只要相乘模xA8+xA4+xA3+x+1为1的就是逆。*/#in clude#in clude#in clude#in cludeusing n amespace std;int const N = 8;typedef vector pair plo yn ;IN 是 xA8+xA4+xA3

9、+x+1 为 1plo yn V;II用递归方法求出域vectorvplo yn make_field(i nt n)vector field;if(n = 0 )如果n = 0,说明域只有0和1两个元素plo yn temp ;temp.push_back(make_pair(1,0); field.push_back(temp);elsefield = make_field(n-1);先求得出n-1时的域的多项式的集合plo yn temp1,temp2 ; temp1.push_back (make_pair(1, n);int size = field.size();field.pus

10、h_back (tempi);for(i nt j=0;jsize;j+)temp2 = fieldj;temp2.push_back (make_pair(1,n); 在每一项多项式后面添加xAn 次方field.push_back (temp2);return field;输出多项式void show1(plo yn p)for(i nt j=O;jp.size()_1;j+)if(pj.second!=0 )coutxApj.second+;else if(pj.sec on d=0)cout1+;coutx a pp.size()_1.sec on de ndl;/输出域void sh

11、ow(vector _field)cout该域总共有_field.size()+1个元素，它们是：endl;cout0;cout1;for(i nt i=1;i_field.size();i+)show1(_fieldi);plo yn additi on( plo yn p1,plo yn p2)int i=0,j=0;plo yn p3;/*声明一个数组，数组的下标表示项的次数，数组存储的是系数，初始为0这样只要遍历一下两个多项式，项的次数相同(也就是下标相同的，每遍历一次就加1)*/int aa15=0;for(i nt p=0;pp1.size();p+)aa p1p.sec ond

12、+;for(i nt p=0;pp2.size();p+)aa p2p.sec ond +;/遍历两个多形式后，这里把系数为不为偶数的项都留下来，就是加法的最后结果/因为加法次数不会增大，所以不需要进行模运算。for(int i=0;i=14;i+)if(aai%2 !=0)p3.push_back (make_pair(1,i);return p3;plo yn Simplify(plo yn p)/*这是个模运算，递归基是多项式次数小于8，我存储的多项式阶从左到右是上升的。这个函数利用了类似欧几里得算法，每循环一次次数都会下降，直到次数小于if(p.back().sec ond N)ret

13、ur n p ;plo yn p5;plo yn v1 = V;int aa = p.back().sec ond - N;for(i nt i=0;iv1.size();i+)v1i.sec ond += aa;p5 = additi on( v1,p);return Simplify(p5);乘法的实现类似于加法，只是后面有个模运算plo yn Multiplicati on( plo yn p1,plo yn p2)plo yn p3;int aaa15=0;for(i nt i=0;ip1.size();i+)for(i nt j=0;jp2.size();j+)aaap1i.sec

14、ond + p2j.sec on d+;for(int i=0;i=14;i+)if(aaai%2 !=0)p3.push_back (make_pair(1,i);return Simplify(p3);plo yn qiu_ni( vector field,plo yn p)plo yn a,b;in t i=1;/在域中用穷搜素的方法寻找逆元for(;i field;field = make_field(N-1); show(field);/ 输出域int nu m1, nu m2;num1 = ran d()%255;num2 = ran d()%255;plo yn p1 = field nu m1;plo yn p2 = field nu m2;plo yn p3;cout随机选的两个多项式为：endl;show1(p1);show1(p2);p3=additio n( p1,p2);cout两个多项式相加为：e ndl;show1(p3);c