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

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

2、p.push_back(make_pair(1,4);則多項(xiàng)式temp變?yōu)閤A0+xA4make_pair中第一個兀素是系數(shù)，第二個是次數(shù)2、怎么牛生成域？用遞歸生成，我們知道成域GFpn會有2的n次方個兀素，只要能求出 2的n-1個，就可以求出2的n個因?yàn)楫?dāng)為n時，n-1中的每一個多項(xiàng)式添加一個xAn次方就可以了。3、實(shí)現(xiàn)四則運(yùn)算，尤其是在乘法和除法時，還有一個模運(yùn)算的？因?yàn)槭窃诙S的情形下啊的，所以實(shí)驗(yàn)中的加法減法的答案是同一個，至于乘法，乘出來的多項(xiàng)式的次數(shù)每循環(huán)一次都會減小至少1，所以最終會小于 8的除法就是先求逆，因?yàn)槲覀冎烙蛑械拿總€多項(xiàng)式都會有逆而且逆唯一并就在域中，所以用窮搜素

3、的方法在于中一個一個試，只要相乘模 xA8+xA4+xA3+x+1為1的就是逆。1、學(xué)生自己生成一個有限域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+x5xXX 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 + a x in x in 4* + m x x

5、 - x h x h + 才x x4- x x z 仆 4 夏.Inllj2X2. 10?y eJVQW lols苦 TOrMe +y * y 址fi$ROFxhx*wxiXAxx*r+ +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、任選兩個多項(xiàng)式進(jìn)行四則運(yùn)算:x 1+k 2+x 3*x5+)t 6+x T1 +x*1 +m*2+x3+x*M+x*5*x*+x* ?逋機(jī)選的兩個多頊?zhǔn)綖椋?+x 5+x7 I+jc*1+h*2+x*4兩平多項(xiàng)式相加為.1 *x* 1 tx*2+?c* 3+x *4+x*5+xWr式相減為； l+xl+x2+x*3+x4+x5+x7 阡i詩頊?zhǔn)较喑藘?+x14*3+x1+xl+ac*2+x*4的逆多璜式智1+x1+x2+xa?*x4+x&兩卜羅陋丈相除為：1*

7、x*1t*2+x*3*x*T館按任意握維陵代碼如下：/*本實(shí)驗(yàn)需要解決的幾個問題：1、用什么方法存儲多項(xiàng)式最好我用的是向量來儲存多項(xiàng)式，比如：plo yn temp ;temp.push_back(make_pair(1,0);說明多項(xiàng)式temp中只有一項(xiàng)，為xA0，如果再執(zhí)行 temp.push_back(make_pair(1,4);則多項(xiàng)式temp變?yōu)閤A0+xA4make_pair中第一個元素是系數(shù)，第二個是次數(shù)2、怎么生生成域用遞歸生成，我們知道成域 GFpn會有2的n次方個元素，只要能求出2的n-1個,就可以求出2的n個因?yàn)楫?dāng)為n時，n-1中的每一個多項(xiàng)式添加一個xAn次方就可以了

8、。3、實(shí)現(xiàn)四則運(yùn)算，尤其是在乘法和除法時，還有一個模運(yùn)算的因?yàn)槭窃诙S的情形下啊的，所以實(shí)驗(yàn)中的加法減法的答案是同一個，至于乘法，乘出來的多項(xiàng)式的次數(shù)每循環(huán)一次都會減小至少1，所以最終會小于 8的所以除法就是先求逆，因?yàn)槲覀冎烙蛑械拿總€多項(xiàng)式都會有逆而且逆唯一并就在域中， 用窮搜素的方法在于中一個一個試，只要相乘模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時的域的多項(xiàng)式的集合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); 在每一項(xiàng)多項(xiàng)式后面添加xAn 次方field.push_back (temp2);return field;輸出多項(xiàng)式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;/*聲明一個數(shù)組，數(shù)組的下標(biāo)表示項(xiàng)的次數(shù)，數(shù)組存儲的是系數(shù)，初始為0這樣只要遍歷一下兩個多項(xiàng)式，項(xiàng)的次數(shù)相同(也就是下標(biāo)相同的，每遍歷一次就加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 +;/遍歷兩個多形式后，這里把系數(shù)為不為偶數(shù)的項(xiàng)都留下來，就是加法的最后結(jié)果/因?yàn)榧臃ù螖?shù)不會增大，所以不需要進(jìn)行模運(yùn)算。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*/*這是個模運(yùn)算，遞歸基是多項(xiàng)式次數(shù)小于8，我存儲的多項(xiàng)式階從左到右是上升的。這個函數(shù)利用了類似歐幾里得算法，每循環(huán)一次次數(shù)都會下降，直到次數(shù)小于 if(p.back().sec ond N)

13、retur 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);乘法的實(shí)現(xiàn)類似于加法，只是后面有個模運(yùn)算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.s

14、ec 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隨機(jī)選的兩個多項(xiàng)式為：endl;show1(p1);show1(p2);p3=additio n( p1,p2);cout兩個多項(xiàng)式相加為：e ndl;show1(p3);c