问题标题: gcd的意思与使用

简单的描述就是，记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就行了。

　　算法的性能和Euclid算法一致，但离RSA还很远。RSA的安全性建立在n=pq的大素数的分解上，老师说一般选几百bit。于是上面这些全部需要改写，需要一个大数运算库，支持四则运算，这都不算什么，Euclid算法还是会很快收敛，关键是在加/解密时的运算，运算量大，所以RSA一般用于加密很小的数据，比如DES的密钥。

　　另一个方面，我觉得在大数中挑选p,q，以及找r比较困难，不知道用的什么算法，如果真不好算，可以做一个大素数表，每次从中挑几个，表做大一些安全性也不低。

欧几里德算法(Euclid)阐述了一种gcd算法。gcd(greatest common divisor)，简言之，我们想求gcd(x,y)，假设(x>y)，如果存在下式:x =  q*y + r，那么则有gcd(x,y) = gcd(y,r) ，其实上式也称为gcd递归定理，即gcd(a,b) = gcd (b,a mod  b)。
这个递归式看似很简单。实则它还是很值得推敲的，首先，它怎么证明？其次，该算法的运行时间为如何？
在密码学中，欧几里德算法有着相当广泛的应用，譬如求乘法逆元，大整数分解等等。。
在<<编程之美>>一书中，给出了不少gcd算法的简单实现。因为gcd算法的实现是递归，所以要特别注意栈溢出。先做个标记，以后会把栈详细分析一下。
 

gcd(a,b)就是a和b的最大公因数。

使用时要用万能头：#include <bits/stdc++.h>

gcd(a,b)是求a和b的最大公约数

就是求两个数的最大公约数

求两个数(a和b)的最大公约数

1