CSI讲义9: GCD算法
本文简介求两个整数的最大公因子的GCD算法，并作简要分析。目标：让大一新生建立起关于算法的若干概念。
欧几里得
GCD算法
GCD算法世界上最古老的算法（并没有之一），可追溯至公元前300年前。
给定两个整数a和b，求a和b的最大公因子，记为GCD(a, b)。该算法也被称为欧几里得算法，或称辗转相除法。
算法思路：
0、输入整数a和b，要求 a >= b >= 0 ；
1、如果输入a和b中的b为0，则返回a；这可视为定义；
2、否则，递归计算GCD(b, a mod b).
伪代码
function GCD(a, b)
#input: a, b, two integers with a >= b >= 0
#output: the greatest common divisor of a and b
if b == 0:
return a;
else:
return GCD(b, a mod b)
例子
第一次阅读该算法的读者一定要动手做以下练习，从中体会所谓“辗转相除”的含义：
求8、4的gcd，8 mod 4 ＝＝ 0；所以，递归gcd(4,0)，然后返回4。
求7和3的gcd，第一步递归gcd(3,1)；第二步递归gcd(1,0)，结果为1。
利用GCD的定义可以给出互素、素数等定义：
定义（互素、素数）
如果整数a和b的最大公因子为1，则称a与b互素。如果对于整数a，所有小于a且大于0的数都与a互素，则称a为素数。
算法正确性
为什么算法是正确的？要证明，我们需要一个简单的中间结论gcd(a,b) == gcd(a-b,b)。
证明：
1、因为a和b的公因子肯定整除
a-b，所以gcd(a,b) <= gcd(a-b,b);
2、同时能整除a-b和b的家伙一定可以整除a和b！所以，gcd(a-b,b) <= gcd(a,b)。
这里利用了一种证明方法，要证明a == b，我们只需要证明：a <= b 且b < = a。一种非常常规的证明方式。推广，如果a和b为集合，证明这两个集合相等，只需要证明a是b的子集且b是a的子集。
为什么gcd(a,b) == gcd(a-b,b)就得到结论gcd(a,b) == gcd(b, a mod b)？因为：
gcd(a,b) == gcd(a-b,b) ＝＝ gcd(((a-b)-b),b)
== gcd((((a-b)-b)-b),b)== ... == gcd(a mod b, b)
不断对a进行减b，当然会得到a mod b。mod运算无非是a除b取余数。
小结
GCD算法是古老的算法，然而也是目前使用最广泛的算法之一。GCD算法的一个简单扩展（扩展欧几里得算法，简记为EGCD）是目前互联网中使用最广泛的安全保密算法 -- RSA算法 -- 的基础。由GCD算法引申出的一些高级算法，比如LLL算法，更能体现GCD算法中“辗转相除”的深刻内涵。
要理解递归也许我们需要更多的练习与阅读，不知道我以前的这份递归讲义是否可以帮助大家？
最后需要指出，在计算机中实现的运算，尤其以加法和乘法最为本质。而计算机的加法和乘法都是“mod加”和“mod乘”。这是未来大家需要重点理解的内容。
课后自习内容
编程练习
1、用C语言、Python语言实现GCD算法，递归实现；
2、不使用递归，使用迭代法用C语言、Python语言实现GCD算法；并分析，当输入整数为32bits、64bits、1024bits时，程序需要进行多少次迭代？
