历史上第一个称得上算法的好像就是这个欧几里得算法，其实就是地球人都知道的辗转相除，不要小看她，她是很美的。 简单的描述就是，记gcd(a,b)表示非负整数a,b的最大公因数，那么：gcd(a,b)=gcd(b,a%b)或者gcd(a,0)=gcd(0,a)=a。 写成程序很简单，不管是用递归还是循环： int gcd(int a,int b){        if(a==0)                return b;        if(b==0)                return a;        return gcd(b,a%b);} 不仅算法形式简单，而且效率很高，我不知道具体是多少复杂度的，我只知道效率很高；） 前天看ＲＳＡ算法，是非对称加密的标准算法，其实算法很简单：找到两个素数p,q，再找一个数r，使gcd(r,(p-1)(q-1))=1，也就是说互素，然后再找一个数m，使rm=1(mod (p-1)(q-1))，然后再作乘法n=pq，然后把pq丢掉，最好是让任何人都不知道，包括自己（免得说梦话的时候被人听到），然后手里拿到r,m,n，r就是Private Key，只有你知道，而m,n就是Public Key。设信息为a,加密过程：a^r=b (mod n)，b就是密文，解密过程：b^m=a(mod n)，反过来用m加密，用r解密是一样的。 书上说由gcd(r,(p-1)(q-1))=1到求m，使rm=1(mod (p-1)(q-1))是很容易的，就用辗转相除，我想了好久才想到一个方法。 问题：如果gcd(a,b)=1，求x，使ax=1(mod b)由gcd(a,b)=1可知x是一定存在的，因为前式等同于：存在这样的x,y使ax+by=1，把by拿过去就是ax=-yb+1，即ax=1(mod b) 我令r0=a,r1=b，开始辗转相除r0=q2r1+r2r1=q3r2+r3……r(s-1)=q(s+1)r(s)+r(s+1)，r(s+1)=1（一定存在着某个r(s+1)=1） 再把余数专门写到一边：r0=ar1=br2=r0-q2r1r3=r1-q3r2……1=r(s+1)=r(s-1)-q(s+1)r(s) 后面的式子是关于前面的式子的多项式，而最开始是a和b，由最后一个式子就可以证明一定存在1=ax+by，它们都是关于a,b的一次多项式，那如何求x?把前面的式子代到后面，一个一个代，但是你会发现很复杂，不太容易求，于是我想到的就是同样的办法迭代。 设经过从前面的式子的代换，可以得到r(n)=x(n)a+y(n)b，那么有r(n+1)=r(n-1)-q(n+1)r(n)=x(n-1)a+y(n-1)b-q(n+1)(x(n)a+y(n)b)=(x(n-1)-q(n+1)x(n))a+(...)b 于是得到x(n)的迭代式：x(n)=x(n-2)-q(n)x(n-1)，同时有初值x0=1,x1=0，而q(n)=[r(n-2)/r(n-1)]，于是x(n)是确定可求的。一个小小的问题是这样求出的x可能是负数，很简单，在mod b的情况下只需要加上b就行了。 代码：#include<assert.h>#include<iostream.h> int euc(int r1,int r2,int x1,int x2){ if(r2==1)  return x2; if(r2==0)  return 0; return euc(r2,r1%r2,x2,x1-r1/r2*x2);} int euclid(int a,int b){ assert(a>0&&b>0); int x=euc(b,a%b,0,1); if(x<0)  x+=b; return x;} int main(void){ int a,b,x; cin>>a>>b; x=euclid(a,b); if(x==0)  cout<<"gcd(a,b)!=1"<<endl; else  cout<<"x="<<x<<endl;  return 0;} 算法的性能和Euclid算法一致，但离RSA还很远。RSA的安全性建立在n=pq的大素数的分解上，老师说一般选几百bit。于是上面这些全部需要改写，需要一个大数运算库，支持四则运算，这都不算什么，Euclid算法还是会很快收敛，关键是在加/解密时的运算，运算量大，所以RSA一般用于加密很小的数据，比如DES的密钥。 另一个方面，我觉得在大数中挑选p,q，以及找r比较困难，不知道用的什么算法，如果真不好算，可以做一个大素数表，每次从中挑几个，表做大一些安全性也不低。

评论