實(shí)驗(yàn)二：有限域上的運(yùn)算

1、實(shí)驗(yàn)二：有限域GF28上的加減乘除運(yùn)算實(shí)現(xiàn)姓名韋能龍班級(jí)11信息平安學(xué)號(hào)11350023實(shí)驗(yàn)?zāi)康耐ㄟ^(guò)上機(jī)操作,使學(xué)生對(duì)有限域的概念、性質(zhì)及運(yùn)算有一個(gè)充分的熟悉,為接下來(lái)現(xiàn)代密碼學(xué)的學(xué)習(xí)打好根底.實(shí)驗(yàn)內(nèi)容及要求1、學(xué)生自己生成一個(gè)有限域GF28并輸出2、在生成的有限域中,隨機(jī)選取兩個(gè)元素進(jìn)行加減乘除運(yùn)算并輸出結(jié)果實(shí)驗(yàn)結(jié)果(可續(xù)頁(yè))(包括實(shí)驗(yàn)代碼、實(shí)驗(yàn)結(jié)果)思路：本實(shí)驗(yàn)需要解決的幾個(gè)問(wèn)題：1、用什么方法存儲(chǔ)多項(xiàng)式最好？我用的是向量來(lái)儲(chǔ)存多項(xiàng)式,比方：ployntemp;temp.push_back(make_pair(1,0);說(shuō)明多項(xiàng)式temp中只有一項(xiàng),為xA0,如果再執(zhí)行temp.push_

2、back(make_pair(1,4);那么多項(xiàng)式temp變?yōu)?人0+*人4make_pair中第一個(gè)元素是系數(shù),第二個(gè)是次數(shù)2、怎么生生成域？用遞歸生成,我們知道成域GFpn會(huì)有2的n次方個(gè)元素,只要能求出2的n-1個(gè),就可以求出2的n個(gè)由于當(dāng)為n時(shí),n-1中的每一個(gè)多項(xiàng)式添加一個(gè)xAn次方就可以了.3、實(shí)現(xiàn)四那么運(yùn)算,尤其是在乘法和除法時(shí),還有一個(gè)模運(yùn)算的？由于是在二維的情形下啊的,所以實(shí)驗(yàn)中的加法減法的答案是同一個(gè),至于乘法,乘出來(lái)的多項(xiàng)式的次數(shù)每循環(huán)一次都會(huì)減小至少1,所以最終會(huì)小于8的除法就是先求逆,由于我們知道域中的每個(gè)多項(xiàng)式都會(huì)有逆而且逆唯一并就在域中,所以用窮搜素的方法在于中一

3、個(gè)一個(gè)試,只要相乘模xA8+xA4+xA3+x+1為1的就是逆.1、學(xué)生自己生成一個(gè)有限域GF28并輸出,如下列圖：該域息共有256個(gè)元素,它們是: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&學(xué)封軟件£十十、匚十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、任選兩個(gè)多項(xiàng)式進(jìn)行四那么運(yùn)算:tat'1+k-2*i-3*x4+xS+k,&+xT1+x*1+m*2+x3+x*M+x*5*x*«+x*?裝機(jī)年的兩個(gè)各項(xiàng)式為x3+«5+x7l-hc*1+n*2+x*4兩個(gè)多項(xiàng)式相加為：1+x1+x2+x3+x+*5+x7兩個(gè)各項(xiàng)式相減為；1+x*W*2*x3*x*4+)f*5+x*7其十多項(xiàng)式相乘為；1+-1+.3+04I+x'+mF+xF的逆多項(xiàng)式為：

7、1+x'1+x'2+xa?*x'4+x'&西卜及項(xiàng)式相除為：1*x*1t«*2+x*3*x*T的按任意鍵繼續(xù)一代碼如下：/*本實(shí)驗(yàn)需要解決的幾個(gè)問(wèn)題：1、用什么方法存儲(chǔ)多項(xiàng)式最好我用的是向量來(lái)儲(chǔ)存多項(xiàng)式,比方：ployntemp;temp.push_back(make_pair(1,0);說(shuō)明多項(xiàng)式temp中只有一項(xiàng),為xA0,如果再執(zhí)行temp.push_back(make_pair(1,4);那么多項(xiàng)式temp變?yōu)?人0+*人4make_pair中第一個(gè)元素是系數(shù),第二個(gè)是次數(shù)2、怎么生生成域用遞歸生成,我們知道成域GFpn會(huì)有2的n次方個(gè)

8、元素,只要能求出2的n-1個(gè),就可以求出2的n個(gè)由于當(dāng)為n時(shí),n-1中的每一個(gè)多項(xiàng)式添加一個(gè)xAn次方就可以了.3、實(shí)現(xiàn)四那么運(yùn)算,尤其是在乘法和除法時(shí),還有一個(gè)模運(yùn)算的由于是在二維的情形下啊的,所以實(shí)驗(yàn)中的加法減法的答案是同一個(gè),至于乘法,乘出來(lái)的多項(xiàng)式的次數(shù)每循環(huán)一次都會(huì)減小至少1,所以最終會(huì)小于8的除法就是先求逆,由于我們知道域中的每個(gè)多項(xiàng)式都會(huì)有逆而且逆唯一并就在域中,所以用窮搜素的方法在于中一個(gè)一個(gè)試,只要相乘模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,說(shuō)明域只有0和1兩個(gè)元素ployntemp;temp.push_back(make_pair(1,0);field.push_back(temp);)else(field

10、=make_field(n-1);/先求彳#出n-1時(shí)的域的多項(xiàng)式的集合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);/在每一項(xiàng)多項(xiàng)式后面添加xAn次方field.push_back(temp2);)returnfield;/輸出多項(xiàng)式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<<"個(gè)元素,它們是："<<endl;cout<<0<<""cout<<1<<""for(inti=1;i<_field.size();i+)show1(_fieldi);)ploynaddition(ploynp1,ploynp2)(inti=0,j=0;ploynp3;/*聲明一個(gè)數(shù)組,數(shù)組的下標(biāo)表示項(xiàng)的次數(shù),數(shù)組存儲(chǔ)的是系數(shù),初始為0這樣只要遍歷一下兩個(gè)多項(xiàng)式,項(xiàng)的次數(shù)相同(也就

13、是下標(biāo)相同的,每遍歷一次就加1)*/intaa15=0;for(intp=0;p<p1.size();p+)aap1p.second+;for(intp=0;p<p2.size();p+)aap2p.second+;遍歷兩個(gè)多形式后,這里把系數(shù)為不為偶數(shù)的項(xiàng)都留下來(lái),就是加法的最后結(jié)果/由于加法次數(shù)不會(huì)增大,所以不需要進(jìn)行模運(yùn)算.for(inti=0;i<=14;i+)if(aai%2!=0)p3.push_back(make_pair(1,i);returnp3;ploynSimplify(ploynp)/*這是個(gè)模運(yùn)算,遞歸基是多項(xiàng)式次數(shù)小于8,我存儲(chǔ)的多項(xiàng)式階從左到右是

14、上升的.這個(gè)函數(shù)利用了類似歐幾里得算法,每循環(huán)一次次數(shù)都會(huì)下降,直到次數(shù)小于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);/乘法的實(shí)現(xiàn)類似于加法,只是后面有個(gè)模運(yùn)算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<<"隨機(jī)選的兩個(gè)多項(xiàng)式為："<<endl;show1(p1);show1(p2);p3=addition(p1,p2);cout<<"兩個(gè)多項(xiàng)式相加為："<<endl;show1(p3);cout<<"兩個(gè)多項(xiàng)式相減為："<<endl;show1(p3);p3=Multiplication(p1,p2