離散數(shù)學：第十九章初等數(shù)論

1、1主要內(nèi)容主要內(nèi)容l 素數(shù)素數(shù)l 最大公約數(shù)與最小公倍數(shù)最大公約數(shù)與最小公倍數(shù)l 同余同余l(xiāng) 一次同余方程一次同余方程l 歐拉定理與費馬小定理歐拉定理與費馬小定理l 初等數(shù)論在計算機科學技術中的幾個應用初等數(shù)論在計算機科學技術中的幾個應用第六部分第六部分 初等數(shù)論初等數(shù)論2第十九章第十九章 初等數(shù)論初等數(shù)論 主要內(nèi)容主要內(nèi)容l 素數(shù)素數(shù)l 最大公約數(shù)與最小公倍數(shù)最大公約數(shù)與最小公倍數(shù)l 同余同余l(xiāng) 一次同余方程一次同余方程l 歐拉定理與費馬小定理歐拉定理與費馬小定理l 初等數(shù)論在計算機科學技術中的幾個應用初等數(shù)論在計算機科學技術中的幾個應用319.1 素數(shù)素數(shù)今后只考慮正整數(shù)的正因子今后只考慮

2、正整數(shù)的正因子.平凡因子平凡因子 : 1 和自身和自身真因子真因子 : 除除 1 和自身之外的因子和自身之外的因子例如例如, 2, 3 是是 6 的真因子的真因子設設a, b是兩個整數(shù)，且是兩個整數(shù)，且b0. 如果存在整數(shù)如果存在整數(shù)c 使使 a=bc，則，則稱稱a 被被b 整除整除，或，或 b 整除整除a，記作，記作 b|a. 此時此時, 又稱又稱 a 是是b 的的倍數(shù)倍數(shù)，b是是a 的的因子因子. 把把 b 不整除不整除 a 記作記作 b a.例如例如, 6有有8個因子個因子1, 2, 3和和6.4整除的性質(zhì)整除的性質(zhì)性質(zhì)性質(zhì)19.1 若若a |b且且a |c, 則則 x, y, 有有a

3、| xb+yc.性質(zhì)性質(zhì)19.2 若若a |b且且b |c, 則則a |c.性質(zhì)性質(zhì)19.3 設設 m0, 則則 a |b 當且僅當當且僅當 ma | mb.性質(zhì)性質(zhì)19.4 若若a | b且且b | a, 則則a=b.性質(zhì)性質(zhì)19.5 若若a | b且且b0, 則則|a|b|. 帶余除法帶余除法: a=qb+r, 0r 1, p是素數(shù)且是素數(shù)且d | p, 則則d=p.性質(zhì)性質(zhì)19.7 設設p是素數(shù)且是素數(shù)且p | ab, 則必有則必有p | a 或者或者 p | b. 設設p是素數(shù)且是素數(shù)且p | a1a2ak, 則必存在則必存在1ik, 使得使得p| ai. 注意注意:當當d不是素數(shù)時不

4、是素數(shù)時,d | ab不一定能推出不一定能推出d | a或或d | b. 性質(zhì)性質(zhì)19.8 a1是合數(shù)當且僅當是合數(shù)當且僅當a=bc, 其中其中1ba, 1c1, 則則 a= , 其中其中p1,p2,pk是不相同的素數(shù)是不相同的素數(shù), r1,r2,rk是正整數(shù)是正整數(shù), 并且在并且在不計順序的情況下不計順序的情況下, 該表示是惟一的該表示是惟一的. 該表達式稱作整數(shù)該表達式稱作整數(shù) a 的的素因子分解素因子分解. 例如例如 30=235, 117=3213, 1024=210 推論推論 設設a= , 其中其中 p1, p2,pk 是不相同的素數(shù)是不相同的素數(shù), r1,r2,rk是正整數(shù)是正整數(shù)

5、, 則正整數(shù)則正整數(shù)d為為a的因子的充分必要條件的因子的充分必要條件是是d= , 其中其中0siri, i=1,2,k.krkrrppp2121krkrrppp2121kskssppp21217例題例題例例1 21560有多少個正因子有多少個正因子?解解 21560=2357211由推論由推論, 21560的正因子的個數(shù)為的正因子的個數(shù)為4232=48.例例2 10!的二進制表示中從最低位數(shù)起有多少個連續(xù)的的二進制表示中從最低位數(shù)起有多少個連續(xù)的0?解解 2, 3, 4=22, 5, 6=23, 7, 8=23, 9=32, 10=25.得得 10!=2834527,故故10!的二進制表示中從

6、最低位數(shù)起有的二進制表示中從最低位數(shù)起有8 8個連續(xù)的個連續(xù)的0.8素數(shù)的分布素數(shù)的分布梅森數(shù)梅森數(shù)(Marin Mersenne): 2p 1, 其中其中p為素數(shù)為素數(shù) 當當n是合數(shù)時是合數(shù)時, 2n 1一定是合數(shù)一定是合數(shù), 2ab 1=(2a 1)(2a(b 1)+2a(b 2)+2a+1).梅森數(shù)可能是素數(shù)梅森數(shù)可能是素數(shù), 也可能是合數(shù)也可能是合數(shù): 22 1=3, 23 1=7, 25 1=31, 27 1=127都是素數(shù)都是素數(shù), 而而211 1=2047=2389是合數(shù)是合數(shù).到到2002年找到的最大梅森素數(shù)是年找到的最大梅森素數(shù)是213466917 1, 有有4百萬位百萬位.

7、 定理定理19.2 有無窮多個素數(shù)有無窮多個素數(shù).證證 用反證法用反證法. 假設只有有窮多個素數(shù)假設只有有窮多個素數(shù), 設為設為p1,p2,pn,令令m=p1p2pn+1. 顯然顯然, pi m, 1in. 因此因此, 要么要么m本身本身是素數(shù)，要么存在大于是素數(shù)，要么存在大于pn的素數(shù)整除的素數(shù)整除m, 矛盾矛盾.9素數(shù)的分布素數(shù)的分布( (續(xù)續(xù)) ) (n): 小于等于小于等于n的素數(shù)個數(shù)的素數(shù)個數(shù). 例如例如 (0)= (1)=0, (2)=1, (3)= (4)=2, (5)=3. 168 1229 9592 78498 664579 145 1086 8686 72382 62042

8、11.159 1.132 1.104 1.085 1.071 (n)n/ln n (n)n/ln n 103 104 105 106 107n定理定理19.3 (素數(shù)定理素數(shù)定理) 1ln/)(limnnnn 10素數(shù)測試素數(shù)測試aa定理定理11.4 如果如果a是合數(shù)是合數(shù), 則則a必有小于等于必有小于等于 的真因子的真因子.證證 由性質(zhì)由性質(zhì)19.8, a=bc, 其中其中1ba, 1c( )2=a, 矛盾矛盾.推論推論 如果如果a是合數(shù)是合數(shù), 則則a必有小于等于必有小于等于 的素因子的素因子.證證 由定理由定理, a有小于等于有小于等于 的真因子的真因子b. 如果如果b是素數(shù)是素數(shù), 則

9、結論成立則結論成立. 如果如果b是合數(shù)是合數(shù), 由性質(zhì)由性質(zhì)19.9和性質(zhì)和性質(zhì)19.5, b有有素因子素因子pb . 根據(jù)性質(zhì)根據(jù)性質(zhì)11.2, p也是也是a 的因子的因子, 結論也結論也成立成立.aaaa11157161例例3 判斷判斷157和和161是否是素數(shù)是否是素數(shù).解解 , 都小于都小于13, 小于小于13的素數(shù)有的素數(shù)有: 2, 3, 5, 7, 11.檢查結果如下檢查結果如下: 2 157, 3 157, 5 157, 7 157, 11 157 結論結論: 157是素數(shù)是素數(shù). 2 161, 3 161, 5 161, 7|161（161=723）結論：結論：161是合數(shù)是合

10、數(shù).例題例題12 1 2 3 4 5 6 7 8 9 10 1 2 3 4 5 6 7 8 9 10 1 2 3 4 5 6 7 8 9 10 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79

11、80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82

12、 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 8

13、5 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87

14、88 89 90 91 92 93 94 95 96 97 98 99 100 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90

15、 91 92 93 94 95 96 97 98 99 100埃拉托斯特尼埃拉托斯特尼(Eratosthene)篩法篩法13d是是a與與b的的公因子公因子(公約數(shù)公約數(shù)): d |a且且d |bm是是a與與b的的公倍數(shù)公倍數(shù): a | m且且b | m定義定義19.3 設設a和和b是兩個不全為是兩個不全為0的整數(shù)的整數(shù), 稱稱a與與b的公因子中的公因子中最大的為最大的為a與與b的的最大公因子最大公因子, 或或最大公約數(shù)最大公約數(shù), 記作記作gcd(a,b). 設設a和和b是兩個非零整數(shù)是兩個非零整數(shù), 稱稱a與與b最小的正公倍數(shù)為最小的正公倍數(shù)為a與與b的的最小公倍數(shù)最小公倍數(shù), 記作記作lc

16、m(a,b). 例如例如 gcd(12,18)=6, lcm(12,18)=36. 對任意的正整數(shù)對任意的正整數(shù)a, gcd(0,a)=a, gcd(1,a)=1, lcm(1,a)=a. 19.2 最大公約數(shù)與最小公倍數(shù)最大公約數(shù)與最小公倍數(shù)14定理定理19.5 (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, 0rD, 注意到注意到d |a, D|a, 由由(1), 得得m |a. 同理同理, m |b. 即即, m是是a和和b的公因子的公因子

17、, 與與D是是a和和b的最大公約數(shù)矛盾的最大公約數(shù)矛盾. 最大公約數(shù)與最小公倍數(shù)的性質(zhì)最大公約數(shù)與最小公倍數(shù)的性質(zhì)15最大公約數(shù)與最小公倍數(shù)最大公約數(shù)與最小公倍數(shù)(續(xù)續(xù))例例4 求求150和和220的最大公約數(shù)和最小公倍數(shù)的最大公約數(shù)和最小公倍數(shù).利用整數(shù)的素因子分解利用整數(shù)的素因子分解, 求最大公約數(shù)和最小公倍數(shù)求最大公約數(shù)和最小公倍數(shù). 設設 其中其中p1,p2,pk是不同的素數(shù)是不同的素數(shù), r1,r2,rk,s1,s2,sk是非負是非負整數(shù)整數(shù). 則則 gcd(a,b)= lcm(a,b)=,2121krkrrpppa ,2121ksksspppb ,),min(),min(2),mi

18、n(12211kksrksrsrppp),max(),max(2),max(12211kksrksrsrppp解解 150=2352, 168=2337. gcd(150,168)=21315070=6, lcm(150,168)=23315271=4200. 16輾轉(zhuǎn)相除法輾轉(zhuǎn)相除法定理定理19.6 設設a=qb+r, 其中其中a, b, q, r 都是整數(shù)都是整數(shù), 則則 gcd(a,b) = gcd(b,r).證證 只需證只需證a與與b和和b與與r有相同的公因子有相同的公因子. 設設d是是a與與b的公因的公因子子, 即即d |a且且d |b. 注意到注意到, r=a qb, 由性質(zhì)由性質(zhì)

19、19.1, 有有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的公因子的公因子. 17輾轉(zhuǎn)相除法輾轉(zhuǎn)相除法歐幾里得歐幾里得(Euclid)算法算法輾轉(zhuǎn)相除法輾轉(zhuǎn)相除法設整數(shù)設整數(shù)a, b, 且且b0, 求求gcd(a,b).做帶余除法做帶余除法 a=qb+r, 0r0, 再對再對b和和r做帶余除法做帶余除法 b=q r+r , 0r 0是是a和和b的公因子的

20、公因子, 有有 d |xa+yb, 即即 d |1. 從而從而 d=1, 得證得證a和和b互素互素. 定義定義19.2 如果如果gcd(a,b)=1, 則稱則稱a和和b互素互素. 如果如果a1,a2,an中中的的任意兩個都互素任意兩個都互素, 則稱它們則稱它們兩兩互素兩兩互素.例如例如, 8和和15互素互素,而而8和和12不互素不互素. .4, 9, 11, 35兩兩互素兩兩互素.21例題例題例例6 設設a |c, b |c, 且且a與與b互素互素, 則則ab |c.證證 根據(jù)定理根據(jù)定理19.8, 存在整數(shù)存在整數(shù)x,y,使使xa+yb=1. 兩邊同乘以兩邊同乘以c,得得cxa+cyb=c.

21、 又由又由a |xa和和b |c, 可得可得ab |cxa. 同理同理, ab |cyb. 于是于是, 有有ab |cxa+cyb, 即即ab|c. 2219.3 同余同余定義定義19.3 設設m是正整數(shù)是正整數(shù), a和和b是整數(shù)是整數(shù). 如果如果m|a b, 則稱則稱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同余的充分必要條件同

22、余的充分必要條件:(1) a mod m = b mod m.(2) a=b+km, 其中其中k是整數(shù)是整數(shù).23同余的性質(zhì)同余的性質(zhì)性質(zhì)性質(zhì)19.10 同余關系是等價關系同余關系是等價關系, 即同余關系具有即同余關系具有 自反性自反性. aa(mod m) 傳遞性傳遞性. ab(mod m)bc(mod m) ac(mod m). 對稱性對稱性. ab(mod m) ba(mod m). 縮寫縮寫 a1a2ak (mod m). 性質(zhì)性質(zhì)19.11 模算術運算模算術運算 若若ab(mod m), cd(mod m), 則則 acbd(mod m), acbd(mod m), akbk(mod

23、 m), 其中其中k是非負整數(shù)是非負整數(shù). 性質(zhì)性質(zhì)19.12 設設d1, d | m, 則則ab(mod m) ab(mod d).性質(zhì)性質(zhì)19.13 設設d1, 則則ab(mod m) dadb(mod dm).性質(zhì)性質(zhì)19.14 設設c,m互素互素, 則則ab(mod m) cacb(mod m).24模模m等價類等價類模模m等價類等價類: 在模在模m同余關系下的等價類同余關系下的等價類. am, 簡記作簡記作a. Zm: Z在模在模m同余關系下的商集同余關系下的商集在在Zm上定義加法和乘法如下上定義加法和乘法如下: a, b, a+b=a+b, ab=ab. 例例7 寫出寫出Z4的全部

24、元素以及的全部元素以及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 125例例8 3455的個位數(shù)是多少的個位數(shù)是多少?解解 設設3455的個位數(shù)為的個位數(shù)為x,則則3455x(mod10).由由341(mod 10), 有有 3455=34 113+3337(mod 10),故故3455的個位數(shù)是的個位數(shù)是7.例例9 日期的星期數(shù)日期的星期數(shù) y年年m月

25、月d日星期數(shù)的計算公式日星期數(shù)的計算公式:其中其中M=(m3)mod12 +1, Y=y M/11 =100C+XY年年M月月:3月月下一年下一年2月月, C:Y年的世紀數(shù)年的世紀數(shù) )7(mod12/2/ )7/(224/4/dmMMMCCXXw 例題例題26例題例題 )7(mod6112/82/ )7/88(821924/194/4949 w )7(mod31512/62/ )7/66(621924/194/4545 w例例9 (續(xù)續(xù)) 例如例如, 中華人民共和國成立日中華人民共和國成立日1949年年10月月1日日, C=19, X=49, M=8, d=1,是星期六是星期六.中國人民抗日

26、戰(zhàn)爭勝利日中國人民抗日戰(zhàn)爭勝利日1945年年8月月15日日, C=19, X=45, M=6, d=15,是星期三是星期三. 2719.4 一次同余方程一次同余方程定理定理19.9 方程方程axc(mod m)有解的充要條件是有解的充要條件是gcd(a,m)|c.證證 充分性充分性. 記記d=gcd(a,m), a =da1, m =dm1, c =dc1, 其中其中a1與與m1互素互素. 由定理由定理11.8, 存在存在x1和和y1使得使得a1x1+m1y1=1. 令令x=c1x1, y=c1y1, 得得a1x+m1y=c1. 等式兩邊同乘等式兩邊同乘d, 得得ax+my=c. 所以所以,

27、axc(mod m). 必要性必要性. 設設x是方程的解是方程的解, 則存在則存在y使得使得ax+my=c. 由性質(zhì)由性質(zhì)19.1, 有有d | c. 一次同余方程一次同余方程: axc(mod m), 其中其中m0.一次同余方程的一次同余方程的解解: 使方程成立的整數(shù)使方程成立的整數(shù)例如例如, 2x0(mod 4)的解為的解為x0(mod 2), 2x1(mod 4)無解無解28例題例題例例10 解一次同余方程解一次同余方程 6x3(mod 9).解解 gcd(6,9)=3 | 3, 方程有解方程有解.取模取模9等價類的代表等價類的代表x= 4, 3, 2, 1, 0, 1, 2, 3, 4

28、, 檢查它檢查它們是否是方程的解們是否是方程的解, 計算結果如下計算結果如下: 6( 4)6( 1)623(mod 9), 6( 3)60630(mod 9), 6( 2)61646(mod 9),得方程的解得方程的解 x= 4, 1, 2(mod 9), 方程的最小正整數(shù)解是方程的最小正整數(shù)解是2. 29模模m逆逆定理定理19.10 (1) a的模的模m逆存在的充要條件是逆存在的充要條件是a與與m互素互素.(2)設設a與與m互素互素, 則在模則在模m下下a的模的模m逆是惟一的逆是惟一的.證證 (1) 這是定理這是定理19.9的直接推論的直接推論.(2) 設設ab11(mod m), ab21

29、(mod m).得得a(b1 b2)0(mod m). 由由a與與m互素互素, b1 b20(mod m),得證得證b1b2(mod m). 定義定義19.4 如果如果ab1(mod m), 則稱則稱b是是a的的模模m逆逆, 記作記作a 1(mod m)或或a 1.a 1(mod m)是方程是方程ax1(mod m)的解的解.30例題例題例例11 求求5的模的模7逆逆.解解 5與與7互素互素, 故故5的模的模7逆存在逆存在.方法方法1. 解方程解方程5x1(mod7).檢查檢查x= 3, 2, 1,0,1,2,3, 得到得到 5 13(mod7).方法方法2. 做輾轉(zhuǎn)相除法做輾轉(zhuǎn)相除法, 求得

30、整數(shù)求得整數(shù)b,k使得使得 5b+7k=1, 則則b是是5的模的模7逆逆.計算如下計算如下: 7=5+2, 5=22+1.回代回代 1=5 22=5 2(7 5)= 35 27,得得 5 13(mod7).方法方法3. 直接觀察直接觀察5 3=15, 15 1(mod 7), 得得 5 13(mod7).31歐拉函數(shù)歐拉函數(shù) (n): 0, 1, n 1中與中與n互素的數(shù)的個數(shù)互素的數(shù)的個數(shù) 例如例如 (1)= (2)=1, (3)= (4)=2.當當n為素數(shù)時為素數(shù)時 (n)=n 1; 當當n為合數(shù)時為合數(shù)時 (n)n 1. 定理定理19.11(歐拉定理歐拉定理) 設設a與與n互素互素, 則

31、則 a (n)1(mod n). 19.5 歐拉定理和費馬小定理歐拉定理和費馬小定理 32歐拉定理的證明歐拉定理的證明證證 設設r1, r2, r (n)是是0, 1, n 1中與中與n互素的互素的 (n)個數(shù)個數(shù). 由于由于a與與n互素互素, 對每一個對每一個1i (n), ari也與也與n互素互素, 故存故存在在1 (i) (n) 使得使得 arir (i)(mod n). 是是1,2, (n)上的映射上的映射. 要證要證 是一個單射是一個單射.a的模的模n逆逆a 1存在存在, a 1也與也與n互素互素. 假設假設ij, (i)= (j), 則有則有ariarj(mod n). 兩邊同乘兩

32、邊同乘a 1, 得得rirj(mod n), 矛盾矛盾. 得證得證 是是1, 2,(n)上的單射上的單射, 當然也是當然也是1, 2, (n)上的上的雙射雙射. 從而從而,有有而而 與與n互素互素, 故故a (n)1(mod n). )(mod)(1)(1)(1)(nrarraniiniiniin )(1niir 33費馬費馬(Fermat)小定理小定理定理定理19.12(費馬小定理費馬小定理) 設設p是素數(shù)是素數(shù), a與與p互素互素, 則則 ap-11(mod p).另一種形式是另一種形式是, 設設p是素數(shù)是素數(shù), 則對任意的整數(shù)則對任意的整數(shù)a, apa(mod p). 費馬小定理提供了一

33、種不用因子分解就能斷定一個數(shù)是費馬小定理提供了一種不用因子分解就能斷定一個數(shù)是合數(shù)的新途徑合數(shù)的新途徑. 例如例如, 29 14 (mod 9), 可以斷定可以斷定9是合數(shù)是合數(shù). 3419.6 19.6 初等數(shù)論在計算機科初等數(shù)論在計算機科學技術中的幾個應用學技術中的幾個應用主要內(nèi)容主要內(nèi)容l 產(chǎn)生均勻偽隨機數(shù)的方法產(chǎn)生均勻偽隨機數(shù)的方法l 密碼學密碼學35產(chǎn)生均勻偽隨機數(shù)的方法產(chǎn)生均勻偽隨機數(shù)的方法隨機數(shù)隨機數(shù):隨機變量的觀察值隨機變量的觀察值偽隨機數(shù)偽隨機數(shù)(0,1)上的均勻分布上的均勻分布U(0,1): a(0a1), P0Xa=a 線性同余法線性同余法 選擇選擇4個非負整數(shù)個非負整數(shù)

34、: 模數(shù)模數(shù)m, 乘數(shù)乘數(shù)a, 常數(shù)常數(shù)c和種子數(shù)和種子數(shù)x0, 其中其中2am, 0cm, 0 x0m, 用遞推公式產(chǎn)生偽隨機數(shù)序列用遞推公式產(chǎn)生偽隨機數(shù)序列: xn=(axn 1+c) mod m, n=1,2,取取 un=xn/m, n=1,2,作為作為U(0,1)偽隨機數(shù)偽隨機數(shù). 36線性同余法與乘同余法線性同余法與乘同余法線性同余法產(chǎn)生的序列的質(zhì)量取決于線性同余法產(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

35、,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,.最常用的均勻偽隨機數(shù)發(fā)生器最常用的均勻偽隨機數(shù)發(fā)生器:m=231 1, a=75的乘同余法的乘同余法,它的周期是它的周期是231 2.37密碼學密碼學愷撒愷撒(Caesar)密碼密碼加密方法加密方法: ABCDEFGH I J KLMNOPQRS TUVWXYZ DEFGH I JKLMNO PQRS TUVWXYZ ABC明文明文: SEE YOU TOMO

36、RROW密文密文: 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是一取定的整數(shù)是一取定的整數(shù), 這里取這里取k=3. 38加密算法加密算法線性同余加密算法線性同余加密算法 E(i)=(ai+b)mod 26, i=0, 1,25,其中其中a與與26互素互素. 維吉利亞維吉利亞(Vigene

37、re)密碼密碼把明文分成若干段把明文分成若干段, 每一段有每一段有n個數(shù)字個數(shù)字, 密鑰密鑰k=k1k2kn,加密算法加密算法 E(i1i2in)=c1c2cn,其中其中cj=(ij+kj)mod 26, ij=0,1,25, j=1, 2, n. 39RSA公鑰密碼公鑰密碼 私鑰密碼私鑰密碼:加密密鑰和解密密鑰都必須嚴格保密加密密鑰和解密密鑰都必須嚴格保密公鑰密碼公鑰密碼 (W.Diffie,M.Hellman,1976 ):加密密鑰公開加密密鑰公開,解密解密密鑰保密密鑰保密RSA公鑰密碼公鑰密碼(R. Rivest, A. Shamir, L. Adleeman,1978) 取取2個大素數(shù)

38、個大素數(shù)p和和q(pq), 記記n=pq, (n)=(p 1)(q 1). 選擇正選擇正整數(shù)整數(shù)w, w與與 (n)互素互素, 設設d=w 1(mod (n). 將明文數(shù)字化將明文數(shù)字化, 分成若干段分成若干段, 每一個明文段每一個明文段mn. 加密算法加密算法 c=E(m)=mwmod n,解密算法解密算法 D(c)=cdmod n,其中加密密鑰其中加密密鑰w和和n是公開的是公開的, 而而p,q, (n)和和d是保密的是保密的. 40解密算法正確性證明解密算法正確性證明要證要證m=cdmod n, 即即cdm(mod n), 亦即亦即mdwm(mod n).由由dw1(mod (n), 存在

39、存在k使得使得dw=k (n)+1. 有兩種可能有兩種可能:(1) m與與n互素互素. 由歐拉定理由歐拉定理m (n)1(mod n),得得 mdwmk (n)+1 m(mod n). (2) m與與n不互素不互素. 不妨設不妨設m=cp且且q不整除不整除m. 由費馬小定理由費馬小定理 mq 11(mod q).于是于是, mk (n)mk(p 1)(q 1)1k(p 1)1 (mod q).從而存在從而存在h使得使得 mk (n)=hq+1,兩邊同乘以兩邊同乘以m, 并注意到并注意到m=cp, mk (n)+1=hcpq+m=hcn+m,得證得證 mk (n)+1m(mod n),即即 md

40、wm(mod n). 41模冪乘運算模冪乘運算 )(mod)()(111022naaaarrbbbb)(mod110110nAAAarbrbbb模冪乘運算模冪乘運算ab(mod n)設設b=b0+b12+br 12r 1, 其中其中bi=0或或1, 于是于是令令 A0=a, Ai(Ai 1)2(mod n), i=1, 2,r 1, 則有則有42例題例題例例12 p=43,q=59, n=4359=2537, (n)=4258=2436, w=13. A, B, Z依次用依次用00, 01,25表示表示, 各占各占2位位. 設明文段設明文段m=2106, 即即VG, 密文密文c=210613m

41、od 2537.計算如下計算如下: 13=(1101)2, 即即13=1+22+23.A0=2106 431(mod 2537),A1( 431)2560(mod 2537),A25602 988(mod 2537),A3( 988)2 601(mod 2537),210613( 431)( 988)( 601)2321(mod 2537),得密文得密文c=2321. 43例題例題(續(xù)續(xù))設密文設密文c=0981. d=13 1937(mod 2436), 明文明文m=981937(mod 2537). 計算如下計算如下: 937=(1110101001)2, A0=981, A1981283

42、8(mod 2537), A28382 505, A3( 505)21325, A41325221, A5212441, A64412 868, A7( 868)2 65, A8( 65)2 849, A9( 849)2293, 9819379811325441( 65)( 849)293 704(mod 2537),得明文得明文m=0704, 即即HE. 44第十九章第十九章 習題課習題課主要內(nèi)容主要內(nèi)容l 素數(shù)與合數(shù)素數(shù)與合數(shù), 埃拉托斯特尼篩法埃拉托斯特尼篩法l 最大公約數(shù)與最小公倍數(shù)最大公約數(shù)與最小公倍數(shù), 輾轉(zhuǎn)相除法輾轉(zhuǎn)相除法l 同余同余, 模模m等價類及其運算等價類及其運算l 一次

43、同余方程及有解的充分必要條件一次同余方程及有解的充分必要條件l 歐拉定理與費馬小定理歐拉定理與費馬小定理l 產(chǎn)生均勻偽隨機數(shù)的方法產(chǎn)生均勻偽隨機數(shù)的方法l 密碼學密碼學45基本要求基本要求l 熟練掌握整除、素數(shù)、合數(shù)的概念及其性質(zhì)熟練掌握整除、素數(shù)、合數(shù)的概念及其性質(zhì), 掌握算術掌握算術基本定理基本定理, 能熟練地素因子分解能熟練地素因子分解, 會判斷素數(shù)會判斷素數(shù), 掌握埃拉掌握埃拉托斯特尼篩法托斯特尼篩法.l 熟練掌握最大公約數(shù)和最小公倍數(shù)的概念及其性質(zhì)熟練掌握最大公約數(shù)和最小公倍數(shù)的概念及其性質(zhì), 會求最大公約數(shù)和最小公倍數(shù)會求最大公約數(shù)和最小公倍數(shù), 掌握輾轉(zhuǎn)相除法掌握輾轉(zhuǎn)相除法.l 熟練掌握互素的概念及其性質(zhì)熟練掌握互素的概念及其性質(zhì).l 熟練掌握同余的概念及其性質(zhì)熟練掌握同余的概念及其性質(zhì)