预备知识（不严谨定义）
整除：简单来说， (a = nb)， 则有(b|a)，读作b整除a
约数(divisor)：上面整除的例子里，b就是a的约数，公约数就是多个数的共有约数，如2就是4、6、8的公约数
最大公约数（greast common divisor， 简称gcd)：顾名思义，公约数里最大的一个，设(gcd(a,b)=m)，则任取a、b的公约数c，有(c <= m),需要注意的是，最大公约数往往是整数，特殊的：
- 若(b|a)， 则(gcd(a, b)=b)
- 任取整数(n)，有(gcd(0, n)=n)
互素(relatively prime)：两个数的最大公约数是1，那么我们就称这两个数的互素的
如果我们要求最大公约数，我们先来想一下最简单的思路。
假设(a>b)，我们使用暴力求解的方式，从1开始，设置一个变量存储最大公约数值，每发现一个既能整除a又能整除b的数，将其置为最大公约数，直到遍历到b为止。粗一看，时间复杂度也并不很高，似乎也是可行的方法。但实际上，在实际的密码学程序中，需要大量的这类操作，并且操作的数往往是非常大的数，这时，这种方法就显得十分低效，而欧几里德方法就是为了能够高效的求取最大公约数。
欧几里德算法
首先我们来看，设
[a = q*b+r \d = gcd(a, b)
]
那么(r = a-q*b)，由于(d|a、d|b)，则有(d|(a-q*b)=r)，即d也是b和r的最大公约数，此外，又有(b>r => b=q_1*r+r_1)以此类推，就得到了我们的欧几里德算法。
算法描述为：
- 将输入置为(a>b)
- 令(a=q*b+r)
- 若(r=0)，则(gcd(a,b)=b)
- 否则，令(a := b, b := r)， 注意这里的:=是赋值操作，重复2
建议自己模拟一下，易于理解！
欧几里德算法的实现
# 加减法的实现对计算机的计算方式更友善
def gcd1(a, b):
a, b = max(a, b), min(a, b)
while a != b:
a, b = max(b, a-b), min(b, a-b)
return a
def gcd2(a, b):
a, b = max(a, b), min(a, b)
while a % b != 0:
a, b = b, a%b
return b
实用的欧几里德算法
上面只是欧几里德算法的直接实现，效率较低，不能满足实际环境的需要。
通常的生产代码中使用的最大公约数算法是一种称作binary GCD的算法，其算法描述如下，
openssl中使用的BN_gcd便使用了该算法