學習目標掌握同余、剩余類（系）、歐拉函數(shù)、費馬定理、孫子定理了解同余理論和孫子定理在計算機和密碼學的應用課程內(nèi)容的設置同余的基本概念、性質(zhì)和應用剩余類、完全剩余系、簡化剩余系及應用歐拉函數(shù)、費馬定理及應用孫子定理同余式2.0問題的提出50天后星期幾？234567天后呢？計算機中的溢出問題循環(huán)隊列的的實現(xiàn)？%數(shù)學中的同余整除中：a=qb+r0≤r<b：同余就是余相等如：19=12*1+77=12*0+72.0問題的解決——同余理論07012)7-127112)192.1同余的基本概念與性質(zhì)定義2.1.1,若r1=r2,則稱a，b模m同余：也記為：或2.1同余的基本概念與性質(zhì)例：27≡?(mod7)253天后星期幾？同時：a≡r(mod7)0≤r<7a->r是一個滿射因此：可以按不同的余數(shù)對整數(shù)分類，也就是每一類余數(shù)相同，也就是同余23=8≡1(mod7)所以253≡23*17+2≡4(mod7)2.1同余的基本概念與性質(zhì)定理2.1.1同余關系是一種等價關系：自反性：對稱性：則傳遞性：則2.1同余的基本概念與性質(zhì)例:證明(mn-1,m3)=1證：設（mn-1,m3）=p所以mn-1≡0(modp),m3≡0(modp)所以m2≡mn.m2=n.m3≡0(modp),所以m≡mn.m=n.m2≡0(modp),所以1≡mn=m.n≡0(modp),所以p=12.1同余的基本概念與性質(zhì)性質(zhì)2.2設（1）特別的：（2)特別的：以及：（6）,且則有2.1同余的基本概念與性質(zhì)性質(zhì)2.2（3）特別的：,若（m,n）=1則擴大：擴大：若，d|(a,b,m)則（4）d|m，則特別的：若2.1同余的基本概念與性質(zhì)性質(zhì)2.2（7）若（8）（補充）若，則(a,m)=(b,m)例作業(yè)(1):p57第1題

2.1同余的基本概念與性質(zhì)

作業(yè)(2):p57第5題2.1同余的基本概念與性質(zhì)問題：一個十進制數(shù)，什么時候能被3整除結(jié)論：當各位和為3的倍數(shù)時如：248901why？2.1同余的基本概念與性質(zhì)關鍵：10=3×3+1，100=33×3+1，……所以：若n=am10m+am-110m-1+…+a110+a0

3|n<=>3|am+am-1+…+a1+a0

2.1同余的基本概念與性質(zhì)例：快速判斷某個數(shù)整除7的余數(shù)？10≡3(mod7),100≡30≡2(mod7),1000≡20≡-1(mod7)10002k+1≡-1(mod7),10002k≡1(mod7)若n=am1000m+am-11000m-1+…+a11000+a0對于637692≡692-637=55=6(mod7)2.1同余的基本概念與性質(zhì)擴展：怎樣快速判斷一個數(shù)可以被19整除？提示：湊成19的倍數(shù)2位數(shù)字？多于2位時？作業(yè)(3)：怎樣快速判斷一個數(shù)可以被31整除？,p57第3題2.1同余的基本概念與性質(zhì)補充，性質(zhì)2.2（7）的特殊情況（1）若P,q不同素數(shù)，2.1同余的基本概念與性質(zhì)例：p,p+10,p+14均是素數(shù)？求p因為10=2*5，14=2*7，所以p≠2,5,7對于p=3，若p≡1(mod3)，則p+14≡0(mod3)，排除若p≡2(mod3)，則p+10≡0(mod3)，排除所以p≡0(mod3)因為p素，所以p=32.1同余的基本概念與性質(zhì)（補充），則存在唯一使

因為存在ax+my=1即ax-1=my若存在x1和x2兩個逆元，則x1*a*x2≡x1≡x2(modm)如若(a,m)≠1，則a-1不存在2.1同余的基本概念與性質(zhì)求5模11的逆元11=5*2+15*2≡-1(mod11)5*(-2)≡1(mod11)5模11的逆元為-2（但更常寫為9）求233模1211的逆元1211=233*5+46233=46*5+346=3*15+11=46-3*15=46-(233-46*5)*15=46*76-233*15=(1211-233*5)*76-233*15=1211*76-233*395所以–395為所求2.1同余的基本概念與性質(zhì)求解方程17x≡4(mod19)19=17+217=8*2+1所以17*9-19*8=1所以17*9≡1(mod19)因為(4,9)=1所以17*36≡4(mod19)，所以x≡36≡-2(mod19)作業(yè)(4):p59第25題(1)(3)2.2同余的應用主要應用補碼、隨機數(shù)、文件系統(tǒng)、hash、密碼、檢錯碼等編程時求余的主要實現(xiàn)modexcel、vb、asp、delphi、vfp等%c、c++、c#、java等2.2同余的應用補碼Two’scomplement為什么會有補碼如何計算口訣原理：異或：模2加2.2同余的應用循環(huán)隊列數(shù)組queue[max_size]隊首指針front，指向隊首元素的前一個位置隊尾指針rear，指向隊尾元素初始化front=rear=0插入元素rear=(rear+1)%max_size刪除元素front=(front+1)%max_size什么時候為空？什么時候為滿元素數(shù)量最多為max_size-12.2同余的應用隨機數(shù)（RandomNumber）什么是隨機數(shù)有什么用：仿真、游戲、協(xié)議、密碼……srand(seed)intrand(viod)產(chǎn)生方法：利用隨機過程事先定制好的隨機數(shù)表利用數(shù)學遞推公式模擬偽隨機數(shù)（Pseudo-RandomNumber)隨機數(shù)（RandomNumber）偽隨機數(shù)產(chǎn)生方法迭代取中法：代表性為平方取中乘同余線性乘同余，也叫混合同余改進：2.2同余的應用1961年由IBM提出2.2同余的應用仿射密碼AffineCiphery≡ax+b(mod26)嘗試解密：casear考慮編程的解法LXWPAJCDUJCRXWBy≡x+3(mod26)凱撒密碼CaesarCipher移位密碼、加法密碼ABCDEFABCDEFXYZWXYZABCZABCDEF2.2同余的應用012345678910111213141504812159132610143711150481259131101426153711循環(huán)左移1字節(jié)循環(huán)左移2字節(jié)循環(huán)左移3字節(jié)helloworldbyebyeholewdbebyloelry2.3剩余類（系）Residue同余是一種等價關系=〉可以借助同余實現(xiàn)劃分令Ca={c|}定理2-1(1)任意整數(shù)都包含于一個Cr中，0≤r≤m-1(2)Ca=Cb<=>(3)要么Ca=Cb，要么Ca∩Cb=?(4)兩兩不同的Cr最多m個04812159132610143711152.3剩余類（系）Residue定義2.2.1Ca叫模m的一個剩余類，Ca中的任一數(shù)叫該類的代表元（），若為m個整數(shù)，并且其中任兩個數(shù)都不在同一個剩余類中，叫模m的一個完全剩余系，若（r,m）=1,則這樣的剩余類叫做模m的簡化（緊縮/既約）剩余系,縮系元素的個數(shù)叫做歐拉函數(shù)(m)04812159132610143711152.3剩余類（系）Residue2.3剩余類（系）Residue2.3剩余類（系）Residue例:a1,a2，…，an是一個模n的完系，則∑ak≡0(modn)n=2k+1n/2(modn)n=2k∑ak≡1+2+…+n≡n(1+n)/2（modn）若n=2k+1則，∑ak≡n*(k+1)≡0(modn)若n=2k則，∑ak≡k*(n+1)≡k(modn)2.3剩余類（系）Residue例2-10:a1,a2，…，an，b1,b2，…，bn是兩個模n的完系，證明：當m是偶數(shù)時，a1+b1,a2+b2，…，an+bn一定不是模n的完系2.3剩余類（系）Residue例2-11設m>=3,證明(2)模m的最小正簡化剩余系的各數(shù)之和等于mψ(m)/2證明：若(m,a)=1,則(m,m-a)=1所以，設ai是在1~m/2和m互素的整數(shù)所以，ai和m-ai組成了m的最小正簡化剩余系共ψ(m)/2對，和為mψ(m)/2思考：為什么沒有考慮m/22.3剩余類（系）Residue例：將1(mod5)寫成模15的剩余類的和例：寫出模9的完系，要求全是奇數(shù)對于10呢？作業(yè)(5):p58第9題2.3剩余類（系）Residue定理,(m,n)=1,(1)Ca,Cb為2個不同的剩余類<=>nCa,nCb為2個不同的剩余類(2)為模m的一個完系<=>為模m的一個完系為模m的一個縮系<=>為模m的一個縮系(3)為模m的一個完系<=>為模m的一個縮系<=>(4)為模m的一個完系<=>為模m的一個縮系<=>(5)則x遍歷m的一個完系，則nx+b也遍歷如m=10,n=7,b=6,則13,20,27,34,41,48,55,62,69,76為一個完系2.3剩余類（系）Residue定理2-2

有所以2.3剩余類（系）Residue定理2-32.3剩余類（系）Residue2.3剩余類（系）Residue2.3剩余類（系）Residue定理2-4若（m,n）=1那么呢？2.3剩余類（系）Residue關鍵n=pn時，其縮系的元素？排除與其最大公約數(shù)大于1的,也就是該數(shù)為xp(0,n-1)中，非縮系元素最小為0,最大pn-p,x取值0到pn-1–1，共pn-1個所以，如=22-2=22.3剩余類（系）Residue作業(yè)(6)：用上面的方法計算24的歐拉函數(shù)定理2-5歐拉函數(shù)的計算p素2.3剩余類（系）Residue定理2-6設m是1,2,…,n中的任一數(shù)，可以按照(m,n)的不同對1,2,…,n分類,則n的正因子的個數(shù)即為類的個數(shù)（因為m≤n）,各類中正整數(shù)個數(shù)之和為n。設d’為n的一個正因子，若(x,n)=d’，則(x/d’,n/d’)=1，由于x/d’≤n/d’,所以1,2,…,n中滿足x的個數(shù)等于1,2,…,n/d’中，滿足(y,n/d’)=1的y的個數(shù)，故有(n/d’)個。因此，記d=n/d’，得證2.3剩余類（系）Residue2.3剩余類（系）Residue2.3剩余類（系）Residue例2-14設m>=1,m|n,證n-φ(n)>=m-φ(m)等號當且僅當m=n時成立證明：

n-φ(n)表示n個整數(shù)中與n不互質(zhì)的整數(shù)個數(shù)m|n,所以m-φ(m)

<=n/m(m-φ(m))=n-nφ(m)/mφ(n)=φ(m).φ(n/m)<=φ(m).n/m所以m-φ(m)

<=n-φ(n)當且僅當m=n式成立2.3剩余類（系）Residue2.3剩余類（系）Residue推論：如果(p-1)!≡-1(modp)，則p是素數(shù)反證：如果p=ab，a,b>=2則(ab-1)!≡-1(modab)，則(ab-1)!≡-1(moda),(ab-1)!≡-1(modb)因為a<ab-1,所以a|(ab-1)!所以(ab-1)!≡0(moda)矛盾2.3剩余類（系）Residue例2-17設p為奇素，求證∏k2≡(-1)(p+1)/2(modp)其中1≤k≤p-2,k≡1(mod2)考慮-1(modp)是與(n-1)!同余，所以湊k≡-(p-k)(modp)而k是奇，p-k就是偶所以∏k2≡∏k∏[-(p-k)]≡(p-1)!*(-1)(p-1)/2作業(yè)(6):p58第17題2.3剩余類（系）Residue例2-18設ao,a1,…,ap-1和bo,b1,…,bp-1是模p的兩組完全剩余系，p奇素，證aobo,a1b1,…,ap-1bp-1一定不是模p的完全剩余系反證：設aobo,a1b1,…,ap-1bp-1是模p的完全剩余系不妨設p|aobo,

p|aibi,

1<=i<=p-1,因此設p|ao,

p|bo,

p|ai,

p|bi,

1<=i<=p-1,所以a1,…,ap-1和b1,…,bp-1是模p的兩組簡化剩余系但a1…ap-1≡-1(modp)b1…bp-1≡-1(modp)

與a1b1…ap-1bp-1≡-1(modp)

矛盾2.4剩余類（系）的應用Hash(散列)函數(shù)就是把任意長的輸入字符串（預映射，Pre-image）變換成固定長（一般更短）的輸出字符串單向：多到一=〉碰撞（collision）必然存在也叫壓縮函數(shù)、縮短函數(shù)、消息摘要、指紋、密碼校驗和、信息完整性檢驗（DIC）、操作檢驗碼（MDC）著名的：MD5，SHA-1MOD可以實現(xiàn)2.4剩余類（系）的應用Hash函數(shù)是公開的，對處理過程不用保密安全性是它的單向性：輸出不依賴于輸入預映射單個比特的改變，平均而言，將引起hash值中一半的比特改變。已知一個hash值，要找到預映射的值，使它的hash值等于已知的hash值在計算上是不可行的。優(yōu)良hash函數(shù)的條件：已知輸出，求輸入困難:單向性。已知輸入計算輸出容易的:快速性。已知x，構(gòu)造y使Hash（x）=hash(y)困難:抗碰撞性。輸出的每一比特都與輸入的每一比特有關，輸入每改變一比特，都將對輸出產(chǎn)生明顯影響：雪崩性。

2.4剩余類（系）的應用應用領域密碼學：特別是數(shù)字簽名密碼保存下載軟件：emule：校驗和標示微支付：例如基于沖突的micromint和基于hash鏈的支付payword文件系統(tǒng)：物理組織2.4剩余類（系）的應用文件系統(tǒng)：物理組織文件的組織形式：邏輯組織：用戶看到的文件組織形式物理組織：邏輯組織到磁盤塊的映射=〉地址映像物理組織：順序、鏈式、索引、hash結(jié)構(gòu)Hash結(jié)構(gòu)hash(key)=addr(在磁盤或文件中的存放位置)問題：沖突......文件空間空閑標志沖突記數(shù)記錄內(nèi)容記錄內(nèi)容空閑標志沖突記數(shù)記錄內(nèi)容記錄內(nèi)容Hash(key)=addr起始位置計算addr=hash(key)對應沖突記數(shù)加1本記錄空閑順取下一個標記為占用填記錄內(nèi)容保存記錄：TF查找記錄：計算addr=hash(key)取addr對應記錄的沖突記數(shù)countcount=0無此記錄本記錄空閑順取下一記錄key相等找到

hash(key)相等count:=count-1count=0無此記錄順取下一記錄TFFTTFTFTF刪除記錄：調(diào)用查找過程(key)找到錯誤返回置空閑標志(找到記錄)沖突記數(shù)-1對應hash(key)特點：按關鍵字檢索速度非常快。用途：常用于目錄檢索。注意：文件可循環(huán)使用，滿時保存失敗。2.5歐拉定理與費馬小定理2.5歐拉定理與費馬小定理2.5歐拉定理與費馬小定理需要指出：26

≡1(mod7)，6并不是滿足條件的最小數(shù),23

≡1(mod7)2.5歐拉定理與費馬小定理例：115x15+278x3+12(mod7)，x=10原式≡3x15-2x3-2(mod7)

≡3x3-2x3-2(mod7)≡x3-2(mod7)

≡25(mod7)≡4(mod7)2.5歐拉定理與費馬小定理推論:(a,n)=1,ax≡b(modn)解為x≡baφ(n)-1(modn)例:求解7x≡13(mod19)

x≡13*717(mod19)因為72≡(-8)(mod19)x≡13*7*224≡-4*36≡-4*7≡10(mod19)2.5歐拉定理與費馬小定理計算31000000(mod47)1000000(mod46)≡6原式≡36≡-13*9≡-117≡24(mod47)作業(yè)(7)：計算245678(mod13),p58第19題(1)2.5歐拉定理與費馬小定理2.5歐拉定理與費馬小定理求證：3n5+5n3+7n≡0(mod15)3n5≡05n3≡2n7n≡n(mod3)3n5≡3n5n3≡07n≡2n(mod5)2.5歐拉定理與費馬小定理例：證97104-1能被105整除就是要證97104≡

1（mod105）因為(97,105)=1105=3*5*7，所以(105)=2*4*6=4897104≡9748*2+8≡978(mod105)978≡1(mod3)，978≡1(mod5)，978≡972≡(-1)2(mod7)所以978≡1(mod105)成立作業(yè)(8):p58第24(4)題2.6RSA公鑰密碼機制麻省理工學院的Rivest、Shamir和Adleman三人研究小組于1978年提出機制：(1)選擇兩個大素數(shù)p和q；(2)計算n=p×q,則(n)=(p-1)×(q-1)；(3)隨機選擇一整數(shù)e，0<e<(n),滿足((n)，e)=1；(4)計算d，滿足de≡1(mod(n))(5)d保密，(d,n)是私鑰；發(fā)布(e,n)是公鑰；銷毀p,q(6)若m表示明文，用c表示密文(m和c均小于n)，則加密：；解密：2.6RSA公鑰密碼機制實現(xiàn)中的問題（1）如何計算abmodn（2）如何判定一個給定的整數(shù)是素數(shù)？（3）如何找到足夠大的素數(shù)p和q?2.6RSA公鑰密碼機制如何計算abmodn1）計算a*a*a*…*a*a*a，需要計算n-1次乘法，時間復雜度O(n)2）考慮實例a4，計算b=a*a，再算c=b*b，則c=a4，但是只用了兩次乘法，效率提高。比如a9=a*(a4)*(a4)，只需用4次乘法，一般的，an時間復雜度為O(logn)2.6RSA公鑰密碼機制第二種算法與二進制的關系9=(1001)2，a9=(((12*a)2)2)2*a10=(1010)2，a10=((((12)*a)2)2*a)2從二進制第一位開始，遇到1就先平方乘以a，遇到0就直接平方2.6RSA公鑰密碼機制如何計算abmodnBR算法BinaryRepresentation中國剩余定理能提高速度，下節(jié)內(nèi)容作業(yè)(9):p58第20題d1forikdownto0d(d*d)modnifbi=1 thend(d*a)modnreturnd2.6RSA公鑰密碼機制公鑰發(fā)布當要通信時向?qū)Ψ剿饕涔€可能假冒，因此仍需要額外的可信保障擴散通過可信的朋友之間的輾轉(zhuǎn)交換，如PGP(PrettyGoodPrivacy)公開的目錄服務目錄的維護得由信得過的機構(gòu)執(zhí)行每個用戶在目錄里有一項{身份信息，其公鑰}證書中心CA(CertificateAuthentication)PKI的核心2.6RSA公鑰密碼機制RSA可能受到的攻擊枚舉枚舉所有可能明文m，用e加密和c比較枚舉所有可能的私鑰d數(shù)學方法分解n=pq，就可以計算φ(n)，就可從e求得d不分解n，而直接求φ(n)，再求d不求φ(n)，直接求d2.6RSA公鑰密碼機制從攻擊對象：對RSA的定點攻擊對RSA的共模攻擊對RSA的選擇密文攻擊對RSA的小加密指數(shù)攻擊對RSA的小解密指數(shù)攻擊時間性攻擊：取決于解密算法的運算時間2.6RSA公鑰密碼機制定點攻擊第三者截獲密文C后，反復計算e次冪ce≡

me^2ce^2≡me^3……（modn）一旦ce^t≡c≡me（modn）=〉m≡ce^t-1（modn）

t不是很大時這種攻擊可行如何避免？如何讓t很大？今后分解

2.6RSA公鑰密碼機制選擇密文攻擊利用同態(tài)：Ek(x1x2)=Ek(x1)Ek(x2)例1：m3≡

m1m2(modn),讓A給其中兩個簽名就能夠得到其對第3個的簽名例2：收集到用A公鑰加密的密文C，想要得到明文M他首先選擇隨機數(shù)r,使r<n.然后用A的公開密鑰e計算x≡remodn y≡xc

modn讓A對y簽名，得到u≡ydmodnr-1ydmodn≡r-1xdcdmodn≡cdmodn≡m不要用RSA對陌生人的隨機文件簽名，簽名前先使用一個散列函數(shù)2.6RSA公鑰密碼機制共模攻擊如果相同的消息曾用兩個不同的指數(shù)加密，而這兩個指數(shù)是互素、加密的用戶共模，則明文可以不用任何一個解密密鑰來恢復。設用戶的公開密鑰分別為e1,e2,且e1,e2互素，明文消息為m,密文為C1≡me1modnC2

≡me2modn因為（e1,e2)=1, r*e1+s*e2=1假定r為負數(shù)則：(C1-1)r*C2s=mmodn所以：不要共模2.6RSA公鑰密碼機制總結(jié)加/解密、密鑰交換、數(shù)字簽名使用最廣泛注：實際使用時RSA加密的一般不是直接的明文，而是會話密鑰，然后用對稱算法加解密公鑰算法加密解密速度慢誤區(qū):公開密鑰密碼算法更安全公開密鑰密碼使對稱密鑰密碼過時了公鑰的分發(fā)是簡單和一目了然的2.5同余方程的一般理論2.5同余方程的一般理論2.5同余方程的一般理論2.5同余方程的一般理論2.5同余方程的一般理論法二：直接刪除x4化為：≡3x2+4x+2x3+x+x2+x3+2x2+x≡3x3+x2+x(mod5)問題的提出代數(shù)的主要問題就是解方程隋朝之前有部《孫子算經(jīng)》提出“物不知數(shù)”問題：今有物不知數(shù)，三三數(shù)之有二，五五數(shù)之有三，七七數(shù)之有二，問物有幾何韓信點兵有兵一隊，若列成五行，末行一人，若列成六行，末行五人，列成七行，末行四人，列成十一行，末行十人，求兵數(shù)解決：大衍求一術，鬼谷算天文、歷法的需要中國剩余定理ChineseRemainderTheorem

Letnbeapositiveintegersuchthatitleavestheremainders2,3,2whenitisdividedby3,5,7respectively.Findn.最簡單直接的方法：

Sincen=3k+2willleaveremainder2whenitisdividedby3,n=2,5,8,11,14,17,20…….Wefoundthatn=8cansatisfythefirsttwoconditionsbutnotthethirdone.AstheL.C.M.of3,5is15,weaddthenumber8by15eachtimeuntilwegetoursolutions.n=23Anyothersolutions?GeneralSolutions?2.7孫子定理2.3孫子定理明朝程大位《算數(shù)統(tǒng)籌》：三人同行七十稀，五樹梅花甘一枝，七子團圓整半月，除百零五便得知。

2.3孫子定理利用算式表示：２７０＋３２１＋２１５＝２３３再把２３３－１０５－１０５＝２３233+105n均是答案

３除余數(shù)５除余數(shù)７除余數(shù)７０１００２１０１０１５００１

３除余數(shù)５除余數(shù)７除余數(shù)７０２２００２１３０３０１５２００２２３３２＋０＋０＝２０＋３＋０＝３２＋０＋０＝２三人同行七十稀五樹梅花甘一枝七子團圓整半月除百零五便得知2.3孫子定理把問題一般化如何找70、21、15

３除余數(shù)５除余數(shù)７除余數(shù)７０１００２１０１０１５００１

３除余數(shù)５７＝３５除余數(shù)35x=3y+1１０2.3孫子定理找出A,B,C分別滿足以下條件而答案則為2.3孫子定理定理2-11孫子定理

設兩兩互素，k>=2,，則同余方程組解為2.3孫子定理2.3孫子定理第1步：最后的模M=5*6*7*11=2310第2步：各方程模變?yōu)镸需要乘以的數(shù)Mi

M1=2310/5=6*7*11=462;M2=2310/6=5*7*11=385M3=2310/7=5*6*11=330;M4=2310/11=5*6*7=210第3步：求出逆元Mi-1考慮Mi*x≡Mibi(modM)x≡Mi-1Mibi

(modM)但上面Mi-1是不存在的，因為（M,Mi）=M/mi，但（mi,Mi）=1Mi*x≡Mibi(modM)=>Mi*x≡Mibi(modmi)=>x≡MibiMi-1(modmi)所以求出：462*3≡1(mod5)變成x≡462*1*3(mod5)同理：x≡385*5*1(mod6);x≡330*4*1(mod7);x≡210*10*1(mod11)2.3孫子定理第4步：求出解考慮x≡462*3(mod5)：此時的x≡0(mod6)\(mod7)\(mod11)所以，對于其他方程組，這個x同余于0，可以直接加其實x≡MibiMi-1(modmi)其他mj都|Mi因此下面的解滿足各方程x≡462*3+385*5*1+330*4*1+210*10*1(mod2310)≡6731≡2111(mod2310)2.3孫子定理練習解方程組：7x≡5(mod18);13x≡2(mod15)首先7x≡5(mod18)化為：7x≡5(mod2)和7x≡5(mod9)即：x≡1(mod2)和7x≡5(mod9)13x≡2(mod15)化為:13x≡2(mod5)和13x≡2(mod3)即：3x≡2(mod5)和x≡2(mod3)對于7x≡5(mod9)可以推出7x≡5(mod3)即x≡2(mod3)所以只有3個：3x≡2(mod5)，x≡1(mod2)和7x≡5(mod9)解：x≡4*2*2*9+1*1*5*9+2*1*5*2≡209≡29(mod90)作業(yè)：P59第34題系數(shù)都化為1:x≡4(mod5)，x≡1(mod2)和x≡2(mod9)2.3孫子定理北大ACM網(wǎng)絡熱身賽青蛙的約會兩只青蛙在網(wǎng)上相識了，覺得很有必要見一面。它們很高興地發(fā)現(xiàn)它們住在同一條緯度線上，于是它們約定各自朝西跳，直到碰面為止。青蛙們都是很樂觀的，它們覺得只要一直朝著某個方向跳下去，總能碰到對方的。但是除非這兩只青蛙在同一時間跳到同一點上，不然是永遠都不可能碰面的。為了幫助這兩只樂觀的青蛙，你被要求寫一個程序來判斷這兩只青蛙是否能夠碰面，會在什么時候碰面。

青蛙A和青蛙B，規(guī)定緯度線上東經(jīng)0度處為原點，由東往西為正方向，單位長度1米，青蛙A的出發(fā)點坐標是x，一次能跳m米;青蛙B的出發(fā)點坐標是y。一次能跳n米。兩只青蛙跳一次所花費的時間相同。緯度線總長L米。福大ACM網(wǎng)絡熱身賽豬的安家

Andy和Mary養(yǎng)了很多豬。他們想要給豬安家。但是Andy沒有足夠的豬圈，很多豬只能夠在一個豬圈安家。舉個例子，假如有16頭豬，Andy建了3個豬圈，為了保證公平，剩下1頭豬就沒有地方安家了。Mary生氣了，罵Andy沒有腦子，并讓他重新建立豬圈。這回Andy建造了5個豬圈，但是仍然有1頭豬沒有地方去，然后Andy又建造了7個豬圈，但是還有2頭沒有地方去。Andy都快瘋了。你對這個事情感興趣起來，你想通過Andy建造豬圈的過程，知道Andy家至少養(yǎng)了多少頭豬。2.5加速RSA的實現(xiàn)速度p=23,q=47,e=3,加密字母A，并解密首先A的ASCII碼為65，n=pq=1081,(n)=1012，d=675加密：c≡653≡51(mod1081)變成“3”解密：m≡51675(mod1081)m≡51675≡(46+5)22*30+15≡515≡5*257≡5*27≡20*32≡-4(mod23)m≡51675≡(47+4)46*14+31≡262≡216≡212≡18(mod47)直接使用孫子定理m≡-4*47*1+18*23*(-2)≡-1016≡65(mod1081)2.5加速RSA的實現(xiàn)速度JavaDocumentC#RSAParameters2.5加速RSA的實現(xiàn)速度分析對N求模，現(xiàn)在變成了對P和Q求模,余數(shù)的大小是P和Q的剩余系里的數(shù)了。按位數(shù)來算，現(xiàn)在的乘數(shù)的二進制位數(shù)是原來乘數(shù)的二進制位數(shù)的一半根據(jù)理論分析，用了中國剩余定理后，RSA的速度又提高了約50%2.5加速RSA的實現(xiàn)速度可能受到出錯攻擊設備可能出錯此時如果Cp計算錯誤，而Cq計算正確，則可以分解n若Cp被計算成Cp’，最終計算的C變成C’,=M’(modn)則M-M’≡0(modq)M-M’≡0(modp)所以gcd((M-M’),n)=q其中2.6群簽名方案中國剩余定理最主要的價值在于將單個方程式和一個方程組等價起來若干用戶組成一個群體，使用相關的簽名方案群中心負責為群管理員和群成員分配秘鑰，群管理員則在必要的時候打開簽名確定簽名者的身份?？捎迷陔娮油镀?、電子拍賣等領域一個基本的群簽名應具有匿名性即同一個群中的成員不能識別其他群成員的簽名;不相關性即決定兩個不同的簽名是否來自于同一個人計算上是不可行的;不可偽造性即任何多個群成員不能偽造其他成員的簽名。2.6群簽名方案簽名機制秘鑰生成群中心隨機地生成兩個大素數(shù)p，q，計算n=pq，選擇公開hash函數(shù)h(x)選擇，并求d，使隨機選擇,使選擇素數(shù),且,將()送給用戶做密鑰驗證，以確信消息是群中心送來的群中心將()送給群管理員，其中是群成員的身份。設系統(tǒng)有k個成員，群中心利用中國剩余定理，可求同余方程組：的解C群中心將（n,e,c）作為公鑰，（d,p,q）為群中心的私鑰2.6群簽名方案簽名機制成員的加入和撤銷在有成員加入或撤銷時，群中心只需重新求解c的值并公布出去，而不必改變其他群成員的秘鑰。簽名群成員要對消息m簽名,首先計算h(m),再計算則即為的簽名。驗證若Alice要對

的簽名

進行驗證，Alice利用群公鑰e計算：，得到，然后驗證：是否成立。若成立，簽名合法，否則不接受簽名。群管理員通過對應的IDi確定簽名者的身份。2.6群簽名方案可能遭受的攻擊群中心偽造群成員的簽名

顯然該方案中群中心知道所有的群成員的簽名秘鑰，因此一個不誠實的群中心可以偽造其他群成員的合法簽名而不被發(fā)現(xiàn)聯(lián)合攻擊假設群成員聯(lián)合對方案攻擊，他們分別掌握可知為和為的公因子聯(lián)合人越多成功的可能越大也可以自己通過多次加入群實現(xiàn)總結(jié)同余：余數(shù)相同，關注余數(shù)，離不開除數(shù)一定是模m的意義下同余a≡b(modm)<=>m|a-b<=>a=b+km≡非常類似于==：左右可以同時加減乘除同一個數(shù)，但不能除以0≡:同一個m，左右可以同時加減乘除同余的數(shù)但不能除以與0同余的數(shù)如14≡28(mod7)不能=>2≡4(mod7)除了以后仍然得為整數(shù)≡:a,b不變，m變m可以變成其一個因子，等式仍然成立M可分解成n個不同的素數(shù)：方程與方程組的互化逆元練習一般技巧同時減去同余于0的數(shù)的倍數(shù)，即模m的倍數(shù)將幾個乘數(shù)湊成1，約去，一般使用逆元例：115x15+278x3+12(mod7)，x=15原式≡(7*16+3)x15+(7*40-2)x3+14-2(mod7)

≡3x15-2x3-2(mod7)X=15≡3*1515-2*153-2(mod7)≡3*115-2*13-2(mod7)

≡-1(mod7)類似：求解123456789(mod7)練習例：a,b,c,d4個整數(shù)，求證12|(a-b)(a-c)(a-d)(b-c)(b-d)(c-d)只需證明3|,4|因為a,b,c,d有4個數(shù)，則至少2個數(shù)模3同余，不妨設為a,b，則3|a-b對于模2，若分別2個數(shù)模2余1和0，不妨設為a,b和c,d,則2|a-b,2|c-d,則4|(a-b)(c-d)3個數(shù)模2同余，不妨設為a,b,c則4|(a-b)(a-c)練習7*8*9*10*11*12(mod13)≡(-6)*(-5)*(-4)*(-3)*(-2)*(-1)≡6!擴推12!(mod13)≡(6!)2總結(jié)模m的剩余類：同余的歸一類：2類或者完全一樣，或者完全不同完全不同的最多m個：完全剩余類模m的剩余系每個剩余類中找出一個代表元，組成一個系完全剩余類<->完系，0，1，…,m-1緊縮剩余類<->縮系,(m)縮系最大的價值：每個元素都有逆元m為素的價值：完系-0就是縮系0481215913261014371115總結(jié)關于縮系與完系的定理模m都可統(tǒng)一到0到m-1之間，簡化x遍歷縮（完）系，則ax+b也遍歷，其中（a,m）=1結(jié)合右圖擴展：a也是縮系中的一員，若b=0，如對于72*1≡2

2*2≡42*3≡62*4≡12*5≡32*6≡5(mod7)可形成分離的循環(huán)1*2≡2

2*2≡44*2≡1；

2*3≡62*6≡52*5≡30481215913261014371115總結(jié)技巧不規(guī)則的數(shù)簡化為0，1，…，m的形式要證完系，分別證有m個，兩兩不同余要證縮系，先證完系，在證與m互質(zhì)練習證明：當m>2時，02,12,…,(m-1)2一定不是模m的完全剩余系。m個,所以只需證存在兩個同余(m-1)2=m2-2m+1≡1(modm)類似：m個整數(shù)，都不屬于剩余類0(modm)則其中必有2個數(shù)屬于同一剩余類練習求證：模m簡化剩余系每個元素的和模m與0同余若r為模m的簡化剩余，則m-r也是所以，可以兩兩湊對求和，每對和與0同于總結(jié)歐拉函數(shù)的計算公式：更常用兩個：(m,n)=1時和總結(jié)Wilson定理(p-1)!≡-1(modp)<=>p是素數(shù)判斷素數(shù)的方法之三之一：用不大于sqrt(n)的質(zhì)數(shù)試除（3,i+=2）之二：愛托拉斯散篩法總結(jié)歐拉定理費馬小定理技巧：指數(shù)化簡，指數(shù)中減去歐拉函數(shù)的倍數(shù)模若為合數(shù)，先分離成多個模互質(zhì)的方程練習證明：n整數(shù)，a7≡a(mod63)首先63=7*9，所以分解：先證a7≡a(mod7)，直接根據(jù)費馬定理再由于(9)=9-3=6，所以若(a,9)=1或9時，a7≡a(mod9)

若(a,9)=3，a2k≡0(mod9)

所以(a,9)=3時是不成立注意：歐拉定理與費馬小定理的不同之處總結(jié)應用：判斷素數(shù)的方法之四首先計算2n，若模n是否同余于2注意：此時的判斷方法與費馬小定理的推理正好相反。如果p質(zhì)數(shù)則成立vs.如果成立，則p是質(zhì)數(shù)所以只能排除合數(shù)，并不能肯定素數(shù)偽素數(shù)總結(jié)應用：RSA(1)選擇兩個大素數(shù)p和q；(2)計算n=p×q,則(n)=(p-1)×(q-1)；(3)任選整數(shù)e，0<e<(n),滿足((n)，e)=1；(4)計算d，滿足de≡1(mod(n))(5)(d,n)是私鑰；發(fā)布(e,n)是公鑰；銷毀p,q(6)m表