离散数学课件初等数论.ppt

Click to edit Master text styles,,Second level,,Third level,,Fourth level,,Fifth level,,*,Click to edit Master title style,,*,*,初等数论,主要内容,,素数,,最大公约数与最小公倍数,,同余,,在计算机科学中的应用,,19.1 素数,1. 整除,,定义1：,设,a, b,是两个整数，且,a,≠0， 若存在整数,c,使,b=ac,，则称,b,被,a,整除,，或,a,整除,b,，记作,a,|,b,. 此时, 又称,b,是,a,的,倍数,，,a,是,b,的,因子,. 把,a,不整除,b,记作,a b,.,性质：,令,a,，,b,，,c,为整数，有如下结论：,,1）若,a |b,且,a |c,,则,,x,,,y,, 有,a | xb,+,yc.,,2）若,a |b,且,b |c,,则,a |c.,,3）若,a |b,，那么对于所有整数,m,≠0都有,a | mb.,19.1 素数,2. 素数,,定义2：,大于 1 且只能被 1 和自身整除的正整数称为,素数,（,质数,）。

大于 1 又不是素数的正整数称为,合数,算术基本定理：,每个正整数都可以唯一地表示为素数的乘积，其中素数因子从小到大依次出现，即,,例1,：100, 641, 999的,素因子分解,为：,,100=2×2×5×5=2,2,×5,2,,,641=641,,999=3×3×3×37=3,3,×37,19.1 素数,定理 2,：,如果,n,是合数，那么,n,必有一个小于或等于 的素因子证：如果,n,是合数，它有一个因子,a，,使得1＜,a,＜,n，,,,于是 ，这样 ，这个因子或是素,,数，或是有素因子无论哪种情况，n都有小于或等于,,的素因子,例2,：证明101是素数证明思路：101不含有不超过 的素因子19.1 素数,定理 3,：有无穷多个素数梅森数,(Marin Mersenne): 2,p,,1, 其中,p,为素数当,n,是合数时, 2,n,,1一定是合数,,,2,ab,,1,=,(2,a,,1)(2,a,(,b,,1),+2,a,(,b,,2),+…+2,a,+1).,,梅森数可能是素数, 也可能是合数: 2,2,,1=3, 2,3,,1=7, 2,5,,1=31, 2,7,,1=127都是素数, 而2,11,,1=2047=23×89是合数.,,到2002年找到的最大梅森素数是,2,13466917,,1,, 有4百万位.,19.2 最大公约数和最小公倍数,d,是,a,与,b,的,公因子,(,公约数,):,d,|,a,且,d,|,b,,m,是,a,与,b,的,公倍数,:,a,|,m,且,b,|,m,,定义3：,设,a,和,b,是两个不全为0的整数, 称,a,与,b,的公因子中,,最大的为,a,与,b,的,最大公因子,, 或,最大公约数,, 记作gcd(,a,b,).,,设,a,和,b,是两个非零整数, 称,a,与,b,最小的正公倍数为,a,与,b,的,,最小公倍数,, 记作lcm(,a,b,).,,例3,gcd(12,18)=6, lcm(12,18)=36.,,对任意的正整数,a,, gcd(0,,a,)=,a,, gcd(1,,a,)=1, lcm(1,,a,)=,a,.,19.2 最大公约数和最小公倍数,定理4：,(1) 若,a | m,,,b | m,, 则 lcm(,a,b,)|,m,.,,(2) 若,d |a,,,d |b,, 则,d |,gcd(,a,,,b,).,,证 (1) 记,M,=lcm(,a,,,b,), 设,m,=,qM,+,r,, 0≤,r,<,M,.,,由,a | m,,,a | M,, 及,r,=,m,,qM,, 可推出,a | r,. 同理, 有,b | r,. 即,,r,是,a,,和,b,的公倍数. 根据最小公倍数的定义, 必有,r,=0. 得证,M | m,.,,(2) 记,D,=gcd(,a,b,), 令,m,=lcm(,d,,,D,). 若,m,=,D,, 自然有,d,|,D,, 结,,论成立. 否则,m,>,D,, 注意到,d,|,a,,,D|a,, 由(1), 得,m |a,. 同理,,m |b,.,,即,,m,是,a,和,b,的公因子, 与,D,是,a,和,b,的最大公约数矛盾.,19.2 最大公约数和最小公倍数,利用整数的素因子分解, 求最大公约数和最小公倍数. 设,,,,其中,p,1,,p,2,,…,p,k,是不同的素数,,r,1,,r,2,,…,r,k,,s,1,,s,2,,…,s,k,是非负,,整数. 则,,gcd(,a,b,)=,,lcm(,a,b,)=,例4,求150和220的最大公约数和最小公倍数.,解 150=2×3×5,2,, 168=2,3,×3×7.,,gcd(150,168)=2,1,×3,1,×5,0,×7,0,=6,,,lcm(150,168)=2,3,×3,1,×5,2,×7,1,=4200.,欧几里得算法-辗转相除法,除法算法,:,a=qb+r,,0≤,r,<|,b|,,记余数,r=a,mod,b,,例如, 20 mod 6=2,,,13 mod 4=3, 10 mod 2=0,定理5：,设,a,=,qb,+,r,, 其中,a, b, q, r,都是整数, 则,,gcd(,a,b,) = gcd(,b,r,).,,证明：只需证,a,与,b,和,b,与,r,有相同的公因子. 设,d,是,a,与,b,的公因,,子, 即,d |a,且,d |b,. 注意到,,r,=,a,,qb,, 由性质可得,d |r,. 从而,,,d |b,且,d,|,r,, 即,d,也是,b,与,r,的公因子. 反之一样, 设,d,是,b,与,r,的公,,因子, 即,d,|,b,且,d |r,. 注意到,,a,=,qb,+,r,, 故有,d |a,. 从而,,d |a,且,d |b,,,,即,d,也是,a,与,b,的公因子.,欧几里得算法-辗转相除法,最大公因数的求法：,辗转相除法,,例5,：求,gcd,(15,36),gcd,(54,30),,36=15,,2+6 54=30+24,,15=6,,2+3 30=24+6,,6=3,,2+0 24=4,,6+0,,因此，,gcd,(15,36)=3,gcd,(54,30)=6,,原理：,gcd,(,a,,,b,),,=,gcd,(,b,,,r,),,这里，,gcd,(36,15) =,gcd,(6,15) =,gcd,(6,3) = 3,欧几里得算法-辗转相除法,int gcd(int x，int y),,{ int g;,,if (x < 0) x = -x;,,if (y < 0) y = -y;,,if (x+y = = 0),,printf("Error!\n");,,g = y；,,while(x>0){,,g = x；,,x = y%x;,,y = g;,,},,return g;,,},试跟踪求gcd(36,15)时，变量值变化：,,,y x g,C语言代码：,19-3 同余,定义4：,设,m,是正整数,,a,和,b,是整数. 如果,m|a,,b,, 则称,a,模,,m,同余于,b,, 或,a,与,b,模,m,同余,, 记作,a,≡,b,(mod,m,). 如果,a,与,b,模,,m,不同余, 则记作,a b,(mod,m,).,,例如, 15≡3(mod 4), 16≡0(mod 4), 14≡,,,2(mod 4),,,15 16(mod 4).,,,下述两条都是,a,与,b,模,m,同余的充分必要条件,:,,(1),a,mod,m,=,b,mod,m,.,,(2),a,=,b,+,km,,,其中,k,是整数,.,19-3 同余,性质：,同余关系是等价关系。

模,m,等价类,: 在模,m,同余关系下的等价类. [,a,],m,, 简记作[,a,]Z,m,: Z在模,m,同余关系下的商集在Z,m,上定义加法和乘法如下:,,,a, b,,,,[,a,]+[,b,]=[,a,+,b,], [,a,]·[,b,]=[,ab,].,例6：,写出Z,4,的全部元素以及Z,4,上的加法表和乘法表.,解 Z,4,={[0],[1],[2],[3]}, 其中[,i,]={4,k,+,i,|,k,∈Z},,i,=0,1,2,3.,,[0],,[1],,[2],,[3],[0] [1] [2] [3],+,[0] [1] [2] [3],,[1] [2] [3] [0],,[2] [3] [0] [1],,[3] [0] [1] [2],,[0],,[1],,[2],,[3],[0] [1] [2] [3],·,[0] [0] [0] [0],,[0] [1] [2] [3],,[0] [2] [0] [2],,[0] [3] [2] [1],19-3 同余,例7,： 3,455,的个位数是多少?,解：设3,455,的个位数为,x,，则3,455,≡,x,(mod10).,由3,4,≡1(mod 10), 有 3,455,=3,4,113+3,≡3,3,≡7(mod 10),,,故3,455,的个位数是7.,19-3 同余,模,m,逆,,定义,5,,如果,ab,≡1(mod,m,),,则称,b,是,a,的,模,m,逆元,,,,,记作,a,,1,(mod,m,),或,a,,1,.,,a,,1,(mod,m,),是方程,ax,≡1(mod,m,),的解,.,,性质：,,,当,a,与,m,互素时,,,方程,x,,a,-1,(mod,m,),有唯一解,,即：,ax,–,km,= 1,,,当,a,与,m,不互素时,,,此方程无,解。

一个数关于某一个模,m,的乘法逆元不一定存在如,2,关于模,14,的乘法逆元不存在，因为,2,与,14,不互素,,扩展的Euclid算法,求乘法逆元：,,先用Euclid算法求得gcd(,a,,,n,) = 1,,从1开始逆推，直到得到1 =,ax,–,kn,,则,x,为,a,关于模,n,的乘法逆元,,,例8,：求5关于模14的乘法逆元,,辗转相除：14 = 5  2 + 4 5 = 4 + 1,,逆推：1 = 5 - 4 = 5 - (14 - 5  2) = 5  3 - 14,,因此，5关于模14的乘法逆元为3扩展的Euclid算法,例9,：求10关于模17的乘法逆元,,17 = 10 + 7,,10 = 7 + 3,,7 = 3,,2 + 1,,1 = 7 - 3,,2,,= 7 - (10 – 7),,2,,= 7,,3 - 10,,2,,= (17 – 10),,3 - 10,,2,,= 17,,3 - 10,,5,,= 17,,3 - 17,,10 + 17,,10 - 10,,5,,= 10,,12 - 17,,7,,所以10关于模17的乘法逆元为12,19-4 应用,伪随机数产生,,随机数：,随机变量的观察值,,伪随机数,,(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,<,m,, 用递推公式产生伪随机数序列:,x,n,=(,ax,n,,1,+,c,) mod,m,,,n,=1,2,…,,取,u,n,=,x,n,/,m,,,n,=1,2,…,,作为,U,(0,1)伪随机数.,19-4 应用,线性同余法产生的序列的质量取决于,m,,,a,和,c,. 例如,,m,=8,,a,=3,,c,=1,,x,0,=2, 得到7,6,3,2,7,6,…,周期为4,,m,=8,,a,=5,,c,=1,,x,0,=2, 得到3,0,1,6,7,4,5,2,3,0,1,…, 周期为8.,,a,=0, 得到,c,,,c,,,c,,…,,a,=1, 得到,x,0,+,c,,,x,0,+2,c,,,x,0,+3,c,,…,,,乘同余法:,,c,=0(,x,0≠0)的线性同余法, 即,,x,n,=,ax,n,,1,mod,m,,,n,=1,2,….,,最常用的均匀伪随机数发生器:,m,=2,31,,1,,a,=7,5,的乘同余法,,,它的周期是2,31,,2。

密码学,恺撒(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.,加密算法,线性同余加密算法,,,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,.,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,是保密的.,。