實驗二：有限域上的運算

實驗二：有限域GF28上的加減乘除運算實現(xiàn)姓名班級學(xué)號實驗?zāi)康耐ㄟ^上機操作，使學(xué)生對有限域的概念、性質(zhì)及運算有一個充分的認識，為接下來現(xiàn)代密碼學(xué)的學(xué)習(xí)打好基礎(chǔ)。實驗內(nèi)容及要求1、學(xué)生自己生成一個有限域GF28并輸出2、在生成的有限域中，隨機選取兩個元素進行加減乘除運算并輸出結(jié)果實驗結(jié)果（可續(xù)頁）（包括實驗代碼、實驗結(jié)果）

思路：本實驗需要解決的幾個問題：1、用什么方法存儲多項式最好？我用的是向量來儲存多項式，比如： ployntemp; temp.push_back(make_pair(1,0)); 說明多項式temp中只有一項，為x^0， 如果再執(zhí)行temp.push_back(make_pair(1,4)); 則多項式temp變?yōu)閤^0+x^4 make_pair中第一個元素是系數(shù)，第二個是次數(shù)2、怎么生生成域？用遞歸生成，我們知道成域GFpn會有2的n次方個元素，只要能求出2的n-1個，就可以求出2的n個 因為當(dāng)為n時，n-1中的每一個多項式添加一個x^n次方就可以了。3、實現(xiàn)四則運算，尤其是在乘法和除法時，還有一個模運算的？因為是在二維的情形下啊的，所以實驗中的加法減法的答案是同一個，至于乘法，乘出來的多項式的次數(shù)每循環(huán)一次都會減小至少1，所以最終會小于8的除法就是先求逆，因為我們知道域中的每個多項式都會有逆而且逆唯一并就在域中，所以用窮搜素的方法在于中一個一個試，只要相乘模x^8+x^4+x^3+x+1為1的就是逆。1、學(xué)生自己生成一個有限域GF28并輸出，如下圖：

任選兩個多項式進行四則運算：代碼如下：

/*本實驗需要解決的幾個問題：1、用什么方法存儲多項式最好我用的是向量來儲存多項式，比如： ployntemp; temp.push_back(make_pair(1,0)); 說明多項式temp中只有一項，為x^0， 如果再執(zhí)行temp.push_back(make_pair(1,4)); 則多項式temp變?yōu)閤^0+x^4 make_pair中第一個元素是系數(shù)，第二個是次數(shù)2、怎么生生成域用遞歸生成，我們知道成域GFpn會有2的n次方個元素，只要能求出2的n-1個，就可以求出2的n個 因為當(dāng)為n時，n-1中的每一個多項式添加一個x^n次方就可以了。3、實現(xiàn)四則運算，尤其是在乘法和除法時，還有一個模運算的因為是在二維的情形下啊的，所以實驗中的加法減法的答案是同一個，至于乘法，乘出來的多項式的次數(shù)每循環(huán)一次都會減小至少1，所以最終會小于8的除法就是先求逆，因為我們知道域中的每個多項式都會有逆而且逆唯一并就在域中，所以用窮搜素的方法在于中一個一個試，只要相乘模x^8+x^4+x^3+x+1為1的就是逆。*/#include<iostream>#include<vector>#include<ctime>#include<cstdlib>usingnamespacestd;intconstN=8;typedefvector<pair<int,int>>ployn;//V是x^8+x^4+x^3+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=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=field[j]; temp2.push_back(make_pair(1,n));//在每一項多項式后面添加x^n次方 field.push_back(temp2); } } returnfield;}//輸出多項式voidshow1(ploynp){ for(intj=0;j<p.size()-1;j++) { if(p[j].second!=0)cout<<"x"<<"^"<<p[j].second<<"+"; elseif(p[j].second==0)cout<<1<<"+"; } cout<<"x"<<"^"<<p[p.size()-1].second<<endl;}//輸出域voidshow(vector<ployn>_field){ cout<<"該域總共有"<<_field.size()+1<<"個元素，它們是："<<endl; cout<<0<<""; cout<<1<<""; for(inti=1;i<_field.size();i++)show1(_field[i]);}ploynaddition(ploynp1,ploynp2){ inti=0,j=0; ploynp3; /*聲明一個數(shù)組，數(shù)組的下標(biāo)表示項的次數(shù)，數(shù)組存儲的是系數(shù)，初始為0 這樣只要遍歷一下兩個多項式，項的次數(shù)相同（也就是下標(biāo)相同的，每遍歷一次就加1） */ intaa[15]={0}; for(intp=0;p<p1.size();p++)aa[p1[p].second]++; for(intp=0;p<p2.size();p++)aa[p2[p].second]++; //遍歷兩個多形式后，這里把系數(shù)為不為偶數(shù)的項都留下來，就是加法的最后結(jié)果 //因為加法次數(shù)不會增大，所以不需要進行模運算。 for(inti=0;i<=14;i++) { if(aa[i]%2!=0)p3.push_back(make_pair(1,i)); } returnp3;}ploynSimplify(ploynp){ /*這是個模運算，遞歸基是多項式次數(shù)小于8，我存儲的多項式階從左到右是上升的。 這個函數(shù)利用了類似歐幾里得算法，每循環(huán)一次次數(shù)都會下降，直到次數(shù)小于8*/ if(p.back().second<N)returnp; ploynp5; ploynv1=V; intaa=p.back().second-N; for(inti=0;i<v1.size();i++) { v1[i].second+=aa; } p5=addition(v1,p); returnSimplify(p5);}//乘法的實現(xiàn)類似于加法，只是后面有個模運算ploynMultiplication(ploynp1,ploynp2){ ploynp3; intaaa[15]={0}; for(inti=0;i<p1.size();i++) { for(intj=0;j<p2.size();j++) { aaa[p1[i].second+p2[j].second]++; } } for(inti=0;i<=14;i++) { if(aaa[i]%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(field[i],p); if(a.size()==1&&a[a.size()-1].second==0)returnfield[i]; } }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=field[num1]; ploynp2=field[num2]; ploynp3; cout<<"隨機選的兩個多項式為："<<endl; show1(p1); show1(p2); p3=addition(p1,p2); cout<<"兩個多項式相加為："<<endl; show1(p3); cout<<"兩個多項式相減為："<<endl; show1(p3); p3=Multiplicatio