gcd(a，b)＝1

gcd(a，b)＝1什么意思

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

　　简单的描述就是，记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);
　　}

　　设有两个数num1和num2，假设num1比较大。令余数r = num1 % num2。
　　当r == 0时，即num1可以被num2整除，显然num2就是这两个数的最大公约数。
　　当r != 0时，令num1 = num2（除数变被除数），num2 = r（余数变除数），再做 r = num1 % num2。递归，直到r == 0。
　　以上数学原理可以用具体的两个数做一下分析，这样容易理解。

　　代码实现（求最大公约数）：

　　不仅算法形式简单，而且效率很高，我不知道具体是多少复杂度的，我只知道效率很高；）

　　前天看RSA算法，是非对称加密的标准算法，其实算法很简单：
　　找到两个素数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比较困难，不知道用的什么算法，如果真不好算，可以做一个大素数表，每次从中挑几个，表做大一些安全性也不低。

a与b互质的意思