第8章數(shù)論算法

教學(xué)目標(biāo)理解求最大公約數(shù)的算法掌握歐幾里德公式的推廣掌握求解同余方程的算法掌握運用中國剩余定理解決實際問題理解雙鑰密碼體制概念掌握RSA算法（實驗四）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是兩個整數(shù)，b≠0，則存在唯一的兩個整數(shù)q和r，使得a=bq+r，0≤r<|b|。定義2

在定理1的表達式a=bq+r中，稱q是a被b除的商，r是a被b除的余數(shù)。最大公約數(shù)是指兩個或兩個以上整數(shù)的公共約數(shù)中最大者。8.1.1歐幾里德算法歐幾里德定理任意給定兩個整數(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è)計）解決“已知a,b求解一組x，y使得ax+by=gcd(a,b)

”問題令gcd(a,b)=d，則ax+by=d；gcd(b,amodb)=d(8-1)（1）當(dāng)b=0時，則gcd(a,b)=a；ax+by=a，即ax=a，則x=1，y取任意實數(shù)。簡單起見，算法取y=0；（2）當(dāng)b≠0時，令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)對應(yīng)項相等，則x=y'，y=x'-。8.1.2Stein算法當(dāng)a,b很大時（超出計算機表示能力），歐氏算法復(fù)雜，最好不用除法和取模運算?；诘膬蓷l結(jié)論（1）gcd(a,0)=a。（2）gcd(ka,kb)=kgcd(a,b)算法步驟步驟1：初始時，令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對模m同余。記為或同余式的簡單性質(zhì)（1）若ab(m)，則m|(b-a)。反過來，若m|(b-a)，則ab(m)；（2）如果a=km+b(k為整數(shù))，則ab(m)；（3）每個整數(shù)恰與0,1,…，m-1這m個整數(shù)中的某一個對模m同余；（4）同余關(guān)系是一種等價關(guān)系：反身性

aa(m)；對稱性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ù)多項式，m是正整數(shù)，稱f(x)0(modm)(8-4)是關(guān)于未知數(shù)x的模m的同余方程，簡稱為模m的同余方程。若則稱式(8-4)為n次同余方程同余方程的解設(shè)x0是整數(shù)，當(dāng)x＝x0時式(8-4)成立，則稱x0是同余方程(8-4)的解。凡對于模m同余的解，被視為同一個解，最多m個解。一次同余方程設(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)個解。一次同余方程的求解步驟步驟1：求gcd(a，m)；P252改錯步驟2：令d=gcd(a，m)，如果db，則式(8-5)無解，算法結(jié)束；如果,則轉(zhuǎn)步驟3；步驟3：根據(jù)歐幾里德公式的推廣，求出式(8-5)的一個解x0。步驟3-1：根據(jù)歐幾里德公式的推廣算法求得滿足ax'+my'=d的x'，y'；具體方法：將ax'+my'=d變形可得到：ax'=d-my'(8-8)式（8-8）兩邊同時模m得：(8-9)可見，x'是一次同余方程(8-9)的解。步驟3-2：根據(jù)x'求x0。具體方法：由于，設(shè)，則根據(jù)同余式的性質(zhì)得：即：。因此，x0=px'=x'(modm)。步驟4：根據(jù)(8-7)式可得(8-5)式的其它d-1個解為，i=1,2,…,d-1。算法結(jié)束。量水有三個分別裝有a升水，b升水和c升水的量筒(gcd(a,b)=1，c＞b＞a>0)。現(xiàn)c筒裝滿水，問能否在c簡中量出d升水(c>d>0)。若能，請列出一種方案。算法分析：量水過程實際上就是倒來倒去，每次倒的時候總有如下幾個特點：總有一個筒中的水沒有變動；不是一個筒被倒?jié)M就是另一個筒被倒光；c筒僅起中轉(zhuǎn)作用。而本身容積除了必須足夠裝下a筒和b筒的全部水外，別無其它限制。通過上述分析知：問題實質(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同時滿足n個同余方程：，則r稱為這n個同余方程組成的同余方程組的解定理對同余方程組記，其中，表示m1和m2的最小公倍數(shù)。①若d(a1-a2)，則此同余方程組無解；②若d|(a1-a2)，則此同余方程組有對模M的一類剩余解。中國剩余定理（即孫子定理）設(shè)是兩兩互質(zhì)的正整數(shù)，記M=，則同余方程組例：早在幾千年前中國的一本《孫子算經(jīng)》就已經(jīng)提及這個問題的解法了，原文為：“今有物，不知其數(shù)，三三數(shù)之，剩二；五五數(shù)之，剩三；七七數(shù)之，剩二，問物幾何？”答曰：“二十三”。P256

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

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

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

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

解密算法 解密：X=Ydmodn

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

②計算出n=p*q=7×17=119

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

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

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

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

19

明文19138模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需進行xrmodn運算，當(dāng)x,r很大時，慢且可能溢出，下面介紹冪乘快速算法：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參考程序（實驗四）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(‘請輸入第一個大素數(shù)');q=input('請輸入第二個大素數(shù)');e=input(‘請輸入公鑰');n=p*q;r=(p-1)*(q-1);RSA參考程序while1ifgcd(e,r)~=1e=input(‘請重新輸入公鑰:’)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的一些變種算法已被證明等價于大數(shù)分解。不管怎樣，分解n是最顯然的攻擊方法?，F(xiàn)在，人們已能分解140多個十進制位的大素數(shù)。因此，模數(shù)n須選大一些，因具體適用情況而定。

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

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

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