《清华离散数学第2版13.12》由会员分享，可在线阅读，更多相关《清华离散数学第2版13.12（19页珍藏版）》请在金锄头文库上搜索。
1、第第1313章章 初等数论和初等数论和离散概率的应用离散概率的应用1第第1313章章 初等数论和初等数论和离散概率的应用离散概率的应用 13.1密码学密码学13.2产生伪随机数的方法产生伪随机数的方法13.3算法的平均复杂度分析算法的平均复杂度分析13.4随机算法随机算法213.1密码学密码学13.1.1恺撒密码恺撒密码明文明文,密文密文,加密加密,解密解密,密钥密钥13.1.2RSA公钥密码公钥密码私钥密码与公钥密码私钥密码与公钥密码3恺撒恺撒(Caesar)密码密码加密方法加密方法:ABCDEFGHIJKLMNOPQRSTUVWXYZDEFGHIJKLMNOPQRSTUVWXYZABC明文
2、明文:SEEYOUTOMORROW密文密文:VHHBRXWRPRUURZ184424142019141214171714222177117232217151720201725加密算法加密算法E(i)=(i+k)mod26,i=0,1,25,解密算法解密算法D(i)=(i k)mod26,i=0,1,25其中其中密钥密钥k是一取定的整数是一取定的整数,这里取这里取k=3.4加密算法加密算法线性同余加密算法线性同余加密算法E(i)=(ai+b)mod26,i=0,1,25,其中其中a与与26互素互素. .维吉利亚维吉利亚(Vigenere)密码密码把明文分成若干段把明文分成若干段,每一段有每一段有
3、n个数字个数字,密钥密钥k=k1k2kn,加密算法加密算法E(i1i2in)=c1c2cn,其中其中cj=(ij+kj)mod26,ij=0,1,25,j=1,2,n.5RSA公钥密码公钥密码 私钥密码私钥密码:加密密钥和解密密钥都必须严格保密加密密钥和解密密钥都必须严格保密公钥密码公钥密码(W.Diffie,M.Hellman,1976):加密密钥公开加密密钥公开,解解密密钥保密密密钥保密RSA公钥密码公钥密码(R.Rivest,A.Shamir,L.Adleeman,1978)取取2个大素数个大素数p和和q(pq),记记n=pq, (n)=(p 1)(q 1).选择正选择正整数整数w,w与
4、与 (n)互素互素,设设d=w 1(mod (n).将明文数字化将明文数字化,分成若干段分成若干段,每一个明文段每一个明文段mn.加密算法加密算法c=E(m)=mwmodn,解密算法解密算法D(c)=cdmodn,其中加密密钥其中加密密钥w和和n是公开的是公开的,而而p,q, (n)和和d是保密的是保密的.6解密算法正确性证明解密算法正确性证明要证要证m=cdmodn,即即cdm(modn),亦即亦即mdwm(modn).由由dw1(mod (n),存在存在k使得使得dw=k (n)+1.有两种可能有两种可能:(1)m与与n互素互素.由欧拉定理由欧拉定理 m (n)1(modn),得得mdwm
5、k (n)+1 m(modn).(2)m与与n不互素不互素.不妨设不妨设m=cp且且q不整除不整除m.由费马小定理由费马小定理 mq 11(modq).于是于是,mk (n)mk(p 1)(q 1)1k(p 1)1(modq).7解密算法正确性证明解密算法正确性证明( (续续) )从而存在从而存在h使得使得 mk (n)=hq+1,两边同乘以两边同乘以m,并注意到并注意到m=cp, mk (n)+1=hcpq+m=hcn+m,得证得证 mk (n)+1m(modn),即即 mdwm(modn).8模幂乘运算模幂乘运算模幂乘运算模幂乘运算ab(modn)设设b=b0+b12+br 12r 1,其
6、中其中bi=0或或1,于是于是令令A0=a,Ai(Ai 1)2(modn),i=1,2,r 1,则有则有9实例实例例例1p=43,q=59,n=4359=2537, (n)=4258=2436,w=13.A,B,Z依次用依次用00,01,25表示表示,各占各占2位位.设明文段设明文段m=2106,即即VG,密文密文c=210613mod2537.计算如下计算如下:13=(1101)2,即即13=1+22+23.A0=2106 431(mod2537),A1( 431)2560(mod2537),A25602 988(mod2537),A3( 988)2 601(mod2537),210613(
7、 431)( 988)( 601)2321(mod2537),得密文得密文c=2321.10实例实例(续续)设密文设密文c=0981.d=13 1937(mod2436),明文明文m=981937(mod2537).计算如下计算如下:937=(1110101001)2, A0=981,A19812838(mod2537), A28382 505,A3( 505)21325, A41325221,A5212441, A64412 868,A7( 868)2 65, A8( 65)2 849,A9( 849)2293,9819379811325441( 65)( 849)293704(mod253
8、7),得明文得明文m=0704,即即HE.1113.2产生伪随机数的方法产生伪随机数的方法 13.2.1产生均匀伪随机数的方法产生均匀伪随机数的方法随机数与伪随机数随机数与伪随机数线性同余法与乘同余法线性同余法与乘同余法13.2.2产生离散型伪随机数的方法产生离散型伪随机数的方法离散型均匀分布伪随机数离散型均匀分布伪随机数二项分布伪随机数二项分布伪随机数泊松分布伪随机数泊松分布伪随机数12线性同余法线性同余法随机数随机数:随机变量的观察值随机变量的观察值伪随机数伪随机数(0,1)上的均匀分布上的均匀分布U(0,1): a(0a1),P0Xa=a线性同余法线性同余法选择选择4个非负整数个非负整数
9、:模数模数m,乘数乘数a,常数常数c和种子数和种子数x0,其中其中2am,0cm,0x0Fdo4.kk+1,FF+pk5.xak给定分布律给定分布律PX=ak= pk,k=1,2,设设UU(0,1),可取可取15算法算法13.2 离散型均匀分布伪随机数的产生算法离散型均匀分布伪随机数的产生算法输入输入:n个不同的数个不同的数a1, a2,an输出输出:伪随机数伪随机数x1.产生一个产生一个U(0,1)伪随机数伪随机数u2.fork1ton do3.ifuk/n thenxak,计算结束计算结束(1) 离散型均匀分布离散型均匀分布a1, a2, an上均匀分布的分布律为上均匀分布的分布律为 PX
10、=ak=1/n,k=1,2,n 1.16算法算法13.3 泊松分布伪随机数的产生算法泊松分布伪随机数的产生算法输入输入: 0输出输出:伪随机数伪随机数x1.产生一个产生一个U(0,1)伪随机数伪随机数u2.pe ,Fp,k03.whileuFdo4.kk+1,p p/k,FF+p5.xk(2)泊松分布泊松分布递推公式递推公式:p0=e- ,pk+1= pk/(k+1),k=0,1,2,.17算法算法13.4 二项分布伪随机数的产生算法二项分布伪随机数的产生算法输入输入:整数整数n 2和和p(0p1)输出输出:伪随机数伪随机数x1.产生一个产生一个U(0,1)伪随机数伪随机数u2.cp/(1 p
11、),t(1 p)n,Ft3.fork0tondo4.ifuFthenxk,计算结束计算结束5.elsettc(n k)/(k+1),FF+t(3)二项分布二项分布方法一方法一.递推公式递推公式:p0=qn, pk+1= pk,k=0,1,n-1.18算法算法13.5 二项分布伪随机数的产生算法二项分布伪随机数的产生算法输入输入:整数整数n2和和p(0p1)输出输出:伪随机数伪随机数x1.x02.fori=1tondo3.产生一个产生一个U(0,1)伪随机数伪随机数u4.ifupthenxx+1(3) 二项分布二项分布( (续续) )方法二方法二.B(n,p)可表成可表成n个相互独立的参数个相互独立的参数p的的0-1分布之和分布之和19
