第8章数论算法

教学目标理解求最大公约数的算法掌握欧几里德公式的推广掌握求解同余方程的算法掌握运用中国剩余定理解决实际问题理解双钥密码体制概念掌握RSA算法（实验四）8.1最大公约数定义1

设a，b是整数，b≠0，如果存在整数c，使得a=bc成立．则称a被b整除，a是b的倍数，b是a的约数(因数或除数)，可记为b|a；如果不存在整数c使得a＝bc成立，则称a不被b整除，记为。定理1(带余数除法)设a与b是两个整数，b≠0，则存在唯一的两个整数q和r，使得a=bq+r，0≤r<|b|。定义2

在定理1的表达式a=bq+r中，称q是a被b除的商，r是a被b除的余数。最大公约数是指两个或两个以上整数的公共约数中最大者。8.1.1欧几里德算法欧几里德定理任意给定两个整数a，b（不妨假设a≥b）。它们的最大公约数用gcd(a,b)表示，则gcd(a,b)=gcd(b,amodb)，其中amodb表示a被b除所得的余数欧几里德递归定义式P249算法应用举例（求b=100和a=210最大公约数）

gcd(100,210mod100)=gcd(100,10)=gcd(10,100mod10)=10。欧几里德递归公式的推广（P250算法设计）解决“已知a,b求解一组x，y使得ax+by=gcd(a,b)

”问题令gcd(a,b)=d，则ax+by=d；gcd(b,amodb)=d(8-1)（1）当b=0时，则gcd(a,b)=a；ax+by=a，即ax=a，则x=1，y取任意实数。简单起见，算法取y=0；（2）当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)对应项相等，则x=y'，y=x'-。8.1.2Stein算法当a,b很大时（超出计算机表示能力），欧氏算法复杂，最好不用除法和取模运算。基于的两条结论（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；算法结束。步骤3：令a1=a，b1=b；步骤4：a和b奇偶性的判断。如果a和b都是偶数，则a=a/2，b=b/2，c=2*c；如果a是偶数，b不是偶数，则a=a/2；如果b是偶数，a不是偶数，则b=b/2；如果a和b都不是偶数，则a=|a1–b1|，b=min(a1,b1)；转步骤2。P251算法应用举例求15和9的最大公约数解：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同余方程同余式设a、b和m为整数，其中m＞0。若a和b被m除得的余数相同，则称a和b对模m同余。记为或同余式的简单性质（1）若ab(m)，则m|(b-a)。反过来，若m|(b-a)，则ab(m)；（2）如果a=km+b(k为整数)，则ab(m)；（3）每个整数恰与0,1,…，m-1这m个整数中的某一个对模m同余；（4）同余关系是一种等价关系：反身性

aa(m)；对称性ab(m)，则ba(m)，反之亦然；传递性ab(m)，bc(m)，则ac(m)。（5）如果ab(m)，xy(m)，则①ax(by)(m);②特别地。例1：求使2n+1能被3整除的一切自然数n例2：求2999最后两位数码P252同余方程设是整系数多项式，m是正整数，称f(x)0(modm)(8-4)是关于未知数x的模m的同余方程，简称为模m的同余方程。若则称式(8-4)为n次同余方程同余方程的解设x0是整数，当x＝x0时式(8-4)成立，则称x0是同余方程(8-4)的解。凡对于模m同余的解，被视为同一个解，最多m个解。一次同余方程设a，b为整数，且，a0modm，则称同余方程axb(modm)(8-5)为一次同余方程。定义7设a1,a2,…,an是非零整数，b是整数，称关于未知数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)无解，算法结束；如果,则转步骤3；步骤3：根据欧几里德公式的推广，求出式(8-5)的一个解x0。步骤3-1：根据欧几里德公式的推广算法求得满足ax'+my'=d的x'，y'；具体方法：将ax'+my'=d变形可得到：ax'=d-my'(8-8)式（8-8）两边同时模m得：(8-9)可见，x'是一次同余方程(8-9)的解。步骤3-2：根据x'求x0。具体方法：由于，设，则根据同余式的性质得：即：。因此，x0=px'=x'(modm)。步骤4：根据(8-7)式可得(8-5)式的其它d-1个解为，i=1,2,…,d-1。算法结束。量水有三个分别装有a升水，b升水和c升水的量筒(gcd(a,b)=1，c＞b＞a>0)。现c筒装满水，问能否在c简中量出d升水(c>d>0)。若能，请列出一种方案。算法分析：量水过程实际上就是倒来倒去，每次倒的时候总有如下几个特点：总有一个筒中的水没有变动；不是一个筒被倒满就是另一个筒被倒光；c筒仅起中转作用。而本身容积除了必须足够装下a筒和b筒的全部水外，别无其它限制。通过上述分析知：问题实质上是将a筒倒满x次，b筒倒满y次，使得总结果有ax十by＝d(8-10)设a＝3，b＝7，c＝10，求x,y8.3同余方程组若数r同时满足n个同余方程：，则r称为这n个同余方程组成的同余方程组的解定理对同余方程组记，其中，表示m1和m2的最小公倍数。①若d(a1-a2)，则此同余方程组无解；②若d|(a1-a2)，则此同余方程组有对模M的一类剩余解。中国剩余定理（即孙子定理）设是两两互质的正整数，记M=，则同余方程组例：早在几千年前中国的一本《孙子算经》就已经提及这个问题的解法了，原文为：“今有物，不知其数，三三数之，剩二；五五数之，剩三；七七数之，剩二，问物几何？”答曰：“二十三”。P256

有对模M的唯一解其中RSA公开密钥算法1976年，Diffic,Hellman发表“密码学的新方向”，开创性提出公开密钥密码（双钥密码）体制，双钥密码系统中每人拥有两个密钥由e推d是一个难解的问题，但他们没给出一个可行算法。1978年，Rivest,Shamir,Adleman（数学家）根据数论理论提出了一种构造双钥密码的方法——现代密码学（RSA，同时提出DES单钥密码）。应当注意任何加密方法的安全性取决于密钥的安全性，以及攻破密文所需的计算量。在这方面，公开密钥密码体制并不具有比传统加密体制更加优越之处。由于目前公开密钥加密算法的开销较大，在可见的将来还看不出来要放弃传统的加密方法。公开密钥还需要密钥分配协议，具体的分配过程并不比采用传统加密方法时更为简单。加密和解密算法都是公开的。

RSA公开密钥算法RSA公开密钥密码体制所根据的原理：根据数论，寻求两个大素数比较简单，而将它们的乘积分解开则极其困难。每个用户有两个密钥：加密密钥PK{e,n}和解密密钥SK{d,n}。用户把加密密钥公开，使得系统中任何其他用户都可使用，而对解密密钥中的d则保密。n为两个大素数p和q之积（素数p和q一般为100位以上的十进数），e和d满足一定的关系。当敌手已知e和n时并不能求出d。

RSA算法设计②计算φ(n)。计算出n的欧拉函数φ(n)=（p-1）（q-1），φ(n)是不超过n并与n互素的数的个数。③选择e。用户从[0,φ(n)-1]中随机选择一个与φ(n)互素的数e作为公开的加密密钥。④计算d。计算出满足下式的d，ed=1modφ(n)作为解密密钥。⑤得出所需要的公开密钥和秘密密钥：公开密钥（即加密密钥）PK{e,n}秘密密钥（即解密密钥）SK{d,n}①计算n。秘密地选择两个大素数p和q，n=

pq。n称为RSA算法的模数。例φ(12)=4：小于或等于12且与12互质的数有4个：1，5，7，11。加密和解密运算若用整数X表示明文，用整数Y表示密文（X和Y均小于n），则加密和解密运算为：加密算法 加密：Y=Xemodn

解密算法 解密：X=Ydmodn

RSA运算量大，主要用于数字签名，而不用于信息加密。RSA算法举例①设选择了两个素数，p=7，q=17。

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

③计算出φ=(p-1)*(q-1)=(7-1)(17-1)=96。④从[0,95]中选择一个与96互素的数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及余数

66明文19公开密钥={5,119}加密52476099密文6666==1.0610秘密密钥={77,119}解密及余数

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的大数幂乘快速算法RSA需进行xrmodn运算，当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(‘请输入第一个大素数');q=input('请输入第二个大素数');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的一些变种算法已被证明等价于大数分解。不管怎样，分解n是最显然的攻击方法。现在，人们已能分解140多个十进制位的大素数。因此，模数n须选大一些，因具体适用情况而定。

若n=p×q被分解，则RSA便被击被。若p，q已知则φ(n)=（p-1）×（q-1）可计算出，d关于e满足e*d=1（modφ(n)）

RSA安全性依赖于大数分解困难。公钥和私钥都是两个大素数（大于100个十进制位）的函数。据猜测，从一个密钥和密文推断出明文的难度等同于分解两个大素数的积。8.4线段相交线段性质有向线段P1为始点，P2为终点，长度如果P1(0,0)，则记为无向线段为P1P2叉积的概念叉积是一种向量乘法，向量叉乘向量得到另一个向量，则=×=方向为右手直角坐标系几何意义以和为边的平行四边形的面积叉积定义为一个矩阵行列式思考1：叉积何时小于0？何时大于0？又何时等于0？思考2：对公共点P0而言，如何知道有向线段在有向线段的什么方向？

通过叉积可以知道确定两条线段是否相交第一步：通过快速排斥实验来确定两条线段是否不相交；第二步：在快速排斥实验判断有可能相交的前提下进行跨立实验，来确定两条线段是否相互跨立确定任意一对线段相交对应给定的一个线段集合，确定其中任意两条线段是否相交。该算法输入由若干条线段组成的集合，若这组线段中存在任意一对线段相交，则返回true；否则，返回false两点假设（1）线段集合中的所有线段都不是竖直的；（2）未有三条输入线段相交于同一点的情形。算法思想假设一条垂直扫描线沿X轴方向从左到右顺序移动、穿过已知的若干线段。移动过程中，每遇到一个线段端点，它就将穿过扫描线的所有线段放入一个动态数据结构中，并利用它们之间的关系进行排序，核查是否有相交点存在。该算法要求安排两个集合，一个是T序列，另一个是扫描线的一系列位置，即线段端点位置，并且要标记端点为线段的左端点还是线段的右端点。遇到左端点时将线段插入序列T中，并考察与其相邻的线段是否相交；遇到右端点时将线段从序列T中删除，此时考察被删除线段的左右两条线段是否相交。8.5凸包问题给定一个点集S＝{P0,P1,…,Pn-1}，它的凸包是一个最小的凸多边形P，且满足S中的每个点或者在P的边界上或者在P的内部如果点集S是两个点的集合，显然它的凸包是连接这两个点的线段；如果S是由三个不共线的点组成的集合，那么凸包是以这三个点为顶点的三角形；如果三点共线，则凸包是以距离最远的两个点为端点的线段。对于更大的集合，在直观上，可以把S中的每个点看作订在地上的木桩，那么凸包就是将所有木桩围起来的一个拉紧的橡皮绳的形状，如图8-1所示。算法思想根据凸多边形的定义，对于一个由n个点组成的集合S中的任意两个点Pi和Pj，当且仅当该集合中的其它点要么位于穿过Pi和Pj直线的同侧，要么位于线段PiPj上。则线段PiPj是该集合凸多边形边界的一部分。对每一个点都做一遍检验之后，满足条件的线段就构成了该凸包的边界算法求解步骤对于集合中的任意两点Pi和Pj，定义穿过它们直线方程。将点集S中的其余点代入直线方程，然后检查是否位于线段同侧，如果不是，说明线段PiPj不是点集S的凸多边形的边界。否则，PiPj是凸多边形的边界。对点集中的每个点，重复上述步骤，直到找出全部多边形的边界8.5.1凸包问题的穷举搜索法算法分析点集中的点构成的线段数目最多为n(n-1)/2，对每一条线段，最坏情况要检查点集中其余n-2个点属于哪个半平面，故算法的时间复杂性为O(n3)8.5.2凸包问题的分治法算法思想将点集S中的点按照x坐标升序排序，x坐标相同的按照y坐标升序排序，排好序的序列存放在点结构数组P中。那么最左边的点P0、最右边的点Pn-1肯定是凸包上的点。线段P0Pn-1将集合S中的点分成两个集合S1和S2。子集S1的凸包由线段P0Pn-1作为下边界、多节链条作为上边界组成。这条上边界称为上包。子集S2的凸包由线段P0Pn-1作为上边界、多节链条作为下边界组成。这条下边界称为下包。整个集合的凸包由上包和下包构成。如图8-2所示。算法求解步骤构造上包找到子集S1中的点Pmax，它是距离线段P0Pn-1最远的点连接，找出S1中位于直线左边的点，这些点构成集合S11；找出S1中位于直线左边的点，这些点构成集合S12；△P0PmaxPn-1内部的点不予考虑递归构造S11和S12的上包，然后简单地将它们连接起来，得到S1的上包构造下包找到子集S2中的点Pmin，它是距离线段P0Pn-1最远的点连接，找出S2中位于直线右边的点，这些点构成集合S21；找出S2中位于直线右边的点，这些点构成集合S22；△P0PminPn-1内部的点不予考虑递归构造S21和S22的上包，然后简单地将它们连接起来，得到S2的上包8.6最接近点对问题最接近点对问题要求给定平面上n个点组成的集合S，找出其中n个点组成的点对中距离