历史上第一个称得上算法的好像就是这个欧几里得算法，其实就是地球人都知道的辗转相除，不要小看她，她是很美的。

简单的描述就是，记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+r2
r1=q3r2+r3
……
r(s-1)=q(s+1)r(s)+r(s+1)，r(s+1)=1（一定存在着某个r(s+1)=1）

再把余数专门写到一边：
r0=a
r1=b
r2=r0-q2r1
r3=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比较困难，不知道用的什么算法，如果真不好算，可以做一个大素数表，每次从中挑几个，表做大一些安全性也不低。

评论