19第十九章-初等數(shù)論

1、第六部分 初 等 數(shù) 論(elementary number theory),黃志平物 光 學 院,數(shù)論是研究整數(shù)性質(zhì)的一門很古老的數(shù)學分支，其初等部分是以整數(shù)的整除性為中心的，包括整除性、不定方程、同余式、連分數(shù)、素數(shù)(即整數(shù))分布以及數(shù)論函數(shù)等內(nèi)容，統(tǒng)稱初等數(shù)論。,初等數(shù)論的大部份內(nèi)容早在古希臘歐幾里德的《 幾何原本》中就已出現(xiàn)。歐幾里得證明了素數(shù)有無窮多個，他還給出求兩個自然數(shù)的最大公約數(shù)的方法,即所謂歐幾里得算法。我國古

2、代在數(shù)論方面亦有杰出之貢獻，現(xiàn)在一般數(shù)論書中的“中國剩余定理”正是我國古代《孫子算經(jīng)》中的下卷第26題，我國稱之為“孫子定理”。,近代初等數(shù)論的發(fā)展得益于費馬、歐拉、拉格朗日、勒讓德和高斯等人的工作。1801年，高斯的《算術(shù)探究》是數(shù)論的劃時代杰作。高斯還提出：“數(shù)學是科學之王，數(shù)論是數(shù)學之王”?？梢姼咚箤?shù)論的高度評價。,由于自20世紀以來引進了抽象數(shù)學和高等分析的巧妙工具，數(shù)論得到進一步的發(fā)展，從而開闊了新的研究領域，出現(xiàn)了代數(shù)數(shù)論

3、、解析數(shù)論、幾何數(shù)論等 新分支。而且近年來初等數(shù)論在計算器科學、組合數(shù)學、密碼學、代數(shù)編碼、計算方法等領域內(nèi)更得到了 廣泛的應用，無疑同時促進著數(shù)論的發(fā)展。,本課程介紹的內(nèi)容包括: 素數(shù)最大公約數(shù)與最小公倍數(shù)同余一次同余方程初等數(shù)論的幾個應用,【定義】設a,b是兩個整數(shù), 且b≠0, 如果存在整數(shù)c使a=bc, 則稱a被b整數(shù), 或b整數(shù)a, 記作b|a 。又稱a是b的倍數(shù)，b是a的因子。 把b不整除a記作b |

4、a,§19.1 素數(shù),,【定義】設a, b是兩個整數(shù), 其中b≠0 , 則存在惟一的整數(shù)q及r, 滿足a=bq+r ，0≤r<|b|這個式子稱為帶余除法。記 余數(shù) r = a mod b,對于 整除 有如下性質(zhì)：【性質(zhì)19.1】如果a|b且a|c, 則對任意的整數(shù)x, y, 有 a|xb+yc；【性質(zhì)19.2】如果a|b且b|c，則a|c；【性質(zhì)19.3】設m

5、≠0, 則a|b當且僅當ma|mb；【性質(zhì)19.4】如果a|b且b|a，則a=±b?！拘再|(zhì)19.5】如果a|b且b≠0，則|a| ≤ |b|?！径x19.1】如果正整數(shù)a大于1且只能被1和它自己整除，則稱a是素數(shù)；如果a大于1且不是素數(shù)，則稱a是合數(shù)。素數(shù)也稱為質(zhì)數(shù)。,素數(shù) 和 合數(shù) 有如下性質(zhì)：【性質(zhì)19.6】如果d>1, p是素數(shù)且d|p，則d=p。【性質(zhì)19.7】設p素數(shù)且p|ab，則必有p|a或p|b

6、。 更一般地，設p是一個素數(shù)且p|a1a2…ak, 則必存在1≤i ≤k，使得p|ai?！拘再|(zhì)19.8】 a>1是合數(shù)當且僅當a=bc, 其中1<b<a, 1<c<a .【性質(zhì)19.9】合數(shù)必有素數(shù)因子, 即設a是一個合數(shù), 則存在素數(shù)p, 使得p|a 。,【定理19.1】(算術(shù)基本定理)設a>1 則a能表成素數(shù)的乘積：,其中 是不同的素數(shù)，

7、 是正整數(shù),且在不計次序的意義下，表示上式是惟一的。,上式稱為整數(shù)a的素因子分解。,【例19.1】(1)99099有多少個正因子？ (2) 20的二進制表示中從最低位數(shù)起有多 少個連續(xù)的0.,【定理19.2】有無窮多個素數(shù)。,顯然, a的因子只能含有a中的素因子, 即可下述推論：,【推論】設

8、 , 其中 是不 同的素數(shù)， 是正整數(shù), 則正整數(shù)d為a的因 子的充分必要條件是 ,,其中 。,用反證法證明,記 為小于或等于n的素數(shù)個數(shù)。,例如：,【定理19.3】(素數(shù)定理),檢查一個正整數(shù)是否

9、是素數(shù)稱為素數(shù)測試，素數(shù)測試不僅有重要的理論價值，而且在密碼學中有十分重要的作用。,【定理19.4】如果a是一個合數(shù)，則a必有一個小于或 等于 的真因子。,【推論】如果a是一個合數(shù)，則a必有一個小于或 等于 的素因子。,【例19.2】判斷137和133是否為素數(shù)。,10以內(nèi)的素數(shù)是 2,3,5,7，用它們除100以內(nèi)大于10的數(shù)，刪去所有能被它們整除的數(shù)，剩下的(含2,3,5, 7在內(nèi))就是100以內(nèi)的所有素數(shù)．,表

10、19.2 篩 法,最后剩下2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89和97 . 這25個數(shù)就是100 以內(nèi)的全部素數(shù)．再用這25個素數(shù)除1002＝10000以內(nèi)大于100的數(shù)，刪去所有能被它們整除的數(shù)，可以得到10000以內(nèi)的所有素數(shù)．重復這個做法可以得到任意給定的正

11、整數(shù)以內(nèi)的所有素數(shù)．這個方法叫做埃拉托斯特尼(Eratosthene)篩法．,人們一直在尋找更大的素數(shù)。近代已知的最大素數(shù)差不多總是形如 2n – 1 的數(shù)。當n是合數(shù)時， 2n – 1 一定是合數(shù)．設n=ab，其中a>1,b>1，有,當n為素數(shù)時, 22 – 1=3, 23 – 1＝7, 24 – 1＝31, 27 – 1=127 都是素數(shù), 而 211 – 1 = 2047 = 23 x 89 是合數(shù)．,

12、設P為素數(shù), 稱如 2p–1的數(shù)為梅森(Matin Merdenne)數(shù).到 2002年為止找到的最大梅森素數(shù)是213466917 – 1, 這個數(shù)有 4百萬位．,§19.2 最大公約數(shù)與最小公倍數(shù),設a和b是兩個整數(shù)，如果d|a且d|b，則稱d是a與b的公因子，或公約數(shù)．除0之外, 任何整數(shù)只有有限個因子．因而, 兩個不全為0的整數(shù)只有有限個公因子, 其中最大的叫做最大公因子, 或最大公約數(shù), 記作gcd(a,b

13、),設 a和 b是兩個非零整數(shù), 如果 a|m且 b|h, 則稱 m是 a與 b的公倍數(shù)．a(chǎn)與b有無窮多個公倍數(shù), 其中最小的正公倍數(shù)叫做最小公倍數(shù),記作lcm(a,b),【定理19.5】(1)若 a|m, b|m，則 lcm(a,b)|m．（2）若d|a,d|b，則d|gcd(a,b),證: (1)記 M=Icm(a,b), 設m=qM+ r，0≤r＜M．根據(jù)性質(zhì)19.1, 由a|m, a|M, 及 r=m–qM, 可推出 a|

14、r. 同理, 有b|r, 即 r是a和b的公倍數(shù). 根據(jù)最小公倍數(shù)的定義, 必有r=0, 得證 M|m．(2)記D=gcd(a,b), 令 m=Icm(d, D)．若m=D, 自然有d|D，結(jié)論成立．否則m＞D，注意到d|a, D|a ,由(1)得, m|a. 同理, m|b, 即 m是a和b的公因子, 與D是a和b的最大公約數(shù)矛盾．,可以利用整數(shù)的素因子分解, 求最大公約數(shù)和最小公倍數(shù)．設,其中

15、 是不同的素數(shù)， ， 是非負整數(shù)．則,【例19.3】求168和300的最大公約數(shù)和最小公倍數(shù)．,【定理19.6】設 a = qb+r, 其中a,b,q,r都是整數(shù), 則 gcd(ab) = gcd(b,r)．,證：只需證 a與b 和 b與r 有相同的公因子．設d是a與b的公因子, 即d|a且d|b．注意到 r=a-qb, 由 性質(zhì)19.1 , 有 d

16、|r. 從而, d|b且 d|r, 即 d也是 b與r 的公因子．反之一樣, 設 d 是 b與 r的公因子, 即 dlb且 dlr．注意到, a=qb+r, 故有 d|a . 從而, d|a且 d|b，即 d也是a與b的公因子．,輾轉(zhuǎn)相除法,設整數(shù)a,b, 且b≠0. 做 帶余除法,若r2＞0，再對b和r2做帶余除法，得,重復上述過程．由于 必存在k使

17、 . 于是，有,根據(jù)定理19. 6，有,這就是輾轉(zhuǎn)相除法，又稱做歐幾里得(Euclid)算法．,【定理19.7】設a和b不全為0, 則存在整數(shù)x和y使得 gcd(a,b) = xa + yb .,證: 記 , 上式可寫成,…,其中 gcd(a,b) = rk . 把上式改寫成,從后向前逐個回代, 就可將 寫成 a 和 b 的線性組合.,記

18、 , 把最后一式寫成,一般地, 設 , 代入 ,,取 , 得,【例19.4】用輾轉(zhuǎn)相除法求168與 300的最大公因子 d, 并把 d表成 168和 300的線性組合，即求整數(shù) x 和 y 使 d＝168x + 300y．,解：做輾轉(zhuǎn)相除法,,所以可得,【定義19.2】如果gcd(a

19、,b)=1，則稱a和 b互素．,【定理19.8】整數(shù) a和 b互素的充分必要條件是存在 整數(shù) x和 y使得 xa+yb =1．,如果整數(shù) 中的任意兩個互素, 則稱它們兩兩互素.,§19.3 同 余,【定義19.3】設m是正整數(shù), a,b是整數(shù). 如果m|a-b, 稱a模m同余于b, 或a與b模m同余,記作a≡b(mod m) 如果a與b模m不同余．則記作a≡

20、b(mod m) .,,可驗證, 下述兩條都是a與b模m同余的充分必要條件：,(1) a與b除以m的余數(shù)相同, 即a mod m= b mod m .(2) a=b+km, 其中k是整數(shù)．,【性質(zhì)19.10】同余關(guān)系是等價關(guān)系, 即同余關(guān)系具有 (i) 自反性: a≡ a(mod m) (ii) 傳遞性: a≡b(mod m), b≡c(mod m), a≡c(mod m), (iii)對稱性: a≡b(mod m) ?

21、 b≡a(mod m),【性質(zhì)19.11】 模算術(shù)運算若 a≡b(mod m), c≡ d(mod m) , 則,a±c≡b±d (mod m),ac≡bd (mod m),ak≡bk (mod m), k為非負整數(shù)。,【性質(zhì)19.12】設d≥1, d|m, 則a≡b(mod m) ? a≡b(mod d),【性質(zhì)19.13】設d≥1,

22、 則a≡b(mod m) ? da≡db(mod dm),【性質(zhì)19.14】設c與m互素, 則a≡b(mod m) ? ca≡cb(mod m),整數(shù)a在模m同余關(guān)系下的等價類記作[a]m, 稱作a的模m等價類．在不會引起混淆的情況下，可略去下標m，簡記作[a]. 把整數(shù)集合Z在模m同余關(guān)系下的商集記作Zm . 根據(jù)【性質(zhì)19.11】

23、，可以在 Zm上定義加法和乘法如下：對任意的整數(shù)a, b，,【例19.6】寫出Z5的全部元素以及Z5上的加法表和 乘法表·,加法表,乘法表,【例19.7】 3455的個位數(shù)是多少？,解: 設 3455的個位數(shù)為 x , 則有3455≡x (mod 10) . 由 34≡1 (mod 10)和【性質(zhì)19.11】，有,3455 = 34×113+3≡1113x33 ≡33 ≡7 (mod 10),【例1

24、9.8】 求日期的星期數(shù)．,如何計算y年m月d日是星期幾？,如果今天是2003年3月1日, 為星期六；,則明天2003年3月2日，,為星期天；,則2003年4月2日，,為星期三；,則2004年5月4日，,為星期二；,32 ≡ 4 (mod 7),430≡ 3 (mod 7),為方便起見, 用0,1, …, 6分別表示星期日, 星期一, …，星期六，稱作星期數(shù)．整百年的年份, 即 100 C的年份稱作世紀年人稱作該世紀年的世紀數(shù).

25、 如2000年是世紀年, 其世紀數(shù)為20.,采用下述閏年規(guī)則：除世紀年外, 每 4 年一個閏年,年數(shù)能被 4 整除的年為閏年. 而對于世紀年, 只有其世紀數(shù)能被4整除, 才是閏年. 如1600, 2000,等,為計算方便, 從 3月1日開始算起?；蛘哒f, 把 3月看作第 1月, 12月看作第 10月, 下一年的 1月是第11月, 2月是第 12月．,平年 365天，2月28天．閏年 366天，2月29天．,于是, y年 m月 d日 現(xiàn)

26、在變成 Y年 M月 d日, 其中 M=(m - 3)mod12 + 1，Y=y - ? M/11?,由于 365≡1(mod 7), 3月1日的星期數(shù)每過一個平年加1, 每過一個閏年還要多加一個1.,例如：2004年3月2日，變?yōu)?004年1月2日,2004年12月2日，變?yōu)?004年10月2日,2005年2月2日，變?yōu)?004年12月2日,設1600年3月1日的星期數(shù)為 .,于是, y年3月1日( Y年

27、1月1日) 的星期數(shù)為 。,兩個日期間的星期數(shù)應如何計算？,1600年到 Y年要經(jīng)過100C + X -1600年, 如果都按平年計算, y年3月1日的 星期數(shù) 應 加上,wy≡w1600 + ( 2C + X + 3)+(25C+ ?X/4? – 400) – (C – 16) + ( ?C/4? – 4),設 y = Y = 100 C + X ，,(如 2004 = 100*20 + 4 ),而每4年

28、有一個閏年，則 應 加上,考慮到世紀年, 應從這個數(shù)中減去 C – 16，再 加上 世紀年中的閏年數(shù) ?(C – 16)/4? = ?C/4? – 4 .,因此：,≡w1600 – 2C + X + ?X/4? + ?C/4? (mod 7 ),除每個月加 30天外，由于3, 5, 7, 8, 10, 12, 1月有 31天，應另外加的 天數(shù)z 如下表所示：,已知 2004年3月1日 是 星期一, 代入上式,,1 ≡ w1600

29、 – 2×20 + 4 + ?4/4? + ?20/4? ≡ w1600 + 5 ( mod 7),得 w1600 = 3, 即 1600年 3月 1日是星期三 .,于是, 得到,接下來 計算 從當年3月1日到每個月1號的天數(shù)。,因此, M 月 d 日的星期數(shù) 應是 wY 加上,≡ 2M + ?(M+ ?M/ 7? )/2? + ?M/ 12? + d – 3( mod 7),將(1),(2)兩式合并, 得 y年m月d

30、日 星期數(shù)的計算公式：,w ≡X + ?X/4? + ?C/4? – 2C+2M+ ?(M+ ?M/7? )/2? + ?M/12? +d (mod 7 ),其中 M = (m – 3)mod12 + 1, Y = y – ?M/11? = 100C+X,例如, 中華人民共和國成立日 1949年 10 月 1日，C=19，X=49，M=8，d=1，,是星期六．,w ≡ 49 + ?49/4? + ?19/4? – 2

31、×19 + 2×8 + ?(8+ ?8/7? )/2? + ?8/12? +1,≡6 (mod 7 ),§19.4 一次同余方程,【定義】設m＞0，方程 ax ≡ c (mod m) (19.1) 稱作一次同余方程, 使上式成立的整數(shù)稱作方程的解.,[定理19.9] 方程(19.1)有解的充要條件是 gcd(a,m)|c .,證 : 充分性. 記d= gcd(a,m),

32、 a=da1, m=dm1, c=dc1；其中a1與m1互素. 由 定理19.8, 存在x1和y1 使得 a1x1+m1y1=1. 令x=c1x1, y=c1y2, 得 a1x+m1y=c1. 等式兩邊 同乘 d 得 ax+my=c．所以, ax≡c(mod m).,必要性. 設 x是方程的解, 則存在 y使得 ax+my=c. 由 性質(zhì)19.1，有 d|c ．,設x0是方程(19.1)的解, 不難驗證所有與x0模m同余

33、的數(shù)都是方程 (19.1) 解。 從而 (19.1) 的解可以寫成 x≡x0 (mod m). 于是, 只需對模m的每一個等價類取一個代表, 驗證是否使方程成立, 就能找到方程的所有解．,【例19.9】 解一次同余方程 8x≡ 4(mod 6)．,解：gcd(8,6)=2, 且 2|4 . 由定理19.9, 方程有解。,取 模6等價類的代表 x = –2, –1, 0, 1, 2, 3, 計算如下:,8×( –2

34、) ≡ 8×1 ≡ 2 (mod 6),8×( –1) ≡ 8×2 ≡ 4 (mod 6),8×0 ≡ 8×3 ≡ 0 (mod 6),可得方程的解 x= –1, 2 (mod 6), 最小正整數(shù)解為 2 .,【定義19.4】如果ab≡1 (mod m), 則稱b是a的模m 逆，記作a–1(mod m) 或 a–1．,根據(jù)定義, a的模m逆 就是方程 ax≡1(mod m) 的解.,

35、定理19.10 (1) a的模m逆存在的充要條件是a與m互素． (2) 設a與m互素, 則在模m下 a的模m逆 是惟一的, 即 a的任意兩個模m逆 都是 模m同余．,證：(2)設b1和b2是a的兩個模m逆, 即 ab1≡1(mod m), ab2≡1(mod m). 由 [性質(zhì)19.11], 得 a(b1 – b2) ≡ 0(mod m) 。而 a與 m互素, 由 [性質(zhì)19.14]，b1 – b2

36、≡ 0(mod m), 得證 b1≡b2 (mod m) .,證: (1)這是【定理19.9】的直接推論。,【例19.10】 求5的模7逆．,解：5 與 7 互素，故 5的模7逆 存在。,方法一: 當 a和m 都較小時, 可直接觀察計算。,3×5 – 2×7 = 1, 得 5–1 = 3 (mod 7),方法二: 采用一次同余方程的方法。,用 x = –2, –1, 0, 1, 2, 3, 計算 5x≡ 1(m

37、od 7), 得x=3,所以得到 5–1 = 3 (mod 7),方法三: 做輾轉(zhuǎn)相除法, 求整數(shù), 使得 ab + km = 1，,則 b是 a的模m逆.,7 = 5 + 2,5 = 2×2 + 1,,1 = 5 – 2×2 = 5 – 2×(7 – 5) = 3×5 – 2×7,得 5–1 = 3 (mod 7),,§19.5 歐拉定理和費馬小定理,對任意

38、正整數(shù) n，把 {0, 1, …, n-1}中與 n互素的個數(shù)記作中Ø(X)稱作歐拉(Euler)函數(shù). 如 Ø(1)= Ø(2)=1, Ø(3)= Ø(4)=2．顯然, 當n為素數(shù)時Ø(n) = n-1; 當n為合數(shù)時Ø(n) < n-1,【定理19.11】(歐拉定理) 設a與n互素，則,【定理19.12】(費馬小定理)設p是素數(shù),

39、a與p互素, 則,或者,§19.6 初等數(shù)論 在計算機科學技術(shù)中的幾個應用,計算機模擬是一種常用的有效方法，進行計算機模擬需要大量的隨機數(shù)。,一、 產(chǎn)生均勻偽隨機數(shù)的方法,,真正的隨機數(shù)要用專門的物理裝置產(chǎn)生, 如放射性粒子計數(shù)器, 電子管隨機數(shù)發(fā)生器等, 成本高且使用不方便, 因此通常是用偽隨機數(shù)．,偽隨機數(shù)不是真正的隨機數(shù), 不過它們具有類似隨機數(shù)的性質(zhì), 可以當作隨機數(shù)使用, 偽隨機數(shù)的性能可

40、以用數(shù)理統(tǒng)計方法加以檢驗。,最基本的偽隨機數(shù)是服從(0,1)上均勻分布的偽隨機數(shù)，服從其他分布的偽隨機數(shù)可以利用(0,1)上均勻分布的偽隨機數(shù)產(chǎn)生．,選擇4個非負整數(shù)：模數(shù)m, 乘數(shù)a, 常數(shù)c和種子數(shù)x0. 其中2≤a < m, 0≤c < m, 0≤x0＜m.,為了得到(0,1)上均勻分布偽隨機數(shù)，取,(19.6),最常用的產(chǎn)生(0,1)上均勻分布偽隨機數(shù)的方法是:線性同余法 , 如下所述。,按照下述遞推公式產(chǎn)生偽隨機

41、數(shù)序列：,種子數(shù)x0在計算時隨機給出, 其他3個參數(shù)m, a和c是固定不變的, 它們的取值決定了所產(chǎn)生的偽隨機數(shù)的質(zhì)量。,例：公式為,,xn 循環(huán)重復著…,xn 循環(huán)重復著…,式(19.6)至多能產(chǎn)生m個不同的數(shù), 因此得到的序列一定會出現(xiàn)循環(huán), 即存在正整數(shù)n0和r, 使得所有的 n≥n0都有 xn+r = xn,取c＝0，公式(19.6)簡化為,取m=231-1，a=75的乘同余法是最常用的均勻偽隨機數(shù)發(fā)生器，它的

42、周期是231－2．,使得上式成立的最小正整數(shù) r 稱作該序列的周期．,稱作乘同余法.,采用乘同余法時，顯然不能取 x0=0.,用乘同余法, 取種子數(shù)x0=1得到偽隨機數(shù)如下：,二、 密碼學基礎,早在公元前, 羅馬皇帝凱撒(J.Caesar)就已經(jīng)使用密碼傳遞作戰(zhàn)命令。,密碼的作用是改變數(shù)據(jù)的表現(xiàn)形式，其目的是只讓特定的人能解讀加密的信息。,例如：,take action at middle night,wdnh dfwlr

43、q dw plqqoh qljkw,,其加密方法是把每個字母按照字母表的順序向后移動3位, 最后3個字母變成前3個字母。,所謂密碼, 就是一組含有參數(shù)k的變換E, 信息m通過變換E得到 c=E(m).,原始信息m叫做明文, 經(jīng)過變換得到的信息c叫做密文.,從明文得到密文的過程叫做加密, 變換E稱作加密算法,參數(shù)k稱作加密密鑰。,同一個加密算法E, 可以取不同密鑰k, 給出不同的加密結(jié)果。,密碼學的相關(guān)概念：,從密文恢復明文的

44、過程叫做解密, 加密算法D是加密算法E的逆運算, 解密算法也含有參數(shù), 稱為解密密鑰。,,密碼分析,假設破譯者Oscar是在已知密碼體制的前提下來破譯Bob使用的密鑰。這個假設稱為Kerckhoff原則。最常見的破解類型如下：1.唯密文攻擊：Oscar具有密文串y.2.已知明文攻擊: Oscar具有明文串x和相應的密文y.3.選擇明文攻擊：Oscar可獲得對加密機的暫時訪問， 因此他能選擇明文串x并構(gòu)造出相應的密文串y。4.選

45、擇密文攻擊:Oscar可暫時接近密碼機,可選擇密文串y，并構(gòu)造出相應的明文x.這一切的目的在于破譯出密鑰或密文。,密碼破譯,密碼破譯的原則: 遵循觀察與經(jīng)驗方法: 采用歸納與演繹步驟: 分析、假設、推測和證實三大要素：語言的頻率特征： e連接特征: q …u, I e x, 重復特征: th, tion , tious,無條件安全（Unconditionally secure） 無論破譯者有多少密文,他也無

46、法解出對應的明文,即使他解出了,他也無法驗證結(jié)果的正確性. Onetime pad計算上安全（Computationally secure）破譯的代價超出信息本身的價值破譯的時間超出了信息的有效期.,密碼算法的安全性,基于字符的密碼代替密碼 (substitution cipher)：就是明文中的每一個字符被替換成密文中的另一個字符。接收者對密文做反向替換就可以恢復出明文。 簡單代替密碼(simple subst

47、itution cipher), 即單字母密碼: 明文的一個字符用相應的一個密文字符代替。 多字母密碼(ployalphabetic cipher): 明文中的字符映射到密文空間的字符，還依賴于它在上下文中的位置。置換密碼(permutation cipher)，又稱換位密碼:明文的字母保持相同，但順序被打亂了。,古典密碼,單表代換密碼 移位(shift )密碼、乘數(shù)(multiplicative)密碼、 仿射

48、(affine ) 密碼、多項式(Polynomial)密碼、 密鑰短語(Key Word)密碼多表代換密碼 維吉利亞(Vigenere)密碼、博福特(Beaufort)密碼、 滾動密鑰(running-key)密碼、弗納姆 (Vernam)密碼、 轉(zhuǎn)子機(rotor machine),可以用矩陣變換方便地描述多字母代換密碼, 又稱為矩陣變換密碼。如: Hill cipher, Playfair cip

49、her .,單字母密碼,多字母密碼,例 take action at middle night,移位密碼算法,凱撒加密算法是字母按字母表的順序循環(huán)移位 k 位。,用數(shù)字0~25分別表示a~z這26個字母, 此算法為:,E(i) = (i+k) mod 26 ,i=0,1,…,25,D(i) = (i – k) mod 26 ,i=0,1,…,25,解密算法為,其中加密密鑰和解密密鑰均為k, 可取任意的整數(shù)。,19 0

50、10 4 0 2 19 8 14 13 0 19 12 8 3 3 11 4 13 8 6 7 19,22 3 13 7 3 5 22 11 17 16 3 22 15 11 6 6 14 7 16 11 9 10 22,數(shù)字化為：,取 k=3 ，加密后的密文為,即： wdnh dfwlrq dw plqqoh qljkw,給定加密的消息

51、: PHHW PH DIWHU WKH WRJD SDUWB,移位密碼分析,移位密碼很容易受到唯密文攻擊，通過統(tǒng)計各個字母以及字母之間關(guān)聯(lián)出現(xiàn)的頻率可以破解出密鑰，因此是不安全的。,由于: (1) 加解密算法已知　　 (2) 可能嘗試的密鑰只有２6個,meet me after the toga party.,通過強力攻擊得到明文：,對k=(a,b) ∈K, 解密函數(shù)形式為 D( E(i) ) = a-

52、1( E(i) – b)(mod 26),仿射密碼算法,加密函數(shù)形式為 E(i ) = (ai+b)mod 26 , a,b∈Z,為了保證E是雙射的, 方程有唯一解的充要條件是： gcd(a,26) =1,其中 密鑰為: K={∈Z×Z | gcd(a,26)=1},,b=26 時，可能的密鑰是 26×12 = 311 個,例 設k＝(7, 3)，注意到 7-1(mod 26)=15, 加密

53、函數(shù)是 E(x)=7x+3, 相應的解密函數(shù)是 D(y)=15(y-3)=15y-19 , 易見 D(E(x)) = D(7x+3) = 15(7x+3)-19 = x+45-19 = x (mod 26),若明文為: hot, 首先轉(zhuǎn)換字母為數(shù)字 7,14,19,然后加密：,解密：,仿射密碼算法的密鑰空間雖然增大, 增加破譯難度。然而，可通過統(tǒng)計字母的使用頻率方式破

54、譯它。,與簡單代替密碼類似, 只是映射是一對多的, 每個明文字母可以加密成多個密文字母。 例, A可能對應于5、13、25 B可能對應于7、9、31、42當對字母的賦值個數(shù)與字母出現(xiàn)頻率成比例時。這是因為密文符號的相關(guān)分布會近似于平均的，可以挫敗頻率分析。多表代替密碼: 是以一系列(兩個以上)代換表依此對明文消息的字母進行代換的方法。,多表代替密碼,當代換表個數(shù)有限, 重復使用, 也就稱為周期多表代替密碼.,定義

55、 加密函數(shù)為: E(m1m2…mn) = c1c2…cn其中 ci = (mi+ki) mod 26 , mi=0,1,…,25, i=1,2,…,n,維吉利亞密碼 (Vigenére cipher ),維吉利亞密碼是一種多表移位代替密碼, 先把明文分成 若干段, 對于每一段有n個字母, 密鑰 k=k1k2…kn,,例 q=26, x=polyalphabetic cipher, k=RADIO明文 x=p o

56、 l y a l p h a b e t i c c i p h e r 密鑰 k=R A D I O R A D I O R A D I O R A D I O 密文 y=G O OG O C P K T P N T L K Q Z P K M F,解密函數(shù)為 D(ci) = (ci-ki) mod 26 = (mi+ki-ki)

57、 mod 26 = mi,現(xiàn)代常規(guī)加密技術(shù),DES(Data Encryption Standard)Triple DESIDEABlowfishRC5CAST-128……,傳統(tǒng)密碼的缺陷,(1) 傳統(tǒng)密碼的密鑰是對稱的, 只要知道加密密鑰就 能推算出解密密鑰。,通信雙方分別持有加密密鑰和解密密鑰, 密鑰對外是絕對保密, 必須通過秘密渠道傳送。這種密碼稱作私鑰密碼。,(2) 傳統(tǒng)密碼的密鑰不能適應于網(wǎng)絡通訊的發(fā)展

58、, 既不能直接用網(wǎng)絡傳送，也不能供多方使用。,若有n個用戶之間進行保密通訊, 需要,對 密鑰。,R S A 公鑰密碼,1976年Diffie和Hellman發(fā)表了“密碼學的新方向”，奠定了公鑰密碼學的基礎。公鑰技術(shù)是二十世紀最偉大的思想之一 , 改變了密鑰分發(fā)的方式, 可以廣泛用于數(shù)字簽名和身份認證服務.,公鑰算法的條件： (1) 產(chǎn)生一對密鑰是計算可行的; (2) 已知公鑰和明文, 產(chǎn)生密文是計算可行的; (3) 接收方利用

59、私鑰來解密密文是計算可行的; (4) 對于攻擊者, 利用公鑰來推斷私鑰是計算不可行的; (5) 已知公鑰和密文, 恢復明文是計算不可行的; (6) 加密和解密的順序可交換; (可選),RSA公鑰密碼是由Ron Rivest、Adi Shamir和Len Adleman 于1977年發(fā)明，1978年公布的。,它是一種塊加密算法, 是目前應用最廣泛的公鑰密碼算法, 只在美國申請專利, 且已于2000年9月到期。,它的基礎是歐拉定理,

60、 它的安全性依賴于大數(shù)因子分解的困難性。,取 兩個大素數(shù) p 和 q (p≠q), 即 n = pq, 則,,Ø(n) = (p–1)(q–1),選擇正整數(shù) w , w 與Ø(n) 互素, 即 dw ≡1(mod Ø(n)),為了了解RSA, 選擇如下整數(shù)：,RSA密碼思想：,首先將明文數(shù)字化, 然后把明文分成若干段, 每一個明文段的值小于n, 對于一個明文段 m,定義 加密算法 c = E(m) =

61、mw mod n,解密算法 D(c) = cd mod n,其中加密密鑰w和n是公開的, p,q, Ø(n)和d是保密的.,,證：,如果解密算法是正確的, 則,由于 , 故只需證明 , 亦即,因為 , 所以存在整數(shù) k 使得,分兩種可能討論如下：,(1) m 和 n 互素。 由歐拉定理,即可得到,(2)

62、m 和 n 不互素。,由于 , p和q是素數(shù)且 , 故m必含有 p和q 中的一個為因子, 且只含一個為因子 。,于是,從而存在整數(shù) h 使得,上式兩邊同乘以 m , 并注意到 m=cp ，,得證,綜上所述, 可得,RSA公鑰密碼的加密算法和解密算法都要做模冪乘運算 ab ( mod n).,,設 b 的二進制表示為 , 即,令

63、 , 則有,其中,請大家見P364【例題19.11】,,歐幾里德 高斯,歷史回顧,費馬,歐拉,拉格朗日 畢達格拉斯,圖靈（Alan Mathison Turing）Alan Mathison Turing,1912～1954. 英國數(shù)學家。 一生對

64、智能與機器之間的關(guān)系進行著不懈探索。1936年，24歲的圖靈提出 “圖靈機”的設想。二戰(zhàn)期間成功地破譯了納粹德國的密碼，設計并制造了 COLOSSUS,向現(xiàn)代計算機邁進了重要一步。1952年，圖靈遭到警方拘捕，原因是同性戀。1954年6月8日，服毒自殺，年僅42歲。 圖靈去世12年后，美國計算機協(xié)會以他的名字命名了計算機領域的最高獎“圖靈獎”。,登高蓋山有感登高蓋山頂，放眼遠眺，燈火萬家，街燈如龍，映紅天際間。處福州城內(nèi)，仔

65、細尋找，方圓百里，高樓林立，難覓一個家。 ——于2006年晚春日暮登高蓋山，人生低谷， 思緒萬千，有感而發(fā) 。,望月明月高空掛，佳人伴我行。凝望玉蘭下，香沁忘夜歸。

66、 ——于2007年中秋,游冬青閑游青山綠水間，哪知泥濘苦不堪。起風抱衣冬咋在，卻見山梨花盛開。 ——于2010年春回家游玩所得,無題嚴冬夜半夢驚醒，手足冰冷心更寒。側(cè)畔嬌妻正酣睡，吾本

67、知足何須煩。 ——于2010年12月28日夜半所思,金山雨夜一聲驚雷春雨至，烏龍江上霧蒙蒙。閑來相望兩不語，持書倦臥聽雨聲。 ——于2011年4

68、月,莫相逢十年單思十年夢，夢里夢外皆傷痕。前世今生緣已盡，來世無緣莫相逢。 ——于2011年5月 木棉花開時,??????? ??≠?????????????????????????????????? ????? }???≌≈∽∞?∩∪℃‰≥≤∵∏∈∑≮≯½¼