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

1第13章初等数论和离散概率的应用2第13章初等数论和离散概率的应用•13.1密码学•13.2产生伪随机数的方法•13.3算法的平均复杂度分析•13.4随机算法313.1密码学•13.1.1恺撒密码–明文,密文,加密,解密,密钥•13.1.2RSA公钥密码–私钥密码与公钥密码4恺撒(Caesar)密码加密方法:ABCDEFGHIJKLMNOPQRSTUVWXYZDEFGHIJKLMNOPQRSTUVWXYZABC明文:SEEYOUTOMORROW密文:VHHBRXWRPRUURZ184424142019141214171714222177117232217151720201725加密算法E(i)=(i+k)mod26,i=0,1,…,25,解密算法D(i)=(ik)mod26,i=0,1,…,25其中密钥k是一取定的整数,这里取k=3.5加密算法线性同余加密算法E(i)=(ai+b)mod26,i=0,1,…,25,其中a与26互素.维吉利亚(Vigenere)密码把明文分成若干段,每一段有n个数字,密钥k=k1k2…kn,加密算法E(i1i2…in)=c1c2…cn,其中cj=(ij+kj)mod26,ij=0,1,…,25,j=1,2,…,n.6RSA公钥密码私钥密码:加密密钥和解密密钥都必须严格保密公钥密码(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)).将明文数字化,分成若干段,每一个明文段mn.加密算法c=E(m)=mwmodn,解密算法D(c)=cdmodn,其中加密密钥w和n是公开的,而p,q,(n)和d是保密的.7解密算法正确性证明要证m=cdmodn,即cd≡m(modn),亦即mdw≡m(modn).由dw≡1(mod(n)),存在k使得dw=k(n)+1.有两种可能:(1)m与n互素.由欧拉定理m(n)≡1(modn),得mdw≡mk(n)+1≡m(modn).(2)m与n不互素.不妨设m=cp且q不整除m.由费马小定理mq1≡1(modq).于是,mk(n)≡mk(p1)(q1)≡1k(p1)≡1(modq).8解密算法正确性证明(续)从而存在h使得mk(n)=hq+1,两边同乘以m,并注意到m=cp,mk(n)+1=hcpq+m=hcn+m,得证mk(n)+1≡m(modn),即mdw≡m(modn).9模幂乘运算)(mod)()(111022naaaarrbbbb)(mod110110nAAAarbrbbb模幂乘运算ab(modn)设b=b0+b1×2+…+br1×2r1,其中bi=0或1,于是令A0=a,Ai≡(Ai1)2(modn),i=1,2,…,r1,则有10实例例1p=43,q=59,n=43×59=2537,(n)=42×58=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)2≡560(mod2537),A2≡5602≡988(mod2537),A3≡(988)2≡601(mod2537),210613≡(431)×(988)×(601)≡2321(mod2537),得密文c=2321.11实例(续)设密文c=0981.d=131≡937(mod2436),明文m=981937(mod2537).计算如下:937=(1110101001)2,A0=981,A1≡9812≡838(mod2537),A2≡8382≡505,A3≡(505)2≡1325,A4≡13252≡21,A5≡212≡441,A6≡4412≡868,A7≡(868)2≡65,A8≡(65)2≡849,A9≡(849)2≡293,981937≡981×1325×441×(65)×(849)×293≡704(mod2537),得明文m=0704,即HE.1213.2产生伪随机数的方法•13.2.1产生均匀伪随机数的方法–随机数与伪随机数–线性同余法与乘同余法•13.2.2产生离散型伪随机数的方法–离散型均匀分布伪随机数–二项分布伪随机数–泊松分布伪随机数13线性同余法随机数:随机变量的观察值伪随机数(0,1)上的均匀分布U(0,1):a(0a1),P{0X≤a}=a线性同余法选择4个非负整数:模数m,乘数a,常数c和种子数x0,其中2≤am,0≤cm,0≤x0m,用递推公式产生伪随机数序列:xn=(axn1+c)modm,n=1,2,…取un=xn/m,n=1,2,…作为U(0,1)伪随机数.14线性同余法(续)线性同余法产生的序列的质量取决于m,a和c.例如m=8,a=3,c=1,x0=2,得到7,6,3,2,7,6,…,周期为4m=8,a=5,c=1,x0=2,得到3,0,1,6,7,4,5,2,3,0,1,…,周期为8.a=0,得到c,c,c,…a=1,得到x0+c,x0+2c,x0+3c,…乘同余法:c=0(x0≠0)的线性同余法,即xn=axn1modm,n=1,2,….最常用的均匀伪随机数发生器:m=2311,a=75的乘同余法,它的周期是2312.15产生离散型伪随机数的方法算法13.1离散型随机数产生算法输入:分布律(ak,pk),k=1,2,…输出:伪随机数x1.产生一个U(0,1)伪随机数u2.F←p1,k←13.whileuFdo4.k←k+1,F←F+pk5.x←ak,2,1,,111kpUpaXkiikiik若给定分布律P{X=ak}=pk,k=1,2,…,设U~U(0,1),可取16算法13.2离散型均匀分布伪随机数的产生算法输入:n个不同的数a1,a2,…,an输出:伪随机数x1.产生一个U(0,1)伪随机数u2.fork←1tondo3.ifu≤k/nthenx←ak,计算结束(1)离散型均匀分布{a1,a2,…,an}上均匀分布的分布律为P{X=ak}=1/n,k=1,2,…,n1.17算法13.3泊松分布伪随机数的产生算法输入:0输出:伪随机数x1.产生一个U(0,1)伪随机数u2.p←e,F←p,k←03.whileuFdo4.k←k+1,p←p/k,F←F+p5.x←k,1,0,!}{kekkXPk(2)泊松分布递推公式:p0=e-,pk+1=pk/(k+1),k=0,1,2,….18算法13.4二项分布伪随机数的产生算法Ⅰ输入:整数n2和p(0p1)输出:伪随机数x1.产生一个U(0,1)伪随机数u2.c←p/(1p),t←(1p)n,F←t3.fork←0tondo4.ifu≤Fthenx←k,计算结束5.elset←tc(nk)/(k+1),F←F+t(3)二项分布方法一.递推公式:p0=qn,pk+1=pk,k=0,1,…,n-1.nkqpknkXPpknkk,,1,0,}{qkpkn)1()(19算法13.5二项分布伪随机数的产生算法Ⅱ输入:整数n≥2和p(0p1)输出:伪随机数x1.x←02.fori=1tondo3.产生一个U(0,1)伪随机数u4.ifu≤pthenx←x+1(3)二项分布(续)方法二.B(n,p)可表成n个相互独立的参数p的0-1分布之和