教學(xué)目標(biāo)理解求最大公約數(shù)的算法掌握歐幾里德公式的推廣掌握求解同余方程的算法掌握運(yùn)用中國(guó)剩余定理解決實(shí)際問(wèn)題理解雙鑰密碼體制概念掌握RSA算法（實(shí)驗(yàn)四）8.1最大公約數(shù)定義1

設(shè)a，b是整數(shù)，b≠0，如果存在整數(shù)c，使得a=bc成立．則稱a被b整除，a是b的倍數(shù)，b是a的約數(shù)(因數(shù)或除數(shù))，可記為b|a；如果不存在整數(shù)c使得a＝bc成立，則稱a不被b整除，記為。定理1(帶余數(shù)除法)設(shè)a與b是兩個(gè)整數(shù)，b≠0，則存在唯一的兩個(gè)整數(shù)q和r，使得a=bq+r，0≤r<|b|。定義2

在定理1的表達(dá)式a=bq+r中，稱q是a被b除的商，r是a被b除的余數(shù)。最大公約數(shù)是指兩個(gè)或兩個(gè)以上整數(shù)的公共約數(shù)中最大者。8.1.1歐幾里德算法歐幾里德定理任意給定兩個(gè)整數(shù)a，b（不妨假設(shè)a≥b）。它們的最大公約數(shù)用gcd(a,b)表示，則gcd(a,b)=gcd(b,amodb)，其中amodb表示a被b除所得的余數(shù)歐幾里德遞歸定義式P249算法應(yīng)用舉例（求b=100和a=210最大公約數(shù)）

gcd(100,210mod100)=gcd(100,10)=gcd(10,100mod10)=10。歐幾里德遞歸公式的推廣（P250算法設(shè)計(jì)）解決“已知a,b求解一組x，y使得ax+by=gcd(a,b)

”問(wèn)題令gcd(a,b)=d，則ax+by=d；gcd(b,amodb)=d(8-1)（1）當(dāng)b=0時(shí)，則gcd(a,b)=a；ax+by=a，即ax=a，則x=1，y取任意實(shí)數(shù)。簡(jiǎn)單起見(jiàn)，算法取y=0；（2）當(dāng)b≠0時(shí)，令a’=b，b’=amodb，則gcd(a',b')=d，a'x'+b'y'=d。由于b’=amodb=，則a'x'+b'y'=bx'+()y'=ay'+b(x'-)=d(8-2)

讓式(8-1)和式(8-2)對(duì)應(yīng)項(xiàng)相等，則x=y'，y=x'-。8.1.2Stein算法當(dāng)a,b很大時(shí)（超出計(jì)算機(jī)表示能力），歐氏算法復(fù)雜，最好不用除法和取模運(yùn)算?；诘膬蓷l結(jié)論（1）gcd(a,0)=a。（2）gcd(ka,kb)=kgcd(a,b)算法步驟步驟1：初始時(shí)，令c=1；步驟2：如果a=0，c=b*c；如果b=0，c=a*c；算法結(jié)束。步驟3：令a1=a，b1=b；步驟4：a和b奇偶性的判斷。如果a和b都是偶數(shù)，則a=a/2，b=b/2，c=2*c；如果a是偶數(shù)，b不是偶數(shù)，則a=a/2；如果b是偶數(shù)，a不是偶數(shù)，則b=b/2；如果a和b都不是偶數(shù)，則a=|a1–b1|，b=min(a1,b1)；轉(zhuǎn)步驟2。P251算法應(yīng)用舉例求15和9的最大公約數(shù)解：c=1,a1=15,b1=9→a=6,b=9→a=3,b=9→a1=3,b1=9→a=6,b=3→a1=3,b1=3→a=0,b=3→c=b*c=38.2同余方程同余式設(shè)a、b和m為整數(shù)，其中m＞0。若a和b被m除得的余數(shù)相同，則稱a和b對(duì)模m同余。記為或同余式的簡(jiǎn)單性質(zhì)（1）若ab(m)，則m|(b-a)。反過(guò)來(lái)，若m|(b-a)，則ab(m)；（2）如果a=km+b(k為整數(shù))，則ab(m)；（3）每個(gè)整數(shù)恰與0,1,…，m-1這m個(gè)整數(shù)中的某一個(gè)對(duì)模m同余；（4）同余關(guān)系是一種等價(jià)關(guān)系：反身性

aa(m)；對(duì)稱性ab(m)，則ba(m)，反之亦然；傳遞性ab(m)，bc(m)，則ac(m)。（5）如果ab(m)，xy(m)，則①ax(by)(m);②特別地。例1：求使2n+1能被3整除的一切自然數(shù)n例2：求2999最后兩位數(shù)碼P252同余方程設(shè)是整系數(shù)多項(xiàng)式，m是正整數(shù)，稱f(x)0(modm)(8-4)是關(guān)于未知數(shù)x的模m的同余方程，簡(jiǎn)稱為模m的同余方程。若則稱式(8-4)為n次同余方程同余方程的解設(shè)x0是整數(shù)，當(dāng)x＝x0時(shí)式(8-4)成立，則稱x0是同余方程(8-4)的解。凡對(duì)于模m同余的解，被視為同一個(gè)解，最多m個(gè)解。一次同余方程設(shè)a，b為整數(shù)，且，a0modm，則稱同余方程axb(modm)(8-5)為一次同余方程。定義7設(shè)a1,a2,…,an是非零整數(shù)，b是整數(shù)，稱關(guān)于未知數(shù)x1,x2,…,xn的方程a1x1+a2x2+…+anxn=b是n元一次不定方程。定理3一次同余方程有解的充要條件是gcd(a,m)|b。若有解，則恰有d=gcd(a，m)個(gè)解。一次同余方程的求解步驟步驟1：求gcd(a，m)；P252改錯(cuò)步驟2：令d=gcd(a，m)，如果db，則式(8-5)無(wú)解，算法結(jié)束；如果,則轉(zhuǎn)步驟3；步驟3：根據(jù)歐幾里德公式的推廣，求出式(8-5)的一個(gè)解x0。步驟3-1：根據(jù)歐幾里德公式的推廣算法求得滿足ax'+my'=d的x'，y'；具體方法：將ax'+my'=d變形可得到：ax'=d-my'(8-8)式（8-8）兩邊同時(shí)模m得：(8-9)可見(jiàn)，x'是一次同余方程(8-9)的解。步驟3-2：根據(jù)x'求x0。具體方法：由于，設(shè)，則根據(jù)同余式的性質(zhì)得：即：。因此，x0=px'=x'(modm)。步驟4：根據(jù)(8-7)式可得(8-5)式的其它d-1個(gè)解為，i=1,2,…,d-1。算法結(jié)束。量水有三個(gè)分別裝有a升水，b升水和c升水的量筒(gcd(a,b)=1，c＞b＞a>0)?，F(xiàn)c筒裝滿水，問(wèn)能否在c簡(jiǎn)中量出d升水(c>d>0)。若能，請(qǐng)列出一種方案。算法分析：量水過(guò)程實(shí)際上就是倒來(lái)倒去，每次倒的時(shí)候總有如下幾個(gè)特點(diǎn)：總有一個(gè)筒中的水沒(méi)有變動(dòng)；不是一個(gè)筒被倒?jié)M就是另一個(gè)筒被倒光；c筒僅起中轉(zhuǎn)作用。而本身容積除了必須足夠裝下a筒和b筒的全部水外，別無(wú)其它限制。通過(guò)上述分析知：?jiǎn)栴}實(shí)質(zhì)上是將a筒倒?jié)Mx次，b筒倒?jié)My次，使得總結(jié)果有ax十by＝d(8-10)設(shè)a＝3，b＝7，c＝10，求x,y8.3同余方程組若數(shù)r同時(shí)滿足n個(gè)同余方程：，則r稱為這n個(gè)同余方程組成的同余方程組的解定理對(duì)同余方程組記，其中，表示m1和m2的最小公倍數(shù)。①若d(a1-a2)，則此同余方程組無(wú)解；②若d|(a1-a2)，則此同余方程組有對(duì)模M的一類剩余解。中國(guó)剩余定理（即孫子定理）設(shè)是兩兩互質(zhì)的正整數(shù)，記M=，則同余方程組例：早在幾千年前中國(guó)的一本《孫子算經(jīng)》就已經(jīng)提及這個(gè)問(wèn)題的解法了，原文為：“今有物，不知其數(shù)，三三數(shù)之，剩二；五五數(shù)之，剩三；七七數(shù)之，剩二，問(wèn)物幾何？”答曰：“二十三”。P256

有對(duì)模M的唯一解其中RSA公開(kāi)密鑰算法1976年，Diffic,Hellman發(fā)表“密碼學(xué)的新方向”，開(kāi)創(chuàng)性提出公開(kāi)密鑰密碼（雙鑰密碼）體制，雙鑰密碼系統(tǒng)中每人擁有兩個(gè)密鑰由e推d是一個(gè)難解的問(wèn)題，但他們沒(méi)給出一個(gè)可行算法。1978年，Rivest,Shamir,Adleman（數(shù)學(xué)家）根據(jù)數(shù)論理論提出了一種構(gòu)造雙鑰密碼的方法——現(xiàn)代密碼學(xué)（RSA，同時(shí)提出DES單鑰密碼）。應(yīng)當(dāng)注意任何加密方法的安全性取決于密鑰的安全性，以及攻破密文所需的計(jì)算量。在這方面，公開(kāi)密鑰密碼體制并不具有比傳統(tǒng)加密體制更加優(yōu)越之處。由于目前公開(kāi)密鑰加密算法的開(kāi)銷較大，在可見(jiàn)的將來(lái)還看不出來(lái)要放棄傳統(tǒng)的加密方法。公開(kāi)密鑰還需要密鑰分配協(xié)議，具體的分配過(guò)程并不比采用傳統(tǒng)加密方法時(shí)更為簡(jiǎn)單。加密和解密算法都是公開(kāi)的。

RSA公開(kāi)密鑰算法RSA公開(kāi)密鑰密碼體制所根據(jù)的原理：根據(jù)數(shù)論，尋求兩個(gè)大素?cái)?shù)比較簡(jiǎn)單，而將它們的乘積分解開(kāi)則極其困難。每個(gè)用戶有兩個(gè)密鑰：加密密鑰PK{e,n}和解密密鑰SK{d,n}。用戶把加密密鑰公開(kāi)，使得系統(tǒng)中任何其他用戶都可使用，而對(duì)解密密鑰中的d則保密。n為兩個(gè)大素?cái)?shù)p和q之積（素?cái)?shù)p和q一般為100位以上的十進(jìn)數(shù)），e和d滿足一定的關(guān)系。當(dāng)敵手已知e和n時(shí)并不能求出d。

RSA算法設(shè)計(jì)②計(jì)算φ(n)。計(jì)算出n的歐拉函數(shù)φ(n)=（p-1）（q-1），φ(n)是不超過(guò)n并與n互素的數(shù)的個(gè)數(shù)。③選擇e。用戶從[0,φ(n)-1]中隨機(jī)選擇一個(gè)與φ(n)互素的數(shù)e作為公開(kāi)的加密密鑰。④計(jì)算d。計(jì)算出滿足下式的d，ed=1modφ(n)作為解密密鑰。⑤得出所需要的公開(kāi)密鑰和秘密密鑰：公開(kāi)密鑰（即加密密鑰）PK{e,n}秘密密鑰（即解密密鑰）SK{d,n}①計(jì)算n。秘密地選擇兩個(gè)大素?cái)?shù)p和q，n=

pq。n稱為RSA算法的模數(shù)。例φ(12)=4：小于或等于12且與12互質(zhì)的數(shù)有4個(gè)：1，5，7，11。加密和解密運(yùn)算若用整數(shù)X表示明文，用整數(shù)Y表示密文（X和Y均小于n），則加密和解密運(yùn)算為：加密算法 加密：Y=Xemodn

解密算法 解密：X=Ydmodn

RSA運(yùn)算量大，主要用于數(shù)字簽名，而不用于信息加密。RSA算法舉例①設(shè)選擇了兩個(gè)素?cái)?shù)，p=7，q=17。

②計(jì)算出n=p*q=7×17=119

③計(jì)算出φ=(p-1)*(q-1)=(7-1)(17-1)=96。④從[0,95]中選擇一個(gè)與96互素的數(shù)e。選e=5。⑤計(jì)算d：得5*d=1mod96解出d。不難得出，d=77,因?yàn)閑*d=5×77=385=4×96+1=1mod96。

ＲＳＡ：公開(kāi)密鑰PK={e,n}={5,119}，秘密密鑰SK={d,n}={77,119}。

RSA算法舉例19==20807119771.27...10119140及余數(shù)

66明文19公開(kāi)密鑰={5,119}加密52476099密文6666==1.0610秘密密鑰={77,119}解密及余數(shù)

19

明文19138模n求逆——改進(jìn)的Eudid算法已知e,

φ(n)，求d。（ed=1modφ(n)

）Step1、n1←φ(n),n2←e,b1←0,b2←1Step2、q←int(n1/n2),x←n1-q*nStep3、ifx≠0thenn1←n2,n2←x,t←b2,b2←b1-q*b2,b1←t,gotostep2Step4、ifn2≠1then┐e,elsed←b2modφ(n)

模n求逆——參考程序functiond=Euclid(e,r)%de=mod(1,r)n1=r;n2=e;b1=0;b2=1;while1q=fix(n1/n2);x=n1-q*n2;ifx==0,breakelsen1=n2;n2=x;t=b2;b2=b1-q*b2;b1=t;endendifn2==1,d=mod(b2,r)

elsex=‘逆元不存在!'end模n的大數(shù)冪乘快速算法RSA需進(jìn)行xrmodn運(yùn)算，當(dāng)x,r很大時(shí)，慢且可能溢出，下面介紹冪乘快速算法：Step1、a←x,b←r,c←1Step2、ifb=0,thenoutputc,endStep3、ifbmod2≠0,gotostep5Step4、b←b/2,a←a*amodn,gotostep3Step5、b←b-1,c←c*amodn,gotostep2functiony=maxmod(x,r,n)%y=mod(x^r,n)a=x;b=r;c=1;while1ifb==0,y=c;break,endifmod(b,2)==0b=b/2;a=mod(a*a,n);elseb=b-1;c=mod(c*a,n);endendRSA參考程序（實(shí)驗(yàn)四）clearfid=fopen('mydata','r');F=fread(fid);m=F';s=length(m);%pm,qm為回車換行位置

[v,tm1]=find(m==13);[v,tm2]=find(m==10);p=input(‘請(qǐng)輸入第一個(gè)大素?cái)?shù)');q=input('請(qǐng)輸入第二個(gè)大素?cái)?shù)');e=input(‘請(qǐng)輸入公鑰');n=p*q;r=(p-1)*(q-1);RSA參考程序while1ifgcd(e,r)~=1e=input(‘請(qǐng)重新輸入公鑰:’)elsebreakendend'密鑰為:'d=Euclid(e,r)c=zeros(1,s);pm=c;

fori=1:s

c(i)=maxmod(m(i),e,n);end'密文為:'cc=mod(c,95)+32;cc(tm1)=13;cc(tm2)=10;pc=char(cc)

forj=1:spm(j)=maxmod(c(j),d,n);end'明文為:'char(pm)RSA算法的安全性討論目前，RSA的一些變種算法已被證明等價(jià)于大數(shù)分解。不管怎樣，分解n是最顯然的攻擊方法?，F(xiàn)在，人們已能分解140多個(gè)十進(jìn)制位的大素?cái)?shù)。因此，模數(shù)n須選大一些，因具體適用情況而定。

若n=p×q被分解，則RSA便被擊被。若p，q已知?jiǎng)tφ(n)=（p-1）×（q-1）可計(jì)算出，d關(guān)于e滿足e*d=1（modφ(n)）

RSA安全性依賴于大數(shù)分解困難。公鑰和私鑰都是兩個(gè)大素?cái)?shù)（大于100個(gè)十進(jìn)制位）的函數(shù)。據(jù)猜測(cè)，從一個(gè)密鑰和密文推斷出明文的難度等同于分解兩個(gè)大素?cái)?shù)的積。8.4線段相交線段性質(zhì)有向線段P1為始點(diǎn)，P2為終點(diǎn)，長(zhǎng)度如果P1(0,0)，則記為無(wú)向線段為P1P2叉積的概念叉積是一種向量乘法，向量叉乘向量得到另一個(gè)向量，則=×=方向?yàn)橛沂种苯亲鴺?biāo)系幾何意義以和為邊的平行四邊形的面積叉積定義為一個(gè)矩陣行列式思考1：叉積何時(shí)小于0？何時(shí)大于0？又何時(shí)等于0？思考2：對(duì)公共點(diǎn)P0而言，如何知道有向線段在有向線段的什么方向？

通過(guò)叉積可以知道確定兩條線段是否相交第一步：通過(guò)快速排斥實(shí)驗(yàn)來(lái)確定兩條線段是否不相交；第二步：在快速排斥實(shí)驗(yàn)判斷有可能相交的前提下進(jìn)行跨立實(shí)驗(yàn)，來(lái)確定兩條線段是否相互跨立確定任意一對(duì)線段相交對(duì)應(yīng)給定的一個(gè)線段集合，確定其中任意兩條線段是否相交。該算法輸入由若干條線段組成的集合，若這組線段中存在任意一對(duì)線段相交，則返回true；否則，返回false兩點(diǎn)假設(shè)（1）線段集合中的所有線段都不是豎直的；（2）未有三條輸入線段相交于同一點(diǎn)的情形。算法思想假設(shè)一條垂直掃描線沿X軸方向從左到右順序移動(dòng)、穿過(guò)已知的若干線段。移動(dòng)過(guò)程中，每遇到一個(gè)線段端點(diǎn)，它就將穿過(guò)掃描線的所有線段放入一個(gè)動(dòng)態(tài)數(shù)據(jù)結(jié)構(gòu)中，并利用它們之間的關(guān)系進(jìn)行排序，核查是否有相交點(diǎn)存在。該算法要求安排兩個(gè)集合，一個(gè)是T序列，另一個(gè)是掃描線的一系列位置，即線段端點(diǎn)位置，并且要標(biāo)記端點(diǎn)為線段的左端點(diǎn)還是線段的右端點(diǎn)。遇到左端點(diǎn)時(shí)將線段插入序列T中，并考察與其相鄰的線段是否相交；遇到右端點(diǎn)時(shí)將線段從序列T中刪除，此時(shí)考察被刪除線段的左右兩條線段是否相交。8.5凸包問(wèn)題給定一個(gè)點(diǎn)集S＝{P0,P1,…,Pn-1}，它的凸包是一個(gè)最小的凸多邊形P，且滿足S中的每個(gè)點(diǎn)或者在P的邊界上或者在P的內(nèi)部如果點(diǎn)集S是兩個(gè)點(diǎn)的集合，顯然它的凸包是連接這兩個(gè)點(diǎn)的線段；如果S是由三個(gè)不共線的點(diǎn)組成的集合，那么凸包是以這三個(gè)點(diǎn)為頂點(diǎn)的三角形；如果三點(diǎn)共線，則凸包是以距離最遠(yuǎn)的兩個(gè)點(diǎn)為端點(diǎn)的線段。對(duì)于更大的集合，在直觀上，可以把S中的每個(gè)點(diǎn)看作訂在地上的木樁，那么凸包就是將所有木樁圍起來(lái)的一個(gè)拉緊的橡皮繩的形狀，如圖8-1所示。算法思想根據(jù)凸多邊形的定義，對(duì)于一個(gè)由n個(gè)點(diǎn)組成的集合S中的任意兩個(gè)點(diǎn)Pi和Pj，當(dāng)且僅當(dāng)該集合中的其它點(diǎn)要么位于穿過(guò)Pi和Pj直線的同側(cè)，要么位于線段PiPj上。則線段PiPj是該集合凸多邊形邊界的一部分。對(duì)每一個(gè)點(diǎn)都做一遍檢驗(yàn)之后，滿足條件的線段就構(gòu)成了該凸包的邊界算法求解步驟對(duì)于集合中的任意兩點(diǎn)Pi和Pj，定義穿過(guò)它們直線方程。將點(diǎn)集S中的其余點(diǎn)代入直線方程，然后檢查是否位于線段同側(cè)，如果不是，說(shuō)明線段PiPj不是點(diǎn)集S的凸多邊形的邊界。否則，PiPj是凸多邊形的邊界。對(duì)點(diǎn)集中的每個(gè)點(diǎn)，重復(fù)上述步驟，直到找出全部多邊形的邊界8.5.1凸包問(wèn)題的窮舉搜索法算法分析點(diǎn)集中的點(diǎn)構(gòu)成的線段數(shù)目最多為n(n-1)/2，對(duì)每一條線段，最壞情況要檢查點(diǎn)集中其余n-2個(gè)點(diǎn)屬于哪個(gè)半平面，故算法的時(shí)間復(fù)雜性為O(n3)8.5.2凸包問(wèn)題的分治法算法思想將點(diǎn)集S中的點(diǎn)按照x坐標(biāo)升序排序，x坐標(biāo)相同的按照y坐標(biāo)升序排序，排好序的序列存放在點(diǎn)結(jié)構(gòu)數(shù)組P中。那么最左邊的點(diǎn)P0、最右邊的點(diǎn)Pn-1肯定是凸包上的點(diǎn)。線段P0Pn-1將集合S中的點(diǎn)分成兩個(gè)集合S1和S2。子集S1的凸包由線段P0Pn-1作為下邊界、多節(jié)鏈條作為上邊界組成。這條上邊界稱為上包。子集S2的凸包由線段P0Pn-1作為上邊界、多節(jié)鏈條作為下邊界組成。這條下邊界稱為下包。整個(gè)集合的凸包由上包和下包構(gòu)成。如圖8-2所示。算法求解步驟構(gòu)造上包找到子集S1中的點(diǎn)Pmax，它是距離線段P0Pn-1最遠(yuǎn)的點(diǎn)連接，找出S1中位于直線左邊的點(diǎn)，這些點(diǎn)構(gòu)成集合S11；找出S1中位于直線左邊的點(diǎn)，這些點(diǎn)構(gòu)成集合S12；△P0PmaxPn-1內(nèi)部的點(diǎn)不予考慮遞歸構(gòu)造S11和S12的上包，然后簡(jiǎn)單地將它們連接起來(lái)，得到S1的上包構(gòu)造下包找到子集S2中的點(diǎn)Pmin，它是距離線段P0Pn-1最遠(yuǎn)的點(diǎn)連接，找出S2中位于直線右邊的點(diǎn)，這些點(diǎn)構(gòu)成集合S21；找出S2中位于直線右邊的點(diǎn)，這些點(diǎn)構(gòu)成集合S22；△P0PminPn-1內(nèi)部的點(diǎn)不予考慮遞歸構(gòu)造S21和S22的上包，然后簡(jiǎn)單地將它們連接起來(lái)，得到S2的上包8.6最接近點(diǎn)對(duì)問(wèn)題最接近點(diǎn)對(duì)問(wèn)題要求給定平面上n個(gè)點(diǎn)組成的集合S，找出其中n個(gè)點(diǎn)組成的點(diǎn)對(duì)中距離