1、,初等數(shù)論,主要內(nèi)容 素?cái)?shù) 最大公約數(shù)與最小公倍數(shù) 同余 在計(jì)算機(jī)科學(xué)中的應(yīng)用,19.1 素?cái)?shù),1. 整除 定義1：設(shè)a, b是兩個(gè)整數(shù)，且a0， 若存在整數(shù)c 使 b=ac，則稱b 被a 整除，或 a 整除b，記作 a|b. 此時(shí), 又稱 b 是a 的倍數(shù)，a是b 的因子. 把 a不整除 b 記作 a b.,性質(zhì)：令a，b，c為整數(shù)，有如下結(jié)論： 1）若a |b且a |c, 則 x, y, 有a | xb+yc. 2）若a |b且b |c, 則a |c. 3）若 a |b，那么對(duì)于所有整數(shù) m0都有 a | mb.,19.1 素?cái)?shù),2. 素?cái)?shù) 定義2：大于 1 且只能被 1 和自身整除的正整

2、數(shù)稱為素?cái)?shù)（質(zhì)數(shù)）。大于 1 又不是素?cái)?shù)的正整數(shù)稱為合數(shù)。,算術(shù)基本定理：每個(gè)正整數(shù)都可以唯一地表示為素?cái)?shù)的乘積，其中素?cái)?shù)因子從小到大依次出現(xiàn)，即 例1：100, 641, 999的素因子分解為： 100=2255=2252 641=641 999=33337=3337,19.1 素?cái)?shù),定理 2：如果n是合數(shù)，那么n必有一個(gè)小于或等于 的素因子。 證：如果n是合數(shù)，它有一個(gè)因子a，使得1 a n， 于是 ，這樣 ，這個(gè)因子或是素 數(shù)，或是有素因子。無論哪種情況，n都有小于或等于 的素因子,例2：證明101是素?cái)?shù)。 證明思路：101不含有不超過 的素因子。,19.1 素?cái)?shù),定理 3：有無窮多個(gè)素

3、數(shù)。,梅森數(shù)(Marin Mersenne): 2p1, 其中p為素?cái)?shù)。 當(dāng)n是合數(shù)時(shí), 2n1一定是合數(shù), 2ab1=(2a1)(2a(b1)+2a(b2)+2a+1). 梅森數(shù)可能是素?cái)?shù), 也可能是合數(shù): 221=3, 231=7, 251=31, 271=127都是素?cái)?shù), 而2111=2047=2389是合數(shù). 到2002年找到的最大梅森素?cái)?shù)是2134669171, 有4百萬位.,19.2 最大公約數(shù)和最小公倍數(shù),d是a與b的公因子(公約數(shù)): d |a且d |b m是a與b的公倍數(shù): a | m且b | m 定義3：設(shè)a和b是兩個(gè)不全為0的整數(shù), 稱a與b的公因子中 最大的為a與b的最

4、大公因子, 或最大公約數(shù), 記作gcd(a,b). 設(shè)a和b是兩個(gè)非零整數(shù), 稱a與b最小的正公倍數(shù)為a與b的 最小公倍數(shù), 記作lcm(a,b). 例3 gcd(12,18)=6, lcm(12,18)=36. 對(duì)任意的正整數(shù)a, gcd(0,a)=a, gcd(1,a)=1, lcm(1,a)=a.,19.2 最大公約數(shù)和最小公倍數(shù),定理4： (1) 若a | m, b | m, 則 lcm(a,b)| m. (2) 若d |a, d |b, 則d | gcd(a,b). 證 (1) 記M=lcm(a,b), 設(shè)m=qM+r, 0rD, 注意到d |a, D|a, 由(1), 得m |a.

5、 同理, m |b. 即, m是a和b的公因子, 與D是a和b的最大公約數(shù)矛盾.,19.2 最大公約數(shù)和最小公倍數(shù),利用整數(shù)的素因子分解, 求最大公約數(shù)和最小公倍數(shù). 設(shè) 其中p1,p2,pk是不同的素?cái)?shù), r1,r2,rk,s1,s2,sk是非負(fù) 整數(shù). 則 gcd(a,b)= lcm(a,b)=,例4 求150和220的最大公約數(shù)和最小公倍數(shù).,解 150=2352, 168=2337. gcd(150,168)=21315070=6, lcm(150,168)=23315271=4200.,歐幾里得算法-輾轉(zhuǎn)相除法,除法算法: a=qb+r, 0r |b|, 記余數(shù)r=a mod b 例

6、如, 20 mod 6=2, 13 mod 4=3, 10 mod 2=0,定理5： 設(shè)a=qb+r, 其中a, b, q, r 都是整數(shù), 則 gcd(a,b) = gcd(b,r). 證明：只需證a與b和b與r有相同的公因子. 設(shè)d是a與b的公因 子, 即d |a且d |b. 注意到, r=aqb, 由性質(zhì)可得d |r. 從而, d |b且d |r, 即d也是b與r的公因子. 反之一樣, 設(shè)d是b與r的公 因子, 即d |b且d |r. 注意到, a=qb+r, 故有d |a. 從而, d |a且d |b, 即d也是a與b的公因子.,歐幾里得算法-輾轉(zhuǎn)相除法,最大公因數(shù)的求法：輾轉(zhuǎn)相除法

7、例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,歐幾里得算法-輾轉(zhuǎn)相除法,int gcd(int x，int y) int g; if (x 0) g = x； x = y%x; y = g; return g; ,試跟蹤求gcd(36,15)時(shí)，變量值變化： y x g,C語言代碼：,19-3 同余

8、,定義4： 設(shè)m是正整數(shù), a和b是整數(shù). 如果m|ab, 則稱a模 m同余于b, 或a與b模m同余, 記作ab(mod m). 如果a與b模 m不同余, 則記作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是整數(shù).,19-3 同余,性質(zhì)：同余關(guān)系是等價(jià)關(guān)系。,模m等價(jià)類: 在模m同余關(guān)系下的等價(jià)類. am, 簡(jiǎn)記作a。 Zm: Z在模m同余關(guān)系下的商集。 在Zm上定義加法和乘法如下: a

9、, b, a+b=a+b, ab=ab.,例6：寫出Z4的全部元素以及Z4上的加法表和乘法表.,解 Z4=0,1,2,3, 其中i=4k+i |kZ, i=0,1,2,3.,19-3 同余,例7： 3455的個(gè)位數(shù)是多少?,解：設(shè)3455的個(gè)位數(shù)為x，則3455x(mod10).,由341(mod 10), 有 3455=34113+3337(mod 10), 故3455的個(gè)位數(shù)是7.,19-3 同余,模m逆 定義5 如果ab1(mod m), 則稱b是a的模m逆元, 記作a1(mod m)或a1. a1(mod m)是方程ax1(mod m)的解. 性質(zhì)： 當(dāng)a與m互素時(shí), 方程 x a-1

10、(mod m) 有唯一解 即：ax km = 1 當(dāng)a與m不互素時(shí), 此方程無解。 一個(gè)數(shù)關(guān)于某一個(gè)模m的乘法逆元不一定存在。 如 2關(guān)于模14的乘法逆元不存在，因?yàn)?與14不互素,擴(kuò)展的Euclid算法,求乘法逆元： 先用Euclid算法求得gcd(a, n) = 1 從1開始逆推，直到得到1 = ax kn 則x為a關(guān)于模n的乘法逆元 例8：求5關(guān)于模14的乘法逆元 輾轉(zhuǎn)相除：14 = 5 2 + 4 5 = 4 + 1 逆推：1 = 5 - 4 = 5 - (14 - 5 2) = 5 3 - 14 因此，5關(guān)于模14的乘法逆元為3。,擴(kuò)展的Euclid算法,例9：求10關(guān)于模17的乘法

11、逆元 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關(guān)于模17的乘法逆元為12,19-4 應(yīng)用,偽隨機(jī)數(shù)產(chǎn)生 隨機(jī)數(shù)：隨機(jī)變量的觀察值 偽隨機(jī)數(shù) (0,1)上的均勻分布U(0,1): a(0a1), P0Xa=a 線性同余法 選擇4個(gè)非負(fù)整數(shù): 模數(shù)m, 乘數(shù)a, 常數(shù)c和種子數(shù)x0, 其中2am, 0cm, 0 x0m, 用遞推

12、公式產(chǎn)生偽隨機(jī)數(shù)序列: xn=(axn1+c) mod m, n=1,2, 取 un=xn/m, n=1,2, 作為U(0,1)偽隨機(jī)數(shù).,19-4 應(yīng)用,線性同余法產(chǎn)生的序列的質(zhì)量取決于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=axn1 mod m, n=1,2,. 最常用的均勻偽隨機(jī)數(shù)發(fā)生器

13、:m=2311, a=75的乘同余法, 它的周期是2312。,密碼學(xué),愷撒(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)=(ik)mod 26, i=0, 1,25 其中密鑰k是一取定的整數(shù), 這里取k=3.,加密算法,線性同余加密算法 E(i)=(ai+b)mod 26, i=0, 1,25, 其中a與26互素. 維吉利亞(Vigenere)密碼 把明文分成若干段, 每一段有n個(gè)數(shù)字, 密鑰k=k1k2kn, 加密算法 E(i1i2in)=c1c2cn, 其中cj=(ij+kj)mod 26, ij=0,1,25, j=1, 2, n.,RSA公鑰密碼,私鑰密碼:加密密鑰和解密密鑰都必須嚴(yán)格保密 公鑰密碼 (W.Diffie,M.Hellman,1976 ):加密密鑰公開,解