密码学——加密演算法 邓安文 第9章 质数与大整数算术

《密码学——加密演算法 邓安文 第9章 质数与大整数算术》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、返回总目录第9章质数与大整数算术教学目的掌握大整数算术了解Montgomery算术了解Miller-Rabin质数测试了解Agrawal-Kayal-Saxena算法了解强质数和DSA质数了解Java中的BigIntegerClass套件大整数的加减乘法本章内容大整数的除法Montgomery算术Miller-Rabin质数测试Agrawal-Kayal-Saxena算法公开密钥密码的质数Java的BigIntegerClass大整数算术与数论套件及软件大整数的加减乘法9.1大整数的加减乘法unsignedintcarrier=0;for

2、(unsignedshorti=0;i0xffff){carrier=1;z[i]=(unsignedshort)(w-0x10000);}else{carrier=0;z[i]=(unsignedshort)w;};};z[L]=(unsignedshort)carrier;减法算法x-y=dunsignedintcarrier=0;for(unsignedshorti=0;i

3、nedint)x[i]-(unsignedint)y[i]-carrier;if(w<0){carrier=1;d[i]=(unsignedshort)(w+0x10000);}else{carrier=0;d[i]=(unsignedshort)w;};};乘法算法x×y=munsignedintcarrier=0;for(unsignedshorti=0;i<2*L-1;i++){unsignedintw=carrier;for(unsignedshortj=0;j<=i;j++)w=w+(unsignedint)x[j]*(unsignedint)

4、y[i-j];if(w>0xffff){carrier=(unsignedshort)w/0x10000;m[i]=(unsignedshort)(w-carrier<<16);}//REM:carrier<<16=carrier*0x10000else{carrier=0;m[i]=(unsignedshort)w;};};m[2*L-1]=(unsignedshort)carrier;Karatsuba乘法算法Karatsuba乘法KarastubaMultiply(x,y){L=max(x.bitlength,y.bitlength);if(L>1

5、){LL=ceil(L/2);x=x[1]*2ˆLL+x[0];//将x,y分割成2半y=y[1]*2ˆLL+y[0];A=KarastubaMultiply(x[0],y[0])B=KarastubaMultiply(x[0]+x[1],y[0]+y[1]);C=KarastubaMultiply(x[1],y[1]);return(C,B-A-C,A);//C*4ˆLL+(B-A-C)*2ˆLL+A}elsereturnx*y;//L=1}大整数的除法9.2大整数的除法division(x,y){x=(x[n],x[n-1],...,x[1],x[0

6、]);y(y[n-1],y[n-2],...,y[1],y[0]);q_test=min(x[n]*(2ˆ16)+x[n-1]/y[n-1],2ˆ16-1);temp=q_test*y;while(temp>=x){q_test--;temp=temp-y;};q=q_test;remainder=x-q*y;return(q,remainder)};除法//主要算法部分:a=(a[n+m-1],...,a[1],a[0]);b=(b[n-1],...,b[1],b[0]);if(a[n+m-1]>=b[n-1]){a=(0,a[n+m-1],...,a

7、[1],a[0]);m++};x=(a[n+m-1],a[n+m-2],...,a[m-1]);for(i=m;m>=2;m--){(q[i],remainder)=division(x,b);x=remainder*(2ˆ16)+a[i-2];};(q[0],r)=division(x,b);Montgomery算术9.3Montgomery算术性质有两个互质的整数n和r，令表示r在(modn)模运算中的乘法反元素，n-1表示n在(modr)模运算中的乘法反元素。定义其中t为某整数，则Montgomery乘法算法Montgomery乘法InverseM

8、od2power(n,s)//计算n’=nˆ(-1)(mod2ˆs),其中n为奇