芯有所想
精益求精
Extended Euclid Algorithm
扩展欧几里德算法用来计算在模a乘法域下b的倒数。 算法描述尽可能用利于数字设计的方式，而不是程序设计的角度。
a，b为两个互素的正整数，不妨设 \(a > b\), 如果不满足此条件，则交换a、b顺序
方法1
初始化：
\[\begin{array}{l} r(-1) = a; r(0) = b \\ c(-1) = 1; c(0) = 0 \\ d(-1) = 0; d(0) = 1 \\ flag = 1 \end{array}\]迭代过程：从 \(n=1\) 开始
\[\begin{align} flag = -flag \\ q = r(n-2)/r(n-1) \\ r(n) = r(n-2)\ mod\ r(n-1) \\ c(n) = c(n-2) + q * c(n-1) \\ d(n) = d(n-2) + q * d(n-1) \\ x = flag * c(n-1) \\ y = -flag * d(n-1) \end{align}\]结束条件： \(r(n) == 0\)
输出： \(r(n-1), x, y\) 输出满足条件：
\[\begin{align} gcd(a, b) = r(n-1) \\ x(n-1) * a + y(n-1) * b = r(n-1) \end{align}\]方法2
原始算法
\[\begin{array}{l} 初始化：\\ x(-1) = 1; y(-1) = 0 \\ u(-1) = 0; v(-1) = 1 \\ r(-1) = b; r(-2) = a \\ \\ 从0开始迭代：\\ q = r(n-2)/r(n-1) \\ r(n) = r(n-2)\ mod\ r(n-1) \\ x(n) = u(n-1) \\ y(n) = v(n-1) \\ u(n) = x(n-1) - q * u(n-1) \\ v(n) = y(n-1) - q * v(n-1) \\ \\ 结束条件： r(n)==0 \\ 输出：r(n-1), x(n), y(n) \\ 输出满足条件： \\ gcd(a, b) = r(n-1) \\ x(n) * a + y(n) * b = r(n-1) \end{array}\]迭代算法改进：去掉 \(x, y\)
\[\begin{array}{l} 初始化： \\ u[n], u[n+1] = 1, 0 \\ v[n], v[n+1] = 0, 1 \\ r[n], r[n+1] = a, b \\ q = a/b \\ 迭代: \\ u[n], u[n+1] = u[n+1], u[n] - q*u[n+1] \\ v[n], v[n+1] = v[n+1], v[n] - q*v[n+1] \\ r[n], r[n+1] = r[n+1], r[n]\ mod\ r[n+1] \\ q = r[n]/r[n-1] \\ \\ 结束条件： r[n+1] == 0 \\ 输出: r[n], u[n], v[n] \\ 输出满足条件：\\ gcd(a, b) = r[n] \\ u[n] * a + v[n] * b = r[n] \end{array}\]方法2的结构图如下：
python源代码如下：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
def ext_euclid(a, b):
if a < b:
a, b = b, a
# 初始化条件：
r_n2, r_n1 = a, b
u_n2, u_n1 = 1, 0
v_n2, v_n1 = 0, 1
while True:
# combinational calculcation
q = r_n2/r_n1
u_n = u_n2 - q*u_n1
v_n = v_n2 - q*v_n1
r_n = r_n2 % r_n1
if r_n == 0 : break
# update clocked data into DFF
r_n1, r_n2 = r_n, r_n1
u_n1, u_n2 = u_n, u_n1
v_n1, v_n2 = v_n, v_n1
return a, b, r_n1, u_n1, v_n1