1、1,主要內(nèi)容 素數(shù) 最大公約數(shù)與最小公倍數(shù) 同余 一次同余方程 歐拉定理與費馬小定理 初等數(shù)論在計算機(jī)科學(xué)技術(shù)中的幾個應(yīng)用,第六部分 初等數(shù)論,2,第十九章 初等數(shù)論,主要內(nèi)容 素數(shù) 最大公約數(shù)與最小公倍數(shù) 同余 一次同余方程 歐拉定理與費馬小定理 初等數(shù)論在計算機(jī)科學(xué)技術(shù)中的幾個應(yīng)用,3,19.1 素數(shù),今后只考慮正整數(shù)的正因子. 平凡因子 : 1 和自身 真因子 : 除 1 和自身之外的因子 例如, 2, 3 是 6 的真因子,設(shè)a, b是兩個整數(shù)，且b0. 如果存在整數(shù)c 使 a=bc，則 稱a 被b 整除，或 b 整除a，記作 b|a. 此時, 又稱 a 是b 的 倍數(shù)，b是a 的因子

2、. 把 b 不整除 a 記作 b a. 例如, 6有8個因子1, 2, 3和6.,4,整除的性質(zhì),性質(zhì)19.1 若a |b且a |c, 則 x, y, 有a | xb+yc. 性質(zhì)19.2 若a |b且b |c, 則a |c. 性質(zhì)19.3 設(shè) m0, 則 a |b 當(dāng)且僅當(dāng) ma | mb. 性質(zhì)19.4 若a | b且b | a, 則a=b. 性質(zhì)19.5 若a | b且b0, 則|a|b|.,帶余除法: a=qb+r, 0r |b|, 記余數(shù)r=a mod b 例如, 20 mod 6=2, 13 mod 4=3, 10 mod 2=0,b|a 當(dāng)且僅當(dāng) a mod b =0,5,素數(shù)與

3、合數(shù),性質(zhì)19.6 如果d1, p是素數(shù)且d | p, 則d=p. 性質(zhì)19.7 設(shè)p是素數(shù)且p | ab, 則必有p | a 或者 p | b. 設(shè)p是素數(shù)且p | a1a2ak, 則必存在1ik, 使得p| ai. 注意:當(dāng)d不是素數(shù)時,d | ab不一定能推出d | a或d | b. 性質(zhì)19.8 a1是合數(shù)當(dāng)且僅當(dāng)a=bc, 其中1ba, 1ca. 性質(zhì)19.9 合數(shù)必有素數(shù)因子.,定義19.1 大于 1 且只能被 1 和自身整除的正整數(shù)稱為素數(shù)或質(zhì)數(shù). 大于 1 且不是素數(shù)的正整數(shù)稱為合數(shù). 例如, 2,3,5,7,11是素數(shù), 4,6,8,9是合數(shù).,6,算術(shù)基本定理,定理19.1

4、(算術(shù)基本定理) 設(shè)a1, 則 a= , 其中p1,p2,pk是不相同的素數(shù), r1,r2,rk是正整數(shù), 并且在不計順序的情況下, 該表示是惟一的. 該表達(dá)式稱作整數(shù) a 的素因子分解. 例如 30=235, 117=3213, 1024=210 推論 設(shè)a= , 其中 p1, p2,pk 是不相同的素數(shù), r1,r2,rk是正整數(shù), 則正整數(shù)d為a的因子的充分必要條件 是d= , 其中0siri, i=1,2,k.,7,例題,例1 21560有多少個正因子?,解 21560=2357211 由推論, 21560的正因子的個數(shù)為4232=48.,例2 10!的二進(jìn)制表示中從最低位數(shù)起有多少個

5、連續(xù)的0?,解 2, 3, 4=22, 5, 6=23, 7, 8=23, 9=32, 10=25. 得 10!=2834527,故10!的二進(jìn)制表示中從最低位數(shù)起有8個連續(xù)的0.,8,素數(shù)的分布,梅森數(shù)(Marin Mersenne): 2p1, 其中p為素數(shù) 當(dāng)n是合數(shù)時, 2n1一定是合數(shù), 2ab1=(2a1)(2a(b1)+2a(b2)+2a+1). 梅森數(shù)可能是素數(shù), 也可能是合數(shù): 221=3, 231=7, 251=31, 271=127都是素數(shù), 而2111=2047=2389是合數(shù). 到2002年找到的最大梅森素數(shù)是2134669171, 有4百萬位.,定理19.2 有無窮

6、多個素數(shù). 證 用反證法. 假設(shè)只有有窮多個素數(shù), 設(shè)為p1,p2,pn, 令m=p1p2pn+1. 顯然, pi m, 1in. 因此, 要么m本身 是素數(shù)，要么存在大于pn的素數(shù)整除m, 矛盾.,9,素數(shù)的分布(續(xù)),(n): 小于等于n的素數(shù)個數(shù). 例如 (0)=(1)=0, (2)=1, (3)=(4)=2, (5)=3.,定理19.3 (素數(shù)定理),10,素數(shù)測試,定理11.4 如果a是合數(shù), 則a必有小于等于 的真因子. 證 由性質(zhì)19.8, a=bc, 其中1( )2=a, 矛盾. 推論 如果a是合數(shù), 則a必有小于等于 的素因子. 證 由定理, a有小于等于 的真因子b. 如果

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

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 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100,1

9、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 91 92 93 94 95 96 97 98 99 100,1 2 3 4 5

10、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 91 92 93 94 95 96 97 98 99 100,1 2 3 4 5 6 7 8 9

11、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 91 92 93 94 95 96 97 98 99 100,1 2 3 4 5 6 7 8 9 10 11 12

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 91 92 93 94 95 96 97 98 99 100,埃拉托斯特尼(Eratosthene)篩法,13,d是a與b的公因子

13、(公約數(shù)): d |a且d |b m是a與b的公倍數(shù): a | m且b | m 定義19.3 設(shè)a和b是兩個不全為0的整數(shù), 稱a與b的公因子中 最大的為a與b的最大公因子, 或最大公約數(shù), 記作gcd(a,b). 設(shè)a和b是兩個非零整數(shù), 稱a與b最小的正公倍數(shù)為a與b的 最小公倍數(shù), 記作lcm(a,b). 例如 gcd(12,18)=6, lcm(12,18)=36. 對任意的正整數(shù)a, gcd(0,a)=a, gcd(1,a)=1, lcm(1,a)=a.,19.2 最大公約數(shù)與最小公倍數(shù),14,定理19.5 (1) 若a | m, b | m, 則 lcm(a,b)| m. (2)

14、若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. 同理, m |b. 即, m是a和b的公因子, 與D是a和b的最大公約數(shù)矛盾.,最大公約數(shù)與最小公倍數(shù)的性質(zhì),15,最大公約數(shù)與最小公倍數(shù)(續(xù)),例4 求150和220的最大公約數(shù)和最小公倍數(shù).,利用整數(shù)的素因子分解, 求最大公約數(shù)和最小公倍數(shù). 設(shè) 其中p1,p2,pk是不同的素數(shù), r1,r2,rk,s1,s2,sk是非負(fù) 整數(shù). 則 gcd(a,b)= lcm(a,b)=,解 150=2352, 168=2337.

15、 gcd(150,168)=21315070=6, lcm(150,168)=23315271=4200.,16,輾轉(zhuǎn)相除法,定理19.6 設(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ì)19.1, 有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的公因

16、子.,17,輾轉(zhuǎn)相除法歐幾里得(Euclid)算法,輾轉(zhuǎn)相除法 設(shè)整數(shù)a, b, 且b0, 求gcd(a,b). 做帶余除法 a=qb+r, 0r0, 再對b和r做帶余除法 b=qr+r, 0r r. 若r=0, 則gcd(a,b)=gcd(b,r)= r; 否則重復(fù)上述過程, 直至余數(shù)等于0為止.,例5 求210與715的最大公因子 解 715=3210+85, 210=285+40, 85=240+5, 40=85. 得 gcd(715, 210)=5.,18,關(guān)于最大公因子的一個定理,定理19.7 設(shè)a 和 b 不全為0, 則存在整數(shù) x 和 y 使得 gcd(a,b) = xa+yb.

17、 證 記a=r0, b =r1, 做輾轉(zhuǎn)相除法 ri=qi+1ri+1+ri+2, i=0, 1,k2, rk1=qkrk, gcd(a,b)=rk. 把上式改寫成 ri+2= riqi+1ri+1, i=k2,k3,0 從后向前逐個回代, 就可將 rk 表成 a 和 b 的線性組合.,19,例題,例5 (續(xù)) gcd(715, 210)=5 715=3210+85, 210=285+40, 85=240+5, 40=85. 于是, 有 5=85240 =852(210285) =5852210 =5(7153210)2210 = 5715 17210.,20,互素,定理19.8 整數(shù)a和b互

18、素的充分必要條件是存在整數(shù)x和y使得 xa+yb=1 證 必要性可由定理19.7得到. 充分性. 設(shè)xa+yb=1, x和y是整數(shù). 又設(shè)d0是a和b的公因子, 有 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 設(shè)a |c, b |c, 且a與b互素, 則ab |c.,證 根據(jù)定理19.8, 存在整數(shù)x,y,使xa+yb=1. 兩邊同乘以c, 得cxa+c

19、yb=c. 又由a |xa和b |c, 可得ab |cxa. 同理, ab |cyb. 于是, 有ab |cxa+cyb, 即ab|c.,22,19.3 同余,定義19.3 設(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ù).,23,同余的

20、性質(zhì),性質(zhì)19.10 同余關(guān)系是等價關(guān)系, 即同余關(guān)系具有 自反性. aa(mod m) 傳遞性. ab(mod m)bc(mod m) ac(mod m). 對稱性. ab(mod m) ba(mod m). 縮寫 a1a2ak (mod m). 性質(zhì)19.11 模算術(shù)運算 若ab(mod m), cd(mod m), 則 acbd(mod m), acbd(mod m), akbk(mod m), 其中k是非負(fù)整數(shù). 性質(zhì)19.12 設(shè)d1, d | m, 則ab(mod m) ab(mod d). 性質(zhì)19.13 設(shè)d1, 則ab(mod m) dadb(mod dm). 性質(zhì)19.14

21、 設(shè)c,m互素, 則ab(mod m) cacb(mod m).,24,模m等價類,模m等價類: 在模m同余關(guān)系下的等價類. am, 簡記作a. Zm: Z在模m同余關(guān)系下的商集 在Zm上定義加法和乘法如下: a, b, a+b=a+b, ab=ab.,例7 寫出Z4的全部元素以及Z4上的加法表和乘法表.,解 Z4=0,1,2,3, 其中i=4k+i |kZ, i=0,1,2,3.,25,例8 3455的個位數(shù)是多少?,解 設(shè)3455的個位數(shù)為x,則3455x(mod10).,由341(mod 10), 有 3455=34113+3337(mod 10), 故3455的個位數(shù)是7.,例題,26

22、,例題,例9 (續(xù)) 例如, 中華人民共和國成立日1949年10月1日, C=19, X=49, M=8, d=1, 是星期六. 中國人民抗日戰(zhàn)爭勝利日1945年8月15日, C=19, X=45, M=6, d=15, 是星期三.,27,19.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

23、+my=c. 所以, axc(mod m). 必要性. 設(shè)x是方程的解, 則存在y使得ax+my=c. 由性質(zhì)19.1, 有d | c.,一次同余方程: axc(mod m), 其中m0. 一次同余方程的解: 使方程成立的整數(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, 檢查它 們是否是方程的解, 計算結(jié)果如下: 6(4)6(1)623(mod 9), 6(3)60630(

24、mod 9), 6(2)61646(mod 9), 得方程的解 x= 4, 1, 2(mod 9), 方程的最小正整數(shù)解是2.,29,模m逆,定理19.10 (1) a的模m逆存在的充要條件是a與m互素. (2)設(shè)a與m互素, 則在模m下a的模m逆是惟一的. 證 (1) 這是定理19.9的直接推論. (2) 設(shè)ab11(mod m), ab21(mod m). 得a(b1b2)0(mod m). 由a與m互素, b1b20(mod m), 得證b1b2(mod m).,定義19.4 如果ab1(mod m), 則稱b是a的模m逆, 記作a1(mod m)或a1. a1(mod m)是方程ax1

25、(mod m)的解.,30,例題,例11 求5的模7逆.,解 5與7互素, 故5的模7逆存在.,方法1. 解方程5x1(mod7).,檢查x= 3,2,1,0,1,2,3, 得到 513(mod7).,方法2. 做輾轉(zhuǎn)相除法, 求得整數(shù)b,k使得 5b+7k=1, 則b是 5的模7逆.,計算如下: 7=5+2, 5=22+1. 回代 1=522=52(75)= 3527, 得 5 13(mod7).,方法3. 直接觀察,53=15, 15 1(mod 7), 得 513(mod7).,31,歐拉函數(shù)(n): 0, 1, n1中與n互素的數(shù)的個數(shù) 例如 (1)= (2)=1, (3)= (4)=

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

27、 得證 是1, 2,(n)上的單射, 當(dāng)然也是1, 2, (n)上的 雙射. 從而,有 而 與n互素, 故a(n)1(mod n).,33,費馬(Fermat)小定理,定理19.12(費馬小定理) 設(shè)p是素數(shù), a與p互素, 則 ap-11(mod p). 另一種形式是, 設(shè)p是素數(shù), 則對任意的整數(shù)a, apa(mod p). 費馬小定理提供了一種不用因子分解就能斷定一個數(shù)是 合數(shù)的新途徑. 例如, 2914 (mod 9), 可以斷定9是合數(shù).,34,19.6 初等數(shù)論在計算機(jī)科學(xué)技術(shù)中的幾個應(yīng)用,主要內(nèi)容 產(chǎn)生均勻偽隨機(jī)數(shù)的方法 密碼學(xué),35,產(chǎn)生均勻偽隨機(jī)數(shù)的方法,隨機(jī)數(shù):隨機(jī)變量的觀

28、察值 偽隨機(jī)數(shù) (0,1)上的均勻分布U(0,1): a(0a1), P0Xa=a 線性同余法 選擇4個非負(fù)整數(shù): 模數(shù)m, 乘數(shù)a, 常數(shù)c和種子數(shù)x0, 其中 2am, 0cm, 0 x0m, 用遞推公式產(chǎn)生偽隨機(jī)數(shù)序列: xn=(axn1+c) mod m, n=1,2, 取 un=xn/m, n=1,2, 作為U(0,1)偽隨機(jī)數(shù).,36,線性同余法與乘同余法,線性同余法產(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, 周

29、期為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ā)生器:m=2311, a=75的乘同余法, 它的周期是2312.,37,密碼學(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

30、 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.,38,加密算法,線性同余加密算法 E(i)=(ai+b)mod 26, i=0, 1,25, 其中a與26互素. 維吉利亞(Vigenere)密碼 把明文分成若干段, 每一段有n個數(shù)字, 密鑰k=k1k2kn, 加密算法 E(i1i2in)=c1c2cn, 其中cj=(ij+kj)mod 26, ij=0,1,25, j=1

31、, 2, n.,39,RSA公鑰密碼,私鑰密碼:加密密鑰和解密密鑰都必須嚴(yán)格保密 公鑰密碼 (W.Diffie,M.Hellman,1976 ):加密密鑰公開,解密密鑰保密 RSA公鑰密碼(R. Rivest, A. Shamir, L. Adleeman,1978) 取2個大素數(shù)p和q(pq), 記n=pq, (n)=(p1)(q1). 選擇正 整數(shù)w, w與(n)互素, 設(shè)d=w1(mod(n). 將明文數(shù)字化, 分成若干段, 每一個明文段mn. 加密算法 c=E(m)=mwmod n, 解密算法 D(c)=cdmod n, 其中加密密鑰w和n是公開的, 而p,q, (n)和d是保密的.,

32、40,解密算法正確性證明,要證m=cdmod n, 即cdm(mod n), 亦即mdwm(mod n). 由dw1(mod(n), 存在k使得dw=k(n)+1. 有兩種可能: (1) m與n互素. 由歐拉定理m(n)1(mod n), 得 mdwmk(n)+1 m(mod n). (2) m與n不互素. 不妨設(shè)m=cp且q不整除m. 由費馬小定理 mq11(mod q). 于是, mk(n)mk(p1)(q1)1k(p1)1 (mod q).,從而存在h使得 mk(n)=hq+1, 兩邊同乘以m, 并注意到m=cp, mk(n)+1=hcpq+m=hcn+m, 得證 mk(n)+1m(mo

33、d n), 即 mdwm(mod n).,41,模冪乘運算,模冪乘運算ab(mod n) 設(shè)b=b0+b12+br12r1, 其中bi=0或1, 于是 令 A0=a, Ai(Ai1)2(mod n), i=1, 2,r1, 則有,42,例題,例12 p=43,q=59, n=4359=2537,(n)=4258=2436, w=13. A, B, Z依次用00, 01,25表示, 各占2位. 設(shè)明文段m=2106, 即VG, 密文c=210613mod 2537. 計算如下: 13=(1101)2, 即13=1+22+23. A0=2106431(mod 2537), A1(431)2560(

34、mod 2537), A25602988(mod 2537), A3(988)2601(mod 2537), 210613(431)(988)(601)2321(mod 2537), 得密文c=2321.,43,例題(續(xù)),設(shè)密文c=0981. d=131937(mod 2436), 明文m=981937(mod 2537). 計算如下: 937=(1110101001)2, A0=981, A19812838(mod 2537), A28382505, A3(505)21325, A41325221, A5212441, A64412868, A7(868)265, A8(65)2849, A9(849)2293, 9819379811325441(65)(849)293 704(mod 2537), 得明文m=0704, 即HE.,44,第十九章 習(xí)題課,主要內(nèi)容 素數(shù)與合數(shù), 埃拉托斯特尼篩法 最大公約數(shù)與最小公倍數(shù), 輾轉(zhuǎn)相除法 同余, 模m等價類及其運算 一次同余方程及有解的充分必要條件 歐拉定理與費馬小定理 產(chǎn)生均勻偽隨機(jī)數(shù)的方法 密碼學(xué),45,基本要求,熟練掌握整除、素數(shù)、合數(shù)的概念及其性質(zhì), 掌握算術(shù)基本定理, 能熟練地素因子分解, 會判斷素數(shù), 掌握埃拉托斯特尼篩法.