1、2.1 信息論2.1.1 熵與疑義度2.1.2 自然語言率2.1.3 密碼系統的安全性2.1.4 確定性距離2.1.5 混亂與擴散2.1.1 熵與疑義度假設所有的消息都有相等的可能性。一條消息中的信息量：要將消息中所有可能的含意編碼所需的最少的比特位數。熵：用來形式化地衡量一條消息M中的信息量，記為H(M)。當用比特來衡量時，為log2n，其中n為消息的狀態個數，假設所有狀態有相等的出現概率。例：數據庫中表示“星期”的字段寬度不超過3bit的信息 000 星期一 001 星期二 010 星期三 011 星期四 100 星期五 101 星期六 110 星期日 111 不 用表示星期的信息的熵 H

2、(M)= log2n= log27=2.807表示性別的信息的熵 H(M)= log2n= log22=1表示季節的信息的熵 H(M)= log2n= log24=2表示月份的信息的熵 H(M)= log2n= log212=3.585疑義度：消息的熵同時也可衡量其不確定性（疑義度），即將消息隱藏在密文中時，要破譯它所需的明文比特數。例：性別的疑義度為12.1.2 自然語言率自然語言率：對于給定的一種語言，其自然語言率為r = H(M)/ N其中N為消息長度。英語的自然語言率：1.0比特/字母1.5比特/字母絕對語言率：每個字符編碼的最大比特數，這里假設每個字符序列出現的機會相等。若語言中有L

3、個字母，則絕對語言率為：R = log2L 為單個字母的最大熵。英語的絕對語言率：log226 4.7比特/字母冗余度：語言的冗余度記為D，定義為：D = R - r其中，R為絕對語言率，r為自然語言率。英語：r = 1.3比特/字母，則 D = 4.7 -1.3=3.4比特/字母。2.1.3 密碼系統的安全性絕對安全的密碼系統：一次一密（密鑰與消息本身一樣長，密鑰隨機產生且不重復使用）密碼系統的熵：衡量密鑰空間K的大小的一個標準，通常是密鑰數以2為底的對數。H（K） = log2k2.1.4 確定性距離對于長度為n的消息，能夠將一段密文消息解密成與原始明文同種語言的可懂文本的密鑰個數為：2H

4、(K)- nD - 1確定性距離：能夠唯一地確定密鑰的最短的密文長度的近似值。對稱密碼系統的確定性距離：定義為密碼系統的熵除以語言的冗余度。U = H（K）/ D理想安全的密碼系統：確定性距離無限大的密碼系統。2.1.5 混亂與擴散混亂：在加密變換中，讓密鑰與密文的關系盡可能復雜的做法。實現混亂的方法：代替（愷撒密碼）擴散：在加密過程中，盡可能將明文的統計特性在密文中消除。實現擴散的方法：換位（鑰控序列加密法）2.2 復雜性理論2.2.1 算法復雜性2.2.2 問題復雜性2.2.1 算法復雜性算法的復雜性通常由兩個變量來衡量：T（時間復雜性）和S（空間復雜性，或存儲需求）。T和S都用n的函數來

5、表示，其中n為輸入的大小。數量級法：當n增大時，復雜性函數中增加得最快的一項。時間復雜性為4n5+7n+12復雜性的階為n5 , 表示為O(n5)多項式時間算法：O(1)：常數的O(n)：線性的O(n2)：平方的O(nm)：m為常數指數時間算法：O(tf(n)，其中t為大于1的常數，f(n)為n的多項式函數。超多項式時間算法：O(cf(n)，其中c為大于1的常數，f(n)大于常數，小于線性。2.2.2 問題復雜性圖靈機：一個有限狀態機，具有無限的讀寫存儲磁帶，是一個理想化的計算模型。問題：易解的問題：可以在多項式時間內求解難解的問題：只能在指數時間內求解不確定的問題：找不出解決的算法，不考慮算

6、法的時間復雜性問題復雜性的劃分：P問題：可以在多項式時間內求解的問題。NP問題：只能在一個非確定性的圖靈機（能夠進行猜測的一種圖靈機）上在多項式時間內求解的問題。NP完全問題：一些特定的NP問題，與其他NP問題同等困難。P空間問題：可以在多項式空間內求解，但不能在多項式時間內求解的問題。P空間完全問題：與其他P空間問題同等困難。指數時間問題：在指數時間內求解。PNPNP完全的P空間P空間完全的指數時間的2.3 初等數論2.3.1 模運算2.3.2 素數2.3.3 最大公因數2.3.4 乘法逆元素2.3.5 Fermat小定理及歐拉函數2.3.6 中國剩余定理2.3.7 二次剩余2.3.8 Le

7、gendre（勒讓得）符號2.3.9 Jacobi（雅各比）符號2.3.10 生成元2.3.11 有限域中的計算2.3.1 模運算同余：如果a = b + kn，k為整數，則a b（mod n）含義：b是a除以n的余數； b為a模n的余數； a與b模n同余。a mod n ：a模n操作，表示a除以n的余數，為 0到n 1之間的整數。例如：(78) mod 12 = 15 mod 12 = 3 15 3(mod)12 模運算（+、 ）滿足交換律、結合律和分配律。按模計算原理：對中間結果作模運算與做完了全部運算后再做模運算結果相同。按模指數運算：am mod n將指數運算作為一系列乘法運算，每次做

8、一次模運算。例：a8 mod n = (a2 mod n)2 mod n)2 mod n當m不是2的乘方時，將m表示成2的乘方和的形式。例如：25=(11001)2，即25=24+23+20 a25 mod n = (a16 a8 a) mod n = (a2)2)2)2 (a2)2)2 a) mod n = (a2 a)2)2)2 a) mod n適當存儲中間結果，則只需6次乘法：(a2mod n) a)mod n)2mod n)2mod n)2mod n) a)mod n例：315 mod 11=57 mod 13= 213 mod 9=711 mod 12=415 mod 7 =315

9、mod 11=157 mod 13= 8213 mod 9=2711 mod 12= 7415 mod 7 =12.3.2 素數素數（質數）：大于1的整數，只能被1和本身整除。有無窮多個素數。如：2，73，2521，2365347734339，2756839-12.3.3 最大公因數公因數：兩個整數a，b的公因數定義為能同時整除a，b的所有整數。最大公因數：a與b的公因數中能被所有a，b的公因數整除的正整數，記為gcd(a，b)。 例：gcd(48,36)=12互素（互質）：兩個整數稱為互素的，如果它們除了1以外沒有其他的公因數，即 gcd(a,b)=1。最大公因數的求法：輾轉相除法例如：求g

10、cd(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原理：若a b (mod c)，則 gcd(a,c) = gcd(b,c)這里，gcd(36,15) = gcd(6,15) = gcd(6,3) = 3求最大公因數的Euclid算法 p16 a b 15 36 36 15 15 6 6 3 3 0 2.3.4 乘法逆元素求x，滿足 (a x) mod n = 1, 即 x a-1(mod n)當a與n互素時, 方程 x a-1(mod n)

11、有唯一解；即：ax-kn=1當a與n不互素時, 此方程無解。一個數關于某一個模的乘法逆元不一定存在。2關于模14的乘法逆元不存在，因為2與14不互素a與n互素，a關于模n的乘法逆元才存在求乘法逆元：擴展的Euclid算法例：求5關于模14的乘法逆元輾轉相除：14 = 5 2 + 4 5 = 4 + 1逆推：1 = 5 - 4 = 5 - （14 - 5 2）= 5 3 - 14 因此，5關于模14的乘法逆元為3。例：求4關于模7的乘法逆元 7=4 1+3 4=3+1 1=4-3 =4-(7-4) =4 2-7 所以4關于模7的乘法逆元為2練習練習：求17關于模26的乘法逆元。答案求17關于模2

12、6的乘法逆元。答案：2326 = 17 + 9 1 = 9 - 817 = 9 + 8 = 9 - (17 - 9)9 = 8 + 1 = 9 2 - 17 = (26 - 17) 2 - 17 = 26 2 - 17 3 = 17 (-3) + 26 2+17 26- 17 26 = 17 23 - 26 152.3.5 Fermat小定理及歐拉函數Fermat小定理：如果m為素數，a不能被m整除，則 am-1 1 (mod m)例：210 1 mod 11 610 1 mod 11 710 1 mod 11 810 1 mod 11 36 1 mod 7 模n的簡化剩余集：模n的完全剩余集

13、的一個子集，其中每個元素與n互素。如果n為素數，則模n的簡化剩余集為從1 n-1。例：模12的簡化剩余集為1，5，7，11 模7的簡化剩余集為1，2，3，4，5，6 歐拉函數：記為(n)，為模n的簡化剩余集中元素的個數。如果n是素數，則(n) = n-1若n=pq，其中p、q為素數，則(n)=（p-1)(q-1)例：n=15 , n=3 5 , p=3, q=5 (n)=2 4=8 15的簡化剩余集為1，2，4，7，8，11，13，14歐拉擴展的Fermat小定理：如果gcd(a,n) = 1，則 a(n) mod n = 1。a的乘法逆元：x=a (n)-1 mod n例：求5關于模7的乘法

14、逆元解：方法一：7=5+2 5=2 2+1 1=5-2 2 =5-2 (7-5) =3 5-2 7 5關于模7的乘法逆元為3方法二： n=7 n為素數，gcd(5,7)=1, (n)=n-1=7-1=6x= a (n)-1 mod n =5 6-1 mod 7=55mod 7=3例：4關于模7的乘法逆元解： (7)=7-1=6 n為素數 gcd(4,7)=1 x= a (n)-1 mod n =46-1 mod 7=45mod 7=22.3.6 中國剩余定理定理：如果n的素數因子分解式為p1p2 pt，則一組方程 (x mod pi）= ai，其中i = 1,2,t，有唯一解x，其中x小于n（

15、其中某些pi可能相等）。例：今有物不知其數，三三數之剩二，五五數之剩三，七七數之剩二，問物幾何？x mod 3 = 2x mod 5 = 3x mod 7 = 2解法：令a1=2，a2=3，a3=2，p1=3，p2=5，p3=7，n=p1 p2 p3=3 5 7=105，M1=n/p1=35, M2=n/p2=21, M3=n/p3=15求解 35 x1 mod 3=1, 得x1=2求解 21 x2 mod 5=1, 得x2=1求解 15 x3 mod 7=1, 得x3=1則 x = (M1 x1 a1+M2 x2 a2+M3 x3 a3 ) mod n = (35 2 2+21 1 3+15

16、 1 2) mod 105 = 233 mod 105 = 23練習：今有數不知其數，兩兩數之剩1，三三數之剩2，五五數之剩2，求該數。解法：令a1=1，a2=2，a3=2，p1=2，p2=3，p3=5，n=p1 p2 p3=2 3 5=30M1=n/p1=15, M2=n/p2=10, M3=n/p3=6求解 15 x1 mod 2=1, 得x1=1求解 10 x2 mod 3=1, 得x2=1求解 6 x3 mod 5=1, 得x3=1則 x = (M1 x1 a1+M2 x2 a2+M3 x3 a3 ) mod n = (15 1 1+10 1 2+6 1 2) mod 30 = 47

17、mod 30 = 17課后練習：今有數不知其數，五五數之剩2，七七數之剩5，十一十一數之剩3，求該數。2.3.7 二次剩余定義：設p為素數，a0且ap，如果存在某個x，滿足x2 a (mod p)，則稱a為模p的二次剩余。否則稱a為模p的非二次剩余。例1：p=5, a=4 x=2 22 4 （mod 5）例2：p=11, a=5 x=4 42 5 （mod 11）2.3.8 Legendre（勒讓得）符號記為L(a,p)，其中a為任意整數，p為大于2的素數。定義：L(a,p) = 0，如果a能被p整除；L(a,p) = 1，如果a是模p的二次剩余；L(a,p) = -1，如果a是模p的非二次剩

18、余；計算：L(a,p) = a(p-1)/2 mod p公式驗證：L(a,p) = a(p-1)/2 mod p = (a(p-1) mod p)1/2 = 1 Fermat小定理： am-1 1 (mod m) = 1 L(a,p) = -1=p-1Legendre符號的用途用Legendre符號來驗證a是否是模p的二次剩余舉例:驗證：a=5是否是p=11的二次剩余？L(a,p) = a(p-1)/2 mod p=5(11-1)/2 mod 11=55 mod 11=1 即 L(5,11) =1 所以5是模11的二次剩余 (72 5 mod 11) 再如： L(6,11)= 6(11-1)/

19、2 mod 11=65 mod 11=10=p-1 所以6不是模11的二次剩余22 4 mod 5 L(4,5)=4(5-1)/2 mod 5 =1 42 5 mod 11 L(5,11)=5(11-1)/2 mod 11 =12.3.9 Jacobi（雅各比）符號記為J(a,n)，是Legendre符號的擴展，其中a為任意整數，而n為任意奇數。定義：J(a,n)只對n為奇數時有意義J(0,n)=0如果n為素數，且a能被n整除，則J(a,n)=0如果n為素數，且a是模n的二次剩余，則J(a,n) = 1(即x2 a mod n)如果n為素數，且a是模n的非二次剩余，則J(a,n) = -1如果

20、n是合數，則J(a,n)=J(a,p1)J(a,p2)J(a,pm)，其中將n因數分解為p1p2pmBlum整數：若p和q為兩個素數，且都與3模4同余，則n = pq稱為Blum整數。若n為Blum整數，則每個模n的二次剩余恰好有4個平方根，其中一個也是一個二次剩余，稱為原平方根。例如，139的模437的原平方根為24，另三個平方根為185，252和413。n=437=19*23 p=19 q=23242 139 （mod 437） 1852 139 （mod 437）2522 139 （mod 437） 4132 139 （mod 437）2.3.10 生成元定義：如果p為素數，gp，如果對

21、每個b從1到p-1，存在a，使ga b (mod p)，則g為模p的生成元。例：p=11，2為模11的生成元g=2 p=11 b=110 都可表示成：2a mod p1 210 mod 11 6 29 mod 11 2 21 mod 11 7 27 mod 11 3 28 mod 11 8 23 mod 11 4 22 mod 11 9 26 mod 11 5 24 mod 11 10 25 mod 11生成元的測試q=p-1 q=q1*q2*qn對每個qi, 若 g (p-1)/qi mod p=1，則g不是生成元。例：p=11 q=10=2*5 g=2 2 (11-1)/2 mod 11=

22、 10 2 (11-1)/5 mod 11= 4 所以 2是模11的生成元 g=3 3 (11-1)/2 mod 11= 1 3 (11-1)/5 mod 11= 9 所以 3不是模11的生成元練習：求模11的生成元一共有幾個？2.3.11 有限域中的計算有限域：元素個數有限的域。在有限域中，非0數的加、減、乘、除都有定義。加法單位元是0，乘法單位元是1，每個非0元素都有一個唯一的乘法逆元。有限域中運算滿足交換律、結合律和分配律。有限域中元素個數為素數或素數的乘方：設p為素數，則有限域可記為GF(p)或GF(pn)。不可約多項式：一個多項式如果除了1和本身外，不能分解成其他多項式的乘積形式，則

23、成為不可約多項式。 例：x2+1 而x3+ 2x2+x = x(x+1)(x+1) 不是不可約多項式本原多項式：一個有限域內的生成元多項式，其系數是互素的。在GF(qn)中，所有運算都是模p(x)的運算，其中p(x)是n階不可約多項式。P(x)=xn+x+12.4 因數分解對一個數進行因數分解，是指找出這個數的素數因子。6=2 38=2 2 29=3 310=2 560=2 2 3 5252601=41 61 1012.5 素數的產生2.5.1 Solovay-Strassen方法2.5.2 Lehmann法2.5.3 強素數2.5.1 Solovay-Strassen方法用Jacobi符號來測試p是否為素數：（1）選擇一個隨機數a，ap；（2）如果gcd(a,p)1，則p是合數，停止檢測；（3）計算i=a(p-1)/2 mod p；（4）計算Jacobi符號J(a,p)；（5）如果i J(a,p)，則p不是素數；（6）如果i= J(a,p)，則p不是素數的概率小于50%。對t個不同的隨機數a，重復進行這個測試。能通過所有t個測試的奇數是合數的概率小于1/2t。2.5.2 Lehmann法測試p是否為素數：