离散数学--13.1-2初等数论和离散概率的应用.ppt

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,*,*,第13章 初等数论和离散概率的应用,1,第13章 初等数论和离散概率的应用,13.1 密码学,13.2 产生伪随机数的方法,13.3 算法的平均复杂度分析,13.4 随机算法,2,13.1,密码学,13.1.1恺撒密码,明文,密文,加密,解密,密钥,13.1.2 RSA,公钥密码,私钥密码与公钥密码,3,恺撒(,Caesar),密码,加密方法:,ABCDEFGH I J KLMNOPQRS TUVWXYZ,DEFGH I JKLMNO PQRS TUVWXYZ ABC,明文,:,SEE YOU TOMORROW,密文,:,VHH BRX WRPRUURZ,18 4 4 24 14 20 19 14 12 14 17 17 14 22,21 7 7 1 17 23 22 17 15 17 20 20 17 25,加密算法,E,(,i,)=(,i,+,k,)mod 26,i,=0,1,25,解密算法,D,(,i,)=(,i,k,)mod 26,i,=0,1,25,其中,密钥,k,是一取定的整数,这里取,k,=3.,4,加密算法,线性同余加密算法,E,(,i,)=(,ai,+,b,)mod 26,i,=0,1,25,其中,a,与26,互素.,维吉利亚(,Vigenere,),密码,把明文分成若干段,每一段有,n,个数字,密钥,k,=,k,1,k,2,k,n,加密算法,E,(,i,1,i,2,i,n,)=,c,1,c,2,c,n,其中,c,j,=,(,i,j,+,k,j,)mod 26,i,j,=0,1,25,j,=1,2,n,.,5,RSA,公钥密码,私钥密码,:加密密钥和解密密钥都必须严格保密,公钥密码,(,W.Diffie,M.Hellman,1976):加密密钥公开,解密密钥保密,RSA,公钥密码,(,R.,Rivest,A.,Shamir,L.,Adleeman,1978),取2个大素数,p,和,q,(,p,q,),记,n,=,pq,(,n,)=(,p,1)(,q,1),.选择正,整数,w,w,与,(,n,),互素,设,d,=,w,1,(mod,(,n,),.将明文数字化,分成若干段,每一个明文段,m,n,.,加密算法,c,=,E,(,m,),=,m,w,mod,n,解密算法,D,(,c,),=,c,d,mod,n,其中加密密钥,w,和,n,是公开的,而,p,q,(,n,),和,d,是保密的.,6,解密算法正确性证明,要证,m,=,c,d,mod,n,即,c,d,m,(mod,n,),亦即,m,dw,m,(mod,n,).,由,dw,1(mod,(,n,),存在,k,使得,dw,=,k,(,n,)+1.,有两种可能:,(1),m,与,n,互素.由欧拉定理,m,(n,),1(mod,n,),得,m,dw,m,k,(,n,)+1,m,(mod,n,).,(2),m,与,n,不互素,.,不妨设,m,=,cp,且,q,不整除,m,.,由费马小定理,m,q,1,1(mod,q,).,于是,m,k,(,n,),m,k,(,p,1)(,q,1),1,k,(,p,1),1(mod,q,).,7,解密算法正确性证明(续),从而存在,h,使得,m,k,(,n,),=,hq,+1,两边同乘以,m,并注意到,m,=,cp,m,k,(,n,)+1,=,hcpq,+,m,=,hcn,+,m,得证,m,k,(,n,)+1,m,(mod,n,),即,m,dw,m,(mod,n,)8,模幂乘运算,模幂乘运算,a,b,(mod,n,),设,b,=,b,0,+,b,1,2+,b,r,1,2,r,1,其中,b,i,=0,或1,于是,令,A,0,=,a,A,i,(,A,i,1,),2,(mod,n,),i,=1,2,r,1,则有,9,实例,例1,p,=43,q,=59,n,=4359=2537,(,n,)=4258=2436,w,=13.,A,B,Z,依次用00,01,25表示,各占2位.,设明文段,m,=2106,即,VG,密文,c,=2106,13,mod 2537.,计算如下:13=(1101),2,即13=1+2,2,+2,3,.,A,0,=2106,431(mod 2537),A,1,(,431),2,560(mod 2537),A,2,560,2,988(mod 2537),A,3,(,988),2,601(mod 2537),2106,13,(,431)(,988)(,601)2321(mod 2537),得密文,c,=2321.,10,实例(续),设密文,c,=0981.,d,=13,1,937(mod 2436),明文,m,=981,937,(mod 2537).,计算如下:937=(1110101001),2,A,0,=981,A,1,981,2,838(mod 2537),A,2,838,2,505,A,3,(,505),2,1325,A,4,1325,2,21,A,5,21,2,441,A,6,441,2,868,A,7,(,868),2,65,A,8,(,65),2,849,A,9,(,849),2,293,981,937,9811325441(,65)(,849)293,704(mod 2537),得明文,m,=0704,即,HE.,11,13.2,产生伪随机数的方法,13.2.1 产生均匀伪随机数的方法,随机数与伪随机数,线性同余法与乘同余法,13.2.2 产生离散型伪随机数的方法,离散型均匀分布伪随机数,二项分布伪随机数,泊松分布伪随机数,12,线性同余法,随机数,:随机变量的观察值,伪随机数,(0,1)上的均匀分布,U,(0,1),:,a,(,0,a,1),P,0,X,a,=,a,线性同余法,选择4个非负整数:模数,m,乘数,a,常数,c,和种子数,x,0,其中,2,a,m,0,c,m,0,x,0,F,do,4.,k,k,+1,F,F,+,p,k,5.,x,a,k,给定分布律,P,X,=,a,k,=,p,k,k,=1,2,设,U,U,(0,1),可取,15,算法,13.2,离散型均匀分布伪随机数的产生算法,输入:,n,个不同的数,a,1,a,2,a,n,输出:伪随机数,x,1.产生一个,U,(0,1),伪随机数,u,2.for,k,1 to,n,do,3.if,u,k,/,n,then,x,a,k,计算结束,(1),离散型均匀分布,a,1,a,2,a,n,上均匀分布的分布律为,P,X,=,a,k,=1/,n,k,=1,2,n,1.,16,算法,13.3,泊松分布伪随机数的产生算法,输入:,0,输出:伪随机数,x,1.产生一个,U,(0,1),伪随机数,u,2.,p,e,F,p,k,0,3.while,u,F,do,4.,k,k,+1,p,p,/,k,F,F,+,p,5.,x,k,(2)泊松分布,递推公式:,p,0,=,e,-,p,k,+1,=,p,k,/(,k,+1),k,=0,1,2,.,17,算法,13.4,二项分布伪随机数的产生算法,输入:整数,n,2,和,p,(0,p,1),输出:伪随机数,x,1.产生一个,U,(0,1),伪随机数,u,2.,c,p,/(1,p,),t,(1,p,),n,F,t,3.for,k,0 to,n,do,4.if,u,F,then,x,k,计算结束,5.,else,t,tc,(,n,k,)/(,k,+1),F,F,+,t,(3)二项分布,方法一.,递推公式:,p,0,=,q,n,p,k,+1,=,p,k,k,=0,1,n,-1.,18,算法,13.5,二项分布伪随机数的产生算法,输入:整数,n,2,和,p,(0,p,1),输出:伪随机数,x,1.,x,0,2.for,i,=1 to,n,do,3.,产生一个,U,(0,1),伪随机数,u,4.if,u,p,then,x,x,+1,(3),二项分布(续),方法二,.,B,(,n,p,),可表成,n,个相互独立的参数,p,的,0-1,分布之和,19,