《数论基础算法》word版

《《数论基础算法》word版》由会员上传分享，免费在线阅读，更多相关内容在应用文档-天天文库。

1、数论基础算法原创：怒火之袍2003年7月24日一、引言数论曾经被视为数学领域中华而不实的一个分支，然而现在它已经得到了广泛的应用，这其中的部分原因应归结为以大素数为基础的密码体系的建立。这种体系的可行性在于我们可以轻松地找到一些大素数，而体系的安全性则在于将大素数的乘积重新分解因数往往十分困难。本文将介绍数论中比较基本的一些算法，面向的读者应具有代数结构的基础知识。二、求最大公约数我们首先要介绍的是能够有效计算两个整数的最大公约数的欧几里得算法（Euclid'salgorithm，又称辗转相除法）（下文中用gcd(a,b)来表示整数a与b的最大公约数，由于g

2、cd(a,b)=gcd(

3、a

4、,

5、b

6、)，我们将参数的范围限定在非负整数的范围内）。将a、b分别分解质因数后即可求得二者的最大公约数，然而即使是最好的算法也不能使位操作意义下的时间复杂度达到多项式级（数论算法的时间复杂度分析常常指在位操作的意义下）。高校的欧几里德算法是建立在下面的定理上的：对于任何的非负整数a和正整数b,有gcd(a,b)=gcd(b,amodb)。欧几里得算法的流程为：EUCLID(a,b)         ifb=0           thenreturna           elsereturnEUCLID(b,amodb)比如我

7、们要求31和20的最大公约数,则EUCLID的运行过程为：EUCLID(30,21)=EUCLID(21,9)=EUCLID(9,3)=EUCLID(3,0)=3。关于该算法的效率分析，有如下定理阐述：对任何k>=1，若a>b>=1且b2有Fk+1modFk=Fk-1，所以gcd(Fk+1,Fk)=gcd(Fk,(Fk+1modFk))=gcd(Fk,Fk-1)，而CLID(F3,F2)=E

8、UCLID(2,1)的计算是需要进行一次递归调用的。现在我们来改写欧几里得算法以计算附加的有用信息，使得我们可以在算法结束时获得两个整数（可能为0或负数）x、y使等式d=gcd(a,b)=ax+by成立。如下所示的EXTENDED-EUCLID过程接收一对非负整数，返回满足上述等式的三元组(d,x,y)：EXTENDED-EUCLID(a,b)     ifb=0       thenreturn(a,1,0)     (d',x',y')←EXTEND-EUCLID(b,amodb)     (d,x,y)=(d',y',x'-floor(a/b)*y')

9、     return(d,x,y)EXTENDED-EUCLID过程与EUCLID过程的时间复杂度在渐近意义下相同，差别仅在于常数因子，而由此得出的x、y却对解决一些问题十分有用。三、求解同余线性方程在一些重要的应用中常会涉及到求解如下同余线性方程的问题：a*x模n余b，求x。这个问题有解的条件是d=gcd(a,n)

10、b，在已知有解x0的情况下，可以推出其在模n意义下的全部解,即xi=x0+i*(n/d)(i=0,1...d-1)，具体过程如下：MODULAR-LINEAR-EQUATION-SOLVER(a,b,n)   (d,x',y')←EXTEND

11、ED-EUCLID(a,n)   ifd

12、b     thenx0←x'(b/d)modn       fori←0tod-1         doprint(x0+i(n/d))modn     elseprint"nosolutions"四、中国剩余定理中国有一本数学古书《孙子算经》有这样的记载：「今有物，不知其数，三三数之，剩二，五五数之，剩三，七七数之，剩二，问物几何？」答曰：「二十三」术曰：「三三数之剩二，置一百四十，五五数之剩三，置六十三，七七数之剩二，置三十，并之，得二百三十三，以二百一十减之，即得。凡三三数之剩一，则置七十，五五数之剩一，则置

13、二十一，七七数之剩一，则置十五，即得。」孙子算经的作者及确实着作年代均不可考，不过根据考证，着作年代不会在晋朝之后，以这个考证来说上面这种问题的解法，中国人发现得比西方早，所以这个问题的推广及其解法，被称为中国剩余定理。中国剩余定理（ChineseRemainderTheorem）在近代抽象代数学中占有一席非常重要的地位。它揭示了这样两个系统的一致性：一是模两两互质的一组数的同余方程组，二是模它们的乘积的方程。中国剩余定理的内容如下：令n=n1n2...nk，其中ni是两两互质的数，则对0<=a

14、.,ak)之间有一种一一对应的关系，一切对a的操作均