欧几里得算法

参考：
https://zh.wikipedia.org/wiki/%E8%BC%BE%E8%BD%89%E7%9B%B8%E9%99%A4%E6%B3%95

序：
欧几里得算法又称辗转相除法， 用来求最大公约数的算法，之前学过，但仅仅是学过公式，并不知道有什么用，最近看RSA的公钥私钥生成原理，发现数学真实神奇，借此机会，深入了解一下。

• 算法介绍：
  两个整数的最大公约数是能够同时整除它们的最大的正整数。假设两个整数a，b, 且 a > b, 根据辗转相除法迭代， 每次用 a mod b 的余数 替换b, 用b 替换a, 迭代知道 b == 0, 返回 a的值。
  推导演示：

大的那个数	小的那个数	余数	商
a	b	r0 = a%b	q0
b	r0	r1 = b% r0	q1
r0	r1	r2 = r0 % r1	q2
...	...	...	...
rN-4	rN-3	rN-2 = rN-4 % rN-3	qN-2
rN-3	rN-2	rN-1 = rN-3 % rN-2	qN-1
rN-2	rN-1	rN = rN-2 % rN-1	qN
rN-1	rN == 0	rN-1 = 1 * rN-1 - 0 * rN	0

得到的最大公约数就是r_N-1

• 证明：
  分为两步， 第一步证明r_N-1 能够被 a, b整除， 第二步证明最大公约数g <= r_N-1

  • 第一步基于我们表格的推导很容易：
    r_N-2 = q_N * r_N-1 + r_N = q_N * r_N-1
    r_N-3 = q_N-1 * r_N-2 + r_N-1 = q_N-1 * q_N * r_N-1 + r_N-1 = ( q_N-1 * q_N + 1) * r_N-1
    ........
    r₀ = q₂ * r₁ + r₂
    b =q₁ * r₀ + r₁
    a= q₀ * b + r₀
    所以 r_N-3 也是可以被r_N-1整除的
    以此类推， a, b 均能被r_N-1 整除

  • 第二步证明r_N-1是最大的：
    假设a, b的最大公约数是g, 即有：
    r₀ = a%b = a - q₀ * b =
    (m - q₀ * n) * g
    即有a%b 的余数也是最大公约数g的倍数， 同理 r_{N - 1} 也是最大公约数g的倍数， 即：g <= r_N-1

得证

python 代码：

def gcd(a, b):
    if b == 0:
        return a
    return gcd(b, a % b)

• 贝祖等式:
  贝祖等式说明，两个数a和b的最大公约数g可以表示为a和b的线性和。
  也就是说，存在整数s和t使g = sa + tb。注意是正数哦。
  由辗转相除法逆推：
  g = r_N-1 = r_N-3 - q_N-1 * r_N-2
  r_N-2 = r_N-4 - q_N-2 * r_N-3
  r_N-3 = r_N-5 - q_N-3 * r_N-4
  ......
  r₂ = r₀ - q₂ * r₁
  r₁ = b - q₁ * r₀
  r₀ = a - q₀ * b
  b = 0 * a + 1 * b
  a = 1 * a + 0 * b
  递推可证明贝祖等式成立。
  即找到r_N-3，r_N-2的乘积形式的表达, 乘数都是整数，s_N-1,
  t_N-1一定也是整数
  • 证明：
    找到贝祖等式的s 和 t的值，利用上面的证明过程用数学归纳法递推：
    假设 r_j = s_j * a + t_j * b 对于 j <= k-1 均成立
    r_k = r_k-2 - q_k * r_k-1
    r_k-2 = s_k-2 * a + t_k-2 * b
    r_k-1 = s_k-1 * a + t_k-1 * b
    则：
    r_k = s_k-2 * a + t_k-2 * b - q_k* (s_k-1 * a + t_k-1 * b) = (s_k-2 - q_k*s_k-1) * a + (t_k-2 - q_k * t_k-1) * b
    即：
    s_k = s_k-2 -q_k * s_k-1
    t_k = t_k-2 -q_k * t_k-1
    .....
    算法开始时：
    s₀ = 1, t₀ = -q₀
    s_-1 = 0， q_-1 = 1
    s_-2 = 1， q_-2 = 0

• 扩展欧几里得算法
  扩展欧几里得算法即找到贝祖等式的s 和 t的值，
  s_k = s_k-2 - q_k * s_k-1
  t_k = t_k-2 - q_k * t_k-1
  • python代码：

def ex_gcd(a, b):
    s0 = 1
    t0 = 0
    s1 = 0
    t1 = 1
    m, n = a, b
    while b != 0:
        a, b, q = b, a % b, a // b
        s0, s1 = s1, s0 - q * s1
        t0, t1 = t1, t0 - q * t1
        print "%d = %d * %d + %d * %d" % (a, s0, m, t0, n)
        print "%d = %d * %d + %d * %d" % (b, s1, m, t1, n)
    return s0, t0, a

结果：

30 = 0 * 47 + 1 * 30
17 = 1 * 47 + -1 * 30
17 = 1 * 47 + -1 * 30
13 = -1 * 47 + 2 * 30
13 = -1 * 47 + 2 * 30
4 = 2 * 47 + -3 * 30
4 = 2 * 47 + -3 * 30
1 = -7 * 47 + 11 * 30
1 = -7 * 47 + 11 * 30
0 = 30 * 47 + -47 * 30
(-7, 11, 1)

维基上的算法：
https://zh.wikipedia.org/wiki/%E6%89%A9%E5%B1%95%E6%AC%A7%E5%87%A0%E9%87%8C%E5%BE%97%E7%AE%97%E6%B3%95
这个明显比我自己推导写的代码要简洁多了，这个代码思想和上面的递推公式是反的， 是从先找到最大公约数， 有等式 g = 1 * s _N-1 + 0 * s_N开始往回推， 而上面的逻辑是从a, b开始顺序推，一边找最大公约数， 一边解二元一次方程:
逆推公式：
s_N = 1, t_N = 0
g = 1 * r _N-1 + 0 * r_N = s_N * r _N-1 + t_N * r_N
r_N = 1 * r_N-2 - q_N * r_{N- 1} = s_N-1* r_N-2 +t_N-1 * r_{N- 1}
有 g = (1 - q_N) * r _N-1 + 1* r_N-2 = (s_N - )
r_N-1 = 1 * r_N-3 - q_N-1 * r_{N- 2}
对应的s,t :
s_N = 1, t_N = 0
s_N-1 = 1,

s_{k - 2} = s_k + q_k * s_k-1
t_{k - 2} = t_k + q_k * t_k-1

s_-2 = 1
s_-1 = t _-2 = 0
s₀ = s_-2 - q_k * s_-1 = s_-2 - q_k * t _-2
不妨设t _-3 = 1
上面的式子变为：
s₀ = t _-3 - q_k * t _-2 = t _-1 = 1
利用数据归纳法可以证明

• s_k = t _k-1
• t_k = t_k-2 - q_k * t_k-1 = s_{k -1} - q_k * t_k-1