[分享]数论基础算法

frogfish

数论基础算法
原创：怒火之袍  2003年7月24日  

一、引言

数论曾经被视为数学领域中华而不实的一个分支，然而现在它已经得到了广泛的应用，这其中的部分原因应归结为以大素数为基础的密码体系的建立。这种体系的可行性在于我们可以轻松地找到一些大素数，而体系的安全性则在于将大素数的乘积重新分解因数往往十分困难。本文将介绍数论中比较基本的一些算法，面向的读者应具有代数结构的基础知识。

二、求最大公约数

我们首先要介绍的是能够有效计算两个整数的最大公约数的欧几里得算法（Euclid's algorithm，又称辗转相除法）（下文中用gcd(a,b)来表示整数a与b的最大公约数，由于gcd(a,b)=gcd(|a|,|b|)，我们将参数的范围限定在非负整数的范围内）。

将a、b分别分解质因数后即可求得二者的最大公约数，然而即使是最好的算法也不能使位操作意义下的时间复杂度达到多项式级（数论算法的时间复杂度分析常常指在位操作的意义下）。高校的欧几里德算法是建立在下面的定理上的：

对于任何的非负整数a和正整数b,有gcd(a,b)=gcd(b,a mod b)。欧几里得算法的流程为：

1. EUCLID(a,b)
   
2. 
   
3. if b=0
   
4. 
   
5. then return a
   
6. 
   
7. else return EUCLID(b,a mod b)

复制代码

比如我们要求31和20的最大公约数,则EUCLID的运行过程为：

1. EUCLID(30,21)=EUCLID(21,9)=EUCLID(9,3)=EUCLID(3,0)=3。

复制代码

关于该算法的效率分析，有如下定理阐述：

对任何k>=1，若a>b>=1且b<Fk+1(Fx为Fibonacci数列的第x项)，那么EUCLID(a,b)的递归调用必小于k次。

连续的Fibonacci数是EUCLID输入的最坏情况，因为对任何k>2有Fk+1 mod Fk=Fk-1，所以gcd(Fk+1,Fk)=gcd(Fk,(Fk+1 mod Fk))=gcd(Fk,Fk-1)，而CLID(F3,F2)=EUCLID(2,1)的计算是需要进行一次递归调用的。

现在我们来改写欧几里得算法以计算附加的有用信息，使得我们可以在算法结束时获得两个整数（可能为0或负数）x、y使等式d=gcd(a,b)=ax+by成立。如下所示的EXTENDED-EUCLID过程接收一对非负整数，返回满足上述等式的三元组(d,x,y)：

1. EXTENDED-EUCLID(a,b)
   
2. 
   
3. if b=0
   
4. 
   
5. then return (a,1,0)
   
6. 
   
7. (d',x',y')←EXTEND-EUCLID(b,a mod b)
   
8. 
   
9. (d,x,y)=(d',y',x'-floor(a/b)*y')
   
10. 
    
11. return (d,x,y)

复制代码

EXTENDED-EUCLID过程与EUCLID过程的时间复杂度在渐近意义下相同，差别仅在于常数因子，而由此得出的x、y却对解决一些问题十分有用。

三、求解同余线性方程

在一些重要的应用中常会涉及到求解如下同余线性方程的问题：a*x模n余b，求x。这个问题有解的条件是d=gcd(a,n)|b，在已知有解x0的情况下，可以推出其在模n意义下的全部解,即xi=x0+i*(n/d)(i=0,1...d-1)，具体过程如下：

1. MODULAR-LINEAR-EQUATION-SOLVER(a,b,n)
   
2. 
   
3. (d,x',y')←EXTENDED-EUCLID(a,n)
   
4. 
   
5. if d|b
   
6. 
   
7. then x0←x'(b/d) mod n
   
8. 
   
9. for i←0 to d-1
   
10. 
    
11. do print (x0+i(n/d)) mod n
    
12. 
    
13. else print "no solutions"

复制代码

frogfish

四、中国剩余定理

中国有一本数学古书《孙子算经》有这样的记载：

「今有物，不知其数，三三数之，剩二，五五数之，剩三，七七数之，剩二，问物几何？」

答曰：「二十三」

术曰：「三三数之剩二，置一百四十，五五数之剩三，置六十三，七七数之剩二，置三十，并之，得二百三十三，以二百一十减之，即得。凡三三数之剩一，则置七十，五五数之剩一，则置二十一，七七数之剩一，则置十五，即得。」


孙子算经的作者及确实着作年代均不可考，不过根据考证，着作年代不会在晋朝之后，以这个考证来说上面这种问题的解法，中国人发现得比西方早，所以这个问题的推广及其解法，被称为中国剩余定理。中国剩余定理（Chinese Remainder Theorem）在近代抽象代数学中占有一席非常重要的地位。它揭示了这样两个系统的一致性：一是模两两互质的一组数的同余方程组，二是模它们的乘积的方程。

中国剩余定理的内容如下：

令n=n1n2...nk，其中ni是两两互质的数，则对0<=a<n与0<=ai<ni且ai=a mod ni，a与(a1,a2...,ak)之间有一种一一对应的关系，一切对a的操作均可被等价的转换为对对应k元组中的每一元进行同样的操作。因此我们可以将一种表达经过简单的转换后得出另一种表达，其中从a到(a1,a2...,ak)的转换十分容易，而从(a1,a2...,ak)推得对应的a则要稍微复杂一些。

首先定义mi=n/ni(i=1,2...k)，则mi是除了ni以外的所有nj的乘积，接下来令ci=mi与模n意义下mi的逆元的积，则a为(a1c1+a2c2+...+akck) (mod n)。

例如我们已知a模5余2且模13余3，那么a1=2,n1=m2=5,a2=3,n2=m1=13，则有c1=13*(2 mod 5)=26，c2=5*(8 mod 13)=40，所以a=(2*26+3*40)（mod 65)=42。

五、模取幂运算

m^e mod n叫做模取幂运算，事实上，m^e mod n可以直接计算，没有必要先算m^e，根据简单的数论知识，很容易设计一个分治算法。具体如下:

设<b[k], b[k-1],...,b[1],b[0]>是整数b的二进制表示（即b的二进制有k+1位，b[k]是最高位），下列过程随着c的值从0到b成倍增加，最终计算出a^c mod n

Modular-Exponentiation(a, b, n)

　 c ← 0
d ← 1

　 设<b[k],b[k-1],..b[0]>是b的二进制表示

　 for i←k downto 0

　 do c ← 2c
d ← (d*d) mod n
if b = 1
then c ← c + 1
d ← (d*a) mod n

　 return d


上述伪代码依次计算出的每个幂或者是前一个幂的两倍，或者是前一个幂的两倍再乘上底数a。过程依次从右到左逐个读入b的二进制表示已控制执行哪一种操作。循环中的每次迭代都用到了下面的两个恒等式中的一个：

a^(2c) mod n = (a^c mod n)^2
a^(2c+1) mod n = a * (a^c mod n)^2

用哪一个恒等式取决于b=0还是1。由于平方在每次迭代中起着关键作用，所以这种方法叫做“反复平方法(repeated squaring)”。在读入b位并进行相应处理后，c的值与b的二进制表示<b[k],b[k-1],..b[0]>的前缀的值相同。事实上，算法中并不真正需要变量c，只是为了说明算法才设置了变量c：当c成倍增加时，算法保持条件d = a^c mod n 不变，直至c=b。
如果输入a,b,n是k位的数，则算法总共需要执行的算术运算次数为O(k)，总共需要执行的位操作次数为O(k^3)。


六、RSA公钥加密系统

笔者本想在此文中详细介绍一下这部分的内容，但是最近在一些论坛上经常见到一些传闻说到印度的几个科学家已经发明了在多项式（位操作意义下）时间内分解大合数的方法，使得基于素数理论的加密体系受到动摇。笔者未能证实消息来源的可靠性，因此将简要地对这部分的内容做一个概括，有兴趣的读者需要关注一下密码学最新的动态。

在一个公钥加密系统中，每个参与者都拥有一个公钥和密钥，每个人对自己的密钥保密，而一般将公钥公开，假设基于公钥PA的一个函数是PA(),而基于密钥SA的一个函数是SA()，那么对于传输的信息M,一般有

M=SA(PA(M))且M=PA(SA(M))。


因此，设计一个可行的公钥加密系统的最大困难在于解决如何在展示PA的同时不使除自己外的其它人拥有计算SA的能力。RSA公钥加密系统借助了数论中的这样一个事实：寻找大素数很容易而分解两个大素数的乘积则很困难。

在RSA公钥加密系统中，参与者按照如下的步骤制造商他的公钥与密钥。

1. 随机选择两个不等素数p和q。
2. 计算出n=pq。
3. 选择一个小奇数e使它和(p-1)(q-1)互质。
4. 计算e在模(p-1)(q-1)的逆元d。
5. 公开数对(e,n)作为RSA公钥。
6. 保留数对(d,n)作为他的RSA密钥。

在信息传递的过程中，发送消息者将信息用基于接收者公钥的算法进行加密，因此在消息传递的过程中即使被窃听者截获，也因为他无法获得接收者的密钥而破解密文；至于接收者本身则因为持有自己的密钥而可以解读传递过来的信息。

除了RSA公钥加密系统外，诸如数字签名等一些其他技术也借用了数论中寻找大素数和分解大合数的这一对矛盾，因此从某种意义上讲，人类可能希望分解大合数的问题永远不要被解决，这实在是一个有趣的现象。

christy

数论算法库，包括以下算法：

欧几里德算法求a，b的最大公倍数
扩展的欧几里德算法，求出gcd(a,b)和满足gcd(a,b)=ax+by的整数x和y
求解模线性方程 ax ≡ b (mod n) 其中n>0
求解模线性方程组(中国余数定理)
模取幂运算 计算a^b mod n （a,b可能很大）
Miller-Rabin随机性素数测试算法


程序用C++语言编写，在VisualAge C++ 4.0下调试通过。压缩包内的number theory.h文件包含所有的库函数，其调用接口见程序内注释。其他的文件是用来测试算法的测试程序，在VisualAge C++ 4.0下编译运行。
该算法是我为参加ACM/ICPC竞赛而准备的资料，由于竞赛的对编程速度要求较高，所以为了将代码写的短一点，为了便于调试，代码的写的并不是最优的。
虽然该代码在VisualAge C++ 4.0下写成，但是很容易将其移植到MS Visual C++上。

本程序来自于www.pudn程序联合开发网，版权归原作者所有
http://www.pudn.com/downloads56/ ... mber_theory_c++.zip

szuwqh525

好人呀，谢谢你们了<BR>这正是我要的。<BR>我向你们致敬了