第9章 质数与大整数算术

返回总目录第9章质数与大整数算术1.2©2006第9章质数与大整数算术教学目的•掌握大整数算术•了解Montgomery算术•了解Miller-Rabin质数测试•了解Agrawal-Kayal-Saxena算法•了解强质数和DSA质数•了解Java中的BigIntegerClass套件1.3©2006第9章质数与大整数算术大整数的加减乘法本章内容大整数的除法Montgomery算术Miller-Rabin质数测试Agrawal-Kayal-Saxena算法公开密钥密码的质数Java的BigIntegerClass大整数算术与数论套件及软件1.4©2006第9章质数与大整数算术大整数的加减乘法9.1大整数的加减乘法unsignedintcarrier=0;for(unsignedshorti=0;iL;i++){unsignedintw=(unsignedint)x[i]+(unsignedint)y[i]+carrier;if(w0xffff){carrier=1;z[i]=(unsignedshort)(w-0x10000);}else{carrier=0;z[i]=(unsignedshort)w;};};z[L]=(unsignedshort)carrier;1.5©2006第9章质数与大整数算术减法۩算法x-y=dunsignedintcarrier=0;for(unsignedshorti=0;iL;i++){intw=(unsignedint)x[i]-(unsignedint)y[i]-carrier;if(w0){carrier=1;d[i]=(unsignedshort)(w+0x10000);}else{carrier=0;d[i]=(unsignedshort)w;};};1.6©2006第9章质数与大整数算术乘法۩算法x×y=munsignedintcarrier=0;for(unsignedshorti=0;i2*L-1;i++){unsignedintw=carrier;for(unsignedshortj=0;j=i;j++)w=w+(unsignedint)x[j]*(unsignedint)y[i-j];if(w0xffff){carrier=(unsignedshort)w/0x10000;m[i]=(unsignedshort)(w-carrier16);}//REM:carrier16=carrier*0x10000else{carrier=0;m[i]=(unsignedshort)w;};};m[2*L-1]=(unsignedshort)carrier;1.7©2006第9章质数与大整数算术Karatsuba乘法۩算法Karatsuba乘法KarastubaMultiply(x,y){L=max(x.bitlength,y.bitlength);if(L1){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}1.8©2006第9章质数与大整数算术大整数的除法9.2大整数的除法division(x,y){x=(x[n],x[n-1],...,x[1],x[0]);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)};1.9©2006第9章质数与大整数算术除法//主要算法部分: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[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);1.10©2006第9章质数与大整数算术Montgomery算术9.3Montgomery算术♫性质有两个互质的整数n和r，令表示r在(modn)模运算中的乘法反元素，n-1表示n在(modr)模运算中的乘法反元素。定义1nn(modr)mtn(modr)，其中t为某整数，则1tmntr(modn)r1.11©2006第9章质数与大整数算术Montgomery乘法۩算法Montgomery乘法InverseMod2power(n,s)//计算n’=nˆ(-1)(mod2ˆs),其中n为奇数{result=1;for(i=2;i=s;i++)if(2ˆ(i-1)(x*result)%2ˆi)result+=2ˆ(i-1);returnresult;}MontgomeryProduct(a,b,n){t=ab;//r=2ˆs:s=ceil(log(n)/log(2))+1;//用InverseMod2power(n,s)计算n’=nˆ(-1)(mod2ˆs):n’=InverseMod2power(n,s);m=t*n’;u=(t+m*n)s;//(t+m*n)/rif(u=n)u=-n;returnu;}1.12©2006第9章质数与大整数算术Miller-Rabin质数测试9.4Miller-Rabin质数测试定理令n为奇数，且，其中d为奇数，若a为与n互质的整数，若n为质数，则以下两陈述中必有一个成立：sn1d2；da1(modn)或存在某整数r（其中）使得0rs1r2da1(modn)1.13©2006第9章质数与大整数算术Miller-Rabin质数测试۩算法Miller-Rabin质数测试boolMillerRabin_Test(bigintegern,bigintegera){//a=Random_Integer(2,n-1);if(gcd(a,n)1)return0;//0表示一定不是质数bigintegers=1;bigintegerd=(n-1)/2;while(is_even(d)){d/=2;s++;};//n=2ˆs*d+1if(gcd(a,n)!=1)return0;//×__βóelseif(((aˆd)-1)%==0)return1;else{for(bigintegerr=0;rs;r++)if((aˆ(2ˆr*d)+1)%n==0)return1;//1表示可能为质数概率为1-1/4return0;//一定不是质数};}输入大整数n，判断是否为质数1.14©2006第9章质数与大整数算术Miller-Rabin质数测试۩算法输出一k-bit质数x。Miller_Rabin_Probable_Prime(){Step1:x=Random_Integer(1,b[k-2],b[k-3],...,b[2],b[1],1);//二进位数，b[i]=0或1，x为一奇数Step2:for(i=1;prime[i]=B;i++)//prime[i]表第i个质数if(x%prime[i]==0)gotoStep1;//x非质数，重来!Step3:for(i=1;i=t;i++){a[i]=Random_Integer(2,x-1);if(MillerRabin(x,a[i])==0)gotoStep1;};outputx可能是质数,;output所有=B的质数无法整除,;output并通过Miller-Rabin测试t次数!;}1.15©2006第9章质数与大整数算术Agrawal-Kayal-Saxena算法9.5Agrawal-Kayal-Saxena算法定理Agrawal-Kayal-Saxena令为自然数且。令质数q与r满足nsnr1qqs12[]srq|(r1)n0,1(modr)Cn。若对所有的都满足1as（1）a与n互质。（2）且在多项式环Z[x]中。nnr(xa)xamod(x1,n)则n为某质数的幂次。1.16©2006第9章质数与大整数算术Agrawal-Kayal-Saxena算法۩算法Agrawal-Kayal-Saxena算法boolAgrawal_Kayal_Saxena(bigintegern)//n1整数{Step1:if(isPower(n))//若n=aˆb,其中b1return0;//n为某数幂次，非质数Step2:r=min{r|ord(n,Z/r)4*(log(n)ˆ2)};//ord(n,Z/r)表示n在乘法群Z/r的秩for(a=2;a=r;a++){gcd=gcd(a,n);if(gcd1&&gcdn)return0;//n为合数，非质数};s=floor(2*sqrt(Eulerphi(r))*log(n));step3:for(a=1;a=s;a++)if((x+a)ˆn!=xˆn+a(modxˆr-1,n))return0;//n为合数，非质数return1;//n为质数};输入一个正整数n1，并判断其是否为质数。1.17©2006第9章质数与大整数算术公开密钥密码的质数9.6公开密钥密码的质数定义强质数，StrongPrime质数p称之为强质数，当正整数r、s、t存在满足p-1拥有大质数因子r。p+1拥有大质数因子s，r-1拥有大质数因子t。1.18©2006第9章质数与大整数算术Gordan算法۩Gordan算法Gordan(){s=RandomPrime;t=RandomPrime;//s与t的位数大约相同i=RandomInteger;while(isPrime(r=2*i*t+1)==0)i++;p0=2*(sˆ(r-2)%r)*s-1;j=RandomInteger;while(isPrime(p=p0+2*j*r*s)==0)j++;returnp;}1.19©2006第9章质数与大整数算术DSA质数定义DSA的质数p与q满足：，q为160-bit的质数。1591602q2，其中，而。L1L2p2L51264dd0,1,2,,8q|p-1。同时希望应有大质数因子。p12q1.20©2006第9章质数与大整数算术DSA算法DSA_Prime(d){L=512+64*d;n=(L-1)/160;b=(L-1)%160;while(1){do{s=RandomInteger(g-bit);//g=160h=SHA-1;u=h(s)XORh((s+1)%(2ˆg));q=1(g+1)+u1+1;}while(!isProbablePrime(q));۩DSA算法1.21©2006第9章质数与大整数算术DSA算法//使用Miller-Rabin测试至少18次for(i=0,j=2;i4096;i++,j+=n+1){W=0;for(k=0,k=n,k++){V[k]=h((s+j+k)%(2ˆg));if(k==n)V[k]=V[k]%(1b);W=W+V[k]*(1(160*k));};X=W+(1(2*L));c=X%(2*q);p