1、初等数论v主要内容主要内容素数素数最大条约数与最小公倍数最大条约数与最小公倍数同余同余在计算机科学中应用在计算机科学中应用1/2219.1 素数1.整除整除定义定义1：设设a,b是两个整数，且是两个整数，且a0，若存在整数若存在整数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
2、.3）若）若 a|b，那么对于全部整数，那么对于全部整数 m0都有都有 a|mb.2/2219.1 素数2.素数素数定义定义2：大于大于 1 1 且只能被且只能被 1 1 和本身整除正整数称为和本身整除正整数称为素数素数（质数质数）。大于）。大于 1 1 又不是素数正整数称为又不是素数正整数称为合数合数。算术基本定理：算术基本定理：每个正整数都能够唯一地表示为素数乘积，每个正整数都能够唯一地表示为素数乘积，其中素数因子从小到大依次出现，即其中素数因子从小到大依次出现，即例例1：100,641,999素因子分解素因子分解为：为：100=2255=2252 641=641 999=33337=33
3、373/2219.1 素数定理定理 2：假如假如n是合数，那么是合数，那么n必有一个小于或等于必有一个小于或等于 素因素因子。子。证：假如证：假如n是合数，它有一个因子是合数，它有一个因子a，使得使得1 a n，于是于是 ，这么，这么 ，这个因子或是素，这个因子或是素 数，或是有素因子。不论哪种情况，数，或是有素因子。不论哪种情况，n都有小于或等于都有小于或等于 素因子素因子例例2：证实：证实101是素数。是素数。证实思绪：证实思绪：101不含有不超出不含有不超出 素因子。素因子。4/2219.1 素数定理定理 3：有没有穷多个素数。：有没有穷多个素数。梅森数梅森数(Marin Mersenn
4、e):2p 1,其中其中p为素数。为素数。当当n是合数时是合数时,2n 1一定是合数一定是合数,2ab 1=(2a 1)(2a(b 1)+2a(b 2)+2a+1).梅森数可能是素数梅森数可能是素数,也可能是合数也可能是合数:22 1=3,23 1=7,25 1=31,27 1=127都是素数都是素数,而而211 1=2047=2389是合数是合数.到年找到最大梅森素数是到年找到最大梅森素数是213466917 1,有有4百万位百万位.5/2219.2 最大条约数和最小公倍数vd是是a与与b公因子公因子(条约数条约数):d|a且且d|bvm是是a与与b公倍数公倍数:a|m且且b|m定义定义3：
5、设设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.6/2219.2 最大条约数和最小公倍数定理定理4：(1)若若a|m,b|m,则则 lcm(a,b)|m.(2)若若d|a,d|b,则则
6、d|gcd(a,b).证证(1)记记M=lcm(a,b),设设m=qM+r,0rD,注意到注意到d|a,D|a,由由(1),得得m|a.同理同理,m|b.即即,m是是a和和b公因子公因子,与与D是是a和和b最大条约数矛盾最大条约数矛盾.7/2219.2 最大条约数和最小公倍数利用整数素因子分解利用整数素因子分解,求最大条约数和最小公倍数求最大条约数和最小公倍数.设设 其其中中p1,p2,pk是是不不一一样样素素数数,r1,r2,rk,s1,s2,sk是非负是非负整数整数.则则 gcd(a,b)=lcm(a,b)=例例4 求求150和和220最大条约数和最小公倍数最大条约数和最小公倍数.解解 1
7、50=2352,168=2337.gcd(150,168)=21315070=6,lcm(150,168)=23315271=4200.8/22 欧几里得算法-辗转相除法除法算法除法算法:a=qb+r,0r|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,由性质可得由性
8、质可得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公因子公因子.9/22 欧几里得算法-辗转相除法v最大公因数求法：最大公因数求法：辗转相除法辗转相除法例例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)=gc
9、d(b,r)这里，这里，gcd(36,15)=gcd(6,15)=gcd(6,3)=310/22 欧几里得算法-辗转相除法int gcd(int x，int y)int g;if(x 0)x=-x;if(y 0)g=x；x=y%x;y=g;return g;v试跟踪求试跟踪求gcd(36,15)时，时，变量值改变：变量值改变：y x gC C语言代码：语言代码：11/22 19-3 同余定义定义4：设设m是正整数是正整数,a和和b是整数是整数.假如假如m|a b,则称则称a模模m同余于同余于b,或或a与与b模模m同余同余,记作记作ab(mod m).假如假如a与与b模模m不一样余不一样余,则记
10、作则记作a b(mod m).比如比如,153(mod 4),160(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是整数是整数.12/22 19-3 同余性质：性质：同余关系是等价关系。同余关系是等价关系。模模m等价类等价类:在模在模m同余关系下等价类同余关系下等价类.am,简记作简记作a。Zm:Z在模在模m同余关系下商集。同余关系下商集。在在Zm上定义加法和乘法以下上定义加法和乘法以下:a,b,a+b=a+b,ab=ab.例例6：写出
11、写出Z4全部元素以及全部元素以及Z4上加法表和乘法表上加法表和乘法表.解解 Z4=0,1,2,3,其中其中i=4k+i|kZ,i=0,1,2,3.0123 0 1 2 3+0 1 2 31 2 3 02 3 0 13 0 1 2 0123 0 1 2 30 0 0 00 1 2 30 2 0 20 3 2 113/22 19-3 同余例例7：3455个位数是多少个位数是多少?解：设解：设3455个位数为个位数为x，则，则3455x(mod10).由由341(mod 10),有有 3455=34 113+3337(mod 10),故故3455个位数是个位数是7.14/22 19-3 同余 模模m
12、逆逆定义定义5 假如假如ab1(mod m),则称则称b是是a模模m逆元逆元,记作记作a 1(mod m)或或a 1.a 1(mod m)是方程是方程ax1(mod m)解解.性质：性质：当当a与与m互素时互素时,方程方程 x a-1(mod m)有唯一解有唯一解 即：即：ax km=1 当当a与与m不互素时不互素时,此方程无此方程无解。解。一个数关于某一个模一个数关于某一个模m乘法逆元不一定存在。乘法逆元不一定存在。如如 2关于模关于模14乘法逆元不存在，因为乘法逆元不存在，因为2与与14不互不互素素15/22扩展Euclid算法v求乘法逆元：求乘法逆元：先用先用Euclid算法求得算法求得
13、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。16/22扩展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 1
14、0-10 5 =10 12-17 7 所以所以10关于模关于模17乘法逆元为乘法逆元为1217/2219-4 应用v 伪随机数产生伪随机数产生随机数：随机数：随机变量观察值随机变量观察值伪随机数伪随机数 (0,1)上均匀分布上均匀分布U(0,1):a(0a1),P0Xa=a 线性同余法线性同余法 选择选择4个非负整数个非负整数:模数模数m,乘数乘数a,常数常数c和种子数和种子数x0,其其中中2am,0cm,0 x0m,用递推公式产生伪随机数序用递推公式产生伪随机数序列列:xn=(axn 1+c)mod m,n=1,2,取取 un=xn/m,n=1,2,作为作为U(0,1)伪随机数伪随机数.18
15、/2219-4 应用线性同余法产生序列质量取决于线性同余法产生序列质量取决于m,a和和c.比如比如m=8,a=3,c=1,x0=2,得到得到7,6,3,2,7,6,周期为周期为4 m=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(x00)线性同余法线性同余法,即即 xn=axn 1 mod m,n=1,2,.最惯用均匀伪随机数发生器最惯用均匀伪随机数发生器:m=231 1,a=75乘同余法乘同余法,它周期是它周期是231 2。19/22密码
16、学恺撒恺撒(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是一取定整数是一取定整数,
17、这里取这里取k=3.20/22加密算法线性同余加密算法线性同余加密算法 E(i)=(ai+b)mod 26,i=0,1,25,其中其中a与与26互素互素.维吉利亚维吉利亚(Vigenere)密码密码把明文分成若干段把明文分成若干段,每一段有每一段有n个数字个数字,密钥密钥k=k1k2kn,加密算法加密算法 E(i1i2in)=c1c2cn,其中其中cj=(ij+kj)mod 26,ij=0,1,25,j=1,2,n.21/22RSA公钥密码 私钥密码私钥密码:加密密钥和解密密钥都必须严格保密加密密钥和解密密钥都必须严格保密公钥密码公钥密码(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与与(n)互素互素,设设d=w 1(mod(n).将明文数字化将明文数字化,分成若干段分成若干段,每一个明文段每一个明文段mn.加密算法加密算法 c=E(m)=mwmod n,解密算法解密算法 D(c)=cdmod n,其中加密密钥其中加密密钥w和和n是公开是公开,而而p,q,(n)和和d是保密是保密.22/22
