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